



Next: Computer Graphics and Image Up: Lent Term 2009: Part Previous: Lent Term 2009: Part Contents
Compiler Construction
Lecturer: Professor A. Mycroft
No. of lectures: 16
Prerequisite: (the last lecture of) Regular Languages and Finite Automata (Part IA)
This course is a prerequisite for Optimising Compilers (Part II).
Aims
This course aims to cover the main technologies associated with implementing programming languages, viz. lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation.
Lectures
- Survey of execution mechanisms.
The spectrum of interpreters and compilers; compile-time and run-time.
Structure of a simple compiler. Java virtual machine (JVM), JIT.
Simple run-time structures (stacks).
Structure of interpreters for result of each stage of compilation
(tokens, tree, bytecode).
[3 lectures]
- Lexical analysis and syntax analysis.
Recall regular expressions and finite state machine acceptors.
Lexical analysis: hand-written and machine-generated.
Recall context-free grammars.
Ambiguity, left- and right-associativity and operator precedence.
Parsing algorithms: recursive descent and machine-generated.
Abstract syntax tree; expressions, declarations and commands.
[2 lectures]
- Simple type-checking.
Type of an expression determined by type of subexpressions;
inserting coercions.
[1 lecture]
- Translation phase.
Translation of expressions, commands and declarations.
[1 lecture]
- Code generation.
Typical machine codes.
Code generation from intermediate code.
Simple peephole optimisation.
[1 lecture]
- Object Modules and Linkers.
Resolving external references.
Static and dynamic linking.
[1 lecture]
- Non-local variable references.
Lambda-calculus as prototype, Landin's principle of correspondence.
Problems with rec and class variables.
Environments, function values are closures.
Static and Dynamic Binding (Scoping).
[1 lecture]
- Machine implementation of a selection of interesting things.
Free variable treatment, static and dynamic chains, ML free variables.
Compilation as source-to-source simplification, e.g. closure conversion.
Argument passing mechanisms.
Objects and inheritance; implementation of methods.
Labels, goto and exceptions.
Dynamic and static typing, polymorphism.
Storage allocation, garbage collection.
[3 lectures]
- Parser Generators.
A user-level view of Lex and Yacc.
[1 lecture]
- Parsing theory and practice. Phrase Structured Grammars. Chomsky classification. LL(k) and LR(k) parsing. How tools like Yacc generate parsers, and their error messages. [2 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
* Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions). Cambridge University Press.
Aho, A.V., Sethi, R. & Ullman, J.D. (2007). Compilers: principles, techniques and tools. Addison-Wesley (2nd ed.).
Bennett, J.P. (1990). Introduction to compiling techniques: a first course using ANSI C, LEX and YACC. McGraw-Hill.
Bornat, R. (1979). Understanding and writing compilers. Macmillan.
Fischer, C.N. & LeBlanc, J. Jr (1988). Crafting a compiler. Benjamin/Cummings.
Watson, D. (1989). High-level languages and their compilers. Addison-Wesley.




Next: Computer Graphics and Image Up: Lent Term 2009: Part Previous: Lent Term 2009: Part Contents