FIRST, FOLLOW and LL(1) predictive parsing
Goal and notation
Construct a predictive table and trace it. Uppercase letters are nonterminals, lowercase symbols and id are terminals; id is one token. Epsilon (ε) is the empty string, never a token on the input. $ is the end marker. Stack top is written on the LEFT. LL(1) means left-to-right input, a leftmost derivation, and one lookahead token.
1. Nullable, FIRST and FOLLOW
Nullable(A) means A derives ε. FIRST(α) contains terminals that can begin a string derived from α, plus ε when α is nullable. For a sequence XY, include FIRST(X) without ε; inspect Y only if X is nullable. FOLLOW(A) contains terminals that may immediately follow A in a sentential form, and $ for the start symbol at input end. FOLLOW never contains ε.
For each production X→αAβ, add FIRST(β)−{ε} to FOLLOW(A). If β is nullable, add FOLLOW(X). Repeat until no set changes; one left-to-right pass can miss dependencies. A production A→α goes in table cell M[A,a] for every a in FIRST(α)−{ε}. If α is nullable, also place it for a in FOLLOW(A). A multiply filled cell is an LL(1) conflict.
2. Complete small example
Grammar: S→AB; A→aA | ε; B→bB | c. It generates abc: any number of a tokens, then any number of b tokens, then exactly one c.
A is nullable; B and S are not. FIRST(A)={a,ε}; FIRST(B)={b,c}; FIRST(S)={a,b,c}. FOLLOW(S)={$}; FOLLOW(B)={$}; FOLLOW(A)={b,c}, because B is not nullable. The occurrence A→aA adds only the already-known FOLLOW(A) back to itself.
Nonempty predictive entries are M[S,a]=M[S,b]=M[S,c]=S→AB; M[A,a]=A→aA; M[A,b]=M[A,c]=A→ε; M[B,b]=B→bB; M[B,c]=B→c. All other cells are errors. In particular M[A,$] is empty: A cannot be followed by input end in a complete S string because B must supply c.
3. Stack trace for a b c $
Start with S$ and input abc$. Use the table and replace the leftmost stack symbol by its production RHS, keeping the first RHS symbol on top:
- S$ → AB$ by S→AB; input remains abc$.
- AB$ → aAB$ by A→aA. Match a: stack AB$, input bc$.
- With A on top and b lookahead choose A→ε: stack B$, input bc$.
- B$ → bB$; match b: stack B$, input c$.
- B$ → c$; match c: stack $, input $; accept.
The ε step consumes no input. On input ab$ the parser eventually has B$ with lookahead $, so its table entry is empty and parsing fails. Successful consumption of a prefix is not acceptance of the complete input.
4. Transformations and conflicts
Immediate left recursion E→E+t | t can be rewritten E→tR; R→+tR | ε. A naive recursive-descent call E→E+t recurses before consuming input. The transformation preserves the generated token strings, but the parse-tree shape changes; translation must deliberately preserve intended left associativity.
Left factoring A→ab | ac gives A→aR; R→b | c. It postpones a choice until the distinguishing token is visible. Factoring or removing left recursion alone does not guarantee LL(1): conflicts may remain elsewhere, especially between a nullable alternative and FOLLOW.
Example S→Aa; A→a | ε. FIRST(a)={a}, and FOLLOW(A)={a}; both A→a and A→ε enter M[A,a]. This grammar is not LL(1), even though its language {a,aa} has an LL(1) grammar S→aR; R→a | ε. Classification of a particular grammar is not classification of every grammar for its language.
Pitfalls
Compute FIRST of the entire RHS, not only its first nonterminal. Distinguish ε from $. Never treat an empty table cell as an automatic ε production. A single lookahead conflict is enough to reject the LL(1) claim; do not resolve it by silently preferring one rule.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. For S→AB, A→aA|ε, B→bB|c, FIRST(S) is:
A. {a} B. {a,ε} C. {a,b,c} D. {a,b,c,ε}
Answer: C
A: A can vanish, exposing B.
B: B cannot vanish, so ε is absent.
C: A contributes a; nullable A exposes b and c.
D: B always generates a c, so S is not nullable.
P02. For that grammar FOLLOW(A) is:
A. {b,c} B. {$} C. {a,b,c} D. {ε,b,c}
Answer: A
A: The following nonnullable B begins with b or c.
B: B must occur after A, so $ cannot immediately follow A.
C: The recursive a is before A, not after it.
D: FOLLOW never contains ε.
P03. With stack top LEFT, which replaces A B $ on lookahead b?
A. a A B $ B. B $ C. b $ D. $
Answer: B
A: A→aA requires a lookahead.
B: A→ε removes only A and consumes no token.
C: B has not yet expanded and matched.
D: B must still generate its portion.
P04. In S→Aa; A→a|ε, the conflicting LL(1) cell is:
A. M[S,$] B. M[A,$] C. M[A,a] D. M[S,ε]
Answer: C
A: S is not nullable.
B: FOLLOW(A) is {a}, not {$}.
C: FIRST(a) and FOLLOW(A) both select column a.
D: ε is not a lookahead column.
P05. What is preserved when eliminating immediate left recursion correctly?
A. Every parse-tree shape B. The generated token language C. All semantic action placement automatically D. Ambiguity always disappears
Answer: B
A: Tree shape changes.
B: Equivalent transformation preserves terminal strings.
C: Actions need deliberate adjustment.
D: This transformation is not a universal ambiguity remover.
P06. Which is always true of FOLLOW sets?
A. They contain ε for nullable symbols B. They contain only nonterminals C. They need only one pass D. They exclude ε
Answer: D
A: Nullability does not put ε into FOLLOW.
B: FOLLOW contains terminals and possibly $.
C: Dependencies may require repeated passes.
D: The empty string is not a following token.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in