Compiler ConstructionCore Course
PeopleReinhard Wilhelm, Sebastian Hack, Roland Leißa, Clemens Hammacher, Christoph Mallon
The course treats compiler construction for imperative programming languages. This includes lexical, syntactical, and semantic analysis as well as static program analysis, optimization, and code generation. This course provides all necessary theoretical knowledge required to implement a compiler from scratch, which forms the practical part of the lecture.
All students are asked to register for the exams for the winter semester 2013. Exam registration is possible from now on until November 17th, 2013. A withdrawal is possible two weeks before the first exam at the latest. Most students can use the HISPOS. Students of economy computer science, erasmus students, junior students and to some extent students from other courses of studies must use other systems.
- Place: E2 2
- Exam: Monday, 2014-02-10, 10–12 (s.t.)
- Re-exam: Tuesday, 2014-02-25, 10–12 (s.t.)
- You must hand in and present your project
before2014-03-15. The presentation will take about half an hour. Make an appointment for the presentation at least three daysin advance with me.
- Final grades
Please register for the lecture on this page.
- Type: core lecture (9 credit points)
- Place: lecture hall I (HS 1), building E1 3
- Time: Mondays 14–16 (c.t.) and Wednesdays 12–14 (c.t.)
- First Meeting: Wednesday, 2013-10-16, 12–14 (c.t.)
- Place: lecture hall II (HS 2), building E1 3
- Time: Tuesdays 12–14 (c.t.)
- First Meeting: Tuesday, 2013-10-29, 12–14 (c.t.)
- Use the course's AskBot to communicate with the team and your fellow students.
- We use a GitLab to manage the course project.
- We run nightly tests on your project to provide you with feedback about your progress.
These services are only available from within the university network. You can use a VPN to connect to these services from other locations.
- The Structure of Compilers
- Lexical Analysis
- Pushdown Automata and Parser
- Recursive Equations over Grammars
- LL Parser
- LR Parser
- Attribute Grammars
- Attribute Dependencies
- Program Analysis
- Intra-procedural Data Flow Analysis
- Using SSA in Constant Propagation: Constant Propagation with Conditional Branches
- Cytron et al.'s dominance frontier technique: Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
- The libfirm approach to SSA construction: Simple and Efficient Construction of Static Single Assignment Form
- Slides for the latter: Simple and Efficient Construction of Static Single Assignment Form (Presentation slides)
- Global Value Numbering (GVN)
- Killdall's original paper: A Unified Approach to Global Program Optimization
- The AWZ approach: Detecting Equality of Variables in Programs
- Intermediate Representation Construction in a Nutshell
- Code Generation on Expression Trees
- The paper containing the proof for the NP-hardness of instruction selection: Near-optimal instruction selection on DAGs
Note: To download background reading, it may be necessary to be in the university's subnet due to licensing issues of the papers' publishers
- Exercise 1 (corresponding Mini Test 1)
- Exercise 2 (corresponding Mini Test 2)
- Exercise 3
- Exercise 4 (corresponding Mini Test 3)
- Exercise 5 (reference file for the pretty printer)
- Exercise 6 (corresponding Mini Test 4)
- Exercise 7 (corresponding Mini Test 5)
- Exercise 8
- Exercise 9 (corresponding Mini Test 6)
- Exercise 10 (corresponding Mini Test 7)
- Exercise 11
- Exercise 12
- The final draft of C1X, dated 12 April 2011
- Reference example for the pretty printer
- LLVM-IR construction examples
There will be eight voluntary mini tests which will take place in the last 20 minutes within the tutorial. Additionally, there will be voluntary exercises. To get a course certificate, students must pass the final exam and the project. Final grades will be based on the exam and the project.
- R. Wilhelm and D. Maurer, "Übersetzerbau"
Springer; Berlin, 2nd print, 1997. ISBN 3-540-61692-6.
- R. Wilhelm and D. Maurer, "Compiler Design"
Addison-Wesley; Essex, 2nd print, 1996. ISBN 0-201-42290-5.
- R. Wilhelm and H. Seidl, "Übersetzerbau – Virtuelle Maschinen"
Springer, Berlin, 1st print, 2007. ISBN 978-3-540-49596-3.
- W. Waite and G. Goos, Compiler Construction