Course pages 2017–18
Compiler Construction
Principal lecturer: Dr Timothy Griffin
Taken by: Part IB CST 50%, Part IB CST 75%
Past exam questions
No. of lectures: 16
Suggested hours of supervisions: 4
Prerequisite: Discrete Mathematics (Part IA)
This course is a prerequisite for Optimising Compilers (Part II).
Aims
This course aims to cover the main concepts associated with implementing compilers for programming languages. We use a running example called SLANG (a Small LANGuage) inspired by the languages described in 1B Semantics. A toy compiler (written in ML) is provided, and students are encouraged to extend it in various ways.
Lectures
- Overview of compiler structure
The spectrum of interpreters and compilers; compile-time and run-time.
Compilation as a sequence of translations
from higher-level to lower-level intermediate languages, where
each translation preserves semantics.
The structure of a simple compiler:
lexical analysis and syntax analysis, type checking, intermediate representations, optimisations, code generation.
Overview of run-time data structures: stack and heap. Virtual machines.
[1 lecture]
- Lexical analysis and syntax analysis.
Lexical analysis based on regular expressions and finite state automata.
Using LEX-tools. How does LEX work?
Parsing based on context-free grammars and push-down automata.
Grammar ambiguity, left- and right-associativity and operator precedence.
Using YACC-like tools. How does YACC work?
LL(k) and LR(k) parsing theory.
[3 lectures]
- Compiler Correctness
Recursive functions can be transformed
into iterative functions using the
Continuation-Passing Style (CPS) transformation.
CPS applied to a (recursive) SLANG interpreter
to derive, in a step-by-step manner, a
correct stack-based compiler.
[3 lectures]
- Data structures, procedures/functions
Representing tuples, arrays, references.
Procedures and functions:
calling conventions, nested structure, non-local variables.
Functions as first-class values represented as closures.
Simple optimisations: inline expansion, constant folding,
elimination of tail recursion, peephole optimisation.
[5 lectures]
- Advanced topics
Run-time memory management (garbage collection).
Static and dynamic linking.
Objects and inheritance; implementation of method dispatch.
Try-catch exception mechanisms.
Compiling a compiler via bootstrapping.
[4 lectures]
Objectives
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
* Aho, A.V., Sethi, R. & Ullman, J.D. (2007). Compilers: principles, techniques and tools. Addison-Wesley (2nd ed.).
Mogensen, T. Æ. (2011). Introduction to compiler design. Springer. http://www.diku.dk/ torbenm/Basics.