Compiler Construction

Prerequisites

Schedule

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.

Exercises

• Task for 14 october about tokenizing. tokenizer.h , tokenizer.cpp , a Makefile , and the task list .
• Task list for 21 october about automata and regular expressions. List .
• Exercise nr3. . In order to do it, you need the flex system. You can download it here . After downloading, type:
  1. gunzip flex-2.5.35.tar.gz
  2. tar -xf flex-2.5.35.tar
  3. cd flex-2.5.35
  4. ./configure
  5. make
  The file INSTALL contains more detailed instructions, if you like to study such things. The manual of FLEX is here . This is the project that I showed in class. If the Makefile doesn't work, you probably have to adjust the path to flex in it. The current Makefile uses g++, you can change that to gcc if you like.
• Exercise nr4 .
• Exercise nr5 . (Ignore the tasks about look ahead sets for the moment. These will be covered in more detail on 23 nov)
• Exercise nr6 . It is now the final version. Maphoon and Calculator . Updated 26nov, 13.15. You will see an error 'ill-terminated character constant in line 82 of inputstream'. Simply delete the comment in line 82. If the C++ compiler complains about the exit statement, then add #include "stdio.h" to the beginning of file calculator.m This is the current bug list of Maphoon:
  1. Unproper treatment of comments in semantic actions. Maphoon looks for return statements inside comments. Quoted strings are OK.
  2. Some compilers need to include cstdlib for exit( );
  3. It seems that tokens originating from the tokenizer are not checked for being wellformed.
  4. Word FACULTY should be replaced by FACTORIAL in the example calculator.
  5. Maphoon quietely accept meaningless options like %constaint
  This is Maphoon2008b, with all the bugs fixed.
• The 7th exercise that you all have been waiting for.
• Exercise 8 about compilation of C++. I changed my mind about how the functions in the translation should be called, so instead of the function names in the exercise, it is better to use the names that are used here .
• Exercise 9 about stack machines.
• Exercise 10 about SSA and redundancy.

Point Calculations

Final Project

Suggested Literature

• Compilers: Principles, Techniques and Tools. Alfred A. Aho, Ravi Sethi, Jeffrey D. Ullman.
• Engineering a Compiler, Keith Cooper and Lind Torczon, Morgan Kaufmann Publishers.
• Compiler Design, Reinhard Wilhelm, Dieter Maurer, Addison-Wesley Publishing Company.
• The compiler design Handbook. (Optimizations and Machine Code Generation), Edited by Y.N. Srikant and Priti Shankar. CRC press.