Compiler Construction (Summer 2024)
General Information
- Lecturer: Prof. Dr. Peter Thiemann
- Assistants: Hannes Saffrich, Marius Weidner
- Lecture: Tuesday, 2:15 pm - 3:45 pm, SR 00 006 (G.-Köhler-Allee 051), Zoom
- Exercises: Friday, 2:15 pm - 3:45 pm, SR 00 006 (G.-Köhler-Allee 051), Zoom
Lectures & Tutorials
| Date | Type | Topic | Material | Recordings |
|---|---|---|---|---|
| 2024-04-16 Tu | Lecture | Organization & Introduction | Book, Chapter 1; Slides | missing |
| 2024-04-19 Fr | - | - | - | - |
| 2024-04-23 Tu | Lecture | Integers & Variables | Book, Chapter 2; Slides; Interpreter; Dockerfile | Video |
| 2024-04-26 Fr | Lecture | Scanning & Parsing | Book, Chapter 3; Slides; Lexer; Earley Example | Video |
| 2024-04-30 Tu | Tutorial | Parsing & Compiler for \(\mathcal{L}_{var}\) | Book, Chapter 2 & 3 | Video |
| 2024-05-03 Fr | Lecture | Register Allocation | Book, Chapter 4; Notes | Video |
| 2024-05-07 Tu | Lecture | Booleans & Conditionals | Book, Chapter 5; Notes | Video |
| 2024-05-10 Fr | Tutorial | Parsing & Compiler for \(\mathcal{L}_{var}\) | Video | |
| 2024-05-14 Tu | Lecture | Conditionals and While | Book, Chapter 5 & 6; Notes | Video |
| 2024-05-17 Fr | Tutorial | Register Allocation for \(\mathcal{L}_{var}\) | Video | |
| 2024-05-28 Tu | Lecture | Liveness Analysis & Garbage Collection | Slides (LA) Slides (GC) | Video |
| 2024-05-31 Fr | Tutorial | Compiler for \(\mathcal{L}_{if}\) | Video | |
| 2024-06-04 Tu | Lecture | Tuples & Garbage Collection | Book, Chapter 7; Slides | Video |
| 2024-06-07 Fr | Tutorial | Compiler for \(\mathcal{L}_{while}\) | Video | |
| 2024-06-11 Tu | Lecture | Top-Level Functions (Interpreter) | Book, Chapter 8; Material | Video |
| 2024-06-18 Tu | Lecture | Top-Level Functions (Typing, Codegen) | Book, Chapter 8; Slides; Material | Video |
| 2024-06-21 Fr | Tutorial | Compiler for \(\mathcal{L}_{tuple}\) | Video | |
| 2024-06-25 Tu | Lecture | Lambda Expressions (Interpretation, Typing, Codegen) | Book, Chapter 9; Material | Video |
| 2024-06-28 Fr | Tutorial | Compiler for \(\mathcal{L}_{fun}\) | Video | |
| 2024-07-02 Tu | Lecture | Generics (Typing, Codegen) | Book, Chapter 12; Material | Video |
| 2024-07-05 Fr | Tutorial | Compiler for \(\mathcal{L}_{lam}\) | Video | |
| 2024-07-09 Tu | Lecture | Exceptions (Interpreter, Typing, Codegen) | Material (preliminary) | Video |
| 2024-07-12 Fr | Tutorial | Compiler for \(\mathcal{L}_{exc}\) | Video | |
| 2024-07-16 Tu | Lecture | Optimization | Slides Examples | Video |
| 2024-07-19 Fr | Tutorial | Compiler for \(\mathcal{L}_{exc}\) | Video |
Exercises
Exercises are provided and submitted via GitHub Classroom (follow the invite link).
Exercises will not be graded, but we will provide tests to help you verify the correctness of your work. It is highly recommended to take the exercises seriously, as the exam requires you to extend the compiler from the sample solution with new features.
| Date | Deadline | Topic |
|---|---|---|
| 2024-04-30 Tu | 2024-05-10 Fr | Lexer, Parser and Compiler for \(\mathcal{L}_{var}\) |
| 2024-05-10 Fr | 2024-05-17 Fr | Register Allocation for \(\mathcal{L}_{var}\) |
| 2024-05-17 Fr | 2024-05-31 Fr | Compiler for \(\mathcal{L}_{if}\) |
| 2024-05-31 Fr | 2024-06-07 Fr | Compiler for \(\mathcal{L}_{while}\) |
| 2024-06-09 Su | 2024-06-21 Fr | Compiler for \(\mathcal{L}_{tuple}\) |
| 2024-06-21 Fr | 2024-06-05 Fr | Compiler for \(\mathcal{L}_{fun}\) |
| 2024-06-05 Fr | 2024-07-12 Fr | Compiler for \(\mathcal{L}_{lam}\) |
| 2024-07-12 Fr | 2024-07-19 Fr | Compiler for \(\mathcal{L}_{exc}\) |
Exam
The exam will take place in the computer pools and requires you to extend the compiler implemented in the exercises with new features.
Communication
For communication outside of the lecture, we provide an Ilias course and a discord-like chat.
The Ilias course is used exclusively to send emails in case of updates, e.g. if there is a bug in an exercise. Make sure to register to receive those emails.
The chat requires you to log in with your RZ-Account (same credentials as for Ilias).
Contents
Compiler construction deals with the development and implementation of translation from higher-level programming languages to machine code. This involves several important problems of general interest:
-
Semantic Analysis. A compiler transforms and analyses the tree structure of a program. This phase is specified using attribute grammars.
-
Intermediate Code. A compiler generates machine-independent intermediate code and performs several transformation and optimisation steps on it.
-
Memory model and garbage collection. The compiler maps data structures to memory structures. Languages with dynamic types and/or garbage collection require special care.
-
Machine code. Intermediate code is translated to machine code, which undergoes machine-specific optimisations. This involves techniques like tree grammars, dynamic programming and graph coloring.
Compiler construction has a long tradition, so the structure of compilers has been well thought out. Therefore, a compiler can act as an example for a well-structured software system. “Who can write a compiler, can write any program”.
Knowledge about the memory model is helpful when debugging programs written in a low-level programming language (C, C++).
Literature
This lecture is based on the upcoming book Essentials of Compilation by Jeremy G. Siek.
We will deviate from the book in two ways:
- we will compile to the RISC-V processor architecture instead of x86; and
- we will be using a different python framework for the exercises.
For this purpose, we have started our own fork of the book, which we will be updating during the semester to use RISC-V instead of x86 instructions.
Our version of the book is available on the GitHub Releases
page. Simply download the book.pdf file for the most recent release.
To get notified on new releases, we recommend to push the watch-button on the book’s GitHub repository, select Custom in the dropdown menu, and select Releases.
Additional Literature
- Andrew Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press, 2002
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools (2nd Edition).. Prentice Hall, 2006.
- Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.
- Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
- Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.
- Reinhard Wilhelm and Dieter Maurer. Übersetzerbau – Theorie, Konstruktion, Generierung – 2. Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.