Compiler Design
Compiler Design follows a program through every phase of a compiler. These lessons come with small working pieces of a compiler in Python: a scanner, FIRST/FOLLOW and LL(1) table builders, an LR(0)/SLR item-set builder, a three-address code generator, and liveness analysis, so every set, table and count in the questions is computed.
1Basics
2Front End
- Lexical AnalysisTokens, lexemes and patterns, specifying tokens with regular expressions, the longest-match and priority rules, recognising tokens with finite automata, counting tokens in a program, and lexical errors.
- Top-Down Parsing and LL(1)The parser's job, top-down parsing, eliminating left recursion and left factoring, FIRST and FOLLOW sets, building an LL(1) parsing table, table-driven predictive parsing, and recursive descent.
- Bottom-Up Parsing and LR ParsersShift-reduce parsing and handles, LR(0) items, closure and goto, the canonical collection, SLR, canonical LR(1) and LALR(1) parsers, shift-reduce and reduce-reduce conflicts, and the relative power of parsers.
- Syntax-Directed TranslationAttributes and semantic rules, synthesized and inherited attributes, annotated parse trees, S-attributed and L-attributed definitions, translation schemes with embedded actions, and evaluating them.
3Back End
- Intermediate Code GenerationWhy compilers use an intermediate representation, syntax trees and DAGs, three-address code, quadruples, triples and indirect triples, translating expressions and control flow, and static single assignment form.
- Runtime EnvironmentsHow a running program's memory is organised, activation records and the control stack, static versus dynamic scoping, access links, parameter passing (value, reference, value-result, name), and heap management.
- Basic Blocks and Code OptimizationPartitioning code into basic blocks with leaders, control-flow graphs, local optimizations (constant folding, common subexpressions, copy propagation, dead code), loop optimizations (code motion, induction variables, strength reduction), and peephole optimization.
- Data-Flow AnalysisThe data-flow framework of gen, kill, in and out sets, liveness analysis (backward), reaching definitions (forward), available expressions, constant propagation, and how each one drives an optimization.