Compiler Construction

News

  • Students are allowed to inspect their Grades on the second examination on 18th September 2014 at 2pm.
  • Here is the solution to the exam on 25.07.2014.
  • The grades of the first exam will be uploaded by the end of this week (08.08.2014). Any changes to the grades will not be possible after that.
  • Here are the results of the first exam. (28.07)
  • Here is the solution to the trial exam (as far as it is available). And here is another exam for preparation, the solution is however unavailable. (22.07)
  • Here is an exam from previous years that you can use for your preparation. (20.07)
  • The lecture on Wed, 18.06 will be cancelled! (13.06)
  • We have opened an L2P room for the exercise course. Please register via the CAMPUS system for the exercise course to get access (unless you have been added there already automatically). Please use the L2P room to upload solutions for the programming exercise. Do not forget to include your team members when adding a solution in L2P. Please hand in written exercises on paper as before. (23.05)
  • If you would like to hand in your papers before Friday morning, please do so in course of the Thursday afternoon either at the office of Friedrich Gretz (4210) or Souymodip Chakraborty (4206). (02.05)
  • Please hand in solutions for written tasks on paper in the future! (02.05)
  • Please send solutions for programming exercises to both assistants either as a zip attachment or a download link (e.g. gigamove link). Do not hand in printouts of your source code with the written solutions.
  • There will be no exercise class this Friday (25.04) as announced before.
  • The login for the solutions will be announced in the next lecture.
  • Exercise sheet 0 uploaded. Note that this is just a collection of problems to recap the topics of FoSAP. The solutions will be presented during the tutorial on Wednesday. You do not have to hand in your solutions but please do try to solve the exercises at home before the class.

Schedule

Type Day Time Hall Start Lecturer
Lecture Mon 14:15 – 15:45 AH 6 14 April Noll
Wed 10:15 – 11:45 AH 6 9 April Noll
Exercise Fri 8:15 – 9:45 AH 2 11 April Chakraborty / Gretz

Contents

The goal of this course is to introduce foundational methods and techniques for implementing compilers for high-level (procedural) programming languages. The following topics will be discussed:

  • Lexical analysis of programs (Scanner)
  • Syntactic analysis of programs (Parser)
  • Semantic analysis of programs
  • Code generation
  • Tools for compiler construction

Prerequisites

Basic knowledge of the relevant undergraduate courses of the first two years is required:

  • Programming (essential concepts of imperative and object-oriented programming languages and elementary programming techniques)
  • Data structures and algorithms (lists, stacks, queues, trees and associated algorithms)
  • Formal languages and automata theory (regular and context-free languages, finite and pushdown automata)

Slides

No. Date Subject Slides Handout Exercises Solutions
1 9 April Introduction l1 l1 e0 s0
2 14 April Lexical Analysis I (Introduction) l2 l2 u1
framework
tests		 s1
code
– 16 April [Exercise class]
3 23 April Lexical Analysis II (Extended Matching Problem) l3 l3
4 28 April Lexical Analysis III (Practical Aspects) l4 l4 u2 s2
5 30 April Syntax Analysis I (Introduction) l5 l5 u3
framework		 s3
Code
6 12 May Syntax Analysis II (LL(k) Grammars) l6 l6
7 14 May Syntax Analysis III (LL(1) Parsing) l7 l7 u4 s4
8 19 May Syntax Analysis IV (More on LL(1) & Bottom-Up Parsing) l8 l8
9 21 May Syntax Analysis V (LR(k) Grammars) l9 l9 u5
framework		 s5
10 26 May Syntax Analysis VI (LR(0) and SLR(1) Parsing) l10 l10
11 28 May Syntax Analysis VI (LALR(1) Parsing and Practical Issues) l11 l11 u6
framework		 s6
code
A 2 June Program Analysis and Transformation from a Practitioner’s Point of View [Jonathan Streit; itestra GmbH] see L2P –
B 4 June Important Language Concepts in Old and Recent Programming Languages (and their Consequences) [Ivo Bonev; itestra GmbH] – u7
framework		 code
12 16 June Semantic Analysis I (Attribute Grammars) l12 l12
– 18 June CANCELLED u8
framework		 s8
code
13 23 June Semantic Analysis II (Circularity Check) l13 l13
14 25 June Semantic Analysis III (Attribute Evaluation) l14 l14 u9 s9
JasminFiles
15 30 June Code Generation I (Intermediate Code) l15 l15
16 2 July Code Generation II (The Translator) l16 l16 u10
framework		 s10
code
17 7 July Code Generation III (Implementation of Static Data Structures) l17 l17
18 9 July Code Generation IV (Implementation of Dynamic Data Structures) l18 l18
19 14 July Code Generation V (Machine Code) l19 l19

Exam

  • Registration via this Campus page
  • First exam: Friday, 25 July, 10:00-13:00, AH 1 (BSc students), AH 4 (MSc students)
  • Review of first exam: TBD
  • Second exam: Wednesday, 3 September, 10:00-13:00, AH 4
  • Review of second exam: TBD

Evaluation results

Further information

  • The course will be given partly in German and partly in English. The slides and other course material will be in English. There are no lecture notes (yet); the course material will consist of slides.
  • The form of the exam (oral/written) will be announced in the beginning of the course.

Additional background literature

  • A. Aho, M.S. Lam, R. Sethi, J.D. Ullman: Compilers – Principles, Techniques, and Tools; 2nd ed. Addison-Wesley, 2007.
  • A.W. Appel, J. Palsberg: Modern Compiler Implementation in Java. Cambridge University Press, 2002.
  • D. Grune, H.E. Bal, C.J.H. Jacobs, K.G. Langendoen: Modern Compiler Design. Wiley & Sons, 2000.
  • R. Wilhelm, D. Maurer: Übersetzerbau, 2. Auflage. Springer, 1997.

Interesting Links