Compiler and Language-Processing Tools

Organization

Exam dates: September 1+4, 2017; October 4-6, 2017

  • Please register for one of these dates with our secretary Mrs Stengel.

Lecture: Monday, 10:00 - 11:30, Room 48-453, Wednesday 10:00 - 11:30, 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: Tuesday 13:45, Room 32-411

Additional support session: Friday 10:00, Room 57-165 (Please bring your own notebooks!)

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

Prerequisites:

  • Good programming knowledge in Java (or similar language)

Instructors

Time Table

Week Mo, 10:00 - 11:30 Wed, 10:00 - 11:30
19.04. — (Easter) Organizational issues + Introduction
24.04. + 26.04. Lexical analysis Parser I: Introduction
03.05. — (Tag der Arbeit) Parser II: Top-down
08.05. + 10.05. Parser III: Buttom-up Name + Type analysis I
15.05. + 17.05. Name + Type analysis II Intermediate representation I: Imperative
22.05. + 24.05. Intermediate representation II: Objects SSA I
29.05. SSA II
— (Whitmonday) — (canceled)
12.06. + 14.06. Data flow optimizations: Monotone Framework Data flow optimizations: Loop optimization
21.06. MIPS / Stack frames
26.06. + 28.06. Register allocation I Register allocation II
03.07. + 05.07. Garbage Collection I Garbage Collection II
10.07. JIT
17.07. JastAdd + Attribute Grammars

This plan is not fixed and can change during the remainder of the semester.

Lecture material

Chapter Lecture notes Comments
01 Introduction Slides
02 Lexical analysis Script
03 Parser Script
Slides 1
Slides 2
04 Name and type analysis Script
Slides
05 Intermediate representation Script
Slides
06 Static single assignment form Script
Slides
07 Optimizations Script
Slides 1
Slides 2
08 Stack frames Script
Slides
09 MIPS Script
10 Register allocation Script
Slides

Exercise material

Sheet Deadline Points Template/Additional material Example Solution Comments
ex1.pdf 03.05.2017 10 ex1_template.zip ex1_solution.zip slides
ex2.pdf 15.05.2017 10 ex2_template.zip
ex3.pdf 29.05.2017 18 ex3_tests.zip ex3_template.zip
ex4.pdf 19.06.2017 (extended) 15 ex4_material.zip ex4_template.zip translation2.pdf updated deadline and instructions for Windows
ex5.pdf 03.07.2017 15 slides
ex6.pdf 17.07.2017 15