Compilers

NB: For MSc Students Only

A basic knowledge of Java is recommended.

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

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

• 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.

• 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.

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.