News
- 15.08.2008: Certificates are available at the secretariat.
- 15.07.2008: The exam results are available here as well as the exam questions.
- 14.07.2008: The evaluation results are available - please see "Further information".
- 04.07.2008: The 10th (optional) exercise sheet is out earlier than usual. Bring your solutions to the chair until July 16 to get your extra points.
- 23.06.2008: There was a typo (two actually) in Exercise 7.2: in the first part one has to show that the grammar is not cyclic.
- 17.06.2008: the computation of LR(1) sets in Example 11.13 was not complete. The corrected slides are online. (The "LR(0) vs. LR(1)" slide and Examples 12.2 and 12.5 of lecture 12 were also affected.)
- 04.06.2008: on July 11 there will be DIES Academicus and therefore there will be no exercise course on that date!
- 21.04.2008: the written exam (Master SSE, Leistungsnachweis Diplom) is scheduled for Thursday, July 10. Dates for oral exams (Bachelor) are fixed by appointment.
- 15.04.2008: Simon Wollwage starts providing notes with the material written on the black board. Many thanks!
- 07.03.2008: because of a time clash with the database course, the Tuesday lecture is moved to Monday (10:00-11:30 at AH 2).
Note: Due to public holidays, there will be no lectures on 1, 12 and 22 May. Therefore exercise courses on 30 April, 14 May, 28 May are being canceled.
Schedule
Type | Day | Time | Place | Start | Lecturer | Interval |
V3/4 | Mon | 10:00-11:30 | AH 2 | April 14 | weekly | |
Thu | 15:00-16:30 | AH 5 | April 10 | weekly for Diplom/Master,
bi-weekly for Bachelor | ||
Ü2 | Wed | 13:30-15:00 | AH 3 | April 16 | weekly |
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
(notes provided by S. Wollwage)
Lecture | Date | BSc/MSc/Diplom | Subject | Slides | Handout | Notes |
1 | Thu April 10 | B/M/D | Introduction |  |  | - |
2 | Mon April 14 | B/M/D | Lexical Analysis I
(Simple Matching Problem) |  |  |  |
3 | Thu April 17 | B/M/D | Lexical Analysis II
(First-Longest-Match Analysis) |  |  |  |
4 | Mon April 21 | B/M/D | Lexical Analysis III
(Practical Aspects) |  |  | - |
5 | Thu April 24 | B/M/D | Syntactic Analysis I
(Introduction) |  |  | - |
6 | Mon April 28 | B/M/D | Syntactic Analysis II
(LL(k) Grammars) |  |  |  |
7 | Mon May 5 | B/M/D | Syntactic Analysis III
(LL(1) Grammars) |  |  | - |
8 | Thu May 8 | B/M/D | Syntactic Analysis IV
(Practical Issues in LL Parsing) |  |  | - |
9 | Mon May 19 | B/M/D | Syntactic Analysis V
(LR(k) Grammars) |  |  | - |
10 | Mon May 26 | B/M/D | Syntactic Analysis VI
(LR(0) Parsing) |  |  | - |
11 | Thu May 29 | B/M/D | Syntactic Analysis VII
(LR(1) Parsing) |  |  | - |
12 | Mon June 2 | B/M/D | Syntactic Analysis VIII
(LALR(1) Parsing) |  |  | - |
13 | Thu June 5 | B/M/D | Semantic Analysis I
(Definition of Attribute Grammars) |  |  | - |
14 | Mon June 9 | B/M/D | Semantic Analysis II
(Circularity of Attribute Grammars) |  |  | - |
15 | Thu June 12 | B/M/D | Semantic Analysis III
(Attribute Evaluation) |  |  | - |
16 | Mon June 16 | B/M/D | Semantic Analysis IV &
Code Generation I |  |  | - |
17 | Thu Jue 19 | B/M/D | Code Generation II
(Semantics & Intermediate Code) |  |  | - |
18 | Mon June 23 | B/M/D | Code Generation III
(Translation to Intermediate Code) |  |  | - |
19 | Thu June 26 | B/M/D | Code Generation IV
(Translation Example & Correctness) |  |  | - |
20 | Mon June 30 | B/M/D | Code Generation V
(Jumping Code & Procedure Parameters) |  |  | - |
21 | Thu July 3 | B/M/D | Code Generation VI
(Translation Example & Static Data Structures) |  |  | - |
22 | Mon July 7 | B/M/D | Code Generation VII
(Static & Dynamic Data Structures) |  |  | - |
- | Thu July 10 | M/D | Exam | - | - | - |
23 | Mon July 14 | B/M/D | Code Generation VIII
(Generation of Machine Code) |  |  | - |
- | Thu July 17 | B/M/D | (canceled) | - | - | - |
Exercise sheets
See www.infostudium.de for a discussion forum for computer science students of the RWTH.
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.
- There will be a written exam on July 10, for candidates in the Diplomstudiengang Informatik ("Leistungsnachweis", no previous registration required) and in the Software Systems Engineering Master program (registration at ZPA required).
- Evaluation results
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.
