Compilation Techniques (4 Credits)

Learning Outcomes:

Understanding of the challenges involved in compilation (semantic gap between input and output languages, compiler efficiency and code quality); Understanding of the phases involved in compilation, and knowledge of the techniques applied; Ability to understand design decisions in modern compilers and to justify these; Ability to develop and apply modifications to standard compilation techniques wherever this is necessary; Ability to analyze compilation tasks and to apply standard compilation techniques; Ability to implement standard compilation algorithms and understanding of the challenges involved in compilation for modern architectures and the approaches taken in modern compilers

Topics:

1. Introduction: structure of a compiler
2. Lexical analysis: tokens, regular expressions, Lex
3. Parsing: context-free grammars, predictive and LR parsing, Yacc
4. Abstract syntax: semantic actions, abstract parse trees
5. Semantic analysis: symbol tables, bindings, type-checking
6. Stack frames: representation and abstraction
7. Intermediate code: representation trees, translation
8. Basic blocks and traces: canonical trees and conditional branches
9. Instruction selection: algorithms for selection, RISC and CISC
10. Liveness analysis: solution of dataflow equations
11. Register allocation: colouring by simplification, coalescing
12. Advanced Topics: automatic parallelization, popular open-source compilers: GCC, LLVM