Uni-Logo

Compiler Construction

General

LecturerProf. Dr. Peter Thiemann
AssistantMatthias Keil
LectureMonday, 2pm - 4pm, SR 01-016, Building 101
Thursday, 2pm - 3pm, SR 01-016, Building 101
ExerciseThursday, 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.2016For 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.2016For 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.2016The 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

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

DateDeadlineSheetMaterial
20.10.201603.11.2016ex1.pdf ex1.1-template.zip, ex1.2-template.zip
03.11.201617.11.2016ex2.pdf ex2-template.zip
17.11.201608.12.2016ex3.pdf ex3-template.zip
08.12.201612.01.2017ex4.pdf ex4-template.zip, ex3-solution.pdf
12.01.201702.02.2017ex5.pdf ex5-template.zip, ex4-muster.zip
02.02.201716.02.2017ex6.pdf ex6-template.zip, ex5-muster.zip

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.

TitleLiterature / MaterialStudent
Partial Redundancy EliminationAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second EditionMaximilian Ernestus
Value NumberingAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition
Basic-block SchedulingAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second EditionYuriy Dzerin
Interprocedural AnalysisAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second EditionPolina Koleva
Run-Time Environments for non-local DataAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, and Monica S. Lam Compilers: Principles, Techniques, and Tools, Second Edition
Inline CachingUrs HölzleCraig, Chambers, and David Ungar, Optimizing dynamically-typed object-oriented languages with polymorphic inline cachesJonas Thiem
Virtual-Machine Abstraction and Optimization TechniquesStefan Brunthaler, Virtual-Machine Abstraction and Optimization TechniquesDaniel Blank
Taming MATLABAnton 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

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