Compiler Construction

Core Course

People

Reinhard Wilhelm, Sebastian Hack, Daniel Grund, Michael Jacobs

General Information

The course treats compiler construction for imperative programming languages. This includes lexical, syntactical, and semantic analysis as well as static program analysis, optimization, and code generation. This course provides all necessary theoretical knowledge required to implement a compiler from scratch, which forms the practical part of the lecture.

Type: core lecture (9 credit points)
Place: lecture hall HS 003, building E1 3
Time: Wednesdays and Fridays, 12.15–13.45
Exam: 2012-02-13, 09.00, E2 2, AudiMO
Re-exam: 2012-03-12, 09.00, E2 2, AudiMO

To get a course certificate, students must:

get at least 50% of the points for homework assignments,
pass the exam at the end of the term,
pass the practical project.

Final grades will be based on the exam and the project.

News

Theory: Check. Project: Make appointments.

Lecture Notes

2011-10-19: Introduction and Structure of a Compiler.
2011-10-21: Lexical Analysis.
2011-10-26: Context-Free Grammars and Grammar Flow Analysis.
2011-10-28: Pushdown Automata and Parser.
2011-11-02: LL Parsing.
2011-11-04: Black board lecture about expression parsing and precedence climbing.
2011-11-09: LR Parsing.
2011-11-11: LR Parsing continued.
2011-11-16: Semantic Analysis and Attribute Grammars.
2011-11-18: Attribute grammars continued.
2011-11-23: Attribute Dependencies and Attribute Evaluation.
2011-11-25: CMa - Translation of C.
2011-11-30: CMa continued and Program Analysis Approaches.
2011-12-02: Program Analysis Approaches continued and Data Flow Analysis.
2011-12-16: Lattices as of 2012-01-12.
2011-12-21:
- Slides: SSA Construction
- Background reading: Simple Generation of Static Single-Assignment Form
- Background reading: Constant Propagation with Conditional Branches
2012-01-11/13:
- Slides: Global Value Numbering
- Background reading: Detecting Equality of Variables in Programs
- Background reading: Detecting equalities of variables: Combining efficiency with precision (I took the presentation of Kildall's algorithm from this paper.)
2012-01-18: Code Motion, Code Placement
- Background reading: Lazy Code Motion
2012-01-20: Blackboard lecture on the implementation of inheritance
- Background reading: Multiple inheritance in C++
- Background reading: Implementing Java interface invocations
2012-01-25: Code Generation
2012-01-27: SSA-Form Register Allocation
2012-02-01: SSA-Form Register Allocation and Instruction Selection

Results

The following students have gained at least 50% of the exercise points. The results of both exams are also available now.

Student ID	Final Exam		Re-Exam		Project Grade	Final Grade
Student ID	Points	Grade	Points	Grade	Project Grade	Final Grade
2511042	16	5.0	-	-	-	-
2514359	16	5.0	39.5	2.7	2.7	2.7
2515294	29	3.0	42.5	2.3	-	-
2516088	-	-	46	2.0	1.0	1.7
2518099	22.5	4.0	26	5.0	2.0	3.0
2518686	28	3.0	34	3.3	1.0	2.0
2518834	28	3.0	42	2.3	1.0	1.7
2518894	32	2.3	-	-	3.0	2.7
2519766	28	3.0	46	2.0	1.0	1.7
2521139	21.5	5.0	27.5	4.0	1.0	2.7
2522025	25	3.7	-	-	3.0	3.3
2522705	20.5	5.0	21	5.0	-	-
2524568	40	1.0	-	-	1.0	1.0
2525627	31	2.7	43	2.3	1.0	1.7
2525783	24	4.0	25	5.0	3.0	3.7
2526159	19	5.0	30.5	3.7	2.0	3.0
2526193	24	4.0	44.5	2.0	2.0	2.0
2526240	23	4.0	25.5	5.0	4.0	4.0
2526241	11.5	5.0	10.5	5.0	-	-
2526415	31.5	2.3	45	2.0	2.0	2.0
2528532	28	3.0	35	3.3	1.7	2.3
2530270	30	2.7	-	-	1.7	2.3
2530469	18	5.0	43.5	2.3	2.0	2.3
2530559	22.5	4.0	22	5.0	1.0	2.7
2530690	42.5	1.0	-	-	1.0	1.0
2530699	29	3.0	24	5.0	1.0	2.0
2530947	35.5	1.7	44	2.0	1.0	1.3
2531407	10.5	5.0	26.5	5.0	-	-
2531460	36	1.7	-	-	1.0	1.3
2531557	37.5	1.3	-	-	1.7	1.3
2531835	29.5	3.0	33.5	3.3	1.0	2.0
2535661	14.5	5.0	20.5	5.0	-	-
2536539	15.5	5.0	14	5.0	-	-
2536586	9.5	5.0	19.5	5.0	-	-
2539125	25	3.7	-	-	4.0	3.7
2539755	2	5.0	20.5	5.0	-	-
2539760	12.5	5.0	21	5.0	-	-
2540414	22.5	4.0	37	3.0	1.0	2.0
2540807	27	3.3	-	-	4.0	3.7

Exercises

Exercise sheets will be handed out on Fridays in the lecture and can be downloaded below. Unless stated otherwise, exercises are due the respectively following week on Fridays before the lecture. The exercises will be discussed in the exercise groups the week after. Everybody has to do the exercises on their own. Group work is only for the practical project. Although the project assignments are printed on the exercise sheets, they have separate deadlines.

Tutorial groups

Group 1: Monday, 10.15–11.45, E1 1, U12, Felix Klein
Group 2: Wednesday, 16.00–18.00, E1 1, U12, Michael Bohn
Group 3: Friday, 10.00–12.00, E1 3, SR14, Florian Benz

Project

In the project you will implement a compiler for a small subset of Java. The milestones of the project roughly reflect the structure of a compiler, which also structures the lecture. Although the milestones will not be graded, they serve as a strong indicator—for increasing either your efforts or your confidence. The compiler itself must be written in C or C++ as we will make use of a C library (libFirm) for the back end of the compiler. Below, you can find all materials related to the project:

MiniJava language specification as of 2011-11-08.
Starter kit with test cases for the lexer.
Project tasks A and B: Lexer.
Project task C: Parser.
Project task D: Pretty printers with accompanying reference files.
Project task E: Semantic analysis.
Project task F and G: Firm construction and optimizations. Firm examples. libFirm 1.19.1. yComp.
Introduction to LibFirm as of 2011-12-21.
Project task H and I: Lowering and Back End. Firm back end, presented on 2012-01-20.

Literature

If you spot any errors in the freshly translated book, please drop Prof. Wilhelm a note.

Chapter 1 and 2 of Wilhelm, Seidl, Hack: Compiler Design — Syntactic and Semantic Analysis.
Chapter 2 as of 2011-10-20.
Chapter 3 as of 2011-11-10.
Chapter 3 – LR as of 2011-11-15.
Chapter 4 as of 2011-11-15.
Chapter 4 – Attribute Grammars as of 2011-11-29.
The corresponding bibliography.

The German version of some chapters:

Chapter 3.
Chapter 4.

Parts of Compiler Design – Analysis and Transformation:

Data flow analysis

Literature list

R. Wilhelm and D. Maurer, "Übersetzerbau"
Springer; Berlin, 2nd print, 1997. ISBN 3-540-61692-6.
R. Wilhelm and D. Maurer, "Compiler Design"
Addison-Wesley; Essex, 2nd print, 1996. ISBN 0-201-42290-5.
R. Wilhelm and H. Seidl, "Übersetzerbau -- Virtuelle Maschinen"
Springer, Berlin, 1st print, 2007. ISBN 978-3-540-49596-3.
W. Waite and G. Goos, Compiler Construction