This course is a prerequisite for Optimising Compilers (Part II).
Aims
This course aims to cover the main technologies associated with
compiling 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).
Lexical analysis and syntax analysis.
Regular expressions and finite state machine implementations.
Phrase Structured Grammars.
Chomsky classification.
Parsing algorithms: recursive descent and SLR(k)/LALR(k).
Syntax error recovery.
Abstract syntax tree; expressions, declarations and commands.
Simple type-checking.
Type of an expression determined by type of subexpressions;
inserting coercions.
Translation phase.
Intermediate code design.
Translation of expressions, commands and declarations.
Intermediate code interpreter.
Essential structure of a JVM interpreter, C.
Compiler compilers.
Compiler compilers.
Summary of Lex and Yacc.
Object Modules and Linkers.
Resolving external references.
Static and dynamic linking.
Variable binding and tree-based interpreter.
Lambda-calculus as prototype.
Problems with rec and class variables.
A simple lambda interpreter.
Environments, function values are closures.
Static and Dynamic Binding (Scoping).
Landin's principle of correspondence.
Machine implementation of a selection of interesting things.
Free variable treatment, static and dynamic chains, ML free variables.
Argument passing mechanisms.
Objects and inheritance; implementation of methods.
Labels, goto and exceptions.
Dynamic and static typing, polymorphism.
Storage allocation, garbage collection.
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 books
* Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions).
Cambridge University Press.
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers:
principles, techniques and tools. Addison-Wesley.
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.
.