| Topic |
Chapter |
Lab |
Review Q's |
Details & Review Questions |
| Introduction |
1-1.2 |
- |
- |
Phases of compilation; |
|
|
|
|
Algorithms for manipulating algorithms |
| Lexical |
2 |
1 |
2.1 |
Regular expressions and the “lex” language |
| scanning |
|
|
Run 2.5a w/xzxzy |
Finite Automata |
|
|
|
2.4,5,2,8 |
Converting R.E. →NFA→DFA |
| Parsing |
3 |
2 |
3.3 |
Review of CFG's, LL parsing |
|
|
|
3.11,12a |
LR(0) parse tables — generation and
use |
|
|
|
3.12,13,14 |
SLR, LR(1), and LALR(1) table generation |
| Fixed-point |
3.2 |
|
3.6a,5(no table) |
FIRST, FOLLOW and NULLABLE |
| algorithms |
|
|
|
calculations as examples of fixed-point algorithm |
| Attribute |
Dragon |
3 |
Dragon |
Static analysis as tree labelling; |
| grammars |
5-5.3 |
|
5.1,3,4,6a |
Detecting illegal lvalues |
| Abstract |
4 |
4 |
- |
Abstract syntax trees and their |
| syntax |
|
|
|
construction as synthesized attributes |
| Inherited |
Dragon |
|
Dragon |
Evaluation of arbitrary attribute grammars; |
| attributes |
5.4,7,(10) |
|
5.12a,14 |
Efficient evaluation of L-attributed grammars |
| Type checking |
5 |
5 |
5.3 |
Symbol table data structures; |
|
|
|
|
Representing type information; |
|
|
|
|
Attributes and traversals for type checking |
| Code |
7-7.2,8 |
6 |
7.1,2 in HERA |
Intermediate representations & canonical forms; |
| generation |
|
|
|
Machine language for arithmetic; |
| (arithmetic) |
|
|
|
Sethi-Ullman register allocation; |
|
|
|
|
Simpleminded code generation |
| (control flow) |
7.2 |
6 |
|
Machine language for branches; |
| |
|
|
|
Representations of conditional expressions; |
|
|
|
|
String operations and simple function calls |
| (functions) |
6-6.1,7.2-3 |
6-7 |
6.1,2,3,5 |
Storage for parameters, local variables, returns; |
| |
|
|
|
Return addresses, Dynamic links, Static links; |
|
|
|
|
Code generation for function calls; |
|
|
|
|
Code generation for variable references; |
| |
|
|
|
Escape analysis |
| (types) |
|
8 |
|
Code generation for arrays; |
|
|
|
|
Code generation for records |
| Instruction |
8, 9-9.2 |
|
8.6,7; 9.1,3 |
Instruction tiles |
| selection |
|
|
|
Maximal Munch instruction selection |
| revisited |
|
|
|
Dynamic programming-based instruction selection |
| Register |
10,11 |
|
10.1 & color it |
Liveness analysis |
| allocation |
|
|
|
Fixed point evaluation of live ranges |
| revisited |
|
|
|
Graph coloring and register allocation |
| Optimizations |
17 |
|
17.2,5,1 |
Constant folding |
| and |
|
|
|
Constand and copy propogation |
| analyses |
|
|
|
Dead code elimination |
| (time |
18-18.4 |
|
|
Hoisting invariant computations |
| permitting) |
|
|
|
Induction variables and array bounds checks |
|
19 |
|
19.11,8,7 |
Static Single Assignment form |