Lecturer	Quentin Miller
Degrees	Schedule A1(CS&P) — Computer Science and Philosophy Part A Core — Computer Science Schedule A1(M&CS) — Mathematics and Computer Science
Term	Michaelmas Term 2022  (16 lectures)

Overview

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.

Learning outcomes

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.

Synopsis

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

Syllabus

Programming 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 list

Main Text

• Draft of book on Compilers by J.M. Spivey will be available at the start of the course.

Further Reading

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

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.