Schedule
Project
Project test cases
Tigris judging system
Examination
Study handbook
Code of honour

Examination in DD2488, Compiler Construction

Please make sure to read this entire page! It contains important information about the examination in DD2488 compiler construction!

Booking of oral project presentation/examination

The project presentations will take place 2014-05-15 to 2014-05-23. The slots are 45 minutes.

Press here to get booking lists (visible from 2014-05-08 at 00:00):

If you already have or might write a CPU backend, primarily choose either a "CPU" or a "JVM/CPU" slot. If you aim for just a JVM backend, then primarily choose a "JVM" slot and secondarily a "JVM/CPU" slot.

You must have a compiler and report ready for us at the latest 12 hours before your presentation slot. Also, TIGRIS must have accepted your compiler. The way we find the compiler and reports is through TIGRIS.

Compiler correctness and "purchase" of hidden tests

We require compilers to pass all Tigris' tests.

If your compiler fails some of the non-public tests and you cannot find the compiler bug, then you may "purchase" a test in exchange for 5 project points. Up to 3 tests can be "purchased" in this way, but we strongly recommend that you get one test at a time.

The tests Mean.java, Inno.java, Int64.java are not included in this bargain.

If a "purchased" test turns out to be buggy, and this buggyness is relevant to the failure, then you will of course get your points back. This is a very unlikely scenario, since the relavant tests have been tried by many compilers.

Test cases

Have your test cases ready and readable at ~/DD2488-test-cases by 2012-04-25 23:59. This is a soft deadline, incurring a 25 project point penalty. If you either didn't hand in anything or handed in something too feeble, you have a second change for one more week. If you haven't completed the task by 2014-05-02 23:59, an additional 25 project point penalty will be applied.

Please see the the testcases page for more information.

Informal groups

The informal feedback groups part is cancelled. You do not need to read another student's code and give feedback.

About the report

The report should describe your choices and decisions. E.g., which tools did you use and why did you choose these tools. Which where the tradeoffs you considered for making the decisions? What are your experiences with the choices?

Also provide an overview of the code, with file names, major methods/functions. This is critical documentation for anybody that would want to continue working on your compiler, a common scenario in the real world.

Please also include an appendix about bugs and mistakes made during the project. Trivial bugs are less interesting than design flaws, but trivial bugs with interesting consequences, or trivial bugs which required interesting debuging effort are worth describing here. (What did you learn from the mistakes?)

Write the report not as for the examiner, but for an engineer that might want to use and develop your compiler. Which information would you need in such a situation? Provide that!

The length of the report should be perhaps 5-7 pages, using normal font size.

The report should be written in English or Swedish. Please proofread it, if we find mispellings or grammatical errors in the report we will ask you to submit a corrected version.

Don't forget to write some sort of introduction!

Oral project presentation

If you worked in a project group, you need to make a single booking for both group members and make the presentation together. If you worked alone, you will of course make the presentation alone.

The presentation will be informal. Don't prepare slides. But make sure you have not forgotten any part of your compiler, so you should spend some hours looking through the code as preparation. If your project buddy wrote a part, you still need to understand it in reasonable detail. We suggest that you spend about 4 hours for going through he entire compiler before the oral examination. Looking through one's code is important, please do it without thinking too much about the examination situation!

The main motive for the presentation is to give you an opportunity to show the result of your hard work. We will also ask you to describe different parts of the compiler, and ask you to discuss your various design decisions. You need to be able to do that!

The presentations will last 30-40 minutes.

Written exam

N.B.! We require that the project has been accepted before students take the exam.

Students are allowed up to 8 pages of notes on the exam. These notes must have been typed by yourself, but you may cooperate on composing them. The notes are to be handed in together with the exam, and they will be returned with the corrected exam.

Here are some reading guidelines for the written exam, for Appel's book.

  1. INTRODUCTION: Not relevant for exam.
  2. LEXICAL ANALYSIS: Entire chapter except section 2.4.
  3. PARSING: Algorithms for parser generators can be read briefly, but the parser generator classes are important. Error recovery briefly.
  4. ABSTRACT SYNTAX: Entire chapter.
  5. SEMANTIC ANALYSIS: Entire chapter except "Efficient functional symbol tables".
  6. ACTIVATION RECORDS: Entire chapter.
  7. TRANSLATION TO INTERMEDIATE CODE: Entire chapter.
  8. BASIC BLOCKS AND TRACES: Entire chapter.
  9. INSTRUCTION SELECTION: Entire chapter.
  10. LIVENESS ANALYSIS: Entire chapter.
  11. REGISTER ALLOCATION: Entire chapter, but no deep theoretical understanding required.
  12. PUTTING IT ALL TOGETHER: Not relevant for exam.
  13. Plus: very basic level on optimisation. A highly optimised introduction to compiler optimisation

Exam (incomplete list, reading guidelines are the authorative source of information): You should know how to write a regexp, and explain the role of a lexer and how it works. You should know how to write a context-free grammar (CFG) from informal language descriptions, you should know how to write a CFG of a specific type (such as LL(1)), or rewrite a CFG to work with a weaker type of parser. You should know how to relate syntax trees and CFGs. You should understand the concept Formal Language and understand the Formal Language classes of regexps and CFGs. You should understand the relation between semantics and parse trees. You should understand the role of IR and the role difference between AST and IR. You should know how activation records are used, and explain their various parts. You should be able to perform liveness analysis of a basic block, and how register allocation works in the context of liveness information. You should know about IR → assembly translation ("code selection") and understan the maximal munch algorithm.

Grading

This table gives the final grading from exam and project grades:

Project grade
A B C D E
A A A B C D
Exam B A B C C D
grade C B B C D E
D B C D D E
E C C D D E