Next: Complexity Theory
Up: Lent Term 2004: Part
Previous: Comparative Programming Languages
  Contents
Compiler Construction
Lecturer: Dr A. Mycroft
No. of lectures: 18
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.
- Code generation.
Typical machine codes.
Code generation from intermediate code.
Simple peephole optimisation.
- 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.
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; the virtual function table.
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.
Next: Complexity Theory
Up: Lent Term 2004: Part
Previous: Comparative Programming Languages
  Contents
Christine Northeast
Thu Sep 4 15:29:01 BST 2003