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

Lectures

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

Date
Topic
Slides
Handouts
18.09 Introduction: Compilers, Interpreters, OCaml Slides (PDF) simple.ml
19.09 OCaml Crash Course: Translating Simple to OCaml Slides (PDF) lec02.zip
25.09 X86lite Slides (PDF) lec03.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
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
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

Exercises

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:

Literature

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.