CS 352: Compilers: Principles and Practice

List of Topics (By Week):

1. Introduction: modules and interfaces, tools and software

2. Programming data structures for tree languages

3. Lexical analysis: lexical tokens, regular expressions, finite automata, lexical analyser generators

4. Parsing I: context-free grammars, predictive parsing

5. Parsing II: LR parsing, parser generators

6. Abstract syntax: semantic actions, abstract parse trees

7. Semantic analysis: symbol tables, type-checking expressions, type-checking declarations

8. Activation records: stack frames, allocation

9. Translation to intermediate code: intermediate representation trees, translation into trees

10. Basic blocks and traces: canonical trees, conditional branches

11. Instruction selection: algorithms for instruction selection, CISC and RISC machines

12. Liveness analysis: solution of basic dataflow equations

13. Register allocation: graph coloring, coloring by simplification, coalescing, register allocation for trees

14. Supplemental material: a selection drawn from garbage collection, object-oriented languages, functional languages, dataflow analysis, optimization, polymorphism, static single-assignment form, scheduling and pipelining, memory hierarchies

15. Summary

1998.08