Next: Computation Theory
Up: Lent Term 2002: Part
Previous: Comparative Programming Languages
  Contents
Compiler Construction
Lecturer: Dr A. Mycroft
(am@cam.ac.uk)
No. of lectures: 20
This course is a prerequisite for Optimising Compilers (Part II).
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.
Lectures
- 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. Polymorphism.
- 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.
- Compiler compilers.
Summary of Lex and Yacc.
- 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). 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.
Next: Computation Theory
Up: Lent Term 2002: Part
Previous: Comparative Programming Languages
  Contents
Christine Northeast
Tue Sep 4 09:34:31 BST 2001