Skip to main content

Compilers:  2009-2010

Lecturer

Degrees

Schedule S1(3rd years)Computer Science

Schedule B1Computer Science

Schedule B1(M&CS)Mathematics and Computer Science

ECS Part IIMEng Engineering and Computing Science

Schedule AMSc in Advanced Computer Science

MSc by Research

Term

Overview

This course aims to give an introduction into compiler construction, covering the main phases of compilation. Main techniques for each phase will be described in the context of modern imperative languages and some studied through practical exercises

Learning outcomes

On completion, the students should be able to:

  • Understand and explain the main techniques and algorithms used in compilers
  • Appreciate the main issues in each phase of compilation
  • Use compiler construction tools, such as parser generators

Prerequisites

For MSc Students - A basic knowledge of Java is recommended.

Synopsis

  • Compilers and interpreters. Phases of compilation.
  • Lexical analysis. Tokens. Regular expressions. Deriving DFA from regular expressions. Symbol table.
  • Syntax analysis. Context-free grammars. FIRST and FOLLOW sets. LL(1) parser. Shift-reduce parsing. Conflicts. LR(1) and LALR(1) parsers.
  • Semantic analysis. Attribute grammars. Syntax-directed definitions. Abstract vs concrete syntax trees.
  • Type checking. Type systems (polymorphism, overloading, coercion). Rules for type checking. Type inference.
  • Run-time environments. Procedures and parameter passing. Scope rules. Static vs dynamic binding. Stack and activation records. Translation to intermediate code. Types of intermediate representations.
  • Translation into trees (variable declarations, control flow, function calls). Classes and objects.
  • Basic blocks and flow graphs. Transformations on tree representation (canonical trees, tree rewrites, linearisation). Control flow graphs.
  • Instruction selection. RISC/CISC architecture. Simple machine code. Code generation by tiling.
  • Optimisation. Data flow analysis schema. Iterative solution. Reaching definitions. Transformations using dataflow analysis, e.g. dead code elimination. Live variable analysis. Loop optimisation.
  • Register allocation. Code generation by graph colouring algorithm.
  • Pipelining and scheduling. Instruction-level parallelism. Software pipelining algorithm.

Syllabus

  • Phases of compilation. 
  • Context free grammars. 
  • Programming language representation: concrete and abstract syntax. 
  • Top-down and bottom-up parsing. 
  • Use of lexer and parser generators. 
  • Type checking: type systems and inference. 
  • Procedures and parameter passing. 
  • Run-time system: activation records, stacks and heaps. 
  • Intermediate code generation: types of intermediate code, translation of declarations, control flow and function calls. 
  • Code generation: RISC/CISC architecture, instruction selection, register allocation. 
  • Optimisation: basic blocks and control flow graphs, data flow equations, liveness analysis, loop optimisation.

Reading list

Main Text
  • Alfred V. Aho, Monica S Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, techniques, and Tools, 2nd edition. Pearson 2007 (paperback).
Further Reading
  • Andrew W. Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. CUP 2002.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.