Computer Laboratory

Course pages 2012–13

Compiler Construction

Principal lecturer: Dr Timothy Griffin
Taken by: Part IB
Past exam questions
Information for supervisors (contact lecturer for access permission)

No. of lectures: 16
Suggested hours of supervisions: 4
Prerequisite: (the last lecture of) Regular Languages and Finite Automata (Part IA)
This course is a prerequisite for Optimising Compilers (Part II).

Aims

This course aims to cover the main technologies associated with implementing 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), JIT. Simple run-time structures (stacks). Structure of interpreters for result of each stage of compilation (tokens, tree, bytecode). [3 lectures]

  • Lexical analysis and syntax analysis. Recall regular expressions and finite state machine acceptors. Lexical analysis: hand-written and machine-generated. Recall context-free grammars. Ambiguity, left- and right-associativity and operator precedence. Parsing algorithms: recursive descent and machine-generated. Abstract syntax tree; expressions, declarations and commands. [2 lectures]

  • Simple type-checking. Type of an expression determined by type of subexpressions; inserting coercions. [1 lecture]

  • Translation phase. Translation of expressions, commands and declarations. [1 lecture]

  • Code generation. Typical machine codes. Code generation from intermediate code. Simple peephole optimisation. [1 lecture]

  • Object modules, linkers and run-time system. Resolving external references. Static and dynamic linking. Malloc and system calls. [1 lecture]

  • Non-local variable references. Lambda-calculus as prototype, Landin’s principle of correspondence. Problems with rec and class variables. Environments, function values are closures. Static and dynamic binding (scoping). [1 lecture]

  • Machine implementation of a selection of interesting things. Free variable treatment, static and dynamic chains, ML free variables. Compilation as source-to-source simplification, e.g. closure conversion. Argument passing mechanisms. Objects and inheritance; implementation of methods. Labels, goto and exceptions. Dynamic and static typing, polymorphism. Storage allocation, garbage collection. [3 lectures]

  • Parser Generators. A user-level view of Lex and Yacc. [1 lecture]

  • Parsing theory and practice. Phrase Structured Grammars. Chomsky classification. LL(k) and LR(k) parsing. How tools like Yacc generate parsers, and their error messages. [2 lectures]

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 reading

* Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions). Cambridge University Press.
Aho, A.V., Sethi, R. & Ullman, J.D. (2007). Compilers: principles, techniques and tools. Addison-Wesley (2nd ed.).
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.