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

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 PDF 23.04.13 scanner, regex, NFA, DFA
2 PDF 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 PDF 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

For additional literature concerning the lecture, consult the following web site.