Compiler Construction

News

  • 11.12.2018: We made minor adaptions to the attribute grammar in task 1 of exercise sheet 9 to conform to the definition of attribute grammars. We updated the sheet.
  • 28.11.2018: We clarified task 2 of exercise sheet 7. We updated the sheet.
  • 16.11.2018: The condition n>1 was missing in task 2 of exercise sheet 5. We updated the sheet.
  • 22.10.2018: Questions concerning the lectures or exercises can be posted in the L2P forum or mailed to cb2018 at i2.informatik.rwth-aachen.de
  • 09.07.2018: we are online!

Schedule

Type Day Time Hall Start Lecturer
Lecture Mon 12:30 – 14:00 AH 6 8 Oct Noll
  Thu 12:30 – 14:00 AH 5 11 Oct Noll
Exercise Mon 15:15 – 16:45 AH 5 15 Oct Berger, 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 Ex. Pract. ex.  
1 8 Oct Introduction l1 l1 ex0    
2 11 Oct Lexical Analysis I (Simple Matching Problem) l2 l2 ex1 prog1
code		  
3 18 Oct Lexical Analysis II (Extended Matching Problem) l3 l3      
4 22 Oct Lexical Analysis III (Practical Aspects) l4 l4 ex2 prog2
code		  
5 25 Oct Syntax Analysis I (Introduction) l5 l5      
6 29 Oct Syntax Analysis II (LL(k) Grammars) l6 l6 ex3    
7 5 Nov Syntax Analysis III (LL(1) Parsing) l7 l7 ex4    
8 8 Nov Syntax Analysis IV (LL(1) and Bottom-Up Parsing) l8 l8      
9 12 Nov Syntax Analysis V (LR(k) Grammars and LR(0) Parsing) l9 l9 ex5 prog3
code		  
10 15 Nov Syntax Analysis VI (SLR(1) and LR(1) Parsing) l10 l10      
11 19 Nov Syntax Analysis VII (Practical Issues) l11 l11 ex6    
12 22 Nov Semantic Analysis I (Attribute Grammars) l12 l12      
13 26 Nov Semantic Analysis II (Circularity Check) l13 l13 ex7 prog4
code		  
14 29 Nov Semantic Analysis III (Attribute Evaluation) l14 l14      
15 3 Dec Code Generation I (Intermediate Code) l15 l15 ex8    
A 10 Dec Ivaylo Bonev (itestra GmbH): Programming Language Concepts it1 – ex9 prog5
code		  
16 13 Dec Code Generation II (The Translation) l16 l16      
B 17 Dec Roland Hildebrandt (itestra GmbH): Program Analysis and Transformation it2 – ex10 prog6
code		  
17 20 Dec Code Generation III (Short-Circuit Evaluation & Static Data Structures) l17 l17      
18 7 Jan Code Generation IV (Implementation of Dynamic Data Structures) l18 l18 ex11    
19 10 Jan Code Generation V (Compiler Backend) l19 l19      
20 31 Jan Question & Answers Session – –      

Exam

  • First exam: 21.02.2019, 10:00 – 12:00
    • Matriculation number < 351000 → AH IV
    • Matriculation number > 351000 → Aula 2
  • Review: 01.03.2019, 13:00 – 15:00, 5056
  • Second exam: 25.03.2019, 10:00 – 12:00
    • Matriculation number < 356000 → AH V
    • Matriculation number > 356000 → AH IV
  • Review: 29.03.2019, 12:00 – 14:00, B-IT room 5053.2b

Evaluation results

Further information

  • The lectures and exercise classes will be given in German. The slides and other course material will be in English. There are no lecture notes; the course material will consist of slides.

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