Compiler Construction, WS 2012/2013

General

News

• No news yet.

Organization

• Exercises
• Forum for the discussion of questions and problems

Slides

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.

Materials

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

Contents

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++).