The idea: pick the production from one token
A parser gets a list of tokens, such as id + id * id, and a grammar, and
has to find how the grammar builds those tokens. A top-down parser starts from the start
symbol E and keeps replacing the leftmost nonterminal by the right side of one of its productions. The hard
part is the choice: E' has two productions, which one is right? An LL(1) parser never
guesses and never goes back. It looks at the nonterminal it must expand and at one lookahead
token, the next token of the input, and reads the answer from a table. The name says it: read the
input Left to right, build a Leftmost derivation, use
1 token of lookahead.
The page uses the usual expression grammar. E is a sum of terms, T is a product of factors, F is an
id or a bracketed expression. ε means the empty string, and $ marks the end of
the input.
E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | id
FIRST sets
FIRST(A) is the set of tokens that a string derived from A can start with. If A can derive the empty string, ε is in the set too. Go through the productions of A: a right side that starts with a token gives that token; a right side that starts with a nonterminal B gives all of FIRST(B). So FIRST(F) = {id, (} from F → id and F → ( E ), then FIRST(T) = FIRST(F) because T → F T', and FIRST(E) = FIRST(T). E' → + T E' | ε gives FIRST(E') = {+, ε}.
FOLLOW sets
FOLLOW(A) is the set of tokens that can come right after A in some derivation. It is needed for the productions that can vanish: the parser should pick E' → ε only when the next token is one that may follow E'. Three rules build the sets:
$is in FOLLOW of the start symbol.- For a production B → α A β, everything in FIRST(β) except ε is in FOLLOW(A).
- If A is last in B → α A, or β can vanish, everything in FOLLOW(B) is in FOLLOW(A).
| nonterminal | FIRST | FOLLOW |
|---|---|---|
| E | {id, (} | {), $} |
| E' | {+, ε} | {), $} |
| T | {id, (} | {+, ), $} |
| T' | {*, ε} | {+, ), $} |
| F | {id, (} | {+, *, ), $} |
For example, F → ( E ) puts ) in FOLLOW(E). In E → T E', T is followed by E', which starts with +, and E' can vanish, so FOLLOW(T) = {+} plus FOLLOW(E) = {+, ), $}. (Demo: FIRST, FOLLOW and the table for the expression grammar)
Filling the parse table
The parse table M has one row per nonterminal and one column per token. Each production A → α is filed with two rules:
- under every token in FIRST(α);
- if α can vanish, also under every token in FOLLOW(A).
For the expression grammar, 13 of the 5 × 6 = 30 cells get a production and no cell gets two. A grammar whose table has at most one production per cell is an LL(1) grammar. The 17 empty cells are syntax errors.
The parser loop
The predictive parser is a loop over a stack that starts as $ E (E on
top). Each move looks at the top of the stack X and the lookahead a:
- Expand. X is a nonterminal: take M[X, a] = X → α, pop X and push α in reverse, so the first symbol of α is on top.
- Match. X is a token and X = a: pop it and move to the next token.
- Accept. X and a are both
$.
The input id + id * id takes 17 moves: 11 expansions, 5 matches (one per token) and the
accept. The stack never holds more than 5 symbols. The first moves are:
| # | stack (top at right) | input left | action |
|---|---|---|---|
| 1 | $ E | id + id * id $ | E → T E' |
| 2 | $ E' T | id + id * id $ | T → F T' |
| 3 | $ E' T' F | id + id * id $ | F → id |
| 4 | $ E' T' id | id + id * id $ | match id |
| 5 | $ E' T' | + id * id $ | T' → ε |
| 6 | $ E' | + id * id $ | E' → + T E' |
In move 5 the lookahead + is in FOLLOW(T'), so T' vanishes: the product is over. Read from top to bottom, the expansions are a leftmost derivation of the input. Every move takes constant time and each token is matched once, so parsing is linear in the length of the input. (Demo: accept id + id * id)
Syntax errors
The parser stops at the first token that cannot continue a valid input. There are two ways to fail:
- Empty cell. In
id + * idthe parser has T on top after the + and sees *. M[T, *] is empty, so move 8 reports an error at token 3: a term must start with id or (. (Demo: reject id + * id) - Failed match. In
( id + idthe parser pushed a ) when it expanded F → ( E ). At move 17 that ) is on top but the lookahead is$: the closing bracket is missing. (Demo: reject ( id + id)
Because the table knows which cells of a row are filled, the error message can list what was expected.
Conflicts: left recursion and common prefixes
If two productions land in the same cell, the table has a conflict and the grammar is not LL(1): one token cannot tell the parser which production to use. Two grammar shapes always cause one.
Left recursion. The natural expression grammar says E → E + T | T. The right side E + T starts with E itself, so it can start with everything that T can start with. Both productions go under id and under (. With T → T * F | F doing the same, the table has 4 conflicts: M[E, id], M[E, (], M[T, id] and M[T, (]. The fix moves the repetition to the right: A → A α | β becomes A → β A' and A' → α A' | ε. That turns E → E + T | T into E → T E', E' → + T E' | ε, the grammar at the top of this page. (Demo: left recursion gives 4 conflicts)
Common prefix. In E → T + E | T both right sides start with T, so both go under id:
1 conflict. Left factoring takes the shared start out and puts the choice after it:
A → α β | α γ becomes A → α A' and A' → β | γ. Here E → T E' and E' → + E | ε. Now the choice is made
after T has been read, when the lookahead is + or $, and the table has 4 filled cells and no
conflict. (Demo: common prefix gives a conflict, Demo: left-factored grammar parses
id + id)
| grammar | cells | filled | conflicts | LL(1)? |
|---|---|---|---|---|
| expression grammar | 30 | 13 | 0 | yes |
| left-recursive | 18 | 6 | 4 | no |
| common prefix | 6 | 2 | 1 | no |
| left-factored | 9 | 4 | 0 | yes |
See also Inside a Tiny Compiler, whose recursive-descent parser is the same idea written as functions instead of a table, CYK parsing, a table method that handles any context-free grammar in cubic time, the pushdown automaton, the stack machine behind every context-free parser, and Regex to NFA to DFA for the lexer that produces the tokens.
See also LR parsing, the bottom-up method that shifts tokens and reduces handles, uses the left-recursive grammar as it is, and uses FOLLOW sets to place its reduces.
See also Static vs Dynamic Scoping for what the compiler does with names after parsing: a symbol table kept as a stack of scopes.
See also the Earley parser, which predicts top down like LL(1) but handles left-recursive rules such as NP → NP PP without looping.
See also Hindley-Milner type inference, which takes an expression tree like the one a parser builds and gives each node a type.
What the page leaves out
The grammars and inputs are fixed presets; the page does not rewrite a grammar for you or build the parse tree. It leaves out error recovery (panic mode with synchronizing tokens, so that one parse reports several errors), LL(k) and LL(*) parsers with more lookahead, ambiguous grammars such as the dangling else that no rewriting makes LL(1), and the bottom-up LR family (SLR, LALR, LR(1)) that parser generators such as yacc and bison use.