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.
The course will be based around the study a simple compiler called MinCaml
(http://min-caml.sourceforge.net/index-e.html) that was
designed and implemented by Eijiro Sumii at the University of Tokyo.
Dr Griffin will also make available
extensions to this compiler tailored to the
needs of this course.
Lectures
Survey of execution mechanisms.
The spectrum of interpreters and compilers; compile-time and run-time.
Structure of a simple compiler, virtual machines.
Lexical analysis and syntax analysis.
Regular expressions and finite state machine implementations.
Parsing algorithms: recursive descent and SLR(k)/LALR(k).
Abstract syntax tree; expressions, declarations and commands.
Summary of Lex and Yacc.
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.
Compilation as a sequence of translations.
Low-level representations.
Variable binding, functions, higher-order functions.
Environments, function values are closures.
Free variable treatment, static and dynamic chains, ML free variables.
Argument passing mechanisms.
Objects and inheritance; implementation of methods.
Storage allocation, garbage collection.
Code generation.
Typical machine codes.
Code generation from intermediate code.
Object modules and linkers.
Resolving external references.
Static and dynamic linking.
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. The ML edition is best for this course). Cambridge University Press.
* MinCaml code and documentation. http://min-caml.sourceforge.net/index-e.html
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.
Levine, J.R. (1999). Linkers and loaders. San Francisco: Morgan Kaufmann.
