Compiler Construction

Core lecture

People

Reinhard Wilhelm, Sebastian Hack, Jörg Herter, and Christoph Mallon

General Information

Type: core lecture (9 credit points)
Place: lecture hall HS 003, building E1.3
Time: Monday and Wednesday, 10.00-12.00
Tutorials:
- Group 1: Thursday, 16.00-18.00, SR1, building E2.5
- Group 2: Thursday, 16.00-18.00, SR10 (012), building E2.4
- Group 3: Friday, 14.00-16.00, SR15, building E1.3
Exam: 2010-02-15, 10.00, HS 1, building E2.5
Re-exam: 2010-03-08, 10.00, HS 1, building E2.5

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

The points for the final exam are now online, grades will follow soon. You can have a look at your exam on Friday, 19.02.2010, 13:30hrs, in room 401, building E1.3.
The dates for the final exam as well as the resit are now online.
The first lecture has been rescheduled. It takes place on Wednesday, 14th October, 10.00hrs in lecture hall HS003, E1.3.
~~The first lecture takes place on Monday, 19th October, 10.00hrs in lecture hall HS003, E1.3.~~

Important Dates

First lecture: Wednesday, 2009/10/14, 10.00hrs, in HS003, building E1.3
Exam: 2010-02-15, 10.00, HS 1, building E2.5
Re-exam: 2010-03-08, 10.00, HS 1, building E2.5

Results: Final Exam and Resit

Student ID	Final Exam		Resit		Project	Final Grade
Student ID	Points	Grade	Points	Grade
2026128	17.5	3.7	-	-	1.7	2.7
2026545	9	5.0	22.5	3.0	1.7	2.3
2500225	5.5	5.0	-	-	5.0	5.0
2509135	17.5	3.7	-	-	1.3	2.7
2509421	10	5.0	17	4.0	2.3	3.3
2509715	11	5.0	10.75	5.0	5.0	5.0
2510038	5.5	5.0	6.25	5.0	5.0	5.0
2510494	18.5	3.3	25.5	2.3	1.0	1.7
2510516	-	-	10.5	5.0	5.0	5.0
2510951	11.5	5.0	16.5	5.0	5.0	5.0
2511880	18.5	3.3	22.25	3.0	1.3	2.3
2512788	29	1.0	-	-	1.0	1.0
2513328	0	5.0	-	-	5.0	5.0
2513516	0	5.0	13.5	5.0	5.0	5.0
2513902	20	3.0	24.75	2.3	1.3	1.7
2514212	0.5	5.0	-	-	5.0	5.0
2514464	15.75	4.0	20.5	3.3	2.3	2.7
2514476	9	5.0	28.5	1.7	1.3	1.7
2515500	8.5	5.0	18	4.0	2.3	3.3
2516963	15.25	4.0	15.25	5.0	1.0	2.7
2518059	7.5	5.0	16	5.0	5.0	5.0
2518092	0	5.0	-	-	5.0	5.0
2518099	-	-	9.75	5.0	5.0	5.0
2518834	13	5.0	14.25	5.0	5.0	5.0
2518913	30.75	1.0	-	-	1.3	1.0
2519851	7.5	5.0	15	5.0	5.0	5.0
2521218	21.5	2.7	19.5	3.7	1.3	2.0
2521289	20.5	3.0	26.75	2.0	1.0	1.7
2522929	20	3.0	20	3.3	1.0	2.0
2523290	22.5	2.3	26.75	2.0	1.0	1.7
2523291	17	3.7	20.75	3.3	1.0	2.3
2523391	29	1.0	-	-	1.0	1.0
2525594	21	2.7	17.25	4.0	1.0	2.0
2529001	13	5.0	15.25	5.0	2.3	5.0
2529076	13	5.0	21.5	3.0	2.3	2.7
2529146	24.5	2.0	23	2.7	1.0	1.7
2529289	13	5.0	18.75	3.7	4.0	3.7
2529442	12.5	5.0	18.25	4.0	2.3	3.3
2529649	20	3.0	-	-	1.3	2.3
⌀ (passed)		2.8		3.1	T	T

Lecture Notes

2009-10-19/21: Structure of the compiler and lexical analysis (updated 2009-10-20).
2009-10-26: Grammars and Push-down automata (updated 2009-11-19).
2009-10-28: Grammar Flow Analysis (updated 2009-11-02).
2009-11-02: Top-Down Syntax Analysis.
2009-11-04: Bottom-Up Syntax Analysis (updated 2009-11-09).
2009-11-16: Attribute Grammars. The lecture followed the book: W. Waite and G. Goos, Compiler Construction
2009-11-23: More on Attribute Grammars and their Evaluation (dependencies, evaluation), Short Circuit Evaluation, and CMa.
2009-11-30: Multiple inheritance in C++, Implementing Java interface invocations
2009-12-02/07: Approaches to Program Analysis and Data Flow Analysis.
2009-12-09: Paper: Constant Propagation with Conditional Branches
2009-12-14:
- Paper: Simple Generation of Static Single-Assignment Form
- Example SSA graphs generated with libFirm
- The yComp graph viewer needed to view the graph files
2009-12-16:
- Slides: SSA Construction
- Paper: Detecting Equality of Variables in Programs
2010-01-04:
- Slides: Code Motion, Code Placement
- Paper: Lazy Code Motion
2010-01-06: Code Selection
2010-01-11: Code Generation
2010-01-13: Instruction Selection on SSA Graphs / PBQP
2010-01-20:
- Second part of the Code Generation slides.
- Paper: Translating Out of Static Single Assignment Form
2010-01-20: SSA Register Allocation
2010-01-27/2010-02-01: Instruction Scheduling
2010-02-03:
- Slides: Software Pipelining / Modulo Scheduling
- Paper: Iterative Modulo Scheduling

Exercises

Exercise sheet 1 [pdf]
Exercise sheet 2 [pdf] (updated 2009-11-04)
Exercise sheet 3 [pdf]
Exercise sheet 4 [pdf]
Exercise sheet 5 [pdf] (updated 2009-11-23)
Exercise sheet 6 [pdf]
Exercise sheet 7 [pdf]
Exercise sheet 8 [pdf]
Exercise sheet 9 [pdf]
Exercise sheet 10: [pdf]

Tutorial Groups

Group 1 Thursday, 16-18 SR1, building E2.5 Tutor: Sebastian Hahn	Group 2 Thursday, 16-18 SR10 (012), building E2.4 Tutor: Klaas Boesche	Group 3 Friday, 14-16 SR15, building E1.3 Tutor: Florian Haupenthal
2510494 2512788 2519381 2513962 2513516 2519952 2517098 2518092 2513328 2514212 2516963 2521289 2529289 2529442 2509715 2030493	2521218 2508547 2523391 2523164 2500225 2525558 2519196 2525594 2030119 2505895 2020519 2529076 2529001 2515506 2514476 2509135 2505413 2026150	2510516 2510038 2509421 2510951 2515500 2514464 2523291 2523290 2026128 2026545 2518059 2518099 2511880 2029548 2022759 2029989 2029291 2502671 2519851 2529649 2522929 2529146 2529883

Contact

There exists a mailing list for all participants of the course: cc09@gigasun.cs.uni-sb.de.

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

Literature

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

Compiler Design Lab