Compiler Construction 2015

Lecture: Wednesday 14.15-16.00, room 141.
Laboratory: Wednesday 16.15-18.00 in room 104+137, and Thursday 10.15-12.00 (Kristian Baclawski) in room 104+137

This year's course will be based on LLVM. Recommended literature is at the bottom of this page.

Schedule

07.10.2015. Introduction, Organizational Issues. Planned Topics. History of high-level programming languages, and their compilation. Slides. (Exercises are below.)
14.10.2015. Basics of LLVM. Examples of translations from C++ into LLVM. Slides.
21.10.2015. More examples of translations from C++ into LLVM. Treatment of temporaries and class objects in expressions. Note that I updated the slides.
28.10.2015. Now that you what is the intermediate goal (LLVM), we will study how to obtain it. We start with the tokenizer. NDFAs, regular expresssions.
04.11.2015. More about tokenizing: Transformation from NDFA to DFA. Minimization of a DFA. During the lecture, I didn't like the minimization algorithm. I improved it.
18.11.2015. Top-Down Parsing. Slides (They were revised.)
25.11.2015. Rest of Top-Down parsing. Definitions of FIRST and FOLLOW. Start of Bottom-Up Parsing. Slides .
02.12.2015. computation of prefix automaton in Bottom-Up parsing.
09.12.2015. Computation of lookahead sets in bottom-up parsing. Various approaches: SLR/NQLALR/LALR. Type checking.
16.12.2015. Type checking/overload resolution/insertion of conversions. Important Note: The slides used during the lecture were incredibly buggy. Please use the improved (currently morning 14 jan) version: slides. Mail me if you still find bugs.
13.01.2016. More about type checking. Lowering to intermediate representation. Mail me if you find bugs in the slides.
20.01.2016. Probably still about lowering.
27.01.2016. Optimization through abstract interpretation.
?, we still need to catch up one lecture. Possible topic is transformation to and from SSA.

Exercises

14.10.2015. Nr01.
21.10.2015. Nr02.
28.10.2015. Nr03. This is not a programming exercise! Solutions will be published next week, after Mr. Baclawski's lab.
04.11.2015. Nr04. First part is again not a programming exercise. Second part uses Flex. It seems that you cannot download the sources from there, but flex is in the depository for Ubuntu and Debian. You can use this Makefile, and this file as starting point.
18.11.2015. Nr05. You need the file top_down.tar.gz.
25.11.2015. Nr06 about top-down vs. bottom-up parsing.
02.12.2015. Nr07, about bottom-up parsing. You need maphoon, and example_calculator.
16.12.2015. Nr08, about type checking, and insertion of conversions.
13.01.2016. Nr09. About intermediate code generation.

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 very 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.