News
- The results of the second exam are online (see below). Students may review their exams on Thursday, April 29, from 11:00 to 12:00 at the seminar room of Informatik 2 (or after consultation with Dr. Noll).
- The results of the first exam are online (see below). Students may review their exams on Tuesday, March 2, from 15:00 to 16:00 at room 5052 (or after consultation with Dr. Noll).
- The 26th lecture (on Feb. 2) will be organized as a question time, to prepare for the exam.
- Bachelor or master students should register for the exam through ZPA, bachelor students who would like to have CB as an achievement in master study or Diplom students can register the exam by us
- The 10th exercise sheet is the last one.
- There is no exercise class on Wednesday, January 27. Instead, we offer a question-hour at Informatik 2 in room 4207.
- The 9th exercise is the last one for bachelor students.
- The lecture on December 17 (Code generation II). is the last one for bachelor students.
- There is no exercise class on December 23.
- 13.10.2009: first written exam scheduled for Wed February 3, 10:00-11:30 (in place of exercise class), second written exam scheduled for Wed March 17, 14:00-15:30 at AH 1
- 30.09.2009: start of lecture moved to Oct. 15 (from Oct. 13)
- 11.09.2009: page set up
Schedule
Type | Day | Time | Place | Start | Lecturer |
V3/4 | Tue | 14:00-15:30 | AH 2 | Oct 20 | |
Thu | 13:30-15:00 | AH 1 | Oct 15 | ||
Ü2 | Wed | 10:00-11:30 | AH 2 | Oct 28 |
Contents
The goal of this course is to introduce foundational methods and techniques for implementing compilers for high-level (procedural) programming languages. The following issues will be discussed:
- Lexical analysis of programs (Scanner)
- Syntactic analysis of programs (Parser)
- Semantic analysis of programs
- Code generation
- Tools for compiler construction (lex, yacc)
Prerequisites
Basic knowledge of the relevant undergraduate courses of the first two years (Vordiplom/Bachelor) is required:
- Programming (essential concepts of imperative and object-oriented programming languages and elementary programming techniques)
- Data structures and algorithms (lists, stacks, queues, trees and associated algorithms)
- Formal languages and automata theory (regular and context-free languages, finite and pushdown automata)
Slides
(also have a look at http://videoag.fsmpi.rwth-aachen.de/ for live video recordings)
Lecture | Date | BSc/MSc/Diplom | Subject | Slides | Handout |
1 | Thu Oct 15 | B/M/D | Introduction |  | |
2 | Tue Oct 20 | B/M/D | Lexical Analysis I
(Simple Matching Problem) | | |
3 | Thu Oct 22 | B/M/D | Lexical Analysis II
(First-Longest-Match Analysis) | | |
4 | Tue Oct 27 | B/M/D | Lexical Analysis III
(Practical Aspects) | | |
5 | Thu Oct 29 | B/M/D | Syntactic Analysis I
(Introduction) | | |
6 | Tue Nov 3 | B/M/D | Syntactic Anlysis II
(LL(k) Grammars) | | |
7 | Thu Nov 5 | B/M/D | Syntactic Analysis III
(LL(1) Grammars) | | |
8 | Tue Nov 10 | B/M/D | Syntactic Analysis IV
(LL(1) Parsing) | | |
9 | Thu Nov 12 | B/M/D | Syntactic Analysis V
(LR(k) Grammars) | | |
10 | Tue Nov 17 | B/M/D | Syntactic Analysis VI
(LR(0) Parsing) | | |
11 | Thu Nov 19 | B/M/D | Syntactic Analysis VII
([S]LR(1) Parsing) | | |
12 | Tue Nov 24 | B/M/D | Syntactic Analysis VIII
(LALR(1) Parsing) | | |
13 | Thu Nov 26 | B/M/D | Syntactic Analysis IX (Wrap-Up)/
Semantic Analysis I (Attribute Grammars) | | |
- | Tue Dec 1 | - | CANCELED | - | - |
14 | Thu Dec 3 | B/M/D | Semantic Analysis II
(Definition and Circularity of Attribute Grammars) | | |
15 | Tue Dec 8 | B/M/D | Semantic Analysis III
(Circularity Test) | | |
16 | Thu Dec 10 | B/M/D | Semantic Analysis IV
(Strong Noncircularity and Attribute Evaluation) | | |
17 | Tue Dec 15 | B/M/D | Semantic Analysis V (Attribute Evaluation)/
Code Generation I (Foundations) | | |
18 | Thu Dec 17 | B/M/D | Code Generation II
(Intermediate Code) | | |
19 | Thu Jan 7 | M/D | Code Generation III
(Translation to Intermediate Code) | | |
20 | Tue Jan 12 | M/D | Code Generation IV
(Jumping Code & Static Data Structures) | | |
21 | Thu Jan 14 | M/D | Code Generation V
(Translation of Static Data Structures) | | |
22 | Tue Jan 19 | M/D | Code Generation VI
(Dynamic Data Structures) | | |
23 | Thu Jan 21 | M/D | Code Generation VII
(Garbage Collection & Generation of Machine Code) | | |
24 | Tue Jan 26 | M/D | Code Optimization I
(Introduction to Dataflow Analysis) | | |
25 | Thu Jan 28 | M/D | Code Optimization II
(The Dataflow Analysis Framework)
| | |
26 | Tue Feb 2 | B/M/D | Question Time | - | - |
Exercise sheets
(to follow)
- Exercise 1
- Exercise 2
- Exercise 3
- Exercise 4
- Exercise 5
- Exercise 6
- Exercise 7
- Exercise 8
- Exercise 9
- Exercise 10
See www.infostudium.de for a discussion forum for computer science students of the RWTH.
First Exam
The first exam was written on February 3, with the following outcome.
Matriculation no. | Grade |
|---|---|
242561 | 5.0 |
257816 | 2.0 |
269570 | 5.0 |
270701 | 2.0 |
273154 | 1.7 |
275179 | 5.0 |
275361 | 5.0 |
276005 | 2.7 |
279025 | 2.0 |
279026 | 2.0 |
279185 | 3.3 |
279532 | 1.7 |
279996 | 1.7 |
280029 | 1.3 |
280069 | 1.3 |
280576 | 2.3 |
281109 | 1.7 |
281183 | 2.3 |
281241 | 1.7 |
281289 | 3.3 |
281302 | 3.3 |
281665 | 2.7 |
281866 | 5.0 |
281993 | 2.7 |
282032 | 2.7 |
282642 | 3.0 |
282691 | 2.3 |
282912 | 2.3 |
282953 | 3.7 |
283096 | 1.3 |
287547 | 1.7 |
291375 | 1.3 |
294036 | 3.0 |
296488 | 3.0 |
297775 | 4.0 |
The following grading scheme was used:
Points | Grade |
|---|---|
≥ 35 | 1.0 |
≥ 33 | 1.3 |
≥ 31 | 1.7 |
≥ 29 | 2.0 |
≥ 27 | 2.3 |
≥ 25 | 2.7 |
≥ 23 | 3.0 |
≥ 21 | 3.3 |
≥ 19 | 3.7 |
≥ 18 | 4.0 |
other | 5.0 |
Students may review their exams on Tuesday, March 2, from 15:00 to 16:00 at room 5052 (or after consultation with Dr. Noll). The second exam is scheduled for Wednesday, March 17, from 14:00 to 16:00 at AH 1.
Second Exam
The second exam was written on March 17, with the following outcome.
Matriculation no. | Grade |
|---|---|
242561 | 4.0 |
265955 | 1.7 |
267666 | 3.0 |
273138 | 2.7 |
273140 | 3.3 |
275179 | 3.7 |
275361 | 2.7 |
279124 | 2.7 |
281516 | 2.0 |
281912 | 1.0 |
281913 | 1.0 |
283277 | 1.3 |
The following grading scheme was used:
Points | Grade |
|---|---|
≥ 38 | 1.0 |
≥ 36 | 1.3 |
≥ 34 | 1.7 |
≥ 32 | 2.0 |
≥ 30 | 2.3 |
≥ 28 | 2.7 |
≥ 26 | 3.0 |
≥ 24 | 3.3 |
≥ 12 | 3.7 |
≥ 20 | 4.0 |
other | 5.0 |
Students may review their exams on Thursday, April 29, from 11:00 to 12:00 at the seminar room of Informatik 2 (or after consultation with Dr. Noll).
Remark: The last statement in the multiple-choice part (Question 1) about "jumping code" for Boolean expressions was not adequate for Bachelor students. Wrong answers were not take into account therefore.
Further information
- The course will be entirely given in German. The slides and other course material will be in English. There are no lecture notes (yet); the course material will consist of slides.
- The form of the exam (oral/written) will be announced in the beginning of the course.
Additional background literature
- A. Aho, M.S. Lam, R. Sethi, J.D. Ullman: Compilers – Principles, Techniques, and Tools; 2nd ed. Addison-Wesley, 2007.
A.W. Appel, J. Palsberg: Modern Compiler Implementation in Java. Cambridge University Press, 2002.
D. Grune, H.E. Bal, C.J.H. Jacobs, K.G. Langendoen: Modern Compiler Design. Wiley & Sons, 2000.
R. Wilhelm, D. Maurer: Übersetzerbau, 2. Auflage. Springer, 1997.
