Compiler Construction

Lecturers: Dr A.C. Norman and Dr M. Richards
(acn@cam.ac.uk and mr@cl.cam.ac.uk)

No. of lectures: 20

Aims

This course aims to cover the main technologies assocoiated with compiling programming languages, viz. lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation. It also aims to provide the background material for a Part II course on Optimising Compilers in such years as that course is offered.

Lectures

Note: For the year 1999-2000 this course will be in a state of flux, in part because the regular lecturer will be on leave. The exact order in which topics are covered will be adjusted to obtain a good split between the parts given by the two lecturers involved, and final details of how this will be done will be issued at the start of the course.

• Introduction. The overall structure and purpose of typical compilers. The concept of object code and other intermediate formats, and of assembly and linking. The features that will be assumed to be present in a target architecture, and fundamental issues of mapping language constructs onto it.

• Lexical analysis and syntax analysis. Regular expressions and finite state machine implementations. Grammars, Chomsky classification of phrase structured grammars. Parsing algorithms: recursive descent, (operator-) precedence and LR-based parsing. Syntax error recovery.

• Compiler compilers. Summary of Lex and Yacc and/or Java equivalents.

• Simple type-checking. Type of an expression determined by type of subexpressions; inserting coercions. Overloading versus Polymorphism.

• Survey of language constructs and their implementation. Expressions, applicative structure, lambda expressions. Environments and a simple lambda evaluator. Situations where a simple stack is inadequate. Heap versus Stack storage allocation. The concept of garbage collection. Evaluation of function calls using static and dynamic chains, Dijkstra displays. 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, objects and inheritance.

• Survey of execution mechanisms. The spectrum of interpreters and compilers; compile-time and run-time. Structure of a simple compiler. Java virtual machine and the trade-offs involved in the use of a VM at that level.

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

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

• Runtime. Object modules and linkers. Resolving external references. Static and dynamic linking. Debuggers, break points and single step execution. Profiling, portability.

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). 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.