Compiler Design (Autumn 2019)

Basic Information

Please check the course moodle for announcements, discussions, and information on the homework assignments and exercise sessions.

Both the course webpage and moodle may be frequently updated; please check them regularly.

Course Description

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.

Course Objectives


The following schedule is tentative --- topics may get changed, deleted, or added.

18.09 Introduction: Compilers, Interpreters, OCaml Slides (PDF)
19.09 OCaml Crash Course: Translating Simple to OCaml Slides (PDF)
25.09 X86lite Slides (PDF)
26.09 X86lite programming / C calling conventions Slides (PDF)
02.10 Intermediate Representations I (by Tobias Grosser) Slides (PDF)
03.10 Intermediate Representations II (by Tobias Grosser) Slides (PDF)
09.10 Intermediate Representations III / LLVM (by Tobias Grosser) Slides (PDF)
10.10 Structured Data in the LLVM IR (by Tobias Grosser) Slides (PDF)
16.10 Lexing: DFAs and ocamllex Slides (PDF)
17.10 Parsing I: Context Free Grammars Slides (PDF)
23.10 Parsing II: LL(k) parsing, LR(0) parsing Slides (PDF)
24.10 Parsing III: LR(1) Parsing and Menhir Slides (PDF)
30.10 First-class Functions I Slides (PDF)
31.10 First-class Functions II: Interpreters Slides (PDF)
06.11 Guest Lecture by Dr. David Leopoldseder on GraalVM Slides (PDF)
07.11 Exercise session
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)


Teaching assistants:

Exercise sessions: Mon 15-18, ETF C 1 (first session: 23.09.2019)

Further information will be announced/posted on course moodle.

Project: Implementing a Compiler

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:

The following additional papers and Web sites provide supplementary material:

Acknowledgements: The course content is adapted with permission from course materials by Steve Zdancewic at UPenn.