Compiler Construction

Lecture: Tuesday 08.15-10.00, room 139.
Exercise: Tuesday 10.15-12.00, room 140.
Note that in System Zapisow, the times are different. The times on this page are the correct times.

Midway Exam

Deadline for delivery into my mailbox on the ground floor is tuesday morning, 8.15. This deadline is sharp. This is the exam.

Schedule

27.09.2011. Introduction, Organizational Issues. Planned Topic. History of high-level programming languages. Slides .
04.10.2011. Tokenizing. What must be in a token? Regular Expressions, Non-Deterministic Finite Automata. Deterministic Finite Automata. Slides .
11.10.2011. Example of complete transformation from a regular expression into a DFA. How to obtain the minimal DFA from a given DFA. How to do the transformation from regular expressions to DFA in the case of large character sets. (Unicode). How to do the attribute calculation by hand.
18.10.2011. Demonstration of Flex . Grammars, attribute grammars and parsing .
25.10.2011. Bottom Up parsing, usage of attributes. We messed up, and still do not understand, how to automatically generate a grammar from a description of operator priorities. The transformation in the slides (of 18.10.2011) is still incorrect.
08.11.2011. LALR parsing, definition of item set, construction of the prefix automaton, computation of lookahead sets. Slides .
16.11.2011. (Tuesday by rector's decision).
22.11.2011. On this day, a graded exercise is due, which I will publish on the course homepage. In the lecture, we studied type checking, and resolution of polymorphic types. These are the slides.
29.11.2011. We had the first lab exercise. In the lecture, I covered the recursive definition of C-types, and field functions.
06.12.2011. I gave an algorithm for the translation of C/C++-expressions, which I believe is more or less complete. These are the slides.
13.12.2011. We tried the compilation algorithm on the statements. a = b + c; and a = b + 1. We had troubles with a = fact(b), but I believe that this is repaired in the new and (hopefully) final version of the slides. I think that the slides now describe a complete algorithm for the compilation of C/C++. These are the updated slides.
20.12.2011. We do a few more expressions with outline functions, and with arrays and structs. I explain compilation of box functions.
03.01.2012. I explained how to do exercise 9.
10.01.2012. Example of automatically generated code and possibilities of optimization. Removal of recomputed expressions. The SSA normal form. Difficulties with analyzing memory locations. Here are the slides.
17.01.2012. Elimination of phi-functions. Merging of variables, register assignment, instruction selection. These are the slides.

Exercises

04.10.2011. Nr1 .
11.10.2011. Nr2 .
18.10.2011. Nr3 .
25.10.2011. Nr4 .
08.11.2011. Nr5 .
29.11.2011. Nr6 . You need the parser generator Maphoon, and the Example Calculator . It seems that I forgot to include calculator.cpp in the calculator. Also, you must add '#include <stdio.h>' in the first line of 'reader.h' on some compilers.
06.12.2011. Nr7 . You need an implementation of abstract syntax trees, which is in intermediate2011 .
20.12.2011. Nr8 . We finish the type checking algorithm. This is the typechecking error thrown by typecheck( ).
03.01.2012. We make another attempt to implement the type checking algorithm. The first exercise 9 that I handed out in the morning, was undoable. For those that didn't come to the lecture, we made some parts of the initial exercise in class, it is all included in the updated file intermediate2011, which now compiles on all computers in room 7. The updated exercise is here . I think that the new exercise is reasonable.
10.01.2012. We connect the result of the previous exercise to a parser, this is the exercise. Here is another version of intermediate2011 to download, hopefully the last one. Be careful not to overwrite earlier work when you unpack it.

Grading

The exam has a weight of 100 points. Each of the exercises 6,7,8,9,10 has a weight of 20 points. This gives a total number of points in the course of 200. Since the course was fairly hard, I will set fairly low borders:
90 => 3.0
110 => 3.5
130 => 4.0
150 => 4.5
170 => 5.0

Deadline is 03 feb. (Start of the next semester).

Recommended Literature

(more to the front means more recommended.)

Principles of Compiler Design. Alfred A. Aho, Jeffrey D. Ullman, Addison-Wesley Publishing Company, 1977. (The book with the dragon. Old but still good on syntactic analysis.)
The compiler design Handbook. (Optimizations and Machine Code Generation), Edited by Y.N. Srikant and Priti Shankar. CRC press.
Engineering a Compiler, Keith Cooper and Lind Torczon, Morgan Kaufmann Publishers. (I do not recommend this book anymore. It has no real contents. It is clear that the authors understand nothing of formal methods.)