Welcome to CS143: Compilers

● Course Information
● Why Study Compilers?
● A Quick History of Compilers
● The Structure of a Compiler
 Course Staff

Instructor: Keith Schwarz

(htiek@cs.stanford.edu)

TA: Jinchao Ye
(jcye@stanford.edu)

TA: Naran Bayanbat

(narab@stanford.edu)
http://cs143.stanford.edu
Grading Policies
Grading Policies

60% Programming Assignments

20% Written Assignments
20% Midterm Exam
Grading Policies

60% Programming Assignments

20% Written Assignments
20% Midterm Exam
Grading Policies

60% Programming Assignments

20% Written Assignments
20% Midterm Exam
Grading Policies

60% Programming Assignments

20% Written Assignments
20% Midterm Exam

Midterm
Midterm exam:
exam:
July
July 25,
25,
11:00AM
11:00AM –– 1:00PM,
1:00PM,
Location
Location TBA
TBA
A Word on the Honor Code...
Prerequisites

CS107

CS103
 Why Study Compilers?
● Build a large, ambitious software
system.
● See theory come to life.
● Learn how to build programming
languages.
● Learn how programming languages
work.
● Learn tradeoffs in language design.
 A Short History of Compilers
● First, there was nothing.
● Then, there was machine code.
● Then, there were assembly languages.
● Programming expensive; 50% of costs for
machines went into programming.
 High-Level Languages

Image: http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Grace_Hopper.jpg/300px-Grace_Hopper.jpg
http://www.nytimes.com/2007/03/20/business/20backus.html
 High-Level Languages

Rear Admiral Grace

Rear Admiral Grace
Hopper,
Hopper, inventor
inventor ofof
A-0,
A-0, COBOL,
COBOL, and
and the
the
term
term “compiler.”
“compiler.”

Image: http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Grace_Hopper.jpg/300px-Grace_Hopper.jpg
http://www.nytimes.com/2007/03/20/business/20backus.html
 High-Level Languages

Image: http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Grace_Hopper.jpg/300px-Grace_Hopper.jpg
http://www.nytimes.com/2007/03/20/business/20backus.html
 High-Level Languages

John
John Backus,
Backus,
team
team lead
lead on
on
FORTRAN.
FORTRAN.
Image: http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Grace_Hopper.jpg/300px-Grace_Hopper.jpg
http://www.nytimes.com/2007/03/20/business/20backus.html
How does a compiler work?
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω
 4Ω

6V 3Ω 6Ω

1
=2 Ω
1 1
+
3Ω 6 Ω
 4Ω

6V 2Ω

1
=2 Ω
1 1
+
3Ω 6 Ω
 4Ω

6V 2Ω
 4Ω

6V 2Ω

4 Ω+ 2 Ω=6 Ω
 6Ω

6V

4 Ω+ 2 Ω=6 Ω
 6Ω

6V
 6Ω

6V

6V
 6Ω

6V

Total Cost: $4.75

6V
 6Ω

1.5V

1.5V

1.5V

1.5V
 6Ω

1.5V

1.5V

1.5V AAA

1.5V AAA

AAA

AAA
 6Ω

1.5V

1.5V

1.5V AAA

1.5V AAA

AAA

Total Cost: $1.00 AAA

 From Description to Implementation

● Lexical analysis (Scanning): Identify logical

pieces of the description.
● Syntax analysis (Parsing): Identify how those
pieces relate to each other.
● Semantic analysis: Identify the meaning of the
overall structure.
● IR Generation: Design one possible structure.
● IR Optimization: Simplify the intended structure.
● Generation: Fabricate the structure.
● Optimization: Improve the resulting structure.
The Structure of a Modern Compiler

Source Lexical Analysis

Code
Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization Machine
Code
The Structure of a Modern Compiler

Source Lexical Analysis

Code
Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization Machine
Code
The Structure of a Modern Compiler

Source Lexical Analysis

Code
Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization Machine
Code
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis

Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis

Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

T_While Lexical Analysis

T_LeftParen
T_Identifier y
T_Less Syntax Analysis
T_Identifier z
T_RightParen Semantic Analysis
T_OpenBrace
T_Int
T_Identifier x IR Generation
T_Assign
T_Identifier a
T_Plus
IR Optimization
T_Identifier b
T_Semicolon Code Generation
T_Identifier y
T_PlusAssign
T_Identifier x Optimization
T_Semicolon
T_CloseBrace
while (y < z) {
int x = a + b;
y += x;
}

T_While Lexical Analysis

T_LeftParen
T_Identifier y
T_Less Syntax Analysis
T_Identifier z
T_RightParen Semantic Analysis
T_OpenBrace
T_Int
T_Identifier x IR Generation
T_Assign
T_Identifier a
T_Plus
IR Optimization
T_Identifier b
T_Semicolon Code Generation
T_Identifier y
T_PlusAssign
T_Identifier x Optimization
T_Semicolon
T_CloseBrace
 while (y < z) {
int x = a + b;
y += x;
}
While
Lexical Analysis

Syntax Analysis
Sequence
Semantic Analysis

< = = IR Generation

IR Optimization
y z x + y +
Code Generation

Optimization
a b y x
 while (y < z) {
int x = a + b;
y += x;
}
While
Lexical Analysis

Syntax Analysis
Sequence
Semantic Analysis

< = = IR Generation

IR Optimization
y z x + y +
Code Generation

Optimization
a b y x
 while (y < z) {
int x = a + b;
y += x;
}
While void
Lexical Analysis

Syntax Analysis
Sequence void
Semantic Analysis

< bool = int = int IR Generation

IR Optimization
y z x + int y + int
Code Generation
int int int int
Optimization
a b y x
int int int int
 while (y < z) {
int x = a + b;
y += x;
}
While void
Lexical Analysis

Syntax Analysis
Sequence void
Semantic Analysis

< bool = int = int IR Generation

IR Optimization
y z x + int y + int
Code Generation
int int int int
Optimization
a b y x
int int int int
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
Loop: x = a + b
y = x + y Syntax Analysis
_t1 = y < z
Semantic Analysis
if _t1 goto Loop
IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
Loop: x = a + b
y = x + y Syntax Analysis
_t1 = y < z
Semantic Analysis
if _t1 goto Loop
IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
x = a + b
Loop: y = x + y Syntax Analysis
_t1 = y < z
Semantic Analysis
if _t1 goto Loop
IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
x = a + b
Loop: y = x + y Syntax Analysis
_t1 = y < z
Semantic Analysis
if _t1 goto Loop
IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
add $1, $2, $3
Loop: add $4, $1, $4 Syntax Analysis
slt $6, $1, $5
Semantic Analysis
beq $6, loop
IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
add $1, $2, $3
Loop: add $4, $1, $4 Syntax Analysis
slt $6, $1, $5
Semantic Analysis
beq $6, loop
IR Generation

IR Optimization

Code Generation

Optimization
while (y < z) {
int x = a + b;
y += x;
}

Lexical Analysis
add $1, $2, $3
Loop: add $4, $1, $4 Syntax Analysis
blt $1, $5, loop
Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization
 The Course Project: Decaf
● Custom programming language similar
to Java or C++.
● Object-oriented with free functions.
● Single inheritance with interfaces.
Programming Assignments
Source Lexical Analysis
Code
Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization Machine
Code
Programming Assignments
Source Lexical Analysis
Code
Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization Machine
Code
 Next Time...
Source Lexical Analysis
Code
Syntax Analysis

Semantic Analysis

IR Generation

IR Optimization

Code Generation

Optimization Machine
Code