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 three parts of an LL(1) parser. The input id + id * id $ with the lookahead on the first id. The stack holding $ and E' with T on top. The parse table M: row T, column id holds T → F T'. An arrow from the stack top T and an arrow from the lookahead id meet at that cell; the result is to pop T and push F T', leaving F on top.
The parser's whole decision: the stack top (T) and the lookahead (id) pick one table cell, and the cell says what to push.

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).
nonterminalFIRSTFOLLOW
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).
Row E' of the parse table with columns id, +, *, (, ), $. The production E' → + T E' has FIRST = {+}, so it goes under +. The production E' → ε can vanish, so it uses FOLLOW(E') = {), $} and goes under ) and under $. The cells under id, * and ( stay empty: errors.
Row E': the production that starts with + goes under +; the ε production goes under FOLLOW(E') = {), $}; the rest are errors.

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 leftaction
1$ Eid + id * id $E → T E'
2$ E' Tid + id * id $T → F T'
3$ E' T' Fid + id * id $F → id
4$ E' T' idid + 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 + * id the 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 + id the 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)

Two rewrites, before and after. Left recursion: E → E + T | T puts two productions in M[E, id], a conflict; rewritten as E → T E' and E' → + T E' | ε, each cell holds one production. Common prefix: E → T + E | T puts two productions in M[E, id]; left factored as E → T E' and E' → + E | ε, each cell holds one production.
Both problems put two productions in M[E, id]; both rewrites add a helper nonterminal E' so the choice is made one token later.
grammarcellsfilledconflictsLL(1)?
expression grammar30130yes
left-recursive1864no
common prefix621no
left-factored940yes

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.

On the mind map

Open the Java & the JVM mind mapJava & the JVMFrom source to bytecode: translate first, or while runningFrom source to bytecodeStartup and class loading: what happens before main()Startup and class loadingJIT compilers: compile hot code using profilesJIT compilersMemory and GC: find and free unreachable objectsMemory and GCCollections: how java.util stores keysCollectionsThreads and memory model: Java threads on real coresThreads and memory modelSpring framework: a container builds your objectsSpring frameworkCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceHindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingStack top + one token pick the productionLR parsingLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links onceOpen the Java & the JVM mind mapJava & the JVMtranslate first, or while runningFrom source to bytecodeCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceHindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingStack top + one token pick the productionLR parsingLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links once
This page on the Java & the JVM mind map · 35 pages in 7 branches · open it to see the whole map and test yourself in recall mode.