Compiler and Language-Processing Tools


Exam: The oral exams will be held on February 19./20. and March 28. Please register with the examination office and our secretary Mrs Stengel for a time slot.

Lecture: Tuesday, 11:45 - 13:15, Room 48-453; Wednesday 11:45 - 13:15, Room 42-105

In addition to the lecture there will be practical exercises. In the practical exercises, the topics of the lecture are put into a practical perspective by constructing a compiler from scratch. The practical exercises will not influence the final grade, however they are mandatory to be admitted to the final examination.

Exercise session: alternating with the lecture, see time table below

Additional support session: Friday, 15:30-16:30, Room 32-411-PC (starting on November 16)

The first practical exercise sheet will be given out during the first lecture and the last exercise sheet during the last lecture. Therefore you should plan to spend 2 more weeks after the last lecture for completing the last exercise sheet.

As this is a 8CP lecture, you should plan to spend around 240 hours on the lecture and the practical exercises. If you do not have much experience with implementing bigger projects in Java, you should plan to spend more time on the practical exercises. If you lack some of the theoretical prerequisites (definition of formal languages, regular expressions, context-free grammars, finite-state machines, pushdown automata), you should also incorporate this into your planning.

The lecture will be held in English.

Topics of the Lecture

  • Syntax specification of programming and formal languages
  • Lexical analysis: scanning, scanner generation, application of scanner generators
  • Context free analyses: parsing, parser generation, application of parser generators
  • Design and use of abstract syntax
  • Context sensitive analysis: name analysis, type analysis, attribution techniques and tools
  • Processing of XML documents
  • Compilation techniques for procedural and object-oriented languages
  • Intermediate languages for compilation
  • Semantical aspects and optimization techniques
  • Instruction selection
  • Register assignment
  • Code generation
  • Automatic memory management and garbage collection


  • Good programming knowledge in Java (or similar language)


Time Table

Week Tue, 11:45 - 13:15 Wed, 11:45 - 13:15
23.10. + 24.10. Organizational issues + Introduction Lexical analysis
30.10. + 31.10. Parser I: Introduction Exercise
06.11. + 07.11. Parser II: Bottom-up Exercise
13.11. + 14.11. Parser III: Top-down Name + Type analysis I
20.11. + 21.11. Exercise Name + Type analysis II
27.11. + 28.11. Intermediate representation: LLVM Intermediate representation: Imperative
04.12. + 05.12. Exercise SSA I
11.12. + 12.12. SSA II Data flow optimizations
18.12. + 19.12. Exercise Data flow optimizations: Loop optimizations
08.01. + 09.01. Intermediate representation: Objects Stack frames / MIPS
15.01. + 16.01. Exercise Register allocation I
22.01. + 23.01. Register allocation II Garbage Collection I
29.01. + 30.01. Garbage Collection II Exercise
05.02. + 06.02. Topic of choice Conclusion

This plan is only preliminary and is likely to change during the semester.

Lecture material

Chapter Lecture notes Comments
01 Introduction Slides
02 Lexical analysis Slides Script
03 Parser Slides 1 Slides 2 Slides 3 Script
04 Name and type analysis Slides Script
05 Intermediate representation Slides Slides 2 (OOP) Script
06 Static single assignment form Slides Script [06.12.] There was a typo in the definition of Dominance Frontier, check the script for the example!
07 Optimizations Script Slides 1 Slides 2
08 Stack frames Slides Script
09 MIPS / Register allocation Slides [08.02] Simplified example for MIPS, corrected reg alloc example
Script: MIPS
Script: Register allocation
10 Garbage collection Handout
11 Compiling Functional Languages Slides
12 Conclusion Slides

Exercise material

Sheet Deadline Material Comments
ex1.pdf 07.11.2018 On October 31 there will be an introduction to the tools needed for this sheet
theory1.pdf - hints/solutions In-class exercise on bottom up parsers for October 31
ex2.pdf 20.11.2018
theory2.pdf - hints/solutions In-class exercise on regular expressions for November 7
ex3.pdf 04.12.2018
ex4.pdf 07.01.2019
theory3.pdf - In-class exercise on bottom up parsers for December 18
ex5.pdf 22.01.2019
ex6.pdf 08.02.2019
theory4.pdf - In-class exercise on bottom up parsers for January 30