Uni-Logo

Compiler Construction

General

LecturerProf. Dr. Peter Thiemann
TutorFabian Krause
LectureWednesday, 14:15 - 15:45, online on zoom
Exercise biweeklyMonday, 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

GitHub repository

Lecture recordings

DateMaterial
2021-10-25Chapter 1, Chapter 2 (LVar, x86)
2021-10-27Chapter 2.2 - end
2021-11-03Chapter 3 (recording)
2021-11-10Chapter 3.3 - end (recording)
2021-11-15Chapter 4 - 4.4 (recording)
2021-11-17Chapter 4.5 - end (recording)
2021-11-24Chapter 5 (recording)
2021-11-29Chapter 6 - 6.2 (recording)
2021-12-01Chapter 6.2 - end (recording)
2021-12-08 slides on garbage collection (recording)
2021-12-13Chapter 7 - 7.2 (recording)
2021-12-15Chapter 7.3 - end + most of Chapter 8 (recording)
2021-12-22Chapter 8 + roadmap for Chapter 9 (recording)
2022-01-12Chapter 9 (recording)
2022-01-17Interlude: Bootstrapping (recording)
2022-01-19Interlude: Lexical Analysis (recording)
2022-01-26Interlude: Syntax Analysis (Parsing) (recording)
2022-01-31Interlude: Syntax Analysis (recursive descent parsing: first and follow) (recording)
2022-02-02 @ 15:00Chapter 10 (recording)
2022-02-09Chapter 10 (recording), discussion of evaluation (no recording)

Exercises

DateDeadlineSheetMaterial
2021-10-282021-11-08Assignment 1Chapter 1, slides
2021-11-042021-11-22Assignment 2Chapter 2
2021-11-222021-12-06Assignment 3Chapter 3
2021-12-062021-12-20Assignment 4Chapter 4
2022-01-102022-01-24Assignment 5Chapter 6
2022-01-242022-02-07Assignment 6Chapter 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

  1. Andrew Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press, 2002
  2. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools (2nd Edition).. Prentice Hall, 2006.
  3. Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.
  4. Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
  5. Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.
  6. Reinhard Wilhelm and Dieter Maurer. Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2. Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.