Compilers
Building an optimizing compiler for a small imperative language, Tern: scanning with regular expressions, Thompson NFAs, the subset construction and DFA minimization; context-free grammars, FIRST and FOLLOW sets, LL(1), recursive-descent and Pratt parsing; LR(0), SLR(1) and LALR(1) parsing and conflicts; abstract syntax trees, symbol tables and scopes; type checking and type inference by unification; three-address code, basic blocks and control-flow graphs; dominators and static single assignment form; stack frames, calling conventions, closures and the compiler's role in garbage collection; instruction selection by tree tiling, register allocation by interference graphs and linear scan, and instruction scheduling; data-flow analysis, lattices and loop optimization; and a capstone end-to-end compiler to RISC-V, with JIT compilation, compiler testing and verification, security hardening and the LLVM and GCC toolchain.
CMPUT-415 Year 4 3 credits 12 lessons · 7 h 27 min
Offered by HSM University · Computing Science
What you'll learn
- Explain the phases of a compiler, the representations passed between them, and how compilers, interpreters and JIT compilers divide translation and execution.
- Construct NFAs from regular expressions, convert them to minimal DFAs, and write a scanner that applies maximal munch and recovers from lexical errors.
- Transform context-free grammars for predictive parsing, compute FIRST and FOLLOW sets and LL(1) tables, and write recursive-descent and Pratt parsers.
- Build LR(0) item sets and SLR(1) tables, trace shift-reduce parses, and diagnose and resolve shift/reduce and reduce/reduce conflicts.
- Design an abstract syntax tree and implement name resolution with nested scopes, symbol tables and multi-pass semantic analysis.
- Implement a type checker from type rules, including error recovery and return checking, and infer types by unification.
- Lower an AST to three-address code, compile conditions with short-circuit jumps, and partition code into basic blocks and a control-flow graph.
- Compute dominators and dominance frontiers, construct SSA form by φ placement and renaming, and translate out of SSA correctly.
- Lay out stack frames under a calling convention, provide access to non-local variables, and describe the compiler's role in garbage collection.
- Select instructions by tree tiling, perform liveness-based register allocation by graph colouring and linear scan, and explain instruction scheduling.
- Formulate and solve data-flow problems with lattices and worklists, and apply local, global and loop optimizations safely.
- Assemble an end-to-end compiler and explain JIT compilation, compiler testing and verification, security hardening and the modern toolchain.
Course content
12 lessons · 7 h 27 min total · final exam
- 1 What compilers do and how they are built 37 min · quiz
- 2 Lexical analysis 38 min · quiz
- 3 Context-free grammars and top-down parsing 37 min · quiz
- 4 Bottom-up parsing 38 min · quiz
- 5 Abstract syntax trees and semantic analysis 36 min · quiz
- 6 Type checking and type inference 37 min · quiz
- 7 Intermediate representations and control-flow graphs 36 min · quiz
- 8 Static single assignment form 36 min · quiz
- 9 Runtime environments and memory management 37 min · quiz
- 10 Code generation and register allocation 34 min · quiz
- 11 Optimization and data-flow analysis 37 min · quiz
- 12 Capstone: an end-to-end compiler, JITs, correctness and the modern toolchain 44 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
Building an optimizing compiler for a small imperative language, Tern: scanning with regular expressions, Thompson NFAs, the subset construction and DFA minimization; context-free grammars, FIRST and FOLLOW sets, LL(1), recursive-descent and Pratt parsing; LR(0), SLR(1) and LALR(1) parsing and conflicts; abstract syntax trees, symbol tables and scopes; type checking and type inference by unification; three-address code, basic blocks and control-flow graphs; dominators and static single assignment form; stack frames, calling conventions, closures and the compiler's role in garbage collection; instruction selection by tree tiling, register allocation by interference graphs and linear scan, and instruction scheduling; data-flow analysis, lattices and loop optimization; and a capstone end-to-end compiler to RISC-V, with JIT compilation, compiler testing and verification, security hardening and the LLVM and GCC toolchain.
Part of the Science stream, typically taken in year 4.