Compiler Construction

Contents

A Compiler is an essential part of the system software stack. Its job consists in translating programs from a high-level programming language like C or Java into a sequence of machine instructions of an actual processor. Compilers are comparatively complex programs. Their construction involves ideas and approaches from many different areas of computer science. The first two phases, i.e. lexical and syntactical analysis of the input program, are a major application for formal methods. Later on, e.g. during code generation, we treat methods for register allocation via approximative graph colouring.
The lecture is divided into the following topics:

1. Outline of compiler construction
2. Lexikal analysis:
   From regular expressions to NFAs
   Scannerdesign with NFAs
3. Syntactical analysis
   Contextfree languages & pushdown automata
   Item-Pushdownautomata & Recursive Descent Parsing
   Shift-Reduce Parsing & LR(1) Parser
4. Semantical analysis
   Attributevaluation
   Typechecking
5. Codegeneration
   Registerallocation
   Code generation schemes
6. Optimizations

Finally we may find time for less standard techniques for compilers, as e.g. the type inference of programs.

Slides (will be updated during the semester)
Slides long version

Mini Seminar Topics

1. (Mo) Introduction to Parser Combinators - F.S.
2. (Mo) Parsing Expression Grammars and Packrat Parsers - M.T.
3. (We) LALR(k) - M.Z.
4. (Mo) Pager's LR(k) - S.K.
5. (Mo) GLR/Tomita Parser - M.Zi.
6. (We) Follow-Automata - A.M.
7. (Mo) Antimirov-Automata - M.G.
8. (Mo) LL(*) and LL-regular Grammars L.O.
9. (We) Semidicision Procedures for Ambiguous Grammars - L.T.
10. (We) Island Grammars - C.C.
11. (Mo) General First_k and Follow_k Computation with Constraint Solvers - A.B.
12. (We) Reference Attribute Grammars with JastAdd C. V. N.
13. (We) Extensible Grammars with PPG - P.B.
14. (We) Language Processing with Kiama/Scala - Laura
15. (We) Earley Parser - P.K.
16. (We) LL(*) and LL-regular Grammars LL(*) and LL-regular Grammars A.M.

Information regarding the presentation of the seminar topics see Section Tutorial.

Recordings

You can find the recordings in the TTT archive.

Tutorial

Date: Mondays 14.15-15:45 and Wednesdays 8:30-10:00 starting from the second week (29.4.- 3.5.)
On July 22nd at 14:00h seminar topics 1-8 will be presented and on July 24th at 8:30h seminar topics 9-15 will be presented in the tutorials.
Please note that on Monday we start at 14:00h not at 14:15h as usually.

If you have questions or comments to the tutorial please contact Raphaela Palenta (raphaela.palenta<at>tum.de).

Exam FAQ

• You will be allowed to bring hand- and/or machine-written sheets or books to the exam.
• Questions may be answered in English or German.
• Attention: There will be only one exam at the end of the semester, and no repetition exam in the winter!
• In case you did not pass, you have the opportunity to take "Programming Languages" or "Program Optimization" next semester or alternatively repeat the exam next summer.

Literature

• Wilhelm, Seidl, Hack: Compiler Design: Syntactic and Semantic Analysis
  for TUM students, the German edition is downloadable for free through the TUM/LRZ-Proxy, the English edition is available in the form of several hardcopies in the library.