Compiler Construction, WS 2010/2011
General
| Lecture | Prof. Dr. Peter Thiemann |
| thiemann@info... | |
| Time | Tue 16-18, Wed 16-17 |
| Space | 101-01-018 |
| Exercises | Konrad Anton |
| anton@info... | |
| Time | Wed 17-18 |
| Space | 101-01-018 |
News
- No news yet.
Organization
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.
| date | slides | extras |
|---|---|---|
| 19.10.2010 | Introduction* | |
| 20.10.2010 | Lexical Analysis* | |
| 26.10.2010 | continued | |
| 27.10.2010 | Syntax Analysis* | |
| 02.11.2010 | continued | |
| 03.11.2010 | Semantic Analysis* | Symbol table [Wilhelm/Maurer, chapter 8.1] |
| 09.11.2010 | Attribute grammars | |
| 10.11.2010 | Resolution of overloading | Overloading [Wilhelm/Maurer, chapter 8.1.3] |
| 16.11.2010 | Intermediate Representation, Contexts | |
| 17.11.2010 | ||
| 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.2010 | Data Flow Analysis (slides courtesy of Neil D. Jones, Copenhagen) | |
| 08.12.2010 | ||
| 14.12.2010 | Parsing revisited * LR parsing | |
| 15.12.2010 | LR parsing: SLR(1), LR(1) | |
| 21.12.2010 | LR parsing: background | |
| 22.12.2010 | ||
| 11.01.2011 | Functional Programming Languages | |
| 12.01.2011 | ||
| 18.01.2011 | Polymorphic Types and Generics | |
| 19.01.2011 | ||
| 25.01.2011 | Loop Optimization | |
| 26.01.2011 | ||
| 01.02.2011 | ||
| 02.02.2011 | Static Singe Assignment FOrm | |
| 08.02.2011 | ||
| 09.02.2011 | Static Singe Assignment FOrm |
Recordings of some lectures are available at /home/progpult/ws2010-2011/ on the computer science pool.
Materials
- 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
- Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986.
- Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.
- Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
- Guy Cousineau and Michel Mauny. The Functional Approach to Programming. Cambridge University Press, 1998.
- Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.
- Rene Leermakers. The Functional Treatment of Parsing. Kluwer Academic Publishers, Boston, 1993.
- 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++).