Compilers (The Farewell Tour)
This part of Spivey's Corner contains materials for a course on Compilers. Some pages will contain course material, and I will protect those pages from editing, so that everyone can see the material as I presented it. Each protected page will have an associated discussion page, and you are welcome to add comments there, or to make corrections or additions to any of the other pages. To make edits, you will need to create an account for yourself, but anyone with an Oxford e-mail address is welcome to participate, in a way consistent with the code of conduct.
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.
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.
- For convenience, the tutorial exercises are provided in a separate document on another page, with some advice about what problems are appropriate for each tutorial.
- 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.