Compiler Construction

Core Course


Sebastian Hack, Simon Moll, Johannes Doerfert

General Information

The course treats compiler construction for imperative programming languages. This includes lexical, syntactical, and semantic analysis as well as static program analysis, optimization, and code generation. This course provides all necessary theoretical knowledge required to implement a compiler from scratch, which forms the practical part of the lecture.

Modus Operandi

There will be eight voluntary mini tests which will take place in the last 20 minutes within the tutorial. Additionally, there will be voluntary exercises. To get a course certificate, students must pass the final exam and the project. Final grades will be based on the exam and the project.







Date Topic
2015-10-23 Lexical Analysis
2015-10-27 Context-free Grammars, Pushdown Automata
2015-11-03 Top-Down Parsing (LL)
2015-11-10, 2015-11-14 Bottom-Up Parsing (LR)
2015-11-17 Semantic Analysis
2015-11-20 — 2015-12-01Program Analysis
2015-12-04 Intervals, Pentagons
2015-12-08 Global Value Numbering
2015-12-11 SSA Introduction (accessible from UdS IP range only)
2015-12-14 SSA Construction via Dominance Frontiers (lecture notes coming soon)
2015-12-18 Simple and Efficient SSA Construction, IR construction, LLVM-IR generation
2016-01-05 Introduction to Code Generation
Graph-Coloring Register Allocation
2016-01-08, 2016-12-12 Register Allocation of SSA-form Programs
2016-01-15 Instruction Selection using PBQP
2016-01-19 Loop Transformations, Example Code
2016-01-27 Scheduling in the Polyhedral Model
2016-01-29 Data Flow Analysis in Loop Nests


  1. Excercise sheet 1 (including project tasks A and B)
  2. Excercise sheet 2
  3. Excercise sheet 3 (including project task C)
  4. Excercise sheet 4
  5. Excercise sheet 5 (including project task D)
  6. Excercise sheet 6 (including project task E)
  7. Excercise sheet 7
  8. Excercise sheet 8 (including project task F)
  9. Excercise sheet 9
  10. Excercise sheet 10 (including project task G)

Project Material


The course is mainly built on these books:

The library has several copies of the english version of the book.

The following books are among the "standard" compiler textbooks:

The following textbooks are stanard references for loop transformations: The following textbook provides a good introduction into the theory of polyhedra and linear programming: