Software Engineering

Compiler Construction

How does a program written in a high-level language get translated into machine code? This course explores the principles and techniques behind that process. Understanding compilers is not only essential for those building them—it also deepens every programmer’s intuition for what happens “under the hood” during program execution and reveals reusable techniques relevant to many other areas of software engineering.

Using Jeremy Siek’s “The Incremental Approach to Compiler Construction” as a guide, students build a compiler in small, testable stages for a gradually growing language. Topics include parsing, abstract syntax trees, register allocation via graph coloring, dataflow analysis, closure conversion, and garbage collection. Language features are introduced incrementally—from arithmetic and conditionals, to loops, functions, lambdas, and gradual typing—allowing students to see how design choices impact both the compiler architecture and the generated code.

Although Siek’s book uses Python, we build on the student’s experience from the software engineering course and implement the compiler in Scala.

Requirements

  • Theoretische Informatik 1 (e.g., graph theory)
  • Theoretische Informatik 2 (e.g., formal languages)
  • Praktische Informatik 1 – 3 (e.g., we expect that you know functional programming and can program in Scala)

Literature

  • Essentials of Compilation: An Incremental Approach in Python.
    Jeremy G. Siek. 2023. ISBN 9780262375542. (MIT Press, Free PDF)

Team

Dates

Lectures are Monday’s at 8:00 and Friday’s at 10:00. Both take place in F119 at Sand.

  • First lecture: Monday 14.04., 8am, F119 Sand
  • No lecture: Friday 18.04 and Monday 21.04