Compiler Construction

News

  • 07.09.16: The grades of the second exam are available in CAMPUS-Office. The exam inspection takes place on Wednesday, 14th September, at 15:00 in the seminar room of i2 (E1, room 4201b).
  • 05.09.16: The second exam takes place on Tuesday, 6th September, and starts at 10:00. You can find the room mapping below:
    Room Degree Programme
    AH II B.Sc.
    AH III M.Sc., CES
  • 31.07.16: The grades of the first exam are available in CAMPUS-Office. The exam inspection takes place on Monday, 1st August, at 16:00 in the seminar room of i2 (E1, room 4201b).
  • 25.07.16: The first exam takes place on Thursday, 28th July, and starts at 10:00. You can find the room mapping below:
    Room Degree Programme Matriculation Number
    AH I B.Sc. ≤ 334212
    AH II M.Sc. ≤ 323188
    AH VI B.Sc. ≥ 334280
    M.Sc. 323272-323868
    5056 M.Sc. ≥ 331758
    CES all
    SSE all
  • 19.07.16: We uploaded another exam from previous years.
  • 13.07.16: We offer a question time in the exercise slot next Tuesday. If you have questions, please mail them to us beforehand and we can prepare satisfying answers. We also uploaded an exam from previous years.
  • 11.07.16: In the implementation for exercise 8 the SLR(1) parser for the WHILE language has a problem with the rules expr → ( subexpr ) and guard → ( subguard ). Therefore you can ignore these rules for the generation of the Jasmin code.
  • 24.06.16: In the grammar GrammarLR0 of exercise sheet 6, the rules for % and / were not consistent with the implementation. We updated the exercise sheet with the correct rules A → / and B → %.
  • 23.06.16: In the implementation for exercise sheet 6 the analysis result of the parser should be returned as a list of rules of type Rule.java. Use the subclass LR0Item.java instead of Rule.java to get the same output as seen in exercises c) and e).

Schedule

Type Day Time Hall Start Lecturer
Lecture Tue 14:15 – 15:45 AH 6 19 April Noll
  Thu 14:15 – 15:45 AH 6 14 April Noll
Exercise Tue 12:15 – 13:45 AH 2 26 April Matheja/Volk

Contents

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

Prerequisites

Basic knowledge of the relevant undergraduate courses of the first two years 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

No. Date Subject Slides Handout Exercises Solutions
1 14 Apr Introduction l1 l1    
2 19 Apr Lexical Analysis I (Simple Matching Problem) l2 l2 e01 code s01 code
3 21 Apr Lexical Analysis II (Extended Matching Problem) l3 l3 e02 code s02 code
4 28 Apr Lexical Analysis III (Practical Aspects) l4 l4    
5  3 May Syntax Analysis I (Introduction) l5 l5    
6 10 May Syntax Analysis II (LL(k) Grammars) l6 l6 e03 s03
7 12 May Syntax Analysis III (LL(1) Parsing) l7 l7 e04 code s04 code
8 31 May Syntax Analysis IV (LR(k) Grammars) l8 l8    
9 2 Jun Syntax Analysis V (LR(0) and SLR(1) Parsing) l9 l9    
10 7 Jun Syntax Analysis VI (LR(1) and LALR(1) Parsing) l10 l10 e05 s05
11 9 Jun Syntax Analysis VII (Practical Issues) l11 l11    
12 14 Jun Semantic Analysis I (Attribute Grammars) l12  l12 e06 code s06 code
A 16 Jun Program Analysis and Transformation from a Practitioner’s Point of View [Jonathan Streit; itestra GmbH] – –    
B 21 Jun Language Concepts in Old and Recent Programming Languages [Stephan Herold; itestra GmbH] – –    
13 23 Jun Semantic Analysis II (Circularity Check) l13 l13 e07 code s07 code
14 30 Jun Semantic Analysis III (Attribute Evaluation) l14 l14    
15 5 Jul Code Generation I (Intermediate Code) l15 l15 e08 code s08 code
16 7 Jul Code Generation II (The Translation) l16 l16    
17 12 Jul Code Generation III (Implementation of Static Data Structures) l17 l17    
18 14 Jul Code Generation IV (Implementation of Dynamic Data Structures) l18 l18    
19 19 Jul Code Generation V (Compiler Backend) l19 l19    

Exam

  • Registration via this Campus page
  • First exam: Thursday, 28 July, 10:00-13:00, AH 1/2/6, 5056
  • Review of first exam: TBD
  • Second exam: Tuesday, 6 September, 10:00-13:00, AH 2/3
  • Review of second exam: TBD

Evaluation results

Further information

  • The course will be given partly in German and partly in English. 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.

Interesting Links