Compiler Construction

Lecture: Monday 12.15-14.00, room 5.
Exercise: Wednesday 12.15-14.00, room 5.


You need to be able to program in C or C++.


  1. 5 oct. Introduction, Organization Issues. Some history of high-level programming language. Example: Pocket calculator. Some remarks about tokenizing. Slides .
  2. 12oct. Tokenizing. Non-deterministic finite automata and regular expressions. A token consists of a tag and an attribute. How to write a tokenizer by hand using NDFAs. Regular Expressions. Transformation from regular expressions to NDFA. Slides .
  3. 19oct. Transforming an NDFA into a DFA. Minimalization of DFA. Demonstration of LEX.
  4. 26oct. Introduction to Parsing. Context-Free Grammars, Derivations, Context-Free Grammars with Attributes. Slides .

    2 nov. No lecture, because of holiday.

  5. 9 nov. Shift-Reduce parsing. Construction of the prefix automaton.

    16 nov. No lecture, because of holiday (swieto uniwersytetu).

  6. 23 nov. Computation of look ahead sets. Description of parsing algorithm. Usage of Maphoon. Slides on LALR parsing .
  7. 30 nov. How to write a parser by hand. Recursive descent parsing.
  8. 7 dec. Translation of C++/C.
  9. 14 dec. Translation of C++/C.
  10. 21 dec. Translation of C++/C. This is a short document that sketches how to compile C++/C.
  11. 4 jan. Optimization. Elimination of redundant expressions, SSA. These are the slides.
  12. 13 jan. Optimization. (Constant propagation.) We were visited by local television. This is the link.
  13. 18 jan. Elimination of Phi-functions from the SSA, register assignment, code generation through tree matching. Here are the slides.


Point Calculations

This is how the points are calculated.

Final Project

This is the recommended final project. It should be completed by February 26. Send me mail if you have completed the project, and want to present it to me. If you still have exercises to show, you can show them together with the final project.

Suggested Literature

(more to the front is more recommended.)