Compiler Design

Phases of a compiler

What a compiler is and the phases it is built from: lexical, syntax and semantic analysis, intermediate code, optimisation and code generation, the symbol table and error handling, front end and back end, phases versus passes, and which phase catches which error.

Lexical analysis

How the scanner turns characters into tokens: tokens, lexemes and patterns, regular expressions for token classes, the longest-match and rule-priority rules, keywords versus identifiers, input buffering, the symbol table, lexical errors and what a lexer cannot check; with token-counting practice.

Ambiguity, left recursion and left factoring

Preparing a grammar for parsing: recognising ambiguous grammars, removing ambiguity by precedence and associativity layers and the matched-unmatched rule for dangling else, eliminating immediate and indirect left recursion, and left factoring, with the effect of each on the parse tree.

FIRST and FOLLOW sets

Nullable symbols, FIRST of a symbol and of a string, FOLLOW of a nonterminal with the end marker, the rules and the fixed-point algorithm that computes them, worked by hand and animated pass by pass, and how they decide whether a grammar is LL(1).

Top-down parsing and LL(1)

Top-down parsing as a leftmost derivation, predictive parsing with a stack and a table, building the LL(1) table from FIRST and FOLLOW, the LL(1) condition and its common failures, a full parse trace, and error detection and recovery.

Shift-reduce parsing and handles

Bottom-up parsing as a rightmost derivation in reverse: the stack and input, the four actions shift, reduce, accept and error, handles and handle pruning, viable prefixes, and the shift-reduce and reduce-reduce conflicts that make a grammar unusable for a deterministic shift-reduce parser.

Bottom-up parsing and LR

The LR parser: the stack of states and symbols, the ACTION and GOTO tables, the parsing algorithm and its configurations, what LR(k) means and why it is the most general deterministic bottom-up method, error detection, and an overview of the four table constructions LR(0), SLR(1), LALR(1) and LR(1).

LR(0) and SLR(1) construction

LR(0) items, the augmented grammar, closure and goto, the canonical collection and its automaton of viable prefixes, the LR(0) table and its conflicts, and the SLR(1) table that reduces only on FOLLOW; with state counting and the standard grammar that is not SLR(1).

CLR(1) and LALR(1)

LR(1) items with lookaheads, the closure rule, the canonical LR(1) automaton and table, the merging of states with equal cores that gives LALR(1), what merging can and cannot break, state counts, and a grammar that is LR(1) but not LALR(1).

Operator precedence parsing

How a parser decides the grouping of an expression: precedence and associativity of operators, the relations between terminals that drive an operator precedence parser (operator grammars, the push and reduce relations, the parser run step by step), how the same rules are written in a grammar or declared to yacc, how yacc resolves shift-reduce conflicts of an ambiguous grammar, and how the value of an expression depends on the table.

Parser power hierarchy and conflicts

How LL(1), LR(0), SLR(1), LALR(1) and LR(1) compare: the containments between grammar classes, what each method needs from the grammar, table sizes, error detection, how conflicts arise and are resolved, and a procedure for deciding which class a grammar belongs to, with a computed table of eight grammars.

Syntax-directed definitions: synthesized and inherited attributes

Syntax-directed definitions: attributes attached to grammar symbols, semantic rules attached to productions, synthesized and inherited attributes, annotated parse trees, the dependency graph and circular definitions, with the desk calculator, binary numbers and declaration types as examples.

S-attributed, L-attributed and evaluation orders

How an SDD is evaluated: topological orders of the dependency graph, S-attributed definitions evaluated bottom-up during LR parsing, L-attributed definitions evaluated in one depth-first left-to-right pass (recursive descent), the exact condition for L-attributed rules, and a definition that is well defined but not L-attributed.

Translation schemes and semantic actions

Syntax-directed translation schemes: semantic actions embedded in productions, postfix schemes run at reductions, rules for placing actions so that attribute values are available, running a scheme with an LR parser and with an LL(1) parser, and the standard infix-to-postfix translation.

Runtime environments and activation records

How procedure calls are implemented at run time: activations and the activation tree, the control stack, the fields of an activation record, calling and return sequences, static (lexical) and dynamic scoping, access links for nested procedures, and counting activations and stack depth of recursive programs.

Storage organisation: static, stack and heap

Where the compiler puts the data of a running program: static storage fixed at compile time, the stack of activation records, and the heap; what each language feature forces (recursion needs a stack, not a heap; procedures returned as values and dynamic data structures need a heap; static allocation alone cannot support recursion), dangling references, the layout of a process, and how much stack a recursion uses.

Parameter passing modes and access links

How actual parameters reach a procedure: call by value, call by reference, copy-restore (value-result) and call by name with thunks, what each does to aliasing and to the caller's variables, Jensen's device, and how nested procedures reach non-local data through access links or a display.

Intermediate code generation

Why compilers use an intermediate representation, the usual forms (syntax trees, DAGs, postfix notation, three-address code), translating expressions to three-address code with temporaries by a syntax-directed definition, array address calculation and the role of types and declarations.

Three-address code, quadruples and triples

The instruction set of three-address code (assignments, copies, jumps, indexed and pointer operations, procedure calls) and its three storage formats: quadruples, triples and indirect triples, with their trade-offs for optimisation and counting questions.

Translating expressions and control flow, backpatching

Translating boolean expressions as jumping code with short-circuit evaluation, the fall-through label, if, if-else and while statements, and the single-pass method of backpatching with truelists, falselists, nextlists and marker nonterminals, with counting questions.

Basic blocks and control flow graphs

Dividing three-address code into basic blocks by finding leaders, the control flow graph with its edges, entry and exit, and the loop vocabulary (dominators, back edges, natural loops), with counting questions on blocks and edges.

Local optimisation

Optimising inside a basic block: common subexpression elimination, copy propagation, constant folding, algebraic simplification and strength reduction, dead-code elimination, renaming and reordering, local value numbering as a systematic method, and peephole optimisation.

DAG representation of basic blocks

The directed acyclic graph of a basic block: leaf nodes for initial values, interior nodes for operations, identifiers attached as labels, the construction algorithm, how it finds common subexpressions and dead code, regenerating code from the DAG, and counting nodes and edges.

Data flow analysis framework

The common structure of global data flow analyses: data flow values at program points, transfer functions per block, direction, the meet operator and boundary values, the iterative algorithm and why it terminates, monotone and distributive frameworks, meet over paths versus the iterative solution, and the table of the four standard analyses.

Reaching definitions and constant propagation

Reaching definitions (gen, kill, the equations, use-definition information) and constant propagation on the lattice of undefined, constant and not-a-constant values, with the transfer function, the meet, a worked flow graph, and the example that shows constant propagation is not distributive.

Liveness analysis

Live variable analysis: definition of liveness, use and def sets, the backward equations with union, the iterative solution on a flow graph, dead assignments, and the uses in dead-code elimination and register allocation.

Available expressions and common sub-expression elimination

Available expressions analysis: when an expression is available, e_gen and e_kill, the forward intersection equations with the universal set as initial value, the worked solution on a flow graph, and global common sub-expression elimination with a temporary.

Code generation and register allocation (outside syllabus, used in the journey)

The last phase of a compiler for a register machine: how many registers an expression needs (Sethi-Ullman numbering) and the code that uses exactly that many, live variables and the interference graph, assigning registers by graph colouring, spilling when there are too few registers, and a code generator for a basic block with register and address descriptors.