Compiler and Language-Processing Tools
Information about this lecture can be found in KIS (Lecture/Exercise) and in the Module Handbook.
The lecture will be held in English.
Topics of the Lecture
- Syntax specification of programming and formal languages
- Lexical analysis: scanning, scanner generation, application of scanner generators
- Context free analyses: parsing, parser generation, application of parser generators
- Design and use of abstract syntax
- Context sensitive analysis: name analysis, type analysis, attribution techniques and tools
- Processing of XML documents
- Compilation techniques for procedural and object-oriented languages
- Intermediate languages for compilation
- Semantical aspects and optimization techniques
- Instruction selection
- Register assignment
- Code generation
- Automatic memory management and garbage collection
People
- Prof. Dr. Arnd Poetzsch-Heffter and Annette Bieniusa will give the lecture.
- The exercises will be supervised by Annette Bieniusa and Patrick Michel.
Organisation
- The lecture will take place on Mondays and Thursdays, from 11:45 to 13:15 in room 48-462. The first lecture is on Monday, April 15.
- The exercises will take place on Tuesday, from 10:00 to (at most) 11:30 in room 32-411.
Exceptions
- There will be no lectures on the holidays 09.05., 20.05. and 30.05.13.
- Due to a scheduling conflict, the lecture on Thursday, 23.05.13 will be held in 32-411, i.e., the room of the exercise meetings.
- There will neither be a lecture nor an exercise on Thursday, 06.06.13; please use the additional time to concentrate on the lab sheet!
- There will neither be a lecture nor an exercise on Thursday, 20.06.13; please use the additional time to concentrate on the lab sheet!
- There will neither be a lecture nor an exercise on Thursday, 04.07.13; please use the additional time to concentrate on the lab sheet!
- The last lecture is on Monday 15.07.2013, so there will also be no lecture or exercise on Thursday, 18.07.2013.
Material
Lecture Slides
Chapter | Title | Date of lectures | Slides | Info | |
---|---|---|---|---|---|
1 | Introduction | 15.04.13 | Slides | updated 17.07. | |
2 | Syntax and type analysis | ||||
Lexical analysis | 18.04.13 | Slides | updated 17.07. | ||
Context-free syntax analysis | 22.04.13 | Slides | updated 17.07. | ||
Context-dependent analysis | 02.05.13 | Slides | updated 17.07. | ||
3 | Translation to intermediate representation | 15.05.13 | Slides | updated 17.07. | |
4 | Optimization and code generation | 13.06.13 | Slides | updated 17.07. | |
(additional slides) | 27.06.13 | Slides | uploaded 27.06. | ||
5 | Selected topics in language implementation | 28.06.13 | Slides | updated 17.07. | |
6 | Further literature | 15.07.13 | Slides | uploaded 17.07. |
Practical Exercises
In the practical exercises, the topics of the lecture are put into a practical perspective by constructing a compiler from scratch. Solutions can be submitted in teams of up to 3 students via Mercurial (see this page). To be admitted to the final examination, each participant needs to achieve at least 50% in the practical exercises.
You have to maintain a members.txt
file in your repository root with all the names and email addresses of group members. It would be a great help, if you change the username
of your mercurial client to Your Name your@email.address
, so we (and your group members) can identify your commits.
No | Exercise sheet | Weight | Weeks | Submission date | Material | |
---|---|---|---|---|---|---|
1 | Warm-up: Scanner + parser | 10% | 2-T | 29.04.13 | Sample HGRC | |
2 | MiniJava: Scanner + parser | 10% | 2-T | 13.05.13 | (T is the time needed for the theory sheets) | |
3 | MiniJava: Name + type analysis | 10% | 2-T | 27.05.13 | File stubs: names.jrag error.jragcheckNames.jadd | |
4 | S/Piglet: Transformation | 15% + 10% | 3 | 17.06.13 | (sheet was updated once) | |
5 | Kanga: Transformation | 15% | 2 | 01.07.13 | ||
6 | MIPS: Transformation + Register allocation | 15% + 15% | 3+1 | 22.07.13 |
Homework policy
Programming is a creative process. Individuals must reach their own understanding of problems and discover paths to their solutions. During this time, discussions with friends and colleagues are encouraged, and they must be acknowledged when you submit your written work. When the time comes to write code, however, such discussions are no longer appropriate. Each program must be entirely your own group’s work!
Do not, under any circumstances, permit any student from another group to see any part of your program, and do not permit yourself to see any part of another group’s program. In particular, you may not test or debug another group’s code, nor may you have someone from another group test or debug your code. If you can’t get code to work, consult the teaching assistant! You may look in the library (including the internet, etc.) for ideas on how to solve homework problems, just as you may discuss problems with your classmates. All sources must be acknowledged. The standard penalty for violating these rules on one part of one assignment is to receive a zero for the entire assignment. In case of repeated violations you will not be able to finish this course successfully.
(The above policies were adapted from policies used by Norman Ramsey at Purdue University in Spring 1996.)
Theoretical Exercises
These exercise sheets contain assignments to deepen the understanding of the underlying principles of compiler construction. We will discuss the topics of the sheet and possible solutions in the exercise meeting referenced in the Date column.
You do not have to turn in solutions. Please prepare the sheet and try to solve it on your own. This is the only way to really benefit from the sheets and the exercise meetings.
No | Sheet | Date | Topics | |
---|---|---|---|---|
1 | 23.04.13 | scanner, regex, NFA, DFA | ||
2 | 07.05.13 | parser, ambiguity, LL(1), LR(0) | ||
2 | 14.05.13 | (rest of exercise 2), conflicts, ambiguity resolution in S/LA/LR(1) | ||
3 | 21.05.13 | name analysis, JLS |
Exams
- You can register and take an oral examination for this course, if you passed the lab (i.e. have reached at least 50% of the points).
- There will be one examination day per month, for which you can register with our secretary.
- Please be aware that if there are too many students at one particular date, we might have to move your exam by one day (i.e. one day earlier or later).
- The currently fixed dates are 25.07.13 (July), 23.08.13 (August) and 26.09.13 (September).
- There will also be an examination day in October, etc. (if necessary).
Literature
A. Appel: Modern Compiler Implementation in Java, Cambridge University Press, 2002 (2nd edition), INF 466/120
Wilhelm, R.; Maurer, D.: Übersetzerbau: Theorie, Konstruktion, Generierung, Springer, 1992. INF 466/109
Wilhelm, R.; Maurer, D.; S. Hack: Übersetzerbau
For additional literature concerning the lecture, consult the following web site.