Syllabus and synopsis (Compilers)

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.

Prerequisites

For MSc Students: A basic knowledge of functional programming is recommended. Those with substantial programming experience should find it possible to study this course concurrently with Functional Programming.

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.

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.

Reading list

• A V Aho, R Sethi and J D Ullman, Compilers: principles, techniques and tools, Addison-Wesley.
• R Bornat, Understanding and writing compilers, available on the web.
• A W Appel, Modern Compiler Implementation in ML, Cambridge University Press.
• H Abelson and G J Sussman, Structure and Interpretation of Computer Programs, MIT Press, 2nd Edition, 1996.