CD · Section 7: Compiler Design
Compiler Design
Lexical analysis, parsing, syntax-directed translation, runtime environments, intermediate code and optimisation.
Topics
9 topics in syllabus order, each with study material.
The analysis and synthesis phases of a compiler, what each phase takes in and gives out, the symbol table and error handler, passes, and which phase reports which kind of error.
Tokens, lexemes and patterns, longest match and rule priority, counting tokens in C fragments, lexical errors, input buffering with sentinels, and how a regular expression becomes a DFA for the scanner.
Derivations, parse trees and ambiguity, left recursion removal and left factoring, FIRST and FOLLOW computed to a fixed point, the LL(1) table and its conflicts, predictive parsing traces and recursive descent.
Handles and shift-reduce parsing, operator precedence, LR(0) items and automata, SLR, CLR(1) and LALR(1) tables, shift-reduce and reduce-reduce conflicts, state counts, and which grammar falls in which class.
Syntax-directed definitions with synthesized and inherited attributes, S-attributed and L-attributed definitions, dependency graphs and evaluation order, and translation schemes evaluated on given inputs.
Static, stack and heap storage, activation records and the control stack, access links and displays, static and dynamic scoping, and parameter passing by value, reference, value-result and name.
Syntax trees, DAGs, postfix and three-address code, quadruples, triples and indirect triples, SSA form, array addressing, translation of control flow and Boolean expressions, and backpatching.
Leaders, basic blocks and flow graphs, loops and dominators, the DAG of a block, common-subexpression and dead-code elimination, folding, copy propagation, strength reduction, peephole rules and register counts.
The data-flow framework, reaching definitions, available expressions for global common-subexpression elimination, liveness solved backward by iteration, and constant propagation on its lattice.
Compiler Design revision: traps, patterns and last day
The Compiler Design traps sheet, the question-pattern sheet and the last-day master sheet.