Compiler Construction

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

No. of lectures: 20  

Survey of language constructs and their implementation.

Expressions, applicative structure, lambda expressions. Environments and a simple lambda evaluator. Evaluation of function calls using Dijkstra displays. Static and dynamic chains, optimisations. Situations where a simple stack is inadequate. Argument passing mechanisms. Implementation of labels, jumps, arrays and exceptions. Data types.

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). Parser matrix compaction. Syntax error recovery.

Translation phase.

Intermediate code design. Translation of commands, expressions and declarations.

Code generation.

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

Compiler compilers.

Summary of Lex and Yacc. A rule base parse tree pattern matching algorithm.

Runtime.

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

Recommended books:

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.