Compilers (The Farewell Tour)
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 languageA symbolic representation of the machine code for a program., using registers, addressing modes and calling conventions to make a correct and efficient translation of source language constructs.
Everything you need to follow the course is contained in one handy coursebook, including
- Notes for the lectures.
- Problems for the classes.
- Instructions for the lab exercises.
- Appendices containing extra information about the OCaml language and the Keiko and ARM machines.
- Listings of relevant parts of the compilers used for the lab exercises.
- A course outline with the subject of each lecture.
The tutorials and labs
As a Core course, Compilers will be supported by tutorials organised by colleges. There will also be a sequence of four lab exercises, leading up to a practical assessment carried out during the Christmas vacation.
- The tutorial exercises are contained in the coursebook, and for convenience they are also accessible as a separate document on another page, with some advice about what problems are appropriate for each tutorial.
- Instructions for the labs are also contained in the coursebook, and practical arrangements are set out on their own page.
The burning questions
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).
- In addition, a glossary gives definitions of terms used in the course. Feel free to suggest new entries!
The reading list
- The coursebook contains most of what you need to know to follow the course, including notes on the lectures, instructions for the practical exercises, and appendices describing the instruction sets of the Keiko machine and the ARM, together with listings of relevant modules of the lab compilers.
Some other books:
- The book Modern Compiler Implementation in ML by Andrew Appel (Cambridge) is closest to this course, except that the ML dialect he uses is Standard ML, and not OCaml. There are two translations of the book that use respectively Java and C as the implementation language, but in each case something is lost in the translation.
- The classic text Compilers: principles, techniques and tools by Aho, Hopcroft and Ullman (Addison–Wesley). Either the original 1977 edition or the second edition of 2006 (with Monica Lam) will do. I've been referring to the 1977 edition, but as far as I can see, little of the common material has changed in the second edition.
- Although it differs in many details, Richard Bornat's classic book is close to the course in spirit. I recommend it for supplementary reading.
- In later parts of the course, you might like to look at the reference manual for the ARM architecture. (This edition is not the latest, but it is the first to describe the ARMv6 instruction set we shall target. Later editions have become steadily more complicated as they describe more different variants of the ARM.)
- The Revised Report on Algol 60 is the first significant language description to use context free grammars to define the syntax of a programming language. Knuth's paper The remaining trouble spots in Algol 60 fixes the very few problems in the Revised Report.
- For tutorial material on OCaml, there is a copy online of the O'Reilly book Real World OCaml by Yaron Minsky, Anil Madhavapeddy and Jason Hickey.
Part of the assessment for the course will be a traditional sit-down exam at the end of Trinity Term, but another part is a take-home practical assignment completed over Christmas that counts for 35% of the marks. The assignment will be based on the lab exercises you have completed during the term, so it's vital that you take the maximum advantage of the help offered by demonstrating staff during the term.
- Details of the format of the assignment are given in a Notice to Candidates issued by the examiners.
- The assignment will appear on Friday of Eighth Week.
- The plan is to have a programming exercise that will address all phases of the course: lexical and syntax analysis, semantic analysis, intermediate code generation and machine code generation. It will be based on the compiler in Lab 4, and will involve generating code for the ARM.
- To complete the assignment, you will need access to a Linux-based software environment similar to the one we use in the labs. There's a page with suggestions and instructions for how to set this up, with a choice between a real Linux machine, a Linux installation running under VirtualBox (with its own page of setup instructons), or a Raspberry Pi. It's best to get things set up before you leave Oxford for the vacation: then we can help you to sort out any problems before we are miles apart. Doing the assignment in Oxford using the lab machines, or (perhaps less reliably) using remote access over SSH are also options.
- Candidates will be asked to prepare and submit a report showing the changes they made to the compiler to satisfy the requirements. The kind of report that is wanted is shown by a sample report, describing an exercise that is similar in kind to the actual assignment, but a bit simpler.
There's a page for tutors giving more information about the assignment.