www.au.dk

Compilation (2010)

www.au.dk
dOvs
DAIMI / Courses / dOvs

Note: this is the 2010 dOvs homepage. The 2011 edition runs under CourseAdmin.

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 Store Aud
Fridays 9-11 in Store 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

Asger Feldthaus <>
Lasse Klųjgaard Staal <>
Jakob Sandholm <>

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 34
Aug
Mo Tu We Th Fr Sa Su
23 24 25 26 27 28 29
Tuesday
The what and why of compilers
What will you learn?
Fun read: The FORTRAN Compiler, a local copy
Friday
OBS: lecture moved to Lille Aud
The Joos languages
Java 1.5 features
Week 35
Aug Sep
Mo Tu We Th Fr Sa Su
30 31 01 02 03 04 05
Tuesday
Context-free languages
Scanning and parsing

Groups must be formed and

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

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

Friday
Joos 0 type checking
Exercises
Week 40
Oct
Mo Tu We Th Fr Sa Su
04 05 06 07 08 09 10
Tuesday
Program transformations
Friday
Joos 0 constant normalization
Exercises
Week 43
Oct
Mo Tu We Th Fr Sa Su
25 26 27 28 29 30 31
Tuesday
No lecture  

Friday
Static analysis
Week 44
Nov
Mo Tu We Th Fr Sa Su
01 02 03 04 05 06 07
Tuesday
Garbage collection
Hand-in: type checking
Friday
No lecture
Week 45
Nov
Mo Tu We Th Fr Sa Su
08 09 10 11 12 13 14
Tuesday
Code generation
Hand-in: static analysis
Friday
Guest lecture: Kevin Millikin, Google
Destination-driven code generation (in V8)
Fun read: Dybvig-Hieb-Butler: Destination-driven code generation
Week 46
Nov
Mo Tu We Th Fr Sa Su
15 16 17 18 19 20 21
Tuesday
Optimization
 
Friday
No lecture
Week 47
Nov
Mo Tu We Th Fr Sa Su
22 23 24 25 26 27 28
Tuesday
Domain-specific languages
Syntax extensions

Hand-in: code generation EXTENDED 24 hours! New deadline is Thursday
Friday
No lecture
Week 48
Nov Dec
Mo Tu We Th Fr Sa Su
29 30 01 02 03 04 05
Tuesday
Hand-written, one-pass compilers
The C0 compiler (Joos1 version)
IJVM Tools (download)
Friday
No lecture
Week 49
Dec
Mo Tu We Th Fr Sa Su
06 07 08 09 10 11 12
Tuesday
What have we learned?
Friday

Afternoon: 14.15-15.30, 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
  2. a score for an individual multiple choice test
It is only possible to sign up for the exam if the score for the programming project is at least 50%. Note that all members of a group will receive the same score for their programming project.


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

F
FX
E
D
C
B
A


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