Master Rule Sheet: every rule card from Phases 0–6

At a glance: the parser family

At a glance: data-flow problems

At a glance: parameter passing

🧭 Phase 0 — Foundations

0.1.1 Programs, machine code and why we translate; compiler vs interpreter

• Compiler: whole source → equivalent target program, before running; reports source errors at compile time.
• Interpreter: source + input → results directly, statement by statement; no target program.
• Compiled code is usually faster; interpreted code is easier to change and test.
• Break-even: compile when the number of runs n > C / (i − r).
• Target can be machine code, assembly-like text, bytecode or another high-level language.

0.1.2 The toolchain: preprocessor, compiler, assembler, linker, loader

• Order: preprocessor → compiler → assembler → linker → loader.
• Files: .c → .i → .s → .o → executable.
• Preprocessor: #include, #define, textual only.
• Assembler output: relocatable object code with unresolved external references.
• Linker: joins objects + libraries, resolves references → executable; “undefined reference” errors.
• Loader (OS): copies into memory, relocates if needed, starts execution.

0.1.3 The phases of a compiler; symbol table; error handler; which phase catches which error

• Phases: lexical → syntax → semantic → intermediate code → optimizer → code generator.
• Front end (analysis) = first three, language-dependent; back end (synthesis) = last three, machine-dependent.
• Symbol table: one entry per name (type, location, …), shared by all phases.
• Errors: illegal character → lexical; shape/brackets/semicolon → syntax; undeclared/types/argument count → semantic; input-dependent → run time.
• A misspelled keyword is an identifier to the scanner.
• m languages × n machines: m × n compilers vs m + n parts.

0.2.1 Alphabets, strings, languages; sets, union, intersection

• Alphabet Σ: finite set of symbols. String: finite sequence; |w| its length; ε has length 0.
• Concatenation xy; εw = w.
• Length-n string: n + 1 prefixes, n + 1 suffixes; n(n+1)/2 non-empty substrings if symbols distinct.
• Language = set of strings ⊆ Σ*. ∅ ≠ {ε}.
• LM = {xy}; L* = {ε} ∪ L ∪ LL ∪ …; L⁺ = LL*.
• Sets: ∪, ∩, −; |A ∪ B| = |A| + |B| − |A ∩ B|.

0.2.2 Regular expressions (what lexical analysis needs)

• Building blocks: ε, a, r|s, rs, r*, (r).
• Precedence: * > concatenation > |.
• Shorthands: r+ = rr*, r? = r|ε, [a-z], [0-9].
• id → letter (letter | digit)*; number → digits (. digits)? (E [+-]? digits)?
• (a|b)* = (ab); (r)* = r*.
• Cannot count without limit (balanced brackets).

0.2.3 Finite automata: DFA, NFA and the idea of converting NFA to DFA

• DFA (Q, Σ, δ, q₀, F): one move per state and symbol; accept if the run ends in F.
• NFA: sets of next states, ε-moves; accept if some path ends in F.
• NFA ≡ DFA in power (same languages).
• Subset construction: start = ε-closure({q₀}); next = ε-closure(moves on a); at most 2ⁿ states.
• Regular expression → NFA (Thompson) → DFA → minimal DFA: the lexer’s pipeline.

0.2.4 Data structures: stack, tree, hash table, directed graph

• Stack: push/pop/top, LIFO.
• Tree: root, parent, children, leaves; height = longest root-to-leaf path in edges.
• Preorder: node, then children. Postorder: children, then node.
• Hash table: h(k) = k mod m; collisions handled by chaining; average O(1) lookup → symbol tables.
• Directed graph: nodes, edges u → v, successors/predecessors, paths, cycles; DAG = no cycle.

🔤 Phase 1 — Lexical Analysis

1.1.1 Tokens, lexemes, patterns and attributes; how the lexer works with the parser and symbol table

• Token = ⟨token name, attribute⟩; lexeme = matched characters; pattern = rule (regular expression).
• Token classes: keywords, identifiers, constants, string literals, operators, punctuation.
• Attributes: id → symbol table pointer; num → value; relop → which operator.
• Parser calls getNextToken(); lexer strips blanks/comments, fills symbol table, counts lines.
• Each occurrence = one token; main/printf are identifiers.

1.1.2 Counting tokens in C code: whitespace, comments, string literals, ++ and >=

• Whitespace, comments → 0 tokens.
• String literal, character constant → 1 token each, whatever is inside.
• Keyword, identifier, number (3.14, 2.5e3) → 1 each.
• Each punctuation mark and each operator → 1; multi-character operators (++, >=, +=, ->, =) count once.
• Longest match from the left: x+++y = x ++ + y.
• C comments do not nest; quotes inside comments and /* inside quotes are plain text.

1.2.1 Writing token definitions as regular expressions

• digit → [0-9]; digits → digit+; letter → [A-Za-z_].
• id → letter (letter | digit)*.
• number → digits (. digits)? (E [+-]? digits)?.
• relop → | = | == | != | > | >=.
• ws → (blank | tab | newline)+ gives no token.
• Patterns overlap (keywords match id): resolve by rules, not by the patterns.

1.2.2 Transition diagrams; longest match and priority rules; lookahead

• Transition diagram: states, character edges, accepting states with actions; * = retract one character.
• Longest match first; then priority (earlier pattern, keywords before id).
• Combined DFA: remember the last accepting position; on failure go back to it.
• Lookahead: characters read past the lexeme to decide; then retracted.
• Keywords: pre-load into symbol table; installID() + getToken().

1.3 Lexical errors and recovery; how a lexer generator (Lex/Flex) is structured

• Lexical error: no pattern matches a prefix of the remaining input (illegal char, unterminated string/comment, over-long name).
• Recovery: panic mode (delete until a token can start); local repairs (delete, insert, replace, transpose); minimum-distance (rare).
• Lex file: declarations %% rules (pattern {action}) %% functions.
• lex.l → Lex → lex.yy.c → C compiler → lexer; yylex(), yytext, yyleng, yylval.
• Conflicts: longest match, then earliest rule; catch-all . last.

🌳 Phase 2 — Syntax Analysis (Parsing)

2.1.1 Context-free grammar primer: productions, derivations (leftmost/rightmost), parse trees

• CFG = terminals, nonterminals, productions A → α, start symbol.
• Derivation step: replace one nonterminal by a right side. Leftmost (⇒lm) / rightmost (⇒rm = canonical).
• Sentential form: derivable string; sentence: all terminals; L(G) = all sentences.
• Parse tree: root = start symbol, interior = nonterminals, leaves = terminals/ε; yield = leaves left to right.
• Steps in any derivation of a tree = number of interior nodes.
• Grammars ⊃ regular expressions (aⁿbⁿ, balanced brackets).

2.1.2 Ambiguity; encoding operator precedence and associativity in a grammar

• Ambiguous grammar: some sentence has ≥ 2 parse trees (≥ 2 leftmost derivations).
• Fix precedence: one nonterminal per level; lowest precedence nearest the start symbol.
• Fix associativity: E → E op T (left), E → T op E (right).
• Dangling else: else matches the nearest unmatched then (matched/unmatched grammar).
• Trees of an operator chain in E → E op E | id: Catalan numbers 1, 2, 5, 14, 42.

2.2 Grammar transformations: eliminating left recursion (direct and indirect); left factoring

• Left recursion: A ⇒⁺ Aα; direct if A → Aα.
• A → Aα₁|…|Aαₘ|β₁|…|βₙ ⇒ A → β₁A′|…|βₙA′; A′ → α₁A′|…|αₘA′|ε.
• Indirect: order nonterminals; substitute earlier ones into Aᵢ → Aⱼγ; then remove direct.
• Left factoring: A → αβ₁|αβ₂ ⇒ A → αA′; A′ → β₁|β₂ (longest common prefix, repeat).
• Neither transformation changes the language; neither removes ambiguity.

2.3.1 Recursive-descent parsing and backtracking

• Top-down parsing: root to leaves, leftmost derivation.
• Recursive descent: one procedure per nonterminal; terminals matched with match().
• Backtracking: on failure restore input position and try the next alternative; exponential worst case.
• Predictive parsing: lookahead token selects the production; needs no left recursion, left factoring, disjoint starts.
• Left recursion → infinite recursion.

2.3.2 FIRST and FOLLOW sets

• FIRST(a) = {a}; X → ε adds ε; X → Y₁…Yₖ: add FIRST(Yᵢ)−ε while Y₁…Yᵢ₋₁ are nullable; all nullable ⇒ add ε.
• FOLLOW: $ ∈ FOLLOW(S); A → αBβ: FIRST(β)−ε ⊆ FOLLOW(B); β nullable or absent: FOLLOW(A) ⊆ FOLLOW(B).
• FOLLOW never contains ε; FIRST may.
• Compute nullable first; iterate to a stable result.

2.3.3 LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a string

• M[A, a] ∋ A → α for a ∈ FIRST(α); if ε ∈ FIRST(α), for every b ∈ FOLLOW(A) (incl. $).
• LL(1) ⇔ no cell has two productions.
• Never LL(1): left-recursive, ambiguous, not left-factored.
• Parser: stack $ S; terminal on top → match; nonterminal → replace by right side reversed; $ $ → accept.
• Outputs form the leftmost derivation; empty cell = error (panic mode: skip to FOLLOW).

2.4.1 Shift-reduce parsing; handles; viable prefixes; shift/reduce and reduce/reduce conflicts

• Bottom-up = leaves to root = rightmost derivation in reverse.
• Actions: shift, reduce A → β (β on top), accept ($S, $), error.
• Handle: the right side to reduce next; always on top of the stack.
• Viable prefix: stack content that can still lead to a handle; the set is regular.
• Conflicts: shift/reduce, reduce/reduce; ambiguous grammars always have them.
• Reduces = interior nodes; shifts = tokens.

2.4.2 LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) table

• Item: production with a dot; |rhs| + 1 items per production; A → ε gives A → •.
• Augment: S′ → S.
• CLOSURE: A → α•Bβ adds B → •γ.
• GOTO(I, X): advance the dot over X, then CLOSURE.
• LR(0) table: shift on terminals after the dot; complete item reduces in all columns; S′ → S• accepts on $.
• LR(0) conflict: complete item with another complete item (R/R) or with a terminal-after-dot item (S/R).

2.4.3 SLR(1)

• SLR(1) = LR(0) automaton + reduce A → α only on FOLLOW(A).
• S/R conflict: A → α• and B → β•aγ with a ∈ FOLLOW(A).
• R/R conflict: A → α•, B → β• with FOLLOW(A) ∩ FOLLOW(B) ≠ ∅.
• LR(0) ⊂ SLR(1); same number of states.
• Weakness: FOLLOW is global (false conflicts, e.g. L = R).

2.4.4 Canonical LR(1) (CLR) items with lookaheads

• LR(1) item [A → α•β, a].
• CLOSURE: [A → α•Bβ, a] ⇒ [B → •γ, b] for b ∈ FIRST(βa).
• GOTO keeps lookaheads.
• Reduce [A → α•, a] only on a; accept [S′ → S•, $].
• CLR (canonical LR(1)) ⊇ SLR; states ≥ LR(0) states; S → CC: 10 vs 7.

2.4.5 LALR(1): merging states and which conflicts merging can create

• Core = LR(0) part of an LR(1) state.
• LALR(1): merge CLR states with equal cores; union lookaheads.
• LALR states = LR(0) states ≤ CLR states.
• Merging can create R/R conflicts, never S/R.
• LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1).

2.4.6 Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drills

• LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1); LL(1) ⊂ LR(1); LL(1) and SLR/LALR overlap without inclusion.
• States: LR(0) = SLR = LALR ≤ CLR.
• Ambiguous ⇒ in no class.
• Classify in order: ambiguity, LL(1), LR(0), SLR, LALR, CLR.

2.4.7 Operator-precedence parsing (brief); YACC conflict resolution with precedence and associativity; panic-mode error recovery (brief)

• Operator grammar: no ε, no adjacent nonterminals. Relations <·, =·, ·> between terminals.
• Shift if top <· a or =·; reduce if top ·> a (pop until <·).
• Precedence functions f, g can encode the table.
• YACC: LALR(1); default S/R → shift, R/R → earlier production.
• %left/%right/%nonassoc: later = higher; equal precedence: left reduces, right shifts.
• Panic mode: pop to a state with GOTO on A, skip input to FOLLOW(A).

🏷️ Phase 3 — Syntax-Directed Translation

3.1 Syntax-directed definitions: attributes, semantic rules, synthesized vs inherited, annotated parse trees, dependency graphs and evaluation order

• SDD = grammar + attributes + semantic rules per production.
• Synthesized: computed at the node’s own production from children; flows up.
• Inherited: computed at the parent’s production from parent/siblings; flows down or sideways.
• Terminals: synthesized only (lexval).
• Annotated parse tree shows all attribute values.
• Dependency graph: edge b → a if a uses b; evaluate in topological order; cycle ⇒ no order.

3.2 S-attributed and L-attributed definitions; which parsers can evaluate which

• S-attributed: synthesized only → postorder; LR evaluates on reductions with a value stack.
• L-attributed: inherited attrs of Xⱼ depend only on A’s inherited and X₁…Xⱼ₋₁ (and Xⱼ, acyclically).
• S-attributed ⊂ L-attributed.
• L-attributed: one depth-first left-to-right walk; recursive descent: inherited = parameters, synthesized = return values.
• LR + inherited attributes: needs marker nonterminals M → ε.

3.3 Translation schemes with embedded actions; tracing what an SDT prints or computes

• SDT = grammar + actions {…} inside bodies.
• Execution = depth-first left-to-right walk; action runs when reached.
• Postfix SDT (actions at ends) = S-attributed on LR.
• L-attributed → SDT: inherited before the symbol, synthesized at the end.
• Middle actions in LR: marker M → ε {act}.
• Trace: tree first, insert actions as leaves, walk.

3.4 Applications: building syntax trees; basic type checking (brief)

• Syntax tree: operators inside, operands at leaves; no chains, no brackets.
• SDD: E.node = new Node(op, E₁.node, T.node); leaves new Leaf(id/num); S-attributed.
• Type expressions: basic types; array(n, t), pointer(t), t₁ × t₂, t₁ → t₂.
• Structural vs name equivalence.
• int op float → float (coercion); incompatible operands → type_error.

🧱 Phase 4 — Intermediate Code Generation

4.1 Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG

• IR: between front end and back end; retargeting (m + n) and machine-independent optimization.
• DAG = syntax tree with identical subexpressions shared.
• Value numbering: reuse node (op, left, right) if it already exists.
• Block DAG: labels move to the newest node of each variable; initial values are leaves x₀.
• Nodes = distinct leaves + distinct operator applications; edges = 2 per binary node.

4.2.1 Three-address code instruction forms; quadruples, triples, indirect triples

• TAC: ≤ 1 operator, ≤ 3 addresses per instruction; temporaries for intermediate values.
• Forms: x = y op z, x = op y, x = y, goto L, if x relop y goto L, param/call/return, x = y[i], x[i] = y, &, *.
• Quadruple: (op, arg1, arg2, result).
• Triple: (op, arg1, arg2), result = position (k).
• Indirect triples: pointer list gives order; easy reordering.

4.2.2 TAC for expressions and array accesses (address calculation)

• 1-D: base + (i − low) × w.
• Row-major 2-D: base + ((i − low₁) × n₂ + (j − low₂)) × w.
• Column-major 2-D: base + ((j − low₂) × n₁ + (i − low₁)) × w.
• k-D row-major: Horner form ((i₁ n₂ + i₂) n₃ + …) × w.
• TAC: scale indices by constants, then x = a[t] / a[t] = y with byte offset t.

4.2.3 TAC for if/while and Boolean expressions (short-circuit; backpatching brief)

• Relop: if a relop b goto B.true; goto B.false.
• ||: B₁.true = B.true, B₁.false → start of B₂. &&: B₁.true → start of B₂, B₁.false = B.false. !: swap.
• if: B; L1: S1; next. if-else: B; L1: S1; goto next; L2: S2; next. while: begin: B; L1: S; goto begin; next.
• Backpatching: truelist/falselist/nextlist; || fills B₁.falselist, && fills B₁.truelist.

4.3 Static single assignment (SSA) form; counting variables and temporaries

• SSA: each variable assigned once in the text; versions x₁, x₂, ….
• Straight-line: rename targets in order; uses take the latest version.
• Joins: x₃ = φ(x₁, x₂) picks by incoming path; loop headers too.
• Count = assignments + read-only variables.

4.4 Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges

• Basic block: enter only at the first instruction, leave only after the last.
• Leaders: first instruction; jump targets; instructions after jumps (and after return/halt).
• Block = leader … before next leader.
• Flow graph edges: jump target, and fall-through unless the block ends in an unconditional jump.
• CFG = context-free grammar (parsing) vs control flow graph (optimization): read the context.

🗄️ Phase 5 — Runtime Environments

5.1 Storage organization: code, static, stack, heap

• Areas: code (read-only), static data (globals, static locals, constants, literals), stack (call records), heap (malloc/new).
• Usual layout: code, static at low addresses; heap grows up; stack grows down; free memory between.
• Static sizes fixed at compile time; stack and heap managed at run time.
• Lifetime: whole run → static; one call → stack; arbitrary → heap.

5.2 Activation records, activation trees, the call stack; caller vs callee duties; recursion

• Activation tree: node per activation, children in call order; calls = preorder, returns = postorder.
• Stack holds the root-to-current path.
• Record: actual parameters, returned value, control link, static link, saved status (return address, registers), locals, temporaries.
• Caller: evaluates actuals, saves return address and control link. Callee: saves registers, sets up locals; on return restores and jumps back.
• calls(n) via recurrence; max depth = tree height.

5.3 Static vs dynamic scoping; tracing program output under each; access links and displays (brief)

• Scope: region where a declaration applies; non-local = used but not declared locally.
• Static: nearest enclosing declaration in the text (compile time).
• Dynamic: most recent active caller that declares it (run time, control links).
• Access link → record of the lexically enclosing procedure; hops = depth(user) − depth(declaration).
• Display d[i] → most recent record at depth i; save/restore d[i] on call/return.

5.4 Parameter passing: by value, by reference, by value-result, by name; output tracing

• Value: copy in; caller unaffected.
• Reference: pass address (fixed at the call); aliasing possible.
• Value-result: copy in, copy back on return to call-time locations, in order.
• Name: re-evaluate the actual expression at every use (thunk).
• Trace with a table of the caller’s cells.

5.5 Static vs stack vs heap allocation: which language features force which

• Static: fixed addresses; needs no recursion, known sizes, no run-time data.
• Stack: supports recursion; lifetimes nested (LIFO).
• Heap: lifetimes beyond calls (malloc/new, objects, returned closures).
• Dangling reference: pointer outlives its target (address of a local, use after free).
• Garbage collection: reclaim unreachable heap objects (reference counting, mark-and-sweep).

✂️ Phase 6 — Optimization

6.1 Local optimization: constant folding, algebraic simplification, strength reduction, copy propagation, dead-code elimination, local CSE with the block DAG, peephole optimization

• Constant folding: compute constant expressions at compile time.
• Algebraic simplification: x+0, x1, x0, x−0, x/1.
• Strength reduction: x2 → x+x or x1; x² → xx.
• Copy propagation: after x = y, use y.
• Dead code: assignments to variables not used later (no side effects).
• Local CSE: block DAG shares (op, operands) nodes; emit code only for needed values.
• Peephole: redundant load/store, unreachable code, jump-to-jump, idioms.

6.2 The data-flow analysis framework: gen/kill sets, in/out equations, forward vs backward, meet operator, iterating to a fixed point

• Facts per block: IN[B], OUT[B].
• Forward: IN[B] = meet over preds of OUT[P]; OUT[B] = gen[B] ∪ (IN[B] − kill[B]).
• Backward: OUT[B] = meet over succs of IN[S]; IN[B] = f_B(OUT[B]).
• Meet: ∪ for may problems (start ∅); ∩ for must problems (start with the universe).
• Iterate until no change: fixed point.
• Reaching definitions: forward, ∪; gen = last definitions in B; kill = other definitions of the same variables.

6.3 Constant propagation

• Lattice per variable: UNDEF (⊤) > constants > NAC (⊥).
• Meet: UNDEF ∧ v = v; c ∧ c = c; c₁ ∧ c₂ = NAC (c₁ ≠ c₂); NAC ∧ v = NAC.
• Transfer x = y op z: both constant → fold; any NAC → NAC; else UNDEF.
• Forward; iterate from UNDEF to a fixed point.
• Not distributive: safe but can miss constants.

6.4 Liveness analysis: live variables at each point; what liveness is used for

• x live at p: its value may be used on some path from p before redefinition.
• use[B]: read before written in B; def[B]: assigned in B.
• IN = use ∪ (OUT − def); OUT = ∪ IN of successors; backward; start ∅.
• Inside a block, backwards: remove target, add operands.
• Uses: dead code (dead after assignment), register allocation (max live, interference).

6.5 Global common-subexpression elimination via available expressions

• x op y available at p: computed on every path to p, operands unchanged since.
• e_gen: computed in B, operands not redefined later in B. e_kill: expressions using a variable B defines.
• Forward, ∩: IN = ∩ OUT[preds]; OUT = e_gen ∪ (IN − e_kill); IN[entry] = ∅; other OUT start = U.
• Global CSE: save earlier results in a temporary; replace the later computation by a copy.

6.6 Loop optimizations: code motion, induction variables (brief, low weight)

• Loop: header + back edge; preheader holds moved code.
• Loop-invariant: operands constant, defined outside, or invariant; code motion → preheader.
• Basic induction variable: i = i + c; derived: j = a·i + b → j = j + a·c (strength reduction).
• Induction-variable elimination: rewrite the test in terms of j, delete i.
• Unrolling, jamming (fusion): brief.