Compiler Construction

Introduction Video

Please make sure to check out the content of the moodle course for this event.

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. Lexical 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.

Prerequisites

Necessary:

• Basics of Programming in Java (IN0001 & IN0002)
• Introduction to Theory of Computation (IN0011)
• Fundamentals of Algorithms and Data Structures (IN0007)

Beneficial:

• Automata and Formal Languages (IN2041)
• Virtual Machines (IN2040)
• Introduction to Computer Architecture (IN0004)

Tutorial

The tutorial is given by Sarah Tilscher on Mondays 1-3 pm and Wednesdays 10-12 am in room 02.07.014.

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 via Institutional Login.