Course pages 2015–16
Compiler Construction
Lecturer: Dr T.G. Griffin
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 -- lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation.
Lectures
- 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]
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.