Compiler Construction
General
| Lecturer | Prof. Dr. Peter Thiemann |
| Assistant | Matthias Keil |
| Lecture | Monday, 2pm - 4pm, SR 01-016, Building 101 |
| Thursday, 2pm - 3pm, SR 01-016, Building 101 | |
| Exercise | Thursday, 3pm - 4pm, SR 01-016, Building 101 |
News
| 17.11.2016 | On Thursday, 17 November, there will be two hours of lecture. The exercise sessions gets postponed to Monday, 21 November. |
| 03.11.2016 | For Exercise Sheet 2, the definition of MainClass is correct! It really takes an element of type String[] as an argument, even if we do not have strings at all. This is required because MiniJava is a subset of Java. |
| 21.10.2016 | For Exercise Sheet 1, please consider the definition of the straight-line programming language on slides 28-30. The pretty-printing visitor (exercise 1.2) should output a string according to given program. This means, for the example program on the exercise sheet it shout output the string "a := (print(3),5)". |
| 17.10.2016 | The course starts on Monday, 17 October with an introduction of the exercise program. The first lecture will be on Thursday, 20 October. |
Slides and Materials
| Date | Material |
|---|---|
| 17.10.2016 | Introduction to the exercise program, Arith.zip |
| 20.10.2016 | Introduction |
| 24.10.2016 | Lexical Analysis |
| 27.10.2016 | Syntax Analysis |
| 14.11.2016 | Semantic Analysis |
| 17.11.2016 | Storage Allocation |
| 21.11.2016 | Types and Type Soundness |
| 28.11.2016 | Intermediate Representation |
| 05.12.2016 | Attribute Grammars |
| 12.12.2016 | Instruction Selection |
| 15.12.2016 | Tree Patterns, MIPS |
| 19.12.2016 | Liveness Analysis |
| 22.12.2016 | Register Allocation |
| 09.01.2017 | Polymorphism and Generics |
| 12.01.2017 | Loop Optimization I |
| 16.01.2017 | Loop Optimization II |
| 19.01.2017 | Static Single-Assignment Form (SSA) |
| 23.01.2017 | SSA (cont) |
| 26.01.2017 | Register Assignment in SSA |
| 30.01.2017 | Garbage Collection |
| 02.02.2017 | Garbage Collection |
| 06.02.2017 | Functional Programming Languages I |
| 09.02.2017 | Functional Programming Languages II |
Exercises
Detailed information on the exercise can be found on the exercise page.
| Date | Deadline | Sheet | Material |
|---|---|---|---|
| 20.10.2016 | 03.11.2016 | ex1.pdf | |
| 03.11.2016 | 17.11.2016 | ex2.pdf | |
| 17.11.2016 | 08.12.2016 | ex3.pdf | |
| 08.12.2016 | 12.01.2017 | ex4.pdf | |
| 12.01.2017 | 02.02.2017 | ex5.pdf | |
| 02.02.2017 | 16.02.2017 | ex6.pdf |
Homework Topics
To register for a homework topic please send an email with the preferred topic to Matthias Keil.
Submission deadline for the written homework is: 09.02.2017, 12:00 (noon). Submit your solution to the subversion repository. Your submission will consist of one folder (homework) which includes your homework.
| Title | Literature / Material | Student |
|---|---|---|
| Partial Redundancy Elimination | Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition | Maximilian Ernestus |
| Value Numbering | Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition | |
| Basic-block Scheduling | Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition | Yuriy Dzerin |
| Interprocedural Analysis | Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition | Polina Koleva |
| Run-Time Environments for non-local Data | Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition | |
| Inline Caching | Urs HölzleCraig, Chambers, and David Ungar, Optimizing dynamically-typed object-oriented languages with polymorphic inline caches | Jonas Thiem |
| Virtual-Machine Abstraction and Optimization Techniques | Stefan Brunthaler, Virtual-Machine Abstraction and Optimization Techniques | Daniel Blank |
| Taming MATLAB | Anton Willy Dubrau and Laurie Jane Hendren,Taming MATLAB |
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++).
Literature
- Andrew Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press, 2002
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools (2nd Edition).. Prentice Hall, 2006.
- 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.