Latest News

Staff

Conveners Tutor
Dr Alban Grastien Felix Friedlander
Professor Tony Hosking  

Timetable

Day Time Activity Location Mode
Mondays 11am-1pm Lecture A DA Brown Building 47 108+110 In-person & on-line
Tuesdays 12noon-2pm Lecture B Birch Building 35 1.43 In-person & on-line
Wednesdays 11am-1pm Lab 1 CSIT Building 108 N111 In-person & on-line
Fridays 4pm-6pm Lab 2 CSIT Building 108 N114 In-person only

Lectures

You will get the most from this course by attending live lectures. Lectures will be delivered live in-person and on-line, but also recorded for those unable to attend live. You should attend both lectures each week.

Labs

The course is structured around a major software project to build a compiler for a simple but non-trivial programming language. Labs will be where you practise the techniques you learn from lectures, using appropriate tools to construct the compiler. Java is the implementation language in the course. You should attend one 2-hour lab each week. While we do support on-line lab attendance, we strongly recommend attending in-person if at all possible.

Synopsis

The theory and practice of programming language translation, compilation, and run-time systems, organized around a significant programming project to build a compiler for a simple but non-trivial programming language. Modules, interfaces, tools. Data structures for tree languages. Lexical analysis, syntax analysis, abstract syntax. Symbol tables, semantic analysis. Translation, intermediate code, basic blocks, traces. Instruction selection, CISC and RISC machines. Liveness analysis, graph coloring register allocation. Supplemental material drawn from garbage collection, object-oriented languages, higher-order languages, dataflow analysis, optimization, polymorphism, scheduling and pipelining, memory hierarchies.

Learning Outcomes

Upon successful completion, students will have the knowledge and skills to:

  1. Explain how programs that process other programs treat the other programs as their input data. Describe the benefits of having program representations other than strings of source code.
  2. Distinguish a language definition (what constructs mean) from a particular language implementation (compiler vs. interpreter, run-time representation of data objects, etc.). Distinguish syntax and parsing from semantics and evaluation.
  3. Use formal grammars to specify the syntax of languages. Describe an abstract syntax tree for a small language. Identify key issues in syntax definitions: ambiguity, associativity, precedence.
  4. Use declarative tools to generate parsers and scanners. Write a program to process some representation of code for some purpose, such as an interpreter, an expression optimizer, or a documentation generator.
  5. Implement context-sensitive, source-level static analyses such as resolving identifiers to identify their binding occurrences and type-checking of program constructs.
  6. Sketch a low-level run-time representation of core language constructs, such as objects or closures. Explain how programming language implementations typically organize memory into global data, text, heap, and stack sections and how features such as recursion and memory management map to this memory model. Explain the use of metadata in run-time representations of objects and activation records, such as class pointers, array lengths, return addresses, and frame pointers.
  7. Identify all essential steps for automatically converting source code into assembly or other low-level languages. Generate the low-level code for calling functions/methods in modern languages. Discuss why separate compilation requires uniform calling conventions. Discuss why separate compilation limits optimization. Discuss opportunities for optimization introduced by naive translation and specific techniques, such as instruction selection, instruction scheduling, register allocation, and peephole optimization.
  8. Define useful static analyses in terms of a conceptual framework such as data-flow analysis. Use the results of a static analysis for program optimization.

Prerequisites

To enroll in this course you should have completed the following courses with at least a credit grade:

References

The recommended course text is “the tiger book” by Andrew Appel and Jens Palsberg.1

Additional references include “the dragon book”2 and Engineering a Compiler.3

  1. Modern Compiler Implementation in Java, Second Edition Second Edition, Andrew W. Appel and Jens Palsberg, Cambridge University Press, 2002, 978-0521820608. ↩

  2. Compilers: Principles, Techniques, and Tools Aho, Lam, Sethi, Ullman, Addison-Wesley, 2007, 978-0133002140 ↩

  3. Engineering a Compiler, Third Edition, Keith D. Cooper and Linda Torczon, Elsevier, 2022, 978-0128154120 ↩

arrow-right bars search times arrow-up