OrganisationExercisesTools and SupportForum

Compiler Construction, WS 2012/2013


Lecture Prof. Dr. Peter Thiemann
TimeMon 14-16, Thu 10-11
Place051 - SR 00-034
Exercises Manuel Geffken
TimeThu 11-12
Place051 - SR 00-034


  • No news yet.



The slide sets marked with * are based on a slide set by Anthony Hosking. They are used by permission of the author and reposted and modified under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.

dateslideslast update
25.10.2012Lexical Analysis20121025
29.10.2012Extra: DFA to RE using derivatives
05.11.2012Top-Down Parsing20121029
12.11.2012Bottom-Up Parsing
19.11.2012Semantic Analysis20121122
26.11.2012Attribute Grammars20121126
29.11.2012Extra: Attribute grammar example
03.12.2012Intermediate Representation20121202
06.12.2012Instruction Selection, Extra: (slides by Torsten Grust). MIPS20121205
10.12.2012Extra: Compilation example20121210
13.12.2012Liveness Analysis20121209
17.12.2012Register Allocation20121209
20.12.2012Extra: program analysis slides 1-37
07.01.2013Garbage Collection20130107
10.01.2013Functional Programming Languages20130109
21.01.2013Polymorphic Types and Generics20130121
24.01.2013Type Inference20130124
28.01.2013Loop Optimization20130127
04.02.2013Static Single Assignment Form20130207
11.02.2013Register Allocation for Programs in SSA-Form20130211


  • This course is based on the book: Andrew Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press (2002)

Further Literature

  1.   Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools (2nd Edition).. Prentice Hall, 2006.
  2.   Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.
  3.   Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
  4.   Guy Cousineau and Michel Mauny. The Functional Approach to Programming. Cambridge University Press, 1998.
  5.   Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.
  6.   Rene Leermakers. The Functional Treatment of Parsing. Kluwer Academic Publishers, Boston, 1993.
  7.   Reinhard Wilhelm and Dieter Maurer. Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2. Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.


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:

Lexical and syntactic analysis
A compilers parses the input program, i.e. it translates the input string into a tree which reflects the structure of the program. This is a practical application of concepts from formal language theory, in particular regular and context-free languages.
Semantic Analysis
Next, the compiler transforms and analyses the tree structure. This phase is specified using attribute grammars.
Intermediate Code
Finally, the 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
In the last step, 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 having a long tradition, 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".

Techniques from compiler construction are also applied in many other occasions. Syntax analysis methods, for example, simplify reading config files and defining mini-languages.

Knowledge about the memory model is helpful when debugging programs written in a low-level programming language (C, C++).