Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Syllabus - Compiler Construction
Computer Laboratory > Computer Science Syllabus - Compiler Construction

Compiler Construction next up previous contents
Next: Computation Theory Up: Lent Term 2006: Part Previous: Comparative Programming Languages   Contents

Compiler Construction

Lecturer: Dr T.G. Griffin

No. of lectures: 18

This course is a prerequisite for Optimising Compilers (Part II).


This course aims to cover the main technologies associated with compiling programming languages, viz. lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation.


  • Survey of execution mechanisms. The spectrum of interpreters and compilers; compile-time and run-time. Structure of a simple compiler. Java virtual machine (JVM).

  • Lexical analysis and syntax analysis. Regular expressions and finite state machine implementations. Phrase Structured Grammars. Chomsky classification. Parsing algorithms: recursive descent and SLR(k)/LALR(k). Syntax error recovery. Abstract syntax tree; expressions, declarations and commands.

  • Simple type-checking. Type of an expression determined by type of subexpressions; inserting coercions.

  • Translation phase. Intermediate code design. Translation of expressions, commands and declarations.

  • Intermediate code interpreter. Essential structure of a JVM interpreter, C$\sharp$.

  • Code generation. Typical machine codes. Code generation from intermediate code. Simple peephole optimisation.

  • Compiler compilers. Compiler compilers. Summary of Lex and Yacc.

  • Object Modules and Linkers. Resolving external references. Static and dynamic linking.

  • Variable binding and tree-based interpreter. Lambda-calculus as prototype. Problems with rec and class variables. A simple lambda interpreter. Environments, function values are closures. Static and Dynamic Binding (Scoping). Landin's principle of correspondence.

  • Machine implementation of a selection of interesting things. Free variable treatment, static and dynamic chains, ML free variables. Argument passing mechanisms. Objects and inheritance; implementation of methods. Labels, goto and exceptions. Dynamic and static typing, polymorphism. Storage allocation, garbage collection.


At the end of the course students should understand the overall structure of a compiler, and will know significant details of a number of important techniques commonly used. They will be aware of the way in which language features raise challenges for compiler builders.

Recommended reading

* Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions). Cambridge University Press.
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: principles, techniques and tools. Addison-Wesley.
Bennett, J.P. (1990). Introduction to compiling techniques: a first course using ANSI C, LEX and YACC. McGraw-Hill.
Bornat, R. (1979). Understanding and writing compilers. Macmillan.
Fischer, C.N. & LeBlanc, J. Jr (1988). Crafting a compiler. Benjamin/Cummings.
Watson, D. (1989). High-level languages and their compilers. Addison-Wesley.

next up previous contents
Next: Computation Theory Up: Lent Term 2006: Part Previous: Comparative Programming Languages   Contents
Christine Northeast
Sun Sep 11 15:46:50 BST 2005