Compiler Construction

Lecturer: Dr A. Mycroft (am@cam.ac.uk)

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. Grammars, Chomsky classification of phrase structured grammars. 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. Polymorphism.

• 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 the parse tree and from intermediate code. Simple 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

Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: Principles, Techniques and Tools. Addison-Wesley.
Appel, A. (1997). Modern Compiler Implementation in Java/C/ML (3 editions). Cambridge University Press.
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.