Formula Vault · CD
Compiler Design
Sheet 1
Lexical Analysis & Parsing
3 formulasCore concepts
- LL(1): top-down; needs FIRST/FOLLOW sets; no left recursion, no ambiguity
Key formulas
Test your recall
Can you recall the bottom-up parser power formula?
Reveal formula
\[ LR(0) \subset SLR \subset LALR \subset LR(1) \]
GATE traps 4 traps
Eliminate left recursion first
Left recursion (A -> A alpha | beta) must be eliminated before LL(1) parsing -- it causes infinite recursion top-down. The standard transformation (A -> beta A', A' -> alpha A' | epsilon) is a frequently tested 'convert this grammar' question.
LL(1) ⇒ unambiguous, not the reverse
Every LL(1) grammar is unambiguous, but not every unambiguous grammar is LL(1) -- assuming 'unambiguous' automatically means 'LL(1)-parseable' is a common overreach.
The containment chain only goes one way
The containment LL(1) subset of LALR(1) subset of LR(1) is tested as a chain of increasingly permissive checks -- getting the direction backwards is a common error.
Check ε-derivable non-terminals first
FIRST/FOLLOW computation for epsilon-derivable non-terminals is the most error-prone step -- always check whether a non-terminal can derive epsilon before propagating FOLLOW sets across it.
Sheet 2
Syntax-Directed Translation & Intermediate Code
1 formulaCore concepts
- Synthesized attributes: computed from children (S-attributed, bottom-up evaluable)
- Inherited attributes: computed from parent/siblings (need L-attributed for single pass)
- Quadruples: (op, arg1, arg2, result) -- explicit result. Triples: implicit, by position
Key formulas
Test your recall
Can you recall the three-address code formula?
Reveal formula
\[ x = y\ op\ z \]
GATE traps 4 traps
S-attributed parses bottom-up in one pass
S-attributed grammars can be evaluated during bottom-up (LR) parsing in a single pass; L-attributed grammars are needed for single-pass evaluation with inherited attributes in EITHER top-down or bottom-up parsing -- mixing up these two requirements is a common trap.
Every S-attributed grammar is L-attributed
Every S-attributed grammar is also L-attributed (synthesized-only is a special case), but not the reverse -- a frequently tested one-directional containment.
Triples break under reordering
Triples reference results by POSITION (statement number), so reordering statements breaks them; quadruples use named temporaries, making reordering safe -- this distinction is a recurring question about which representation survives code motion.
TAC generation is naturally post-order
Generating three-address code from an expression tree is naturally post-order (bottom-up) -- attempting pre-order produces incorrect operand ordering, a subtle hand-trace mistake.
Sheet 3
Code Optimization & Runtime Environment
Core concepts
- Activation record: return address, saved registers, locals, parameters, control link, access link
- Static scoping -> uses the ACCESS link. Dynamic scoping -> uses the CONTROL link
- Basic block: maximal instruction sequence, single entry, single exit, no internal jumps
- Common optimizations: constant folding, dead code elimination, common subexpression elimination, loop-invariant code motion, strength reduction
GATE traps 4 traps
Static uses access link, dynamic uses control link
Static (lexical) scoping resolves variables based on where a function is DEFINED (access link); dynamic scoping resolves based on the CALL chain (control link) -- a heavily tested contrast, especially with nested-function trace examples.
A jump target always starts a new block
A basic block has exactly one entry (first instruction) and one exit (last instruction, typically a jump) -- any instruction that's a jump TARGET from elsewhere must start a NEW basic block, a common oversight when identifying blocks in a code snippet.
Loop-invariant motion needs no side effects
Loop-invariant code motion is only safe if the computation has no side effects tied to being inside the loop -- GATE sometimes gives a 'trick' loop body where motion looks valid but actually isn't.
Strength reduction swaps costly ops for cheap ones
Strength reduction replaces expensive operations (e.g. multiplication in a loop) with cheaper equivalents (e.g. repeated addition) -- commonly tested by asking which optimization transformed a given before/after code pair.