Skip to main content

Compilers:  2021-2022

Lecturer

Degrees

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

Term

Overview

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.

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.