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.
Deadline for delivery into my mailbox on the ground floor is
tuesday morning, 8.15. This deadline is sharp.
This is the exam.
Introduction, Organizational Issues. Planned Topic.
History of high-level programming languages.
Tokenizing. What must be in a token?
Regular Expressions, Non-Deterministic Finite Automata.
Deterministic Finite Automata.
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.
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.
LALR parsing, definition of item set, construction of the prefix
automaton, computation of lookahead sets.
(Tuesday by rector's decision).
On this day, a graded exercise is due, which I will publish on the
In the lecture, we studied type checking,
and resolution of polymorphic types.
These are the slides.
We had the first lab exercise.
In the lecture, I covered the recursive definition of
C-types, and field functions.
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.
We do a few more expressions with outline functions,
and with arrays and structs. I explain compilation
of box functions.
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.
Elimination of phi-functions. Merging of variables, register assignment,
These are the slides.
You need the parser generator Maphoon,
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.
You need an implementation of abstract syntax trees,
which is in
Nr8 . We finish the type checking
algorithm. This is the typechecking
error thrown by typecheck( ).
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
which now compiles on all computers in room 7.
The updated exercise is here .
I think that the new exercise is reasonable.
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.
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
90 => 3.0
110 => 3.5
130 => 4.0
150 => 4.5
170 => 5.0
Deadline is 03 feb. (Start of the next semester).
(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.
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.)