Compiler Construction

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

No. of lectures: 20

This course is being revised for 1998/99; accordingly the final syllabus may vary but will be published as part of the ``Teaching and Learning Guide'' included in the course notes.

Survey of language constructs and their implementation.

Expressions, applicative structure, lambda expressions. Environments and a simple lambda evaluator. Evaluation of function calls using static and dynamic chains, Dijkstra displays. Situations where a simple stack is inadequate. Objects and inheritance. Implementation of labels, jumps, arrays and exceptions. L-value and r-value; choices for argument passing and free-variable association. Dynamic and static binding. Dynamic and static types, polymorphism.

Survey of execution mechanisms.

The spectrum of interpreters and compilers; compile-time and run-time. Structure of a simple compiler. Java virtual machine.

Lexical analysis and syntax analysis.

Regular expressions and finite state machine implementations. Grammars, Chomsky classification of phrase structured grammars. Parsing algorithms: recursive descent, precedence and SLR(k). Syntax error recovery.

Simple type-checking.

Type of an expression determined by type of subexpressions; inserting coercions.

Translation phase.

Intermediate code design. Translation of commands, expressions and declarations. Translating variable references into access paths.

Code generation.

Typical machine codes. Codes generation from the parse tree and from intermediate code. Simple optimisation.

Compiler compilers.

Summary of Lex and Yacc.

Runtime.

Object modules and linkers. Resolving external references. Debuggers, break points and single step execution. Profiling, portability.

Odd ends.

Other languages; the language standard as a treaty between users and implementers.

Recommended books:

Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: Principles, Techniques and Tools. Addison-Wesley.

Appel, A. (1997). Compiler Design 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.