Apply what you learned — work through each problem yourself before revealing the step-by-step solution.
Five complete problems covering FIRST sets, FOLLOW sets, LL(1) tables, LR(0) items, and SLR parsing.
Topic: FIRST set algorithm from scratch
Given the following grammar G:
By definition, FIRST of any terminal is itself: FIRST(a)={a}, FIRST(b)={b}, FIRST(c)={c}, FIRST(d)={d}
A → aA: production starts with terminal 'a', so add a to FIRST(A).
A → ε: production is ε, so add ε to FIRST(A).
B → bB: starts with terminal 'b', add b.
B → d: terminal 'd', add d. Note: B cannot derive ε.
C → cC: starts with terminal 'c', add c.
C → ε: add ε. So C can derive ε.
S → aAB: starts with terminal 'a', add a. (We don't look further because 'a' is a terminal.)
S → bC: starts with terminal 'b', add b. (C can derive ε, but S→bC starts with 'b' not C.)
Does S derive ε? No — both alternatives start with a terminal (a or b), so S→ε is impossible.
Topic: FOLLOW set algorithm using three rules
Using the same grammar as Problem 1:
S is the start symbol → $ ∈ FOLLOW(S)
From S → aAB: A is followed by B. Apply Rule 2: FIRST(B)\{ε} ⊆ FOLLOW(A).
FIRST(B) = {b, d}, no ε, so add {b, d} to FOLLOW(A).
From S → aAB: Can B derive ε? No (FIRST(B) has no ε). So Rule 3 doesn't apply here.
From A → aA: A is at the end of the production — Rule 3 applies: FOLLOW(A) ⊆ FOLLOW(A). (Circular, no new info.)
From S → aAB: B is at the end of the production → Rule 3: FOLLOW(S) ⊆ FOLLOW(B). Add {$}.
From B → bB: B is at the end → Rule 3: FOLLOW(B) ⊆ FOLLOW(B). (Circular, no new info.)
From S → bC: C is at the end of the production → Rule 3: FOLLOW(S) ⊆ FOLLOW(C). Add {$}.
From C → cC: C is at the end → Rule 3: FOLLOW(C) ⊆ FOLLOW(C). (Circular, no new info.)
Topic: Build LL(1) table and trace a parse
FIRST(aS) = {a} — starts with terminal 'a'
FIRST(b) = {b} — just the terminal
FIRST(S) = {a, b} — union of both productions
FOLLOW(S) = {$} — S is the start symbol, and nothing follows it in aS except end-of-input; from S→aS, S follows S, circular, same set
Rule: M[A,a] = A→α when a ∈ FIRST(α)
S → aS: FIRST(aS) = {a} → M[S, a] = S → aS
S → b: FIRST(b) = {b} → M[S, b] = S → b
No ε in any FIRST, so no FOLLOW rule entries needed.
| Non-terminal | a | b | $ |
|---|---|---|---|
| S | S → aS | S → b | — |
No cell has two entries → grammar IS LL(1) ✓
Stack grows rightward; top-of-stack is leftmost symbol.
| Stack | Remaining Input | Action |
|---|---|---|
| $S | aab$ | M[S,a] = S→aS; replace S with aS → stack: $Sa |
| $Sa | aab$ | Top is 'a', input is 'a' → match, pop 'a' |
| $S | ab$ | M[S,a] = S→aS; replace S with aS → stack: $Sa |
| $Sa | ab$ | Top is 'a', input is 'a' → match, pop 'a' |
| $S | b$ | M[S,b] = S→b; replace S with b → stack: $b |
| $b | b$ | Top is 'b', input is 'b' → match, pop 'b' |
| $ | $ | Stack = $, Input = $ → ACCEPT ✓ |
Topic: Building the LR(0) automaton from scratch
Total: 10 items (one per position in each production, including augmented)
Start kernel: { S' → •S }
→ S has dot before S (non-terminal) → add all S-productions with dot at left:
Add: S → •AA
→ S → •AA has dot before A → add all A-productions:
Add: A → •aA, A → •b
→ A → •aA has dot before 'a' (terminal). A → •b has dot before 'b' (terminal). No more expansions.
Topic: Complete SLR construction and simulation
FOLLOW(E'): {$} (start symbol)
FOLLOW(E): E' → E: add FOLLOW(E') = {$}; E → E+T: E followed by '+', add {+}; So FOLLOW(E) = {+, $}
FOLLOW(T): E → E+T: T at end, add FOLLOW(E) = {+, $}; T → T*id: T followed by '*', add {*}; So FOLLOW(T) = {+, *, $}
| State | ACTION | GOTO | ||||
|---|---|---|---|---|---|---|
| id | + | * | $ | E | T | |
| 0 | s3 | 1 | 2 | |||
| 1 | s4 | acc | ||||
| 2 | r2 | s5 | r2 | |||
| 3 | r4 | r4 | r4 | |||
| 4 | s7 | 6 | ||||
| 5 | s8 | |||||
| 6 | r1 | s5 | r1 | |||
| 7 | r4 | r4 | r4 | |||
| 8 | r3 | r3 | r3 | |||
r1=E→E+T, r2=E→T, r3=T→T*id, r4=T→id. No conflicts → grammar is SLR(1) ✓
| Stack | Input | Action |
|---|---|---|
| 0 | id+id*id$ | s3 — shift 'id' |
| 0 id 3 | +id*id$ | r4 — reduce T→id (FOLLOW(T)∋+) |
| 0 T 2 | +id*id$ | r2 — reduce E→T (FOLLOW(E)∋+) |
| 0 E 1 | +id*id$ | s4 — shift '+' |
| 0 E 1 + 4 | id*id$ | s7 — shift 'id' |
| 0 E 1 + 4 id 7 | *id$ | r4 — reduce T→id (FOLLOW(T)∋*) |
| 0 E 1 + 4 T 6 | *id$ | s5 — shift '*' |
| 0 E 1 + 4 T 6 * 5 | id$ | s8 — shift 'id' |
| 0 E 1 + 4 T 6 * 5 id 8 | $ | r3 — reduce T→T*id |
| 0 E 1 + 4 T 6 | $ | r1 — reduce E→E+T |
| 0 E 1 | $ | acc — ACCEPT ✓ |
Key strategies for tackling parsing problems on exams — based on the most common student errors.
Start from terminals (trivial), then work outward to nonterminals. ε only propagates if ALL symbols before the current position can derive ε. A common mistake: forgetting to check the full prefix.
Always add $ to FOLLOW(S) first. FOLLOW sets can be circular (A appears in B's rule, B in A's). Resolve by taking the union iteratively until the fixed point. Don't panic — just keep iterating.
If M[A,a] would need two entries, the grammar is NOT LL(1). The two root causes: (1) left recursion (E→E+T), (2) common prefixes in alternatives (S→if...|if...else...). Fix with left-factoring or left-recursion elimination.
Always compute the full closure before computing GOTO. A kernel item [A→α•Bβ] requires adding ALL B-productions with dot at the start. Forgetting closure items is the #1 DFA-building mistake.
Grammar: S→L=R|R, L→*R|id, R→L. SLR conflicts in I2 because = ∈ FOLLOW(R). CLR resolves it: [R→L•, {$}] only reduces on $, not '='. This is the exam example — know it cold.
LALR merges CLR states with the same LR(0) core. The only time this introduces conflicts is reduce/reduce: if two merged states have different lookaheads that collide. This is rare in practice but examinable.
sN means "shift and push state N". rK means "reduce by production K". Pop 2×|α| entries, push the LHS nonterminal, then do GOTO. Remember: the state at the top after popping is used for GOTO.
LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1). LL(1) ⊂ LALR but is not the same family as LR. For any exam question "which parser handles this grammar", remember: more powerful parsers can always handle simpler grammars.
Test your understanding. Click an answer — you'll see immediately if you're right and why.
Quiz complete!