Compilers: 2011-2012
Information
|
Lecturer |
|
|
Degrees |
Part A Options — Honour School of Computer Science Schedule B1 — Honour School of Computer Science Schedule B1 — Honour School of Mathematics and Computer Science |
|
Term |
Hilary Term 2012 (16 lectures) |
Overview
MSc students will be assessed by invigilated exam lasting approximately 2 hours in week 0 of TT.
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.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.