Lehrstuhl Informatik II   
Sprachen und Beschreibungsstrukturen      
   Home Lehre Sommersemester 16 Vorlesungen Compiler Construction I login

Compiler Construction I

Dozent:Dr. Michael Petter
Ort/Zeit:Mo 14:00-16:00 in 00.13.009A
Beschreibung:    Introduction to Compilerconstruction - how to translate an imperative language.


  • two groups: Monday 4-5:30 p.m. and Tuesday 2:15-3:45 p.m., both in room 02.07.014 (tutorials start in the second week, i.e. from 18th April)


  1. Introduction
  2. Glushkov or Berry/Sethi
  3. DFA from NFA & Longest Match
  4. Item-Pushdown Automaton
  5. LL(k) Parsing and First/Follow Sets
  6. Shift-Reduce Parser and LR(0)/LR(1) Parsing
  7. Attribute Grammars and Strongly Acyclicness
  8. L-Attributation and Decl.-Use Analysis
  9. Type Checking - structural and by name
  10. Generating code for expressions
  11. Generating code for statements and functions



A Compiler is an essential part of the system software stack. Its job consists in translating programs from a high-level programming language like C or Java into a sequence of machine instructions of an actual processor. Compilers are comparatively complex programs. Their construction involves ideas and approaches from many different areas of computer science. The first two phases, i.e. lexical and syntactical analysis of the input program, are a major application for formal methods. Later on, e.g. during code generation, we treat methods for register allocation via approximative graph colouring.

The lecture is divided into the following topics:

  1. Outline of compiler construction
  2. Lexikal analysis:
    From regular expressions to NFAs
    Scannerdesign with NFAs
  3. Syntactical analysis
    Contextfree languages & pushdown automata
    Item-Pushdownautomata & Recursive Descent Parsing
    Shift-Reduce Parsing & LR(1) Parser
  4. Semantical analysis
  5. Codegeneration
    Code generation schemes
  6. Optimizations

Finally we may find time for less standard techniques for compilers, as e.g. the type inference of programs.

Exam FAQ:

  1. Attention: There will be only one exam at the end of the semester, and no repetition exam in the winter!
  2. You are allowed to bring a DIN A4 sheet of paper with notes on both sides.
  3. In case you did not pass, you have the opportunity to take "Programming Languages" or "Program Optimization" next semester or alternatively repeat the exam next summer.
  4. We will provide two printouts of the lecture slides in case there is some information you forgot to add to your A4 sheet. We will also provide some copies of the RCMa specification document.


Wilhelm, Seidl, Hack: Compiler Design: Syntactic and Semantic Analysis

for TUM students, the German edition is downloadable for free through the TUM/LRZ-Proxy, the English edition is available as several hardcopies in the library.

R-CMa specification

The instructions and the code generation schemes are summarized in the R-CMa specification.



Exercise Sheet 1
Exercise Sheet 1 (Solution)
Exercise Sheet 2
Exercise Sheet 2 (Solution)
Exercise Sheet 3
Exercise 3 (Solution)
Exercise Sheet 4
Exercise Sheet 4 (Solution)
Exercise Sheet 5  (aktualisiert!, 11.5.16)
Exercise Sheet 5 (Solution)
Parser.java (Solution)
Exercise Sheet 6
Exercise Sheet 6 (Solution)
Exercise Sheet 7
newExercise Sheet 7 (Solution)
Exercise Sheet 8
Exercise Sheet 8 (Solution)
Exercise Sheet 9
Package Exercise 9
Exercise Sheet 9 Solution
Exercise Sheet 10
Exercise Sheet 10 (Solution)
Exercise Sheet 11
Exercise Sheet 11 (Solution)

Exam 2015

The solution of the exam is only an example. There are different ways to solve the assignments.
Solution Exam 2015

angehängte Dateien:


TUM - Lehrstuhl Informatik II (Sprachen und Beschreibungsstrukturen) Thanks: Tango and TinyMCE     Generationszeit: 8 ms