LL Parsing and Parse Tables
Imagine a compiler front end that must decide, from a single token of lookahead, exactly which grammar rule to apply next. It does this with no backtracking, no guessing, and no wasted work. This is the promise of LL(1) parsing: a parser that reads its input left to right, builds a leftmost derivation. It needs only one symbol of lookahead to make every decision deterministically. The technique underlies hand-written recursive-descent parsers. It also underlies automatically generated table-driven parsers used in tools throughout the compiler ecosystem. The central engineering question is this: given a context-free grammar, can we mechanically decide which production to use at each step? Can we prove that decision is always unambiguous? The answer rests on two static analyses — FIRST sets and FOLLOW sets. These summarize, for every grammar symbol, which terminals can appear at the start of what it derives. They also summarize which terminals can follow it in some sentential form. From these sets we build a parse table, a two-dimensional lookup structure indexed by nonterminal and lookahead terminal. This table drives a simple stack-based parsing engine. This matters in real systems because table-driven predictive parsers are fast (linear time), compact, and easy to reason about formally. These properties are prized in compilers, configuration-file parsers, protocol decoders, and any tool that must parse untrusted or high-volume input predictably. Unlike general CFG parsing, LL(1) parsing rejects ambiguity and unbounded backtracking by construction. If the grammar satisfies the LL(1) conditions, parsing succeeds in one deterministic pass with no wasted lookahead. This article builds the theory from the ground up. It covers precise definitions of FIRST and FOLLOW, the algorithms that compute them, and the LL(1) condition that certifies a grammar is table-parsable. It also covers the construction of the parse table itself, and the driver algorithm that consumes it. We verify correctness via an invariant on the parser's stack. We analyze the exact time and space costs, closing with common grammar transformations (left-factoring, left-recursion elimination) needed to make real grammars LL(1)-friendly.
- FIRST(X) is the set of terminals that can begin some string derived from X; FOLLOW(A) is the set of
terminals that can immediately follow A in some derivation from the start symbol.
- A grammar is LL(1) if, for every nonterminal, the productions can be chosen uniquely given one lookahead
token — formalized via a no-overlap condition on FIRST/FOLLOW across alternatives.
- The parse table M[A, a] maps a nonterminal and terminal to the single production to expand, or to error.
- The table-driven parser is a simple stack machine: push the start symbol, then repeatedly expand
nonterminals via the table or match terminals against input.
- Parsing runs in O(n) time and O(n) worst-case stack space for input of length n, given a fixed grammar.
- Left recursion and shared prefixes among alternatives break the LL(1) condition and must be eliminated by
grammar transformation (left-recursion removal, left-factoring) before table construction.
LL(1) parsing works by precomputing, for every nonterminal and lookahead symbol, the single unambiguous production to expand — turning parsing into a deterministic table lookup.
The idea
A context-free grammar generates strings by rewriting nonterminals using productions. LL(1) parsing builds a leftmost derivation of the input string by scanning it left to right (the first "L") and constructing that derivation left-to-right as well (the second "L"), using exactly one token of lookahead (the "1"). The parser never backtracks: at every point, the single lookahead token determines which production to apply, or whether to match a terminal directly. To make this determinism possible we need two static sets. FIRST(α), for a string of grammar symbols α, is the set of terminals that can appear as the first symbol of some string derived from α; if α can derive the empty string ε, then ε is also considered a member for bookkeeping purposes. FOLLOW(A), for a nonterminal A, is the set of terminals that can appear immediately after A in some sentential form derivable from the start symbol S, including a special end-of-input marker `$` if A can be the last symbol before input ends. These two sets let us answer the question "given nonterminal A and lookahead token a, which production A → α should I expand?" without trying more than one alternative. A grammar is said to satisfy the LL(1) condition when, for every nonterminal A with alternative productions A → α₁ | α₂ | … | αₖ, the sets of terminals that can legally trigger each alternative are pairwise disjoint. This guarantees the parse table has at most one entry per cell — the defining property of predictive parsing, as opposed to general nondeterministic Context-Free Grammars parsing that may require backtracking or the more powerful machinery used in Bottom-Up Parsing.
How it works
Step 1 — Compute FIRST sets
FIRST is computed for every grammar symbol (terminals trivially first-of-themselves) and extended to strings. ``` function FIRST(X): // X is a single grammar symbol; memoized/global sets are built iteratively if X is a terminal: return { X } if X is ε: return { ε } // X is a nonterminal: computed via fixpoint iteration over all productions return FIRST_set[X] // filled in by the fixpoint algorithm below function COMPUTE_FIRST_SETS(grammar): for each nonterminal A: FIRST_set[A] = {} repeat changed = false for each production A -> X1 X2 ... Xn: // compute FIRST of the RHS symbol by symbol add_epsilon = true for i = 1 to n: if Xi is terminal: if Xi not in FIRST_set[A]: FIRST_set[A].add(Xi); changed = true add_epsilon = false break else: // Xi is a nonterminal for each t in FIRST_set[Xi] where t != ε: if t not in FIRST_set[A]: FIRST_set[A].add(t); changed = true if ε not in FIRST_set[Xi]: add_epsilon = false break if add_epsilon: // every Xi could derive ε, or n == 0 (A -> ε) if ε not in FIRST_set[A]: FIRST_set[A].add(ε); changed = true until not changed return FIRST_set ```
Step 2 — Compute FOLLOW sets
FOLLOW depends on FIRST and on where each nonterminal appears on the right-hand side of productions. ``` function COMPUTE_FOLLOW_SETS(grammar, FIRST_set): for each nonterminal A: FOLLOW_set[A] = {} FOLLOW_set[start_symbol].add('$') // end-of-input marker repeat changed = false for each production A -> X1 X2 ... Xn: for i = 1 to n: if Xi is a nonterminal: // look at what follows Xi in this production rest = X(i+1) ... Xn firstOfRest = FIRST_of_string(rest, FIRST_set) // may include ε for each t in firstOfRest where t != ε: if t not in FOLLOW_set[Xi]: FOLLOW_set[Xi].add(t); changed = true if rest is empty or ε in firstOfRest: for each t in FOLLOW_set[A]: if t not in FOLLOW_set[Xi]: FOLLOW_set[Xi].add(t); changed = true until not changed return FOLLOW_set function FIRST_of_string(X1 X2 ... Xn, FIRST_set): result = {} add_epsilon = true for i = 1 to n: for t in FIRST(Xi) where t != ε: result.add(t) if ε not in FIRST(Xi): add_epsilon = false break if add_epsilon: result.add(ε) return result ```
Step 3 — Build the parse table
For each production A → α, add it to cell M[A, a] for every terminal a in FIRST(α); if ε ∈ FIRST(α), also add it for every terminal (and ``) in FOLLOW(A). ``` function BUILD_PARSE_TABLE(grammar, FIRST_set, FOLLOW_set): M = empty table indexed by (nonterminal, terminal ∪ {}) is_LL1 = true for each production A -> α: firstAlpha = FIRST_of_string(α, FIRST_set) for each terminal a in firstAlpha where a != ε: if M[A, a] is already set: is_LL1 = false // conflict: grammar is not LL(1) M[A, a] = (A -> α) if ε in firstAlpha: for each b in FOLLOW_set[A]: // b ranges over terminals and possibly $ if M[A, b] is already set: is_LL1 = false M[A, b] = (A -> α) return M, is_LL1 ```
Step 4 — Drive the parser with a stack
``` function PARSE(input_tokens, M, start_symbol): stack = [ '' to input_tokens i = 0 while stack is not empty: top = stack.peek() a = input_tokens[i] if top is a terminal or top == '` as a sentinel marking the bottom.
Complexity & correctness
Table construction. Computing FIRST and FOLLOW uses fixpoint iteration over a monotonically growing family of finite sets bounded by the number of terminals plus ε (for FIRST) or terminals plus `$` (for FOLLOW). Each pass over all productions takes O(P·L) time, where P is the number of productions and L the maximum production length; because each set can only grow and is bounded by |Σ| + O(1), the number of passes is O(|N| + |Σ|), giving an overall polynomial bound — in practice near-linear for real grammars. Building the table itself is O(P·|Σ|) since each production contributes entries for at most |FIRST(α)| ≤ |Σ| terminals (plus FOLLOW(A) entries when ε is derivable).
Parsing time. Each iteration of the driving loop either matches a terminal (advancing the input pointer by one) or expands a nonterminal (replacing one stack symbol with a production's right-hand side). Since every terminal in the input is matched exactly once, and every stack expansion is charged against grammar symbols eventually derived, the total number of loop iterations is O(n + d) where n is the input length and d bounds the number of expansions used to derive it; for a fixed grammar this is O(n), because grammar size is a constant factor and every symbol pushed is eventually popped. Each iteration performs a single table lookup in O(1) time (array indexed by nonterminal and terminal). Hence predictive parsing runs in O(n) time.
Space. The stack can grow to depth proportional to the nesting depth of the derivation, which is O(n) in the worst case (e.g., deeply right-recursive or deeply nested constructs), giving O(n) space in the worst case, though typically much smaller (proportional to expression nesting depth) for realistic programs.
Correctness — invariant argument. Define the invariant: at every step, the stack contents (read top to bottom) concatenated with the unread suffix of the input, forms a string derivable from the start symbol via the leftmost derivation constructed so far, and the stack top is the leftmost remaining symbol to expand or match. Initially the stack is `[S, ` trivially satisfies this (S derives itself in zero steps). Each parser step preserves the invariant:
- If the top is a terminal equal to the lookahead, replacing "match top against input" with "advance both"
keeps the derived string consistent — we've simply confirmed one more terminal of the leftmost derivation.
- If the top is a nonterminal A and M[A, a] = (A → α) is defined, the LL(1) condition guarantees this is the
unique production whose expansion is consistent with lookahead a — by construction, a ∈ FIRST(α) or (α ⇒* ε and a ∈ FOLLOW(A)). Replacing A with α on the stack corresponds exactly to applying that production in the leftmost derivation. Termination follows because each step either consumes an input token or reduces the "derivation distance" — a well-founded measure since the derivation from A to the matched terminal string is finite for any grammar without infinite ε-loops. The parser accepts iff the stack and input are simultaneously exhausted, meaning the full leftmost derivation has been constructed matching the entire input — this is exactly membership in the language generated by the grammar.
LL(1) condition, formally. For productions A → α₁ | … | αₖ, correctness of table construction (each cell has at most one entry) requires: for all i ≠ j, ``` FIRST(αᵢ) ∩ FIRST(αⱼ) = ∅ ``` and if ε ∈ FIRST(αᵢ), then ``` FIRST(αⱼ) ∩ FOLLOW(A) = ∅ for all j ≠ i. ``` These conditions are exactly what BUILD_PARSE_TABLE checks implicitly via the "already set" collision test. If they fail, the grammar is not LL(1) — some other technique (Bottom-Up Parsing, general CFG parsing, or grammar rewriting) is required.
Honest tradeoffs. LL(1) parsing is fast and simple but strictly less powerful than LR parsing: it cannot handle left-recursive grammars directly, cannot handle grammars with unbounded lookahead requirements (genuinely needing 2+ tokens to disambiguate), and requires manual or automated grammar transformation to become table-friendly, which can obscure the grammar's original structure and complicate error messages tied to source productions.
Worked example
Consider the classic arithmetic expression grammar (already left-factored and non-left-recursive): ``` E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id ```
FIRST sets:
| Symbol | FIRST |
|---|---|
| F | { (, id } |
| T | { (, id } |
| T' | { *, ε } |
| E | { (, id } |
| E' | { +, ε } |
FOLLOW sets:
| Symbol | FOLLOW |
|---|---|
| E | { $, ) } |
| E' | { $, ) } |
| T | { +, $, ) } |
| T' | { +, $, ) } |
| F | { *, +, $, ) } |
Parse table (only nonempty cells shown):
| id | + | * | ( | ) | $ | |
|---|---|---|---|---|---|---|
| E | E→TE' | E→TE' | ||||
| E' | E'→+TE' | E'→ε | E'→ε | |||
| T | T→FT' | T→FT' | ||||
| T' | T'→ε | T'→*FT' | T'→ε | T'→ε | ||
| F | F→id | F→(E) |
Now trace parsing the input `id + id * id $`:
| Step | Stack (top→bottom) | Lookahead | Action |
|---|---|---|---|
| 1 | E, $ | id | M[E,id]=E→TE'; push T E' |
| 2 | T, E', $ | id | M[T,id]=T→FT'; push F T' |
| 3 | F, T', E', $ | id | M[F,id]=F→id; push id |
| 4 | id, T', E', $ | id | match id, advance input |
| 5 | T', E', $ | + | M[T',+]=T'→ε; pop T' |
| 6 | E', $ | + | M[E',+]=E'→+TE'; push + T E' |
| 7 | +, T, E', $ | + | match +, advance input |
| 8 | T, E', $ | id | M[T,id]=T→FT'; push F T' |
| 9 | F, T', E', $ | id | M[F,id]=F→id; push id |
| 10 | id, T', E', $ | id | match id, advance input |
| 11 | T', E', $ | * | M[T',]=T'→FT'; push * F T' |
| 12 | *, F, T', E', $ | * | match *, advance input |
| 13 | F, T', E', $ | id | M[F,id]=F→id; push id |
| 14 | id, T', E', $ | id | match id, advance input |
| 15 | T', E', $ | $ | M[T',$]=T'→ε; pop T' |
| 16 | E', $ | $ | M[E',$]=E'→ε; pop E' |
| 17 | $ | $ | match $, stack empty, input consumed |
Result: SUCCESS. The sequence of productions applied (steps 1, 2, 3, 6, 8, 9, 11, 13, 15, 16) is exactly the leftmost derivation of `id + id * id`, confirming the invariant held throughout: the stack never needed to guess, because at every branching point (E, E', T, T', F) the single lookahead token pinpointed one unique table cell.
Common pitfalls & traps
| Pitfall | Why it happens | Fix | ||
|---|---|---|---|---|
| Left recursion (A → Aα) | FIRST(Aα) includes FIRST(A), causing infinite table-construction loops or immediate parser non-termination | Rewrite using the standard left-recursion-elimination transformation into right-recursive form with a fresh nonterminal | ||
| Common prefixes among alternatives | A → αβ₁ \ | αβ₂ means FIRST sets overlap on α, violating LL(1) | Left-factor: introduce A → αA', A' → β₁ \ | β�2 |
| Forgetting ε in FIRST propagation | Omitting the case where a symbol derives ε causes FIRST(αβ) to miss terminals that start β | Explicitly check "does Xᵢ derive ε" before stopping the FIRST-of-string scan | ||
| FOLLOW computed before FIRST stabilizes | FOLLOW depends on FIRST-of-suffix; using a partial FIRST set yields incomplete FOLLOW sets | Always run FIRST to a complete fixpoint before starting FOLLOW's fixpoint | ||
| Off-by-one in table lookup on ε-productions | Forgetting to add ε-productions to every terminal in FOLLOW(A), not just one | Loop over the entire FOLLOW(A) set, including `$` | ||
| Treating LL(1) table conflicts as fatal without diagnosis | A single ambiguous cell can stem from left recursion, common prefixes, or genuine ambiguity in the language | Inspect FIRST/FOLLOW overlap directly to classify the cause before rewriting blindly |
Pioneers & history
The theory of LL parsing emerged from the broader formalization of context-free languages and their algorithmic recognition, closely tied to the study of deterministic parsing strategies that made compiler construction tractable and teachable.
Origins · 1 minJohn Backus and how this was discovered
Where this matters
Table-driven LL(1) parsing (and its close relative, recursive-descent parsing built by hand from the same FIRST/FOLLOW analysis) appears throughout production compiler front ends, particularly for languages whose grammars can be shaped to avoid left recursion and shared prefixes — configuration languages, many domain-specific languages, JSON-like data formats, and simplified expression grammars in scripting engines. Parser generators historically offered LL(1)/LL(k) modes as lightweight alternatives to LALR tables when grammars were simple and hand-tuned error messages mattered more than raw grammar generality. Understanding FIRST/FOLLOW analysis is also a prerequisite for Bottom-Up Parsing techniques like LR and LALR parsing, which use analogous lookahead sets (though computed and applied differently) to build shift-reduce tables, and for understanding why certain grammars require backtracking parsers or Context-Free Grammars transformations before they become efficiently parsable at all. The discipline of proving a grammar LL(1) before generating code also underlies static verification tools that catch grammar ambiguities before they become runtime parsing bugs.
:::quiz[In the table-driven parser, what happens when the stack top is a nonterminal A and lookahead is a, with M[A,a] undefined?]
- The parser silently skips the nonterminal and continues
- The parser reports a syntax error, since no production is legally applicable ✓
- The parser backtracks and tries a different production
- The parser inserts an ε-production automatically
Ask the tutor: Can you show how to eliminate indirect left recursion in a multi-nonterminal grammar before building its LL(1) table?
Why is one token of lookahead enough for LL(1) grammars but not for all context-free grammars?
LL(1) grammars are specifically those satisfying the disjointness condition on FIRST/FOLLOW sets, meaning one lookahead token always uniquely determines the next production. Not every context-free grammar has this property — some require unbounded lookahead to disambiguate, or are inherently ambiguous, meaning no fixed lookahead bound suffices. For such grammars, parsing needs either backtracking, transformation into an LL(1)-equivalent grammar (not always possible while preserving structure), or a fundamentally different strategy such as Bottom-Up Parsing, which defers decisions until more context (via the stack of already recognized symbols) is available.
How exactly does left-recursion elimination make a grammar LL(1)-compatible?
Left recursion, A → Aα | β, is rewritten as A → βA', A' → αA' | ε, converting immediate left recursion into right recursion via a fresh nonterminal A'. This preserves the language generated (the same set of strings is derivable) while removing the infinite regress that made both FIRST-set computation and predictive parsing loop indefinitely on A. Indirect left recursion, spread across multiple nonterminals, requires a more general substitution algorithm that first expands indirect derivations back into direct left recursion before applying this rewrite, and orders nonterminals to guarantee termination.
What is left-factoring and when is it needed?
Left-factoring is required when two productions for the same nonterminal share a common prefix, such as A → αβ₁ | αβ₂, which makes FIRST(αβ₁) and FIRST(αβ₂) overlap on FIRST(α). The transformation introduces a new nonterminal A' to defer the choice: A → αA', A' → β₁ | β₂. This lets the parser consume the shared prefix α first, then use the next token after α to choose between β₁ and β₂, restoring the LL(1) disjointness condition without changing the language.
Can every deterministic context-free language be expressed by some LL(1) grammar?
No. LL(1) grammars form a strict subset of the deterministic context-free grammars; some deterministic languages have no LL(1) grammar at all, because LL parsing commits to a production based only on what has been derived so far plus one lookahead token, whereas LR parsing (used in Bottom-Up Parsing) can defer decisions until an entire right-hand side has been recognized on the stack. This is why LR(1) and LALR parsers, though more complex to construct by hand, accept a strictly larger class of unambiguous grammars.
How does the FIRST/FOLLOW fixpoint algorithm guarantee termination?
Both FIRST and FOLLOW are computed by repeatedly scanning productions and adding terminals to sets, never removing them, until no set changes in a full pass. Since every set is a subset of a finite universe (terminals, plus ε for FIRST or `$` for FOLLOW), and each pass either adds at least one element to some set or does nothing, the total number of element-additions is bounded by |N| × (|Σ| + O(1)). This finite, monotonically increasing quantity guarantees the fixpoint is reached in a bounded number of passes.
Why does the parser use a stack instead of, say, recursive function calls?
A stack-based driver with an explicit parse table and a recursive-descent parser are two implementations of the exact same underlying algorithm: recursive descent uses the language runtime's call stack implicitly (one function per nonterminal, with the "table lookup" hardcoded as if/switch statements), while the table-driven version manages an explicit stack and a single generic driving loop. The explicit-stack version is often preferred when the grammar is generated automatically, since the parser logic is entirely data-driven by the table and requires no per-grammar code generation.
What happens if the grammar has ambiguity that FIRST/FOLLOW analysis alone cannot detect?
FIRST/FOLLOW analysis and the LL(1) disjointness check are a sufficient mechanism for certifying a grammar usable by a predictive parser, but genuine language-level ambiguity (multiple distinct parse trees for the same string) will always manifest as a table conflict somewhere, since two different derivations must diverge on some production choice reachable by some lookahead. So while the analysis doesn't directly "prove ambiguity" in the abstract sense, any LL(1) table-construction conflict is a reliable, mechanically detectable symptom that the grammar (as written) cannot support one-token predictive parsing.