Syllabus and synopsis (Compilers)
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.
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.
For MSc Students: A basic knowledge of functional programming is recommended. Those with substantial programming experience should find it possible to study this course concurrently with Functional Programming.
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.
- 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.
- A V Aho, R Sethi and J D Ullman, Compilers: principles, techniques and tools, Addison-Wesley.
- R Bornat, Understanding and writing compilers, available on the web.
- A W Appel, Modern Compiler Implementation in ML, Cambridge University Press.
- H Abelson and G J Sussman, Structure and Interpretation of Computer Programs, MIT Press, 2nd Edition, 1996.