Compiler Construction
Today's lab will be in room 104!
Lecture: Thursday 10.15-12.00, room 105.
Laboratory: Wednesday 16.15-18.00 in room 104+137, and
Thursday 12.15-14.00 in room 104+137
The first 7 exercises will be theory exercises in room 104.
There will be no declaration system, because I think that this
is childish and should not be done at university. However,
if it turns out necessary, I can change my mind at any moment.
Also, there will be an exam halfway through the course.
Information on the exercises is
below. Recomended literature
is at the bottom of this page.
Schedule
-
03.10.2013.
Introduction, Organizational Issues. Planned Topic.
History of high-level programming languages.
Slides.
(Exercises are below.)
-
10.10.2013.
Tokenizing.
Regular Expressions, Non-Deterministic Finite Automata.
Deterministic Finite Automata. Minimalization of
Deterministic Finite Automata.
Slides .
-
17.10.2013.
Some final words about tokenizing. How to handle
large character sets. Usage of
FLEX.
Doing attribute calculation by hand.
Parsing: Attribute grammars.
Slides.
-
24.10.2013. Attribute Grammars. Examples of value calculation.
Stack machine. Assigning Priorities to Operators.
Start of Top-Down Parsing.
Slides (They were revised.)
-
07.11.2013.
Rest of Top-Down parsing. Start of Bottom-Up Parsing.
Slides .
-
14.11.2013.
Bottom-Up parsing. Itemsets. Computation of the prefix automaton.
Computation of look ahead sets. Demonstration of parser generation
tool.
-
21.11.2013.
Some final remarks about bottom-up parsing.
Computation of Lookahead sets from LR(1)-items.
Next topic will be type checking.
These are the slides.
-
28.11.2013.
Type checking, and intermediate code generation.
-
05.12.2013.
Intermediate code generation (slides).
After the course, I have rewritten the slides.
These are the new slides about
intermediate language and lowering for C/C++.
-
12.12.2013.
More about intermediate code generation.
-
19.12.2013.
Final remarks about intermediate code generation: Compilation of
*(p++) = *(q++); into intermediate code.
Expansion of box-operator into local variables.
Generation of Rvalues. Exception Handling.
-
09.01.2014. Possible types of optimization.
Elimination of Redundant Expressions.
-
16.01.2014. Data Flow Analysis/Symbolic Evaluation.
Application of data flow analysis to alias analysis.
Slides.
-
23.01.2014. More about pointer analysis. SSA normal form.
-
30.01.2014. Machine code generation.
Exercises
-
03.10.2013.
Nr1.
-
09.10.2013.
Nr2.
-
16.10.2013.
Nr3.
-
23.10.2013.
Nr4.
-
06.11.2013.
Nr5.
-
13.11.2013.
Nr6. It is a programming exercise
about top-down parsing, which will take place in room 137.
-
20.11.2013.
Nr7, a programming exercise
about bottom-up parsing.
You need Maphoon,
and example_calculator.tar.gz .
-
27.11.2013.
Nr8. You need
lisp.tar.gz, which contains a data structure
of Lisp-style lists.
This is
an explanation on Wikipedia of Lisp-style lists.
-
04.12.2013.
Nr9.
Adding a Lisp interpreter to the parser of Task list 8.
lisp.cpp shows how varstore is used.
-
18.12.2013.
Nr10.
Implementing the type checking algorithm of
typechecking.pdf.
-
19.01.2014.
Nr11.
This is the last task.
In task 4b, you may assume that 0 has type
reg(pointer(list)). There is no need to insert
conversions.
Grading and Passing Rules (2013-2014)
The following exercises contribute to your grade:
6,7,8,9,10,11.
Exercises 6,7,8,9 (about parsing and the Lisp interpreter)
each have a value of 10 points, so that the total amount in
this group is 40 points.
Exercises 10 and 11 (about type checking and compilation) each have
a value of 20 points, so that the total amount in this
group is also 40 points.
This means that there is a total weight of 80 points to obtain.
In order to pass, you need 30 points in the group 6,7,8,9, and
15 points in the group 10,11.
If you meet this condition, then points are mapped to the grade as follows:
50 => 3.0
56 => 3.5
62 => 4.0
68 => 4.5
74 => 5.0
Deadline is Feb 16. (End of the exam period).
Recommended Literature
-
Principles of Compiler Design.
Alfred V. 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.
-
Elements of Compiler Design.
Alexander Meduna,
Auerbach Publications, Taylor and Francis Group.
-
Advanced Compiler Design and Implementation
Steven S. Muchnick, Morgan Kaufmann Publishers, Inc.
1997.