www.au.dk

Compilation (2009)

www.au.dk
dOvs
DAIMI / Courses / dOvs

Description

The participants will after the course have insight into the theory of translation of programming languages and practical experience with the application of compiler technology. The working method of the course will also train the participants to independently seek information and to plan and complete projects. The participants must at the end of the course be able to describe and apply principles and theories of translation of programming languages, to plan and implement a compiler for a modern programming language, and to describe and evaluate how compiler technology influences the design of programming languages. The contents are concrete and abstract syntax, parsing, scopes and environments, type checking, virtual machines, code generation, optimization, static analysis, garbage collection, program transformations, and domain-specific languages.

Time and Place

Tuesdays 12-14 in Lille Aud
Fridays 9-11 in Lille Aud

Phorum

The Phorum is used for discussions about the course and the programming project. Please follow the posting guidelines.

Lecturer

Jan Midtgaard <>

Teaching Assistants

Johnni Winther <>
Christian Hofer <>
Sigurd Meldgaard <>

Lectures

The lectures will cover the general topics, Java specific issues, and solutions to the weekly exercises. The language of the lectures is English.

Project Groups

The participants must work in groups of size 3. Each group will collaborate on a solution to the programming project and will share 70% of their final grades.

Group Homepages

Each group has a homepage, which contains information about the group members and their preliminary evaluation. It is also used for handing in and testing the various parts of the project and for providing documentation through a (private) group blog. Do not use this homepage as the only repository for your source code!

Programming Project

Each group will in Java 1.5 implement a compiler for the language Joos 1, which is a large subset of Java 1.3. The compiler must be implemented as a completion of a skeleton compiler for the Joos 2 superset. For inspiration, a complete compiler for the Joos 0 subset is presented during the lectures. For extra credit, the compiler may be extended with features from the full Joos 2 language (don't attempt this until you have a complete Joos 1 solution). The project consists of several individual parts that must be handed in at specific times during the semester. Note that different groups are not permitted to share source code (but discussions of general techniques are of course allowed).

Joos 2 is implemented by Aske Simon Christensen and Johnni Winther.

Consultations

Each group must arrange a weekly 30-minute consultation with a teaching assistant to receive help and guidance with the programming project and the general topics. Note that such a meeting is only productive if the group is well prepared in advance. Additional help may be obtained by e-mail or through the Phorum and the group blog.

Course Plan

 
Hand-in deadlines are Wednesdays at 14.00.
 
Week 35
Aug
Mo Tu We Th Fr Sa Su
24 25 26 27 28 29 30
Tuesday
The what and why of compilers
What will you learn?
Fun read: The FORTRAN Compiler, a local copy
Friday
The Joos languages
Java 1.5 features
Week 36
Aug Sep
Mo Tu We Th Fr Sa Su
31 01 02 03 04 05 06
Tuesday
Context-free languages
Scanning and parsing

Groups must be formed and

Friday
SableCC
Exercises
Week 37
Sep
Mo Tu We Th Fr Sa Su
07 08 09 10 11 12 13
Tuesday
Abstract syntax trees
Examples: xyz, html
Friday
Joos 0 scanner+parser
Exercises
Week 38
Sep
Mo Tu We Th Fr Sa Su
14 15 16 17 18 19 20
Tuesday
Scopes and environments

Friday
Joos 0 environments+linking
Exercises
Week 39
Sep
Mo Tu We Th Fr Sa Su
21 22 23 24 25 26 27
Tuesday
The Java Virtual Machine
Hand-in: parser+weeder
Friday
Jasmin, Joos 0 instructions
Exercises
Week 40
Sep Oct
Mo Tu We Th Fr Sa Su
28 29 30 01 02 03 04
Tuesday
Static type checking

Friday
Joos 0 type checking
Exercises
Week 41
Oct
Mo Tu We Th Fr Sa Su
05 06 07 08 09 10 11
Tuesday
Program transformations
Friday
Joos 0 constant normalization
Exercises
Week 44
Oct Nov
Mo Tu We Th Fr Sa Su
26 27 28 29 30 31 01
Tuesday
No lecture  

Friday
Static analysis
Week 45
Nov
Mo Tu We Th Fr Sa Su
02 03 04 05 06 07 08
Tuesday
Garbage collection
Hand-in: type checking
Friday
Guest lecture: Kasper Verdich Lund, Google
Efficient Interpretation of Java Bytecodes
Week 46
Nov
Mo Tu We Th Fr Sa Su
09 10 11 12 13 14 15
Tuesday
Code generation
Hand-in: static analysis
Friday
No lecture
Week 47
Nov
Mo Tu We Th Fr Sa Su
16 17 18 19 20 21 22
Tuesday
Optimization (part I)
 
Friday
Optimization (part II)
 
Week 48
Nov
Mo Tu We Th Fr Sa Su
23 24 25 26 27 28 29
Tuesday
Domain-specific languages
Syntax extensions

Hand-in: code generation
Friday
No lecture
Week 49
Nov Dec
Mo Tu We Th Fr Sa Su
30 01 02 03 04 05 06
Tuesday
Hand-written, one-pass compilers
The C0 compiler (Joos1 version)
IJVM Tools (download)
Friday
Guest lecture: Kevin Millikin, Google
Destination-driven code generation in V8
Fun read: Destination-driven code generation
Week 50
Dec
Mo Tu We Th Fr Sa Su
07 08 09 10 11 12 13
Tuesday
What have we learned?
Friday
Course ending and peephole competition results, 14.00-15.00, Shannon-157 Peephole Competition The Ultimate Test

Exam

At the exam, each participant will receive a single individual grade on the 7-scale. The grade will be composed of two weighted components:
  1. a score for the programming project, weighted 70%
  2. a score for an individual multiple choice test, weighted 30%
It is only possible to sign up for the exam if the score for the programming project is at least 50%. Also, to get a grade of 12, the score on the multiple choice test must be at least 80%. Note that all members of a group will receive the same score for their programming project. Thus, if you score % on the project and % on the multiple choice test, your final grade will be .
This means that a result in the following area will yield a passing grade:
multiple choice (0-100%)
project (0-110%)


The final grades (7-scale) for the 2009 course (average = 7.2):

F
FX
E
D
C
B
A


The final grades (7-scale) for the 2008 course (average = 6.0):

F
FX
E
D
C
B
A


The final grades (7-scale) for the 2007 course (average = 8.0):

F
FX
E
D
C
B
A