Course pages 2015–16
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 -- lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation.
- Overview of compiler structure The spectrum of interpreters and compilers; compile-time and run-time. Structure of a simple compiler: lexical analysis and syntax analysis (details postponed to the last four lectures of term), type checking, intermediate representations, optimisations, code generation. Overview of run-time data structures: stack and heap. Virtual machines. [1 lecture]
- A Small LANGguage (SLANG) A complete compiler for a small language will illustrate some of the main concepts. Compilation as a sequence of translations from higher-level to lower-level intermediate languages. Code generation from intermediate code. [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. [4 lectures]
- Advanced topics Run-time memory management (garbage collection). Static and dynamic linking. Objects and inheritance; implementation of method dispatch. Try-catch exception mechanisms. How to compile a compiler via bootstrapping. [4 lectures]
- 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. [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.