Skip to main content

Compilers:  2021-2022



Schedule S1(CS&P)(3rd years)Computer Science and Philosophy

Schedule A1(CS&P)Computer Science and Philosophy

Part A CoreComputer Science

Schedule S1(M&CS)(3rd years)Mathematics and Computer Science

Schedule A1(M&CS)Mathematics and Computer Science



The lectures for this course will be live via MS Teams, via the live lecture channel

Recordings will be made available on the course materials page. 

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.


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


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.


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.

Taking our courses

Matriculated University of Oxford students who are interested in taking this course, or others in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form. Priority will be given to students studying for degrees in the Department of Computer Science.