Compilers (The Farewell Tour)
This part of Spivey's Corner contains materials for a course on Compilers that I gave on and off between 2000-ish and 2023. I've added answers to the tutorial and lab exercises in the course book, and I've also begun to protect the pages from editing so that the site is a faithful record of the course as I last gave it. If you'd like to add to the list of frequently asked questions or make a suggestion, please get in touch by e-mail.
The material you see here is as I last presented it in Michaelmas Term 2023, possibly with future corrections and improvements. If others continue to use the material in the future, for a course at Oxford or elsewhere, you should look on the relevant official website for information about what content is to be covered, and the detailed conventions that apply.
This course will show you one way to build a compiler for an ordinary programming language (like Pascal or C) that generates reasonably good code for a modern machine (the ARM). To make the task manageable, we will write the compiler in a functional style in quite a high-level language (OCaml), and we will use power tools (Lex and Yacc) to automate the easy part – analysing the syntax of the input language. The designs we create can also be used to implement hand-crafted compilers without the benefit of these power tools.
Our compiler will be organised for clarity, being structured as the functional composition of many small passes, each carrying out one part of the compiling task. This organisation allows us to focus on the representations of the program being compiled that are handed from one pass to the next, understanding each pass in terms of the transformation it must achieve. The course doesn't aim to be a survey of all the ways the task might be done, though occasionally we will pause to mention other choices we might have made. Because we will be building a big-ish program, we will naturally want to deploy some of the technical means to deal with large-scale software development: a version control system to keep track of the changes we make, automated building (using Make), and automated testing against a stored corpus of test cases.
The course will bring us into contact with some of the major theoretical and practical ideas of Computer Science. On the theoretical side, we will be using regular expressions and context free grammars to describe the structure of source programs (though relying on automated tools to construct recognisers for us), and we will find a use for many algorithms and data structures. Practically speaking, we will need to deal with the target machine at the level of assembly language, using registers, addressing modes and calling conventions to make a correct and efficient translation of source language constructs; and we shall be using the standard software tools of (Unix-based) software development, including Makefiles and a version control system, in addition to a home-grown setup for automated regression testing.
Course materials
- Syllabus and synopsis.
- Notes for the lectures, instructions for the practicals, and problems for the tutorials are collected in a single 'coursebook'. There are appendices giving extra information about the OCaml language we will use to write compilers, and the Keiko and ARM machines we will use as targets.
- A separate course outline lists the subject of each lecture.
- Problems appear at the end of chapters in the coursebook, and my solutions can be found on the general solutions page.
- Arrangements for the lab sessions are also set out on their own page.
- A Mercurial server provides code for the labs.
- There is a page of frequently asked questions that contains the answers to all your questions (or will do so shortly after you ask them), and a glossary with definitions of terms used in the course. Feel free to suggest new entries!
- The course culminates in a practical assignment done over Christmas. A separate page has the instructions and some partial solutions to assignments set in the past, plus practical hints for carrying out the task and presenting the results.
- A reading list suggests books that might be helpful, and background reading for the Christmas assignment.