COMP3012/G53CMP Compilers 2018/19

Model answers for the exam now on-line!

Overview
Literature Lectures Lecture Links
Coursework Coursework Links Forum
Examination References

Overview


Literature

There is no main reference for the module, but you will likely find it useful to have a book to give you an additional perspective on and more depth to the material covered, as well as a help to understand some of the harder topics. Some suggestions below.

The book Programming Language Processors in Java [WB99] by Watt & Brown was the main reference for the precursor of this module (G52CMP). Because we now have switched to Haskell-based coursework, this book is less relevant than it was. However, the lectures largely still follow the structure of Watt & Brown, and the coursework is partly based on the compiler it presents. Also, where appropriate, the suggested reading for each lecture will include references to this book.

The main advantages of Watt & Brown is its hands-on approach to compiler construction, with a particular emphasis on software engineering aspects, and that it is clearly written. It is also a good book if you like Java and would like to get an understanding of how a compiler might be structured in an object-oriented language. Watt & Brown is a bit weak on linking the theory with practice, though. The lectures will aim at filling in some of the gaps. There are several errors in the book. Consult the authors' web pages for corrections.

The book Compilers: Principles, Techniques, and Tools [ASU86] ("The Dragon book") by Aho, Sethi, & Ullman is a classic in the field, well worth having as a reference book. It covers much more ground in much greater depth than does this module, but it is a great supplement to Watt & Brown and will last you many years.

There is a new (2007) edition of this book, by Aho, Lam, Sethi, and Ullman (Pearson International Edition) [ALSU07]. It is a bit more accessible and it has been updated in many respects. Sadly, the cover no longer features the Dragon!

The book Engineering a Compiler [CT04] by Cooper & Torczon is more recent and consequently in many ways more up-to-date than the Dragon Book. It also covers much more ground in more depth than does this module, but has a more applied focus compared with the Dragon Book. Together with the on-line lecture notes for this module, it is a viable alternative to both Watt & Brown and the Dragon Book, and I am increasingly relying upon it. I will provide references to it for most of the lectures.

The lectures on types and type systems closely follow the first few chapters of the book Types and Programming Languages [Pie02] by Pierece. This is a very good book for those who would like to learn more about types and type systems in the context of programming languages.

If you need to brush up on your Haskell knowledge, I recommend Programming in Haskell [Hut16], by our own Dr. Hutton. The library should have plenty of copies, and so should the local bookshop.

Another great introduction to Haskell (which is also highly entertaining) is Miran Lipovača's Learn You a Haskell for Great Good [Lip11]. Can be bought or read on-line for free!

Should you need more Haskell introductory material, you can also check out:

You may also find it helpful to revise the G52LAC lecture notes on formal languages, regular expressions, context-free grammars, various kinds of automata, and parsing [ACN17].

Wondering how to debug your Haskell programs? Well, there are a number of options. On possibility, while it has certain drawbacks, is the traditional, procedural debugger integrated in GHCi 6.8.1 or later. You can read more about it in Bernie Pope's article in issue 10 of the Monad.Reader [POP08].


Lectures

Somewhat preliminary, especially towards the end.

Lecture#DateContentReading
1 4 Oct Administrative Details and Introduction [WB99, ch. 1–3; CT04, ch. 1]
2 4 Oct Defining Programming Languages [WB99, ch. 1–4; CT04, ch. 1–3; Nil10a]
-- 11 Oct No lectures!
3 18 Oct Syntactic Analysis: Bottom-Up Parsing [WB99, ch. 4; CT04, ch. 3]
4 18 Oct Syntactic Analysis: Parser Generators [WB99, ch. 4; CT04, ch. 3]
5 25 Oct Contextual Analysis: Scope I [WB99, ch. 5; CT04, ch. 4, ch. 5.7]
6 25 Oct Contextual Analysis: Scope II [WB99, ch. 5; CT04, ch. 4, ch. 5.7]
7 1 Nov A Versatile Design Pattern: Monads [Nil10b, Nil10c]
8 1 Nov Contextual Analysis: Types and Type Systems I [WB99, ch. 5; CT04, ch. 4]
9 8 Nov Contextual Analysis: Types and Type Systems II [WB99, ch. 5; CT04, ch. 4]
10 8 Nov Contextual Analysis: Implementing A Type Checker [WB99, ch. 5; CT04, ch. 4]
11 15 Nov Code Generation I [WB99, ch. 7 & 9; CT04, ch. 9.2, 13]
12 15 Nov Code Generation II [WB99, ch. 7 & 9; CT04, ch. 9.2, 13]
13 22 Nov Code Generation II (cont.) [WB99, ch. 7 & 9; CT04, ch. 9.2, 13]
14 22 Nov Run-Time Organisation I [WB99, ch. 6; CT04, ch. 6, 7.1–7.7, 7.9]
15 29 Nov Run Time Organisation II [WB99, ch. 6; CT04, ch. 6, 7.1–7.7, 7.9]
16 29 Nov Code Optimization [WB99, ch. 9; CT04, ch. 8, ch. 10]
17 6 Dec Register Allocation [WB99, ch. 7 & 9; CT04, ch. 7.8, 7.9]
18 6 Dec Register Allocation (cont.) [WB99, ch. 7 & 9; CT04, ch. 7.8, 7.9]
19 13 Dec LLVM: A Real Compiler Backend


Lecture Links

Copies of electronic slides, any major pieces of program code, other electronic material used during the lectures, and useful links can be found here.


Coursework

The coursework counts for 25 % of the total mark (unless you have to resit the module, in which case it does not count). It consists of solving some theoretical and practical programming problems, mainly in the context of a simple compiler for the language MiniTriangle from Watt & Brown. The exact details will be available shortly through the coursework links below. It is to be carried out individually. You are welcome to discuss the coursework with friends, but, in the end, you must solve the problems on your own and your solutions will be assessed individually, in part orally in person.

The coursework is divided into two parts, I & II. A short written report has to be submitted for each part (hard copy to the Student Support Centre) along with a PDF-copy of the report and an archive of the complete source code for your solution (electronically, via Moodle). Important! See detailed submission instructions in the coursework descriptions.

For part I of the coursework, the hard copy of your report will be marked and be handed back to you as feedback during one of the lab sessions. Model solutions for the programming problems will also be released to allow you to critically asses your own solution. You are of course also welcome to ask questions in person during the lab sessions if there is anything that is not clear.

Part II of the coursework is additionally subject to an oral examination. This will take place in an assigned slot during one of the lab sessions. The oral examination serves both to give you timely, personal feedback on your work, and to assess that you have understood what you have done through discussing and explaining your solution. Note that the oral examination is compulsory: your written solution for Part II will not be taken into account unless the examination has taken place and you demonstrated that you can explain your solution to each coursework task in a clear and concise manner. The mark for a solution that is not satisfactorily explained will be reduced; in case you cannot explain at all, no marks will be awarded, regardless of the preliminary marks for the written solution.

The coursework-related dates are as follows:

The schedules for the oral examinations, along with other practical information, is or will be available via the module web pages (TBA) Important! Catch-up slots will only be allocated if you missed your slot with good cause; you need to explain to your personal tutor and ask him/her to make a request to the G53CMP module convener on your behalf.

To support you, course staff will be at hand during the laboratory sessions from 19 October onwards.

There is also a G53CMP forum where you can ask questions about the coursework, or help answering questions! However, we do ask that you do not post direct solutions to coursework questions.

Finally, should you feel that your Haskell knowledge could do with a brush-up, we do recommend the various Haskell resources mentioned in the section on literature above, and trying your hand on the (unassessed) Haskell and GHC revision coursework available here [NS13].


Coursework Links

The coursework descriptions, model answers, results, etc. will be linked from here.

Coursework support will be at hand during the laboratory sessions (from 19 October). Please direct further coursework-related questions to the G53CMP forum.

Christopher Birmingham has written a Vim plugin for MiniTriangle syntax highlighting and more. MiniTriangle programs never looked so good! Available here.


G53CMP Web Forum

A Moodle Forum for G53CMP has been set up.

The forum is intended for asking questions about and discussing aspects of G53CMP, like the coursework. It is monitored by the G53CMP team, and we'll endeavour to answer any outstanding questions reasonably quickly. However, any one is free to contribute to the discussions and help with answering questions. Indeed, in the spirit of an on-line forum, you are encouraged to do so!

Of course, we do ask that you do not post the exact solutions to the coursework. The point of the coursework is that you should ultimately solve the problems yourselves so that you know what you have understood and what you need to work more on or ask about.


Examination

Some basic information about the exam. For the first sit:

In the case of a resit examination:

Some past exams:

Model solutions for the above past exams:


References


Last updated 30 January 2019.