Compiling Techniques

Here are links to the course home page and the formal TQA description.

This course describes the phases of a modern programming language compiler with an emphasis on widely-used techniques. The course project will require students to implement fragments of a compiler for an imperative programming language.

Context:

There are no formal prerequisites other than CS2.

Syllabus

• Introduction: structure of a compiler.
• Lexical analysis: tokens, regular expressions, Lex.
• Parsing: context-free grammars, predictive and LR parsing, Yacc.
• Abstract syntax: semantic actions, abstract parse trees.
• Semantic analysis: symbol tables, bindings, type-checking.
• Stack frames: representation and abstraction.
• Intermediate code: representation trees, translation.
• Basic blocks and traces: canonical trees and conditional branches.
• Instruction selection: algorithms for selection, RISC and CISC.
• Liveness analysis: solution of dataflow equations.
• Register allocation (time permitting): colouring by simplification, coalescing.
• Advanced topics.

Activities

Lectures are given by Kousha Etessami. They will loosely follow Part 1 of the textbook by Andrew W. Appel with references to other textbooks and papers where appropriate.

Assessed Coursework

Two practical compiler exercises.

References:

*** Andrew W. Appel Modern Compiler Implementation in Java, 2nd Edition (Cambridge University Press, 2002). ISBN 052182060X. Be aware that this book also exists in versions for the C and Standard ML languages. Since the compiler project for the course is based on Java, it is recommended that students use the Java version of the book. Multiple copies of these books are available in the JCM library.

** Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman Compilers: Principles, Techniques and Tools Addison Wesles, 1986.

** Steven Muchnick Advanced Compiler Design and Implementation Morgan Kaufmann, 1997.

** Reinhard Wilhelm, Dieter Maurer Compiler Design Addison Wesley, 1995.

* Charles N. Fischer, Richard J. LeBlanc, Jr. Crafting a Compiler in C Benjamin/Cummings, 1991.

* J.P. Bennett Introduction to Compiling Techniques Cambridge University Press, 1998.