Compiler Construction

06.04.2011: Updated results after exam review online! If you could not make it to the review and want to examine your second exam, please do not hesitate to contact us.
06.04.2011: The results of the second exam are online.
04.04.2011: The exam review for the second exam takes part on Wednesday, 06.04.2011, from 16 to 17.30 in room 5054.
08.02.2011: Updated results after exam review online!
03.02.2011: Notice that the exam review will be tomorrow, 04.02.2011, from 15.30 to 17.30 in room 5052. (Campus)
03.02.2011: The results of the exam are online.
31.01.2011: The lecture hall allocation for the exam tomorrow is as follows: AH II Matr.No. 256000-288030 (only 6 Credit exam!), AH III Matr. No. 288200-307078 + all students taking the 8 Credit exam
21.01.2011: In addition to the presentation of the solution for Ex. 11 there will be a question time at the exercise class on Wednesday, 26.01.2011. Please send your questions via e-mail beforehand.
12.01.2011: You can find an overview of the exam permissions below.
15.12.2010: The 9th exercise is the last compulsory exercise for BOTH Bachelor and Master students. The course will be worth 6 Credits then. Any Master students interested in an 8 Credit course, please contact us seperately. Diploma students: In order to get a "Übungsschein" ALL further exercises are compulsory.
06.12.2010: Due to delayed exercise announcement we decided to shorten the current sheet. Two exercises have been shifted to next weeks sheet.
28.10.2010: The lecture on Tuesday, 02. Nov., will begin 15 minutes later because of the Fachschaftvollversammlung.
20.10.2010: Due to some requests: The registration for the compiler construction exam can be found here.
17.09.2010: page set up

Type

Day

Time

Place

Start

Lecturer

V3/4

Tue

14:00-15:30

AH 2

Oct 19

Noll

Thu

13:30-15:00

AH 1

Oct 14

Noll

Ü2

Wed

10:00-11:30

AH 2

Oct 20

Jansen

The goal of this course is to introduce foundational methods and techniques for implementing compilers for high-level (procedural) programming languages. The following topics 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)

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)

Lecture

Date

BSc/MSc/Diplom

Subject

Slides

Handout

Thu Oct 14

B/M/D

Introduction

Tue Oct 19

B/M/D

Lexical Analysis I

(Introduction)

Thu Oct 21

B/M/D

Lexical Analysis II

(The Matching Problem)

Tue Oct 26

B/M/D

Lexical Analysis III

(First-Longest-Match Analysis)

Thu Oct 28

B/M/D

Lexical Analysis IV

(Practical Aspects)

Tue Nov 2

at 14:15

B/M/D

Syntactic Analysis I

(Introduction)

Thu Nov 4

B/M/D

Syntactic Analysis II

(Top-Down Parsing)

Tue Nov 9

B/M/D

Syntactic Analysis III

(LL(k) Grammars)

Thu Nov 11

B/M/D

Syntactic Analysis IV

(LL(1) Parsing)

Tue Nov 16

B/M/D

Syntactic Analysis V

(LR(k) Grammars)

Thu Nov 18

B/M/D

Syntactic Analysis VI

(LR(0) Parsing)

Tue Nov 23

B/M/D

Syntactic Analysis VII

(SLR(1) Parsing)

Thu Nov 25

B/M/D

Syntactic Analysis VIII

(LR(1) Parsing)

Tue Nov 30

B/M/D

Syntactic Analysis IX

(Practical Issues)

Thu Dec 2

B/M/D

Semantic Analysis I

(Attribute Grammars)

Tue Dec 7

B/M/D

Semantic Analysis II

(Circularity of Attribute Grammars)

Thu Dec 9

B/M/D

Semantic Analysis III

(Circularity Test & Attribute Evaluation)

Tue Dec 14

B/M/D

Semantic Analysis IV

(L-Attributed Grammars)/

Code Generation I (Introduction)

Thu Dec 16

B/M/D

Code Generation II

(Intermediate Code)

Tue Dec 21

B/M/D

Code Generation III

(Translation to Intermediate Code)

Tue Jan 11

Error Handling in Top-Down Parsing &

Strongly Noncircular Attribute Grammars

Thu Jan 13

Evaluation of Strongly Noncircular Attribute Grammars

Tue Jan 18

Code Generation IV

(Implementation of Static Data Structures)

Thu Jan 20

Code Generation V

(Implementation of Dynamic Data Structures)

Tue Jan 25

Generation of Machine Code

Thu Jan 27

Code Optimization

Tue Feb 1, 14:00-16:00

B/M/D

1st Exam

Wed Mar 23, 14:00-16:00

B/M/D

2nd Exam

Exercise sheets will be made available on Wednesdays. The deadline for handing in your solution is on Wednesdays, before the exercise class begins.

Exercise 0 (due Wed., 20.10.2010)
Exercise 1 (due Wed., 27.10.2010)
Exercise 2 (due Wed., 03.11.2010) updated!
Exercise 3 (due Wed., 10.11.2010)
Exercise 4 (due Wed., 17.11.2010) updated!
Exercise 5 (due Wed., 24.11.2010) (Correction 5.4b)
Exercise 6 (due Wed., 01.12.2010)
Exercise 7 (due Wed., 08.12.2010) shortened!
Exercise 8 (due Wed., 15.12.2010)
Exercise 9 (due Wed., 22.12.2010)
Exercise 10 (due Wed., 19.01.2011)
Exercise 11 (due Wed., 26.01.2011)

Klausurzulassung (Bachelor/Master 6 Credits!)

See www.infostudium.de for a discussion forum for computer science students at RWTH.

First Exam: Results 6 Credits
First Exam: Results 8 Credits
Second Exam: Results 6 Credits
Solution: 6 + 8 Credit Exam (01.02.2011)

The course will entirely be 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.

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.

General:
- Wikipedia: Compiler [in German]
- The Catalog of Compiler Construction Tools
Lexical Analysis:
- flex: The Fast Lexical Analyzer
Syntactic Analysis:
- Wikipedia: LL parser
- Wikipedia: LR parser
- Andreas Kunert: LR(k)-Analyse für Pragmatiker [in German]
- Bison: The GNU parser generator
- Wikipedia: Comparison of [scanner and] parser generators

BSc/MSc/Diploma Topics
Teaching WS 2012/13
Hybrid Systems Group

We are looking for a HiWi for the Compiler Construction course. If you are interested, please contact Thomas Noll.

Joost-Pieter Katoen has been appointed as a member of the renowned Academia Europaea (Academy of Europe), a European, non-governmental association acting as an Academy whose members are scientists and scholars who collectively aim to promote learning, education and research.

Vacancies for postdoctoral researchers in "Automated Analysis of Probabilistic Programs". Application deadline: August 15, 2013.

Joost-Pieter Katoen has been awarded a Distinguished Professorship from the RWTH Aachen University.

The Hybrid Systems: Computation and Control (HSCC'13) conference in Philadelphia has been very successful: Hongfei Fu received the best student paper award for his paper "Approximating acceptance probabilities of CTMC-paths on multi-clock deterministic timed automata". Besides, the paper by Ilya Tkachev, Alexandru Mereacre, Alessandro Abate and Joost-Pieter Katoen was ranked second in the overall best paper award selection.

Joost-Pieter Katoen has been elected as Steering Committee Chair of ETAPS (www.etaps.org), the largest conference on theory and practice of software in Europe. He is the first non-UK ETAPS SC chair since the conference was initiated in 1998. More information here.

The Alumni-Magazine of RWTH Aachen University contains an interview with our former PhD student and postdoctoral researcher, Dr. Tingting Han.

HiWi's wanted to work in a new European Space Agency project for enhancing state-of-the-art design and analysis tools (COMPASS) for the next generation European rockets. Need programming and model checking affinity. See here for details and contact.

We offer openings for several PhD candidates in the area of
"Model-Based Design and Analysis for Dependable Software Systems". Deadline for application: September 14, 2012. For further information click here.

The Theory of Hybrid Systems Group offers two jobs as student assistants within the CEBug project. For more information, look here.

Dino Distefano received the prestigious Roger Needham Award for his work on software verification. This award is for a distinguished research contribution in computer science by a UK based researcher who has completed up to 10 years of post-doctoral research. Dr. Distefano was the first PhD student supervised by Joost-Pieter Katoen.

Marijn Jongerden received the German MMB (Messung, Modellierung und Bewertung von Rechensystemen) Award 2012 of the GI/ITG-Committee for Measurement, Modelling and Evaluation of Computing Systems for his PhD-thesis on "Model-based energy analysis of battery powered systems". His work was supervised by Boudewijn Haverkort (Twente) and Joost-Pieter Katoen.

Our paper "Formal Correctness, Safety, Dependability and Performance Analysis of a Satellite" has been accepted to ICSE 2012 in the track SE in Practice (18% acceptance rate). The paper treats a new satellite from the European Space Agency that was modeled and analyzed with modern tools during the actual satellite design.

Joost-Pieter Katoen will act as DJ in the "Nacht der Professoren" in the Apollo bar and cinema.