bild
School of
Computer Science
and Communication

Kompilatorkonstruktion / Compiler Construction, 9hp

The course will be given period 3-4 2014. It gives 9hp, and it requires a considerable effort from students.

About this course

The teaching language will be (broken) English if at least one student does not understand Swedish. Since several foreign guests have been admitted this year, it seems likely that not all of them have a good command of Swedish.

The course starts 2014-01-23 at 13 in D2 and will then have a lecture each following 4 Thursdays in period 3. The schedule at http://www.kth.se/schemavt14/ is now correct for the first half of the term.

Compiler Construction is now a normal course, with 8 lectures. We also plan seminars where students will discuss their projects in groups divided based on progress. There will also be lab sessions, at the start of the project.

The main activity on this course is a compiler writing project. We use Andrew Appel's book "Modern Compiler Implementation in Java", 2nd edition, and follow his MiniJava project (with some minor modifications). Since the programming project is quite large, students are encouraged to work in groups of two.

Course material

Lectures

The notes links for future lectures are dead. They will become live gradually. Note that the lectures notes are not adequate as a replacement for the course book, since we will not cover all relevant theoretical material in just 8 lectures.
  1. Course introduction. Overview of compiler passes and their function. Project overview. Chapter 1 (or in some sense chapter 1-12) in Appel. Notes
  2. Lexical analysis, grammars, [formal]language classes of FSMs and grammars, ambiguous grammars, disambiguating grammars, parse trees, (modified) Minijava grammar. Chapter 2 and chapter 3 up to page 45 in Appel. Notes
  3. Parsing techniques and their power wrt grammar classes; LL and LR parsing, predictive parsing. Grammar rewriting. Parser generators. Abstract syntax. Chapter 3 pg 45-76 in Appel. Notes
  4. Symbol table, type checking, activation records. Notes
  5. Intermediate Representation tree (IR). Translation from syntax tree to intermediate code. Notes
  6. More on activation records and ABI. Assembly code. Instruction selection (1). Notes
  7. Instruction selection (2). Control- and data-flow analysis. Register allocation + spilling. Notes
  8. Introduction to optimisation: algebraic rewrites, dead code elimination, common subexpression elimination, instruction scheduling, strength reduction, value propagation, etc. Notes
Copyright © Published by: Per Austrin <austrin@csc.kth.se>
Updated 2014-05-22