Compiler Construction
General
| Lecturer | Prof. Dr. Peter Thiemann |
| Tutor | Fabian Krause |
| Lecture | Wednesday, 14:15 - 15:45, online on zoom |
| Exercise biweekly | Monday, 14:15 - 15:45, online on bbb |
News
| 31.01.2022 | Next (final) exercise on 07.02.2022. Next lecture on 02.02.2022 @ 15-17! Final meeting on 09.02.2022. |
| 26.01.2022 | Next (final) exercise on 07.02.2022. Next lectures on 31.01.2022, 02.02.2022. Final meeting on 09.02.2022. |
| 19.01.2022 | Next exercise on 24.01.2022. Next lecture on 26.01.2022. |
| 22.12.2021 | Next exercise on 10.01.2022. Next lecture on 12.01.2022. |
| 13.12.2021 | Information about the upcoming take-home exam. The task will be published shortly after the end of the lecture period. It is due on March 31, but it should not take more than two working days to complete. If there are questions about the exam, please ask them before March 18 as response times may be up to one week thereafter. During the last week before the deadline, you are on your own. Feel free to share tests among you. I cannot publish the tests used for grading because no feedback on grading is allowed during the exam. |
| 13.12.2021 | Next lectures on 13.12./ 15.12./ 22.12. No lecture/exercise on 20.12. |
| 17.11.2021 | Exercise on November 22. Next lecture November 24. |
| 30.10.2021 | There will be a lecture on November 3. First exercise on November 8. |
| 20.10.2021 | First lectures will take place on October 20, 25, 27. First exercise on November 3. |
Materials
Lecture recordings
| Date | Material |
|---|---|
| 2021-10-25 | Chapter 1, Chapter 2 (LVar, x86) |
| 2021-10-27 | Chapter 2.2 - end |
| 2021-11-03 | Chapter 3 (recording) |
| 2021-11-10 | Chapter 3.3 - end (recording) |
| 2021-11-15 | Chapter 4 - 4.4 (recording) |
| 2021-11-17 | Chapter 4.5 - end (recording) |
| 2021-11-24 | Chapter 5 (recording) |
| 2021-11-29 | Chapter 6 - 6.2 (recording) |
| 2021-12-01 | Chapter 6.2 - end (recording) |
| 2021-12-08 | slides on garbage collection (recording) |
| 2021-12-13 | Chapter 7 - 7.2 (recording) |
| 2021-12-15 | Chapter 7.3 - end + most of Chapter 8 (recording) |
| 2021-12-22 | Chapter 8 + roadmap for Chapter 9 (recording) |
| 2022-01-12 | Chapter 9 (recording) |
| 2022-01-17 | Interlude: Bootstrapping (recording) |
| 2022-01-19 | Interlude: Lexical Analysis (recording) |
| 2022-01-26 | Interlude: Syntax Analysis (Parsing) (recording) |
| 2022-01-31 | Interlude: Syntax Analysis (recursive descent parsing: first and follow) (recording) |
| 2022-02-02 @ 15:00 | Chapter 10 (recording) |
| 2022-02-09 | Chapter 10 (recording), discussion of evaluation (no recording) |
Exercises
| Date | Deadline | Sheet | Material |
|---|---|---|---|
| 2021-10-28 | 2021-11-08 | Assignment 1 | Chapter 1, slides |
| 2021-11-04 | 2021-11-22 | Assignment 2 | Chapter 2 |
| 2021-11-22 | 2021-12-06 | Assignment 3 | Chapter 3 |
| 2021-12-06 | 2021-12-20 | Assignment 4 | Chapter 4 |
| 2022-01-10 | 2022-01-24 | Assignment 5 | Chapter 6 |
| 2022-01-24 | 2022-02-07 | Assignment 6 | Chapter 7 |
Additional material for the exercises (sheets, slides, solutions)
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. 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. The current draft of the book is available in the ongoing course at Indiana University. We will be using the Python edition of the book!
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.