Course pages 2016–17
No. of lectures: 16
Suggested hours of supervisions: 4
Prerequisite: Discrete Mathematics (Part IA)
This course is a prerequisite for Optimising Compilers (Part II).
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.
- 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]
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.
* 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.