Short notes: Compiler Design
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
Easy conceptual marks: which phase does what, and which phase catches which error.
- The phases, front end to back end. Lexical → Syntax → Semantic → Intermediate code → Optimisation → Code generation. The symbol table and error handler are used by every phase. Front end (analysis) depends on the source language; back end (synthesis) depends on the target machine.
- Which phase finds which error. Lexical: illegal characters, malformed tokens, unterminated strings. Syntax: missing/extra brackets or semicolons, bad statement structure. Semantic: type mismatch, undeclared variable, wrong argument count. Run time (not the compiler): divide by zero, array bounds.
- Cross compilers and bootstrapping. A cross compiler runs on machine A but generates code for machine B. Bootstrapping: write a small compiler for a subset of a language, then use it to compile a bigger compiler written in that language. T-diagrams track source language, target language and implementation language.
Formulas
What GATE asks
- ★★★Which phase detects the given error. Classify an erroneous code snippet as lexical, syntax or semantic (or run time).
- ★★★Order / purpose of phases. Which phase produces tokens, parse tree, three-address code, which uses the symbol table.
- ★★★Cross compiler / bootstrapping. Identify the machine a cross compiler runs on and the one it targets.
Traps
Token-counting and DFA-state questions come up regularly; the regex → DFA pipeline is also asked in TOC.
- Tokens, lexemes and patterns. A lexeme is the actual character sequence, a pattern (regular expression) describes a class, and a token is the pair <name, attribute>. Whitespace and comments are discarded, they are not tokens.
- Regular expression → NFA (Thompson). Build ε-NFAs for each symbol and combine with union, concatenation and star. Every fragment has exactly one start and one accept state.
- NFA → DFA (subset construction). Each DFA state is a set of NFA states closed under ε. Compute move(set, a) then ε-closure for each symbol. A DFA state is final if it contains an NFA final state.
- DFA minimisation. Merge states that are indistinguishable. Start with {final} and {non-final} and keep splitting while transitions lead to different groups. Result is unique (Myhill–Nerode).
- Maximal munch and rule priority. The lexer takes the longest prefix matching any pattern; if two rules match the same length, the earlier rule wins (so keywords listed before identifiers).
- Symbol table and lexical errors. The lexer enters identifiers into the symbol table and returns a pointer as the token attribute. On an illegal character it reports the error with line number and recovers (panic mode: skip characters).
Formulas
What GATE asks
- ★★★Count the tokens in a code fragment. Apply maximal munch to a C snippet (e.g. with ++, ->, string literals, comments). Watch compound operators.
- ★★★Minimal DFA states / DFA for a language. Convert a regex or NFA to a DFA and count states in the minimal DFA.
- ★★★Role of the lexical analyser. What it outputs, what it does with whitespace/comments, why it is separate from the parser.
Traps
a+++b is a ++ + b under maximal munch.Foundation of all parsing questions: ambiguity, derivations and especially FIRST/FOLLOW sets.
- Derivations: leftmost and rightmost. A derivation rewrites the start symbol into a string. Leftmost always expands the leftmost non-terminal, rightmost the rightmost. Top-down parsers find leftmost derivations; bottom-up parsers find rightmost derivations in reverse.
- Parse trees and ambiguity. A grammar is ambiguous if some string has two different parse trees (equivalently two leftmost derivations). Ambiguity can change the meaning, and ambiguous grammars are never LL(k) or LR(k).
- Removing ambiguity: precedence and associativity. Use a separate non-terminal per precedence level (lower precedence nearer the start symbol). Left-recursive rule ⇒ left-associative, right-recursive ⇒ right-associative (e.g. ^ and =).
- FIRST and FOLLOW. FIRST(α) = terminals that can begin a string derived from α (plus ε if α is nullable). FOLLOW(A) = terminals that can appear right after A in some sentential form; the start symbol has $.
Formulas
What GATE asks
- ★★★Compute FIRST / FOLLOW sets. Given a grammar with ε-productions, write or count elements of FIRST/FOLLOW of a non-terminal.
- ★★★Is the grammar ambiguous?. Find a string with two parse trees, or pick the unambiguous grammar generating the same language.
- ★★★Derivation / parse tree questions. Number of nodes/steps, which derivation a parser produces, height of the tree.
- ★★★Associativity and precedence from a grammar. Read off the operator behaviour from where the recursion is.
Traps
Building and reading an LL(1) table, and removing left recursion, are frequent.
- Recursive descent and backtracking. One procedure per non-terminal. With ambiguity in the choice of production the parser may try one alternative, fail, backtrack and try the next. Predictive parsers avoid backtracking by looking ahead.
- Left recursion and left factoring. Left recursion (A → A α | β) makes a top-down parser loop forever; rewrite as A → β A′, A′ → α A′ | ε. Left factoring (A → αβ | αγ) delays the choice: A → α A′, A′ → β | γ.
- The LL(1) table and the LL(1) condition. Put A → α in M[A, a] for each a in FIRST(α) (and for each a in FOLLOW(A) if α is nullable). The grammar is LL(1) iff no cell has two entries.
- Predictive (stack) parsing. Stack holds the expected symbols. Terminal on top: match with input. Non-terminal on top: look up M[A, a] and replace A by the right-hand side (pushed reversed). Accept at $ / $.
Formulas
What GATE asks
- ★★★Is the grammar LL(1)? / table entries. Compute FIRST/FOLLOW and look for a cell with two productions; count the filled cells.
- ★★★Remove left recursion / left factor. Transform a grammar and identify the resulting productions.
- ★★★Trace predictive parser. Stack contents after some steps, or number of steps to parse a string.
- ★★★Properties of top-down parsers. True/false statements about left recursion, backtracking, LL(1) vs ambiguity.
Traps
The heaviest topic in CD: items, conflicts and the SLR ⊂ LALR ⊂ CLR relationships.
- Shift-reduce parsing and handles. Keep a stack of symbols. Shift the next token or reduce a handle (right side of a production that matches the top) to its left side. The sequence of reductions is a rightmost derivation in reverse.
- LR(0) items, closure and goto. An item is a production with a dot (A → α • β). closure(I) adds B → • γ for each B right after a dot. goto(I, X) moves the dot over X. The states of the DFA are the canonical collection.
- SLR(1). Same states as LR(0). Reduce A → α only on terminals in FOLLOW(A). FOLLOW is an over-estimate, so SLR can report conflicts that real lookaheads would avoid.
- CLR(1) = canonical LR. Items carry an exact lookahead: [A → α • β, a]. Most powerful, but many more states (can be hundreds of times larger).
- LALR(1). Merge CLR(1) states that have the same core (same items ignoring lookaheads). Same number of states as LR(0)/SLR. May introduce reduce/reduce conflicts, never shift/reduce ones that CLR did not have.
- Hierarchy and conflicts. LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1). LL(1) ⊂ LR(1). Shift/reduce conflict: both possible; reduce/reduce: two completed items. Ambiguous grammars always conflict.
Formulas
What GATE asks
- ★★★Number of states / items in a parser. Build the LR(0) canonical collection (or SLR) for a small grammar and count states.
- ★★★Which parser accepts the grammar. Decide whether a grammar is LR(0), SLR(1), LALR(1) or CLR(1) by looking for conflicts.
- ★★★Shift/reduce or reduce/reduce conflicts. Count or locate conflicts in a given state, or compare SLR vs LALR vs CLR.
- ★★★Trace a parse. Stack contents, handle, or the sequence of actions on an input.
- ★★★Relation between parsers. True/false: LALR has the same states as SLR; CLR has more; power ordering.
Traps
Evaluating attributes on a parse tree and classifying S/L-attributed definitions are regular marks.
- Synthesized and inherited attributes. Synthesized: computed from the children (bottom-up), e.g. E.val. Inherited: computed from the parent or left siblings (top-down), e.g. the type passed along a declaration list.
- S-attributed and L-attributed definitions. S-attributed: only synthesized attributes (evaluate bottom-up, fits LR parsing). L-attributed: inherited attributes depend only on the parent and left siblings (fits one left-to-right depth-first pass). Every S-attributed definition is L-attributed.
- Dependency graphs and evaluation order. Edges go from an attribute to those that depend on it. Evaluate in a topological order. A cycle means the definition cannot be evaluated.
- SDT during bottom-up parsing. Keep a value stack parallel to the parser stack. When reducing by A → X Y Z, the semantic action reads the values of X, Y, Z from the stack and pushes A.val.
- Translation schemes (actions inside rules). Actions are embedded at the point they must run. Output order follows the depth-first, left-to-right traversal. Example: E → E + T {print("+")} yields postfix.
Formulas
What GATE asks
- ★★★Evaluate an attributed parse tree. Compute the final value at the root for a given SDD and input; or the output printed by a translation scheme.
- ★★★Classify S-attributed / L-attributed. Decide whether given semantic rules are S-attributed, L-attributed, or neither.
- ★★★Postfix / output of translation scheme. Order of print statements for an expression.
Traps
Scoping and parameter-passing output questions are classics.
- Activation records and the control stack. Every call pushes an activation record: actual parameters, return value, return address, control link (caller), access link (for static scope), saved registers, locals and temporaries. Return pops it.
- Static vs dynamic scoping. Static (lexical): a name refers to the declaration in the enclosing text of where the function is written. Dynamic: it refers to the most recent binding on the call stack.
- Parameter passing. By value: copy; callee cannot change the caller. By reference: address passed. Copy-restore: copy in, copy out at return. By name: textual substitution, argument re-evaluated at every use.
- Storage organisation: static, stack, heap. Static: fixed at compile time (globals). Stack: procedure calls, LIFO, recursion. Heap: dynamic allocation with explicit or garbage-collected lifetime. Stack and heap grow toward each other.
Formulas
What GATE asks
- ★★★Output under static vs dynamic scoping. Trace nested procedures that print a global/shadowed variable; compare the two rules.
- ★★★Parameter passing result. Values after calling swap-like procedures by value / reference / name / copy-restore.
- ★★★Activation record contents / stack depth. Maximum stack depth or which fields exist.
Traps
Counting temporaries/instructions, forming quads vs triples and finding basic blocks are standard.
- Three-address code. Each instruction has at most one operator on the right:
x = y op z. Compound expressions need temporaries: one per operator. Also copies, jumps, indexed and pointer assignments. - Quadruples, triples, indirect triples. Quadruple (op, arg1, arg2, result): easy to move. Triple (op, arg1, arg2): results referred by position, so moving breaks references. Indirect triples: a separate list of pointers to triples allows reordering.
- DAG of a basic block. One node per distinct value; operators with the same operands reuse the node, exposing common subexpressions and dead code. Variables are labels attached to nodes.
- Basic blocks and the flow graph. Leaders: the first instruction, any jump target, any instruction after a jump. A basic block is a leader up to (not including) the next leader. Edges follow fall-through and jumps.
- Control flow translation. Boolean expressions with short-circuit evaluation compile to conditional jumps with true/false labels; backpatching fills in the targets when they become known.
Formulas
What GATE asks
- ★★★Count basic blocks / leaders. Given three-address code with gotos, find the leaders and the number of basic blocks (or edges).
- ★★★Count temporaries / TAC instructions. Translate an expression and count instructions or temporaries.
- ★★★DAG nodes for a block. Number of nodes or edges in the DAG after reusing common subexpressions.
- ★★★Quadruples vs triples. Which representation allows reordering, or table sizes.
Traps
Directly named in the syllabus: liveness, constant propagation and CSE via data-flow analysis.
- Local optimisations. Constant folding (3*4 → 12), constant propagation, algebraic simplification (x*1, x+0), strength reduction (x*2 → x+x, x/8 → x>>3), dead-code elimination.
- Common subexpression elimination. If an expression was already computed and its operands have not changed, reuse the earlier value. Detected by the DAG or by available expressions analysis.
- Loop optimisations. Code motion (hoist loop-invariant code), induction-variable elimination and strength reduction (multiplication → addition), loop unrolling.
- Live-variable analysis. A variable is live at a point if its current value may be used later. Backward, ∪ (may). Used for dead-code elimination and register allocation.
- Reaching definitions. A definition d reaches p if some path from d to p does not redefine the variable. Forward, ∪ (may). Used for constant propagation and loop-invariant detection.
- Available expressions. Expression x op y is available at p if on every path it is computed and its operands are not redefined afterwards. Forward, ∩ (must). Used for CSE.
- Data-flow framework at a glance. Each analysis picks a direction (forward/backward), a meet (∪ or ∩), and gen/kill sets per block, then iterates to a fixed point. Initialisation: ∅ for ∪-analyses, universal set for ∩-analyses.
Formulas
What GATE asks
- ★★★Live variables at a point / number live. Compute IN/OUT for a small CFG and count variables live at a given point (register-pressure questions).
- ★★★Reaching definitions / available expressions sets. IN/OUT sets for a block, or whether an expression is available, or which definitions reach a use.
- ★★★Which optimisation applies / result of optimisation. Constant propagation + folding, CSE, dead code, strength reduction on a code fragment.
- ★★★Direction / meet of an analysis. Match each analysis with forward/backward and may/must.
Traps
Minimum-register and graph-colouring questions appear now and then.
- Minimum registers for an expression (Sethi–Ullman). Label each tree node with the minimum registers needed to evaluate its subtree without storing to memory. Evaluate the child with the larger label first.
- Register allocation by graph colouring. Variables are nodes; an edge joins variables live at the same time. A k-colouring assigns k registers; if impossible some variable is spilled to memory.
- Peephole optimisation. Slide a small window over the target code and replace patterns: redundant load/store, jumps to jumps, unreachable code, algebraic identities, strength reduction.
Formulas
What GATE asks
- ★★★Minimum registers to evaluate an expression. Label the expression tree or generate code with a given number of registers.
- ★★★Colour the interference graph. Find the minimum registers / whether spilling is needed from liveness info.
- ★★★Peephole transformation. Result of replacing a pattern.