Skip to main content

Compilers:  2018-2019



Schedule S1(CS&P)(3rd years)Computer Science and Philosophy

Part A CoreComputer Science

Schedule S1(M&CS)(3rd years)Mathematics and Computer Science



This course aims to give a simple but practical account of the programming techniques used in implementing high-level programming languages by compiling into code for stack and register-based machines. The course is based on a working implementation, written in Objective Caml, of a compiler for a language comparable to C or Pascal.

Learning outcomes

On completion, the students should be able to:

* Understand and explain the main techniques and algorithms used in compilers.

* Describe the runtime structures used to represent constructs in typical programming languages.

* Use compiler construction tools, such as parser generators, to build a simple compiler.


* Introduction. * A smattering of ML; abstract syntax as an algebraic type. * Regular expressions and context free grammars as ways of specifying concrete syntax. Lex and Yacc considered as black boxes. * Expressions and statements: evaluation by recursion on syntax. * Postfix code for expressions and statements. * A glimpse at RISC architecture. * Translation of arithmetic expressions into RISC code. * Simple optimisations:  constant folding, re-ordering, common sub-expressions. * Procedures and parameters: call by value, and call by reference, static vs. dynamic binding. * Stack-based allocation of activations; static and dynamic chains.


Programming language representation: concrete and abstract syntax, context free grammars. Use of lexer and parser generators. Implementation of expressions and statements in a simple language by postfix code and by simple machine code; simple optimizations. Procedures: value, name and reference parameters, local and non-local variables, static and dynamic binding. Abstract machines and storage management: activation records, static and dynamic chains, stacks and heaps.

Reading list

Main Text

* Draft of book on Compilers by J.M. Spivey will be available at the start of the course.

Further Reading

* A W Appel, Modern Compiler Implementation in ML, Cambridge University Press. * A V Aho, R Sethi and J D Ullman, Compilers: principles, techniques and tools, 3rd edition, Addison-Wesley. * H Abelson and G J Sussman, Structure and Interpretation of Computer Programs, MIT Press, 2nd Edition, 1996. * R Bornat, Understanding and writing compilers, available on the web.