Compiler Construction I
|Dozent:||Dr. Michael Petter|
|Ort/Zeit:||Mo, 14:00-15:30 in MI 00.13.009A|
|Beschreibung: ||Introduction to Compilerconstruction - how to translate an imperative language.|
is managed via moodle.
- two groups: Monday 4-6 p.m. and Tuesday 2-4 p.m., both in room 02.07.014
- The Teleteaching Archives
- Slides 1: Introduction and recap of semantics of Regular Expressions and Finite Automata
- Slides 2: Berry-Sethi/Glushkov Algorithm
- Slides 3: Scanner Design, Context-Free Grammars and Pushdown Automata
- Slides 4: (redone) Item-Pushdown-Automata, First/Follow Computation and LL(1) Parsing
- Slides 5: Shift-Reduce-Parser, Canonical Automaton and LR(0) Parsing
- Slides 6: Canonical LR(1)-Automaton and LR(1) Parsing
- Slides 7: Attribute Grammars, Strong Acyclic Grammar Test
- Slides 8: Evaluation of Attribute Systems, L-Attributation, Symboltables for Def/Use Analysis
- Slides 9: Special Cases in Binding Identifiers, Typechecking with Type Systems, Extension to Structural Type Equality
- Slides 10: Subtyping, Code generation for expressions and basic statements
- Slides 11: Switch statements, functions, memory management and compiling whole programs
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:
- Outline of compiler construction
- Lexikal analysis:
From regular expressions to NFAs
Scannerdesign with NFAs
- Syntactical analysis
Contextfree languages & pushdown automata
Item-Pushdownautomata & Recursive Descent Parsing
Shift-Reduce Parsing & LR(1) Parser
- Semantical analysis
Code generation schemes
Finally we may find time for less standard techniques for compilers, as e.g. the type inference of programs.
- Attention: There will be only one exam at the end of the semester, and no repetition exam in the winter!
- You are allowed to bring a DIN A4 sheet of paper with notes on both sides.
- 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.
- We will provide two printouts of the lecture slides in case there is some information you forgot to add to your A4 sheet. We will also provide some copies of the RCMa specification document.
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 instructions and the code generation schemes are summarized in the R-CMa specification.