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

  1. 03.10.2013. Introduction, Organizational Issues. Planned Topic. History of high-level programming languages. Slides. (Exercises are below.)
  2. 10.10.2013. Tokenizing. Regular Expressions, Non-Deterministic Finite Automata. Deterministic Finite Automata. Minimalization of Deterministic Finite Automata. Slides .
  3. 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.
  4. 24.10.2013. Attribute Grammars. Examples of value calculation. Stack machine. Assigning Priorities to Operators. Start of Top-Down Parsing. Slides (They were revised.)
  5. 07.11.2013. Rest of Top-Down parsing. Start of Bottom-Up Parsing. Slides .
  6. 14.11.2013. Bottom-Up parsing. Itemsets. Computation of the prefix automaton. Computation of look ahead sets. Demonstration of parser generation tool.
  7. 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.
  8. 28.11.2013. Type checking, and intermediate code generation.
  9. 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++.
  10. 12.12.2013. More about intermediate code generation.
  11. 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.
  12. 09.01.2014. Possible types of optimization. Elimination of Redundant Expressions.
  13. 16.01.2014. Data Flow Analysis/Symbolic Evaluation. Application of data flow analysis to alias analysis. Slides.
  14. 23.01.2014. More about pointer analysis. SSA normal form.
  15. 30.01.2014. Machine code generation.

Exercises

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