G52CMP Compilers

This module has been replaced by G53CMP

Spring 2010

Model answers for the exam now on-line!

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 used to be the main reference for the module. 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]. I have not had a chance to look at it in detail, but it looks a bit more accessible, and it has been updated in many respects. Would likely work well with this module and worth checking out. 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 is probably a bit more accessible and a bit lighter on theory than 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. It will probably end up being the closest there is to a main reference book, and I will try to 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 [Hut07], fresh from the presses by our own Dr. Hutton. The library should have plenty of copies, and so should the local bookshop.

You may also find it helpful to revise Dr. Altenkirch's and my G52MAL lecture notes on formal languages, regular expressions, context-free grammars, various kinds of automata, and parsing [AN07].

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]. (Unfortunately, the current GHC version installed on the School's Unix servers is only 6.6. But we hope to have a more up-to-date version installed on the School's Windows computers soon.)


Lectures

Lecture#DateContentReading
1 26 Jan Administrative Details and Introduction [WB99, ch. 1--3; CT04, ch. 1]
2 27 Jan Haskell Overview [Hut07]
S1 29 Jan Coursework Support Lecture 1
3 & 4 2 & 3 Feb A Complete (Albeit Small) Compiler [WB99, ch. 1--3; CT04, ch. 1--3]
5 9 Feb Defining Programming Languages I [WB99, ch. 1--4; CT04, ch. 1--3]
6 10 Feb Defining Programming Languages II [WB99, ch. 1--4; CT04, ch. 1--3]
7 16 Feb Syntactic Analysis: Bottom-Up Parsing [WB99, ch. 4; CT04, ch. 3]
8 17 Feb Syntactic Analysis: Parser Generators [WB99, ch. 4; CT04, ch. 3]
9 23 Feb Contextual Analysis: Scope I [WB99, ch. 5; CT04, ch. 4, ch. 5.7]
10 24 Feb Contextual Analysis: Scope II [WB99, ch. 5; CT04, ch. 4, ch. 5.7]
S2 26 Feb Coursework Support Lecture 2 [Hut09, Nil06]
11 2 Mar Contextual Analysis: Types and Type Systems I [WB99, ch. 5; CT04, ch. 4]
12 3 Mar Contextual Analysis: Types and Type Systems II [WB99, ch. 5; CT04, ch. 4]
13 9 Mar Contextual Analysis: Implementing A Type Checker [WB99, ch. 5; CT04, ch. 4]
14 10 Mar Contextual Analysis: Implementing A Type Checker [WB99, ch. 5; CT04, ch. 4]
15 16 Mar Code Generation I [WB99, ch. 7 & 9; CT04, ch. 9.2, 13]
16 17 Mar Code Generation I cont. [WB99, ch. 7 & 9; CT04, ch. 9.2, 13]
17 23 Mar Code Generation II [WB99, ch. 7 & 9; CT04, ch. 7.8, 7.9]
18 24 Mar Run Time Organisation [WB99, ch. 6; CT04, ch. 6, 7.1--7.7, 7.9]
19 30 Mar Code Optimization (Lecturer: George Giorgidze) [WB99, ch. 9; CT04, ch. 8, ch. 10]
20 31 Mar Code Optimization (Lecturer: George Giorgidze) [WB99, ch. 9; CT04, ch. 8, ch. 10]


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.

Please direct any questions regarding what has been discussed during the lectures to the G52CMP forum or to the mailing list g52cmp-faq@cs.nott.ac.uk.


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, partly in the context of a simple compiler for the language MiniTriangle from Watt & Brown. It is to be carried out individually or in pairs. Note that, while you may work in pairs, the assessment is still individual: see below.

To support you, two lectures specifically addressing various aspects of the coursework and the provided coursework compiler have been scheduled:

(these are G52GRP slots).

Moreover, course staff will be at hand during the laboratory sessions at the following times to help you with the coursework. Unless indicated otherwise, staff will be present during the entire session, 11:00--13:00:

There is also a G52CMP 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. There is also a mailing list g52cmp-faq@cs.nott.ac.uk which can be used to ask questions. (Questions and answers of general interest might form the basis for a forum post or additions to the FAQ.)

You should decide whether you would like to work individually or in a pair and inform the head TA Neil Sculthorpe by sending an e-mail on or before 11 February. If you would like to work in a pair, send a single e-mail with the two names and e-mail addresses. If you would like to work individually, send an e-mail explicitly stating that you intend to do this. The subject should read "G52CMP: groups".

The coursework is divided into two parts. Individual reports must be submitted for each part, and each individual must submit their own work in person, and sign for it. However, pairs should submit their individual reports bundled together. This means that both people need to be present when handing in. The hand-in deadlines are:

If you work in a pair, then the submitted solutions must state explicitly the name of the other person with whom the work has been done.


Coursework Links

The coursework description , code, further information about practical aspects of the coursework, clarifications, tips, FAQ, etc. can be found on the coursework web page.

Please direct regarding the coursework (that are not alreday answered by the G52CMP web pages, in particular, the FAQ) to the web forum (see below).


G52CMP Web Forum

A School Web Forum for G52CMP has been set up. It's accessible via the School of Computer Science intranet by clicking on School Forum to the left. After having logged in, select Teaching, and then G52CMP-2009/10. Or follow this direct link.

The forum is intended for asking questions about and discussing aspects of G52CMP, like the coursework. It is monitored by the G52CMP 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:

Past examination papers can be found by logging in to the Portal and then using the Library Tab to search for Exam Papers. Or follow this link.

Model answers to some past exams can be found here:


References


Last updated 8 June 2010.