Both the course webpage and moodle may be frequently updated; please check them regularly.
This course uses compilers as example to expose students to modern software development techniques. The course introduces the students to the fundamentals of compiler construction. Students will implement a simple yet complete compiler for an object-oriented programming language for a realistic target machine. Students will learn the use of appropriate tools. Throughout the course, students learn to apply their knowledge of theory (automata, grammars, stack machines, program transformation) and well-known programming techniques (module definitions, design patterns, frameworks, software reuse) in a software project.
A tentative list of topics: compiler organization; lexical analysis; top-down and bottom-up parsing; symbol tables; semantic analysis; code generation; local and global optimization; register allocation; automatic memory management; optional advanced topics if/when time permits.
The following schedule is tentative --- topics may get changed, deleted, or added.
|18.09||Introduction: Compilers, Interpreters, OCaml||Slides (PDF)||simple.ml|
|19.09||OCaml Crash Course: Translating Simple to OCaml||Slides (PDF)||lec02.zip|
|26.09||X86lite programming / C calling conventions||Slides (PDF)||lec04.zip|
|02.10||Intermediate Representations I (by Tobias Grosser)||Slides (PDF)||lec05.zip|
|03.10||Intermediate Representations II (by Tobias Grosser)||Slides (PDF)||lec06.zip|
|09.10||Intermediate Representations III / LLVM (by Tobias Grosser)||Slides (PDF)||lec07.zip|
|10.10||Structured Data in the LLVM IR (by Tobias Grosser)||Slides (PDF)||lec08.zip|
|16.10||Lexing: DFAs and ocamllex||Slides (PDF)||lec09.zip|
|17.10||Parsing I: Context Free Grammars||Slides (PDF)||lec10.zip|
|23.10||Parsing II: LL(k) parsing, LR(0) parsing||Slides (PDF)||parser.ml|
|24.10||Parsing III: LR(1) Parsing and Menhir||Slides (PDF)||lec12.zip|
|30.10||First-class Functions I||Slides (PDF)||lec13.zip|
|31.10||First-class Functions II: Interpreters||Slides (PDF)|
|06.11||Guest Lecture by Dr. David Leopoldseder on GraalVM||Slides (PDF)|
|13.11||Closure Conversion and Types: Judgments and Derivations||Slides (PDF)|
|14.11||Subtyping; OO: Dynamic Dispatch and Inheritance||Slides (PDF)|
|20.11||Multiple Inheritance & Optimizations I||Slides (PDF)|
|21.11||Optimizations II / Data Flow Analysis||Slides (PDF)|
|27.11||Register Allocation||Slides (PDF)|
|28.11||Data Flow Analysis II||Slides (PDF)|
|04.12||Control Flow Analysis / SSA Revisited||Slides (PDF)|
|05.12||Garbage Collection||Slides (PDF)|
|11.12||Selected Topics: Compiler Testing||Slides (PDF)|
|12.12||Selected Topics: Compiler Verification (ICALP invited talk by Xavier Leroy)||Slides (PDF)|
|18.12||Selected Topics: MLIR (by Tobias Grosser)||Slides (PDF)|
|19.12||Course Summary||Slides (PDF)|
Further information will be announced/posted on course moodle.
The overall project is to implement a simple yet complete compiler for an object-oriented programming language for a realistic target machine. It consists of six parts, i.e., six homework assignments. Homework 1 must be completed individually, while the rest of the homework assignments should be completed in pairs (all students are strongly encouraged to work in pairs, but may request for permission from the TAs to work alone on them).
Details of the homework assignments will be announced on our course moodle. The following lists the homework assignments and their respective due dates:
The following books contain useful course material, and much of the lecture content is derived from them and other sources:
Acknowledgements: The course content is adapted with permission from course materials by Steve Zdancewic at UPenn.