CS 434T: Overview

Stephen Freund

Williams College

Overall Compiler Structure

High-level source code

Compiler

Low-level target code

int expr(int n) {

int d;

d = 4 * n * n * (n + 1) * (n + 1);

return d;

}

lda $30,-32($30)

stq $26,0($30)

stq $15,8($30)

bis $30,$30,$15

bis $16,$16,$1

stl $1,16($15)

lds $f1,16($15)

sts $f1,24($15)

ldl $5,24($15)

bis $5,$5,$2

s4addq $2,0,$3

ldl $4,16($15)

mull $4,$3,$2

ldl $3,16($15)

​

addq $3,1,$4

mull $2,$4,$2

ldl $3,16($15)

addq $3,1,$4

mull $2,$4,$2

stl $2,20($15)

ldl $0,20($15)

br $31,$33

$33:

bis $15,$15,$30

ldq $26,0($30)

ldq $15,8($30)

addq $30,32,$30

ret $31,($26),1

cmp $0,ecx

cmovz edx,ecx

Source code

Understand source code

Generate

assembly code

Assembly code

Front end

(machine-independent)

Back end

(machine-dependent)

if (b == 0) a = b;

Optimize

Intermediate code

Intermediate code

Optimizer

Source code

(character stream)

Lexical Analysis

Syntax Analysis

(Parsing)

Token�stream

Abstract syntax�tree (AST)

Semantic Analysis

if (b == 0) a = b;

Decorated

AST

Intermediate Code

Generation

Optimizations

Intermediate

code

Intermediate

code

Decorated

AST

cmp $0,ecx

cmovz edx,ecx

Assembly

code

Machine Optimizations

and Code Generation

Source code

Assembler

Executable image

Linker

Loader

Lexical Analysis

Syntax Analysis

Semantic Analysis

Code Generation

Optimization

Assembly code

Object code

(machine code)

Fully-resolved object code

CS 434T

• Theoretical Foundations
• Implementation
• Synthesis of many ideas
• PL, Theory, Algorithms, SE, Computer Organization

IC Demo

Before Your Tutorial Meeting

• Do reading, work on all problems�
• Be prepared to discuss any of them in detail
• work through solution on board
• extend problem in new directions
• explain where you got stuck and why�
• Write "perfect" solutions to a couple questions of my choosing within 24 hours of your meeting
• better preparation before meeting == fewer writeups

Weekly Schedule

• Friday
• tutorial meeting
• hw problems
• updates on IC Projects
• lab
• basic information about tools / techniques
• builds on that weeks homework
• coordinate with project group
• next week's material released�
• Wednesday
• project checkpoints due
• will be most weeks once semester is under way

Administrativia

• Project Group
• Yep, only 3 of you...�
• Midterm? Final? Nope
• but be prepared for meetings, or ...�
• Final project of your own design�
• Honor Code and AI Policy
• see syllabus

Slack, anyone?

​

• Identifiers: x y11 elsen _i00
• Integers: 2 1000 -500 5L
• Floating point: 2.0 .02 1. 1e5 0.e-10
• Strings: “x” “He said, \“moo?\””
• Comments: /** don’t change this **/
• Keywords: if else while break
• Symbols: + * { } ++ < << [ ] >=

​

Source code

(character stream)

Lexical Analysis

Token�stream

if (b == 0) a = b;

Regular Expressions

A language is a set of words: { moo, cow }, { a,b,c,d,... }

Regular expressions describe languages

abab a|b (a|b)* [1-9][0-9]* [a-z][a-z0-9]*

Definition

• a ordinary character stands for itself
• ϵ the empty string
• R | S either R or S (alternation), where R,S are REs
• RS R followed by S (concatenation)
• R* R repeated 0 or more times

​

L(R): the "language" defined by R�

L(a(moo|cow)) = { amoo, acow }

�L([1-9][0-9]*) =

{1,2,3,4,5,6,7,8,9,10,11 , ...}

Acceptors

• Acceptor: determines if an input string belongs to a language L

​

​

​

​

�

• Finite Automata: acceptor for languages described by regular expressions

Language

L

Yes, if w ∈ L

No, if w ∉ L

Acceptor

Input String

w

Finite Automata

Regular Expression: (-|ε)[0-9][0-9]*

Deterministic Finite �Automata

Non-Deterministic Finite Automata

Putting the Pieces Together

RE ⇒ NFA

Conversion

NFA ⇒ DFA

Conversion

DFA

Simulation

Input

String

Regular

Expression

R

w

Yes, if w ∈ L(R)

No, if w ∉ L(R)