Compilers
Undergraduate · CS / Programming
Syllabus focus
Topics typically covered
Standard syllabus
Front end
- Compiler phases and intermediate representations
- Regular expressions, NFAs/DFAs, and lexical analyzers
- Context-free grammars and parse trees
- Top-down and bottom-up parsing (LL, LR intro)
- Syntax-directed translation and attribute grammars
Middle and back end
- Type checking and symbol tables
- Intermediate code: three-address code, SSA (intro)
- Runtime environments: stacks, heaps, activation records
- Code generation for a simple RISC-like target
- Register allocation and instruction selection (intro)
Implementation project skills
- Building a lexer/parser for a mini language
- AST design and visitor/walker patterns
- Error recovery and meaningful compiler diagnostics
- Linking, object files, and calling conventions (intro)
- Debugging generated assembly with a simulator
- Regression tests for front-end and back-end phases
Theoretical / proof-based
Formal foundations
- Ambiguity and grammar transformations
- LR parser table construction proofs (intro)
- Dataflow analysis framework: gen/kill, fixed points
- Correctness of live-variable and reaching-definitions analyses
- SSA construction and dominance frontiers (intro)
Optimization theory
- Peephole and local optimizations
- Global optimizations: constant propagation, DCE
- Loop optimizations: LICM, strength reduction (intro)
- Interprocedural analysis challenges
- Writing proofs for optimization safety (intro)
Analysis and correctness arguments
- Proving scanner/regex equivalence sketches
- Soundness of type systems for a core language (intro)
- Lattice theory for dataflow analyses
- Dominance, loops, and natural loop nesting
- Safety vs liveness properties of optimizations
- Writing machine-checked intuition without full formalization
Notes
Often includes a substantial course project implementing a compiler for a small language.