Compiler Construction

Core Course


Sebastian Hack, Fabian Ritter, Roland Lei├ča

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 voluntary mini tests which will take place in the last 20 minutes within the tutorial. Additionally, there will be voluntary exercise sheets. 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
2017-10-17 Introduction (Code)
2017-10-20 Intro to Syntax Analysis, Lexing
2017-10-24 Grammars, Push-Down Automata
2017-10-27 LL Parsing
2017-11-03, 2017-11-07 LR Parsing
2017-11-14 Semantic Analysis
2017-11-17 Introduction to Program Analysis
2017-11-21 Constant Propagation, Soundness
2017-11-24 Superfluous Computations, Dead Code Elimination
2017-12-01 Interval Analysis, Widening
2017-12-05 Pentagons, Global Value Numbering
2017-12-08 SSA Introduction
2017-12-12 SSA Construction, Background reading
2017-12-15 Simple and Efficient SSA Construction, Background reading
2017-12-19 LLVM Introduction and IR Generation
2018-01-05 Introduction to Code Generation
Graph-Coloring Register Allocation
2018-01-09, 2018-01-12 Register Allocation of SSA-form Programs
2018-01-16 Instruction Selection via PBQP
2018-01-19 Data Dependences
2018-01-23 Loop Transformations, Example Code
2018-01-26 Scheduling in the Polyhedral Model Sections 2, 3


  1. Exercise sheet 1 (including project tasks A and B, updated with fixed indentation in example)
  2. Exercise sheet 2
  3. Exercise sheet 3 (including project task C)
  4. Exercise sheet 4
  5. Exercise sheet 5 (including project task D)
  6. Exercise sheet 6 (including project task E)
  7. Exercise sheet 7
  8. Exercise sheet 8 (including project task F)
  9. Exercise sheet 9
  10. Exercise sheet 10 (including project task G, updated with information about LLVM passes)
  11. Exercise sheet 11

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: