Speaker Dr. Michael Petter
Location bbb.in.tum.de/mic-k3y-d2e
Date Thu, 14:15-15:45
Module IN2227

Inverted Classroom

This lecture will be held in an inverted classroom. This means:

  1. You will obtain several short recordings of lesson units each week via moodle. These are meant to be prepared on your own, particularly prior to the next week's classroom slot
  2. The classroom slot will be populated by
    1. the students asking questions that arise during preparation
    2. the lecturer bringing a few selected examples to live practice and illustrate the concepts of the lesson recordings
  3. For the tutorial
    1. the tutor will provide an exercise sheet (via Moodle) a week in advance to give students an opportunity to practice on their own
    2. in the tutorial slot, the tutor will moderate the students exchanging solution ideas for these exercises

Remarks on this format:

  • Passively consuming the lesson recordings only usually makes it very hard to fully comprehend the concepts of the lecture. Active participation in tutorial and classroom are highly recommended.
  • Classroom and tutorial are interactive formats. These work best, if interaction is as fluent as possible. While we acknowledge the urge to type a question, this is not a particularly fluent way of communication. Please use a decent microphone to ask your question.

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)
  • Introducion to Theory of Computation (IN0011)
  • Algorithms and Data Structures (IN0007)

Beneficial:

  • Automata and Formal Languages (IN2041)
  • Virtual Machnies (IN2040)
  • Computer Organization and Technology (IN0004 & IN0005)

Tutorial

The tutorial is given by Michael Schwarz at https://bbb.rbg.tum.de/mic-t1l-zle-jaj
All information on the tutorial is on Moodle.

Exam FAQ

  • We aim for a written exam in physical presence, if legislation and pandemic situation make this possible.
  • In a written exam for Compiler Construction, you are allowed to bring hand- and/or machine-written sheets or books to the exam.
  • Examination language is English.
  • 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.
  • The examination period is determined by the administration following the academic calendar

Literature