GATE CS - COMPILER DESIGN:LL(1) and LR Parsing

LL(1) and LR Parsing for GATE CS

Parsing is the heaviest Compiler Design topic on GATE (often 4–7 marks). The skill is computing FIRST/FOLLOW, building or reading predictive tables, and knowing LL vs LR power — not memorising parser generator flags.

CFG warm-up

$G=(V,T,P,S)$. Leftmost vs rightmost derivations. Ambiguous ⇒ more than one parse tree for some string — such grammars are not LL(1) / LR(1).

FIRST and FOLLOW

FIRST(α): terminals that begin strings derived from α; include $\varepsilon$ if α ⇒* ε.

FOLLOW(A): terminals that can appear immediately after A in a sentential form; include $\$$ for the start symbol.

Worked: FIRST

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

FIRST(F) = {(, id}; FIRST(T) = FIRST(F); FIRST(E) = FIRST(T); FIRST(E') = {+, ε}; FIRST(T') = {*, ε}.

FOLLOW(E) includes $\$$ and $)$; FOLLOW(E') = FOLLOW(E); etc. Fill carefully — one wrong FOLLOW breaks the LL(1) table.

LL(1)

Predictive parsing table: for production $A \to \alpha$, put it in entries for each $a \in$ FIRST(α); if ε ∈ FIRST(α), also for each $b \in$ FOLLOW(A).

Conflict in a cell ⇒ not LL(1). Left recursion and common prefixes must be eliminated first.

LR family (who is stronger)

Power (roughly): LR(0) ⊂ SLR ⊂ LALR ⊂ CLR. Every LL(1) grammar is LR(1); converse false.

Shift/reduce or reduce/reduce conflict ⇒ grammar not in that class.

Exam habit

1. Compute FIRST/FOLLOW before touching the table
2. For “is it LL(1)?” look for multiple productions in one cell
3. For LR, identify the conflict type if a state is shown

Related: Syntax-Directed Translation. Practice: GATE hub.