Syllabus and synopsis (Compilers)

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search


This course aims to give a simple but practical account of the programming techniques used in implementing high-level programming languages by compiling into code for stack and register-based machines. The course is based on a working implementation, written in Objective Caml, of a compiler for a language comparable to C or Pascal.

Learning outcomes

On completion, the students should be able to:

  • Understand and explain the main techniques and algorithms used in compilers.
  • Describe the runtime structures used to represent constructs in typical programming languages.
  • Use compiler construction tools, such as parser generators, to build a simple compiler.


Programming language representation: concrete and abstract syntax, context free grammars. Use of lexer and parser generators. Implementation of expressions and statements in a simple language by postfix code and by simple machine code; simple optimizations. Procedures: value, name and reference parameters, local and non-local variables, static and dynamic binding. Abstract machines and storage management: activation records, static and dynamic chains, stacks and heaps.


The order of topics will probably change a bit to allow more time to complete the lab exercises.

  1. Introduction.
  2. Lexical analysis.
  3. Syntax analysis.
  4. Postfix code for expressions.
  5. Branching code for control structures.
  6. Semantic analysis.
  7. Data structures.
  8. Subroutines.
  9. Parameters and nested procedures.
  10. Higher-order functions.
  11. A complete compiler.
  12. Object-oriented languages.
  13. Overview of the back end.
  14. Instruction selection.
  15. Common subexpressions.
  16. Register allocation.