FIRST, FOLLOW, and Why LL(1) Parsing Needs Both
An LL(1) parser decides which grammar production to apply by looking at just one token of lookahead — which only works if that single token unambiguously identifies the correct production. FIRST sets (which terminal symbols can begin a string derived from a given non-terminal) and FOLLOW sets (which terminals can immediately follow a non-terminal in some derivation) are the machinery that makes this one-token decision possible, by predicting exactly what token to expect next at each point in a derivation.
A grammar is genuinely LL(1)-parseable only if, for every non-terminal with multiple productions, their FIRST sets don't overlap (with FOLLOW sets brought in for productions that can derive the empty string) — if they do overlap, one token of lookahead isn't enough to decide which production applies, and the grammar needs restructuring (or a more powerful parsing strategy) before an LL(1) parser can handle it.
Building the parsing table from FIRST/FOLLOW sets, then tracing a token string through the parser's stack step by step, is exactly how compiler courses demonstrate whether a given grammar is well-behaved for simple top-down parsing — a check that's tedious but mechanical by hand, and easy to get wrong on a non-trivial grammar.
Worked example
For the classic expression grammar E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → ( E ) | id:
- FIRST(E) = FIRST(T) = FIRST(F) = { (, id }, FIRST(E') = { +, ε } and FIRST(T') = { *, ε }
- FOLLOW(E) = FOLLOW(E') = { ), $ }, FOLLOW(T) = FOLLOW(T') = { +, ), $ } and FOLLOW(F) = { *, +, ), $ }
The parsing table has no conflicts, so the grammar is LL(1), and id + id * id is accepted. This grammar is the left-recursion-free form of E → E + T | T, T → T * F | F, F → ( E ) | id, which is exactly what the Remove left recursion button produces from it.
Why is my grammar not LL(1)?
A conflict means two productions landed in the same table cell, and there are only two ways that happens:
- FIRST/FIRST: two alternatives of A can both start with the same token. Usually the grammar is left-recursive, or two alternatives share a prefix and need left factoring.
- FIRST/FOLLOW: one alternative of A can derive ε, so it goes under every token in FOLLOW(A), and one of those tokens also starts another alternative. The dangling else is the classic case: after left factoring S → i E t S | i E t S e S | a into S → i E t S S' | a and S' → e S | ε, the cell M[S', e] still holds both S' → e S and S' → ε, because e ∈ FOLLOW(S'). No rewrite fixes that: the grammar is ambiguous, and real parsers resolve it by always shifting the else.
The tool names the kind, shows why each production is in the cell, and suggests the fix that applies.
Where this fits
The table here is built from the sets the FIRST and FOLLOW calculator computes, which is where to look when a cell has a conflict. If the grammar is left-recursive or cannot be left-factored into LL(1), bottom-up parsing usually works where top-down fails: try the same grammar in the LR parser, which handles left recursion as written.