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++.
Introduction, Organization Issues.
Some history of high-level programming language.
Example: Pocket calculator.
Some remarks about tokenizing.
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.
Transforming an NDFA into a DFA. Minimalization of DFA.
Demonstration of LEX.
Introduction to Parsing. Context-Free Grammars, Derivations,
Context-Free Grammars with Attributes.
2 nov. No lecture, because of holiday.
Shift-Reduce parsing. Construction of the prefix automaton.
16 nov. No lecture, because of holiday (swieto uniwersytetu).
23 nov. Computation of look ahead sets. Description of
parsing algorithm. Usage of Maphoon.
Slides on LALR parsing .
30 nov. How to write a parser by hand. Recursive descent parsing.
7 dec. Translation of C++/C.
14 dec. Translation of C++/C.
21 dec. Translation of C++/C.
This is a short document
that sketches how to compile C++/C.
4 jan. Optimization. Elimination of redundant expressions,
These are the slides.
13 jan. Optimization. (Constant propagation.)
We were visited by local television.
is the link.
18 jan. Elimination of Phi-functions from the SSA,
register assignment, code generation through tree matching.
Here are the slides.
Task for 14 october about tokenizing.
task list .
Task list for 21 october about automata and regular expressions.
Exercise nr3. .
In order to do it, you need the flex system.
You can download it
After downloading, type:
The file INSTALL contains more detailed instructions, if you like
to study such things.
The manual of FLEX is
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
tar -xf flex-2.5.35.tar
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:
This is Maphoon2008b, with all
the bugs fixed.
Unproper treatment of comments in semantic actions.
Maphoon looks for return statements inside comments.
Quoted strings are OK.
Some compilers need to include cstdlib for exit( );
It seems that tokens originating from the tokenizer are not
checked for being wellformed.
Word FACULTY should be replaced by FACTORIAL in the example
Maphoon quietely accept meaningless options like
The 7th exercise that you all
have been waiting for.
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 .
about stack machines.
Exercise 10 about
SSA and redundancy.
This is how the points are calculated.
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.
(more to the front is more recommended.)
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.