Lecture 
Date 
Title 
Material covered 
Lecture 
1 
8/228/24 
What
is a compiler? 
Structure
of a compiler (introduction and overview) 

2 
8/248/26 
Scanners
and Finite Automata 
Scanning 

3 
8/299/7 
Parsers
and Contextfree Grammars 
Parsing (recursive descendent, overview of shiftreduce) 

4 
9/99/12 
Semantic
actions for declarations and expressions 
Semantic routines (building a symbolic table and AST) 

5 
9/14 
Semantic
actions for control structures 
Semantic routines (for control structures) 

6 
9/149/16 
Functions 
Semantic routines (for functions) 

7 
9/199/21 
Code
Generation and Local Optimization 
Instruction selection, peephole optimization, common subexpression elimination, register allocation 

8 
9/239/26 
Global
Register Allocation 
Register coloring, spilling, register coalescing 

9 
9/30 
Instruction
Scheduling 
Data dependence graph, reservation table, heightbased list scheduling 

10 
10/3 
Control
Flow Graphs 
Control flow graph, basic block 

11 
10/510/7 
Dataflow
Analysis 
Dataflow analysis 

12 
10/710/14 
Lattice
Theory 
Partially ordered set, least fixpoint, fixpoint theorem, lattice 

13 
10/1710/24 
More
Data Flow Analysis 
Liveness analysis, reachingdef analysis, available expression analysis, very busy expression analysis 

14 
10/2611/4 
Loop
Optimizations 
Code motion, strength reduction, loop unrolling, loop fusion, loop interchange, loop tiling 

15 
11/711/14 
Dependence
Analysis 
Dependence analysis, optimistic parallelization 

16 
11/1612/2 
Pointsto
Analysis 
Flowsensitive pointsto analysis, flowinsensitive pointsto analysis, Anderson’s algorithm, Steensgaard’s algorithm 

17 
12/5 
Information
Flow 
Type checking, Security properties, security policies, information flow control 