CPSC 510: COMPILER CONSTRUCTION II
(Two semesters: fall 2007 and winter 2008)
Lecturer: Robin Cockett
Meeting: MS 061 - Tues & Thurs 3:30
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.
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.
- Midterm (25%)
- Final (take home exam)
(45%) -- for graduate sudents this
will include a survey paper of a topic of current interest.
- Register allocation and the backend -- description of CIRL, the Jouette
- Data flow analysis (10%)
- Control flow optimizations (10%)
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,
- Introductory lecture (here).
- Register allocation for expressions (here)
- (Reference from cpsc411 for the front end) Compiler construction:
- (Reference - a useful little book on lexing) Lex & Yacc. J.R.
- (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.
- (Reference - an encyclodedia of techniques) Advanced Compiler
Design Implementation, S. Muchnick
- A web based tool for
context free grammars (developed by Mike Burrell a former CPSC411
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
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).
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
- A catalogue of lexer
and parser generators.
- The ANTLR system: ANother
Language Recognition which has become very popular recently: it uses
based parser generator.
on Parser Monads: well some good fun for those who are interested
- Happy a parser