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
26.09 X86lite programming / C calling conventions
02.10 Intermediate Representations I (by Tobias Grosser)
03.10 Intermediate Representations II (by Tobias Grosser)
09.10 Intermediate Representations III / LLVM (by Tobias Grosser)
10.10 Structured Data in the LLVM IR (by Tobias Grosser)
16.10 Lexing: DFAs and ocamllex
17.10 Parsing I: Context Free Grammars
23.10 Parsing II: LL(k) parsing, LR(0) parsing
24.10 Parsing III: LR(1) Parsing and Menhir
30.10 First-class Functions I
31.10 First-class Functions II: Interpreters
06.11 Closure Conversion and Types I
07.11 Types II: Judgments and Derivations
13.11 Subtyping
14.11 OO: Dynamic Dispatch and Inheritance
20.11 Multiple Inheritance & Optimizations I
21.11 Optimizations II / Data Flow Analysis
27.11 Register Allocation
28.11 Data Flow Analysis II
04.12 Control Flow Analysis / SSA Revisited
05.12 Selected Topics: Garbage Collection
11.12 Selected Topics: Compiler Testing
12.12 Selected Topics: Compiler Verification
18.12 Selected Topics: MLIR (by Tobias Grosser)
19.12 Course Summary


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.