CPSC 510: COMPILER CONSTRUCTION II
(Two semesters: fall 2007 and winter 2008)
Lecturer: Robin Cockett
Meeting: MS 061 - Tues & Thurs 3:30
COURSE OUTLINE:
This is an advanced compiler
construction course suitable for final year undergraduate sudents and
first year graduate sudents. Graduates may take the first
semester as a separate course.
First
semester:
The focus is on the backend of the
compiler (parsing and semantic analysis are assumed, recall, this is
the subject CPSC411). We shall look at both abstract optimization
techniques and machine level optimizations. Abtract optimizations
are largely machine independent and are performed at the level of an
intermediate representation. Data flow analysis and program
reduction techniques will be covered. These will include register
allocation, instruction selection, instruction scheduling for pipeline
and parallel architectures.
Exams:
- Midterm (25%)
- Final (take home exam)
(45%) -- for graduate sudents this
will include a survey paper of a topic of current interest.
Assignments:
- Register allocation and the backend -- description of CIRL, the Jouette
machine (10%)
- Data flow analysis (10%)
- Control flow optimizations (10%)
Second
semester:
Students must build a significant
compiler (or aspect of a compiler)
for a language. During the course of the projects students
must provide formal
presentations describing the tools, techniques, and technical
challenges they are facing in their projects. These are organized
round a series of "milestone"
presentations. They must also develop and keep a website
describing their project up to date.
- Project Websites (for 2007 are here,
2006 are here) for 2008 are here (25%).
- Milestone presentations (25%).
- Project submission: final presentation, website, documentation,
code (50%).
Enjoy!
NOTES:
- Introductory lecture (here).
- Register allocation for expressions (here)
SOME TEXTS
- (Reference from cpsc411 for the front end) Compiler construction:
principles and
practice.
K.C.
Louden.
- (Reference - a useful little book on lexing) Lex & Yacc. J.R.
Levine, T.
Mason,
D. Brown.
- (Recommended/reference - the book with a modern approach)
Modern compiler implementation, A. Appel.
- (Recommended/reference - a new edition of an old bible)
Compilers: principles techniques, and tools.
Aho,
Lam, Sethi,
Ullman.
- (Reference - an encyclodedia of techniques) Advanced Compiler
Design Implementation, S. Muchnick
PARSING LINKS:
- A web based tool for
investigating
context free grammars (developed by Mike Burrell a former CPSC411
student!).
It allows you to: transform grammars into LL(1) (when possible) to look
at LL(1), LR(0), SLR(1), LALR(1), and LR(1) parsing tables and
automata.
It also has examples of context free grammars belonging to most of the
different classes considered in the course.
- A downloadable tool for (Early) parsing called Kakuy
(it is free and for windows platforms).
- Practical
guide to
parsing
by Dick Grune and Ceriel Jacobs.
- Essays by F.D. Lewis on Recursive
descent , top-down
parsing, and building
a top down parser. and bottom
up parsers. These are simple overviews of these parsing ideas.
- Java versions of Lex and Yacc the Java
CUP systems.
- A catalogue of lexer
and parser generators.
- The ANTLR system: ANother
Tool for
Language Recognition which has become very popular recently: it uses
LL(k)
grammars.
- Yapps
is a
python
based parser generator.
- Dr.
Seuss
on Parser Monads: well some good fun for those who are interested
in
functional languages.
- Happy a parser
generator
for Haskell.