Compiler Construction, WS 2010/2011


Lecture Prof. Dr. Peter Thiemann
Time Tue 16-18, Wed 16-17
Space 101-01-018
Exercises Konrad Anton
TimeWed 17-18
Space 101-01-018


  • 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.

20.10.2010Lexical Analysis*
27.10.2010Syntax Analysis*
03.11.2010Semantic Analysis*Symbol table [Wilhelm/Maurer, chapter 8.1]
09.11.2010Attribute grammars
10.11.2010Resolution of overloadingOverloading [Wilhelm/Maurer, chapter 8.1.3]
16.11.2010Intermediate Representation, Contexts
23.11.2010 Instruction selection (using slides by Torsten Grust). CISC challenges (p. 18--25). MIPS.
24.11.2010 Liveness analysis, Register allocation.
30.11.2010 Register allocation example
01.12.2010 Garbage collection
07.12.2010Data Flow Analysis (slides courtesy of Neil D. Jones, Copenhagen)
14.12.2010Parsing revisited * LR parsing
15.12.2010LR parsing: SLR(1), LR(1)
21.12.2010LR parsing: background
11.01.2011Functional Programming Languages
18.01.2011Polymorphic Types and Generics
25.01.2011Loop Optimization
02.02.2011Static Singe Assignment FOrm
09.02.2011Static Singe Assignment FOrm

Recordings of some lectures are available at /home/progpult/ws2010-2011/ on the computer science pool.


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

More Literature

  1.   Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986.
  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++).