This course aims to give a simple but practical account of the programming techniques used in implementing high-level programming languages by compiling into code for stack and register-based machines. The course is based on a working implementation, written in Objective Caml, of a compiler for a language comparable to C or Pascal.
On completion, the students should be able to:
* Understand and explain the main techniques and algorithms used in compilers.
* Describe the runtime structures used to represent constructs in typical programming languages.
* Use compiler construction tools, such as parser generators, to build a simple compiler.
* Introduction. * A smattering of ML; abstract syntax as an algebraic type. * Regular expressions and context free grammars as ways of specifying concrete syntax. Lex and Yacc considered as black boxes. * Expressions and statements: evaluation by recursion on syntax. * Postfix code for expressions and statements. * A glimpse at RISC architecture. * Translation of arithmetic expressions into RISC code. * Simple optimisations: constant folding, re-ordering, common sub-expressions. * Procedures and parameters: call by value, and call by reference, static vs. dynamic binding. * Stack-based allocation of activations; static and dynamic chains.
SyllabusProgramming language representation: concrete and abstract syntax, context free grammars. Use of lexer and parser generators. Implementation of expressions and statements in a simple language by postfix code and by simple machine code; simple optimizations. Procedures: value, name and reference parameters, local and non-local variables, static and dynamic binding. Abstract machines and storage management: activation records, static and dynamic chains, stacks and heaps.
Reading listMain Text
* Draft of book on Compilers by J.M. Spivey will be available at the start of the course.
* A W Appel, Modern Compiler Implementation in ML, Cambridge University Press. * A V Aho, R Sethi and J D Ullman, Compilers: principles, techniques and tools, 3rd edition, Addison-Wesley. * H Abelson and G J Sussman, Structure and Interpretation of Computer Programs, MIT Press, 2nd Edition, 1996. * R Bornat, Understanding and writing compilers, available on the web.