LL(1) Predictive Parsing
A stack of what is still expected, one lookahead token, and no backtracking anywhere.
Skip to the animationAn LL(1) parser holds a stack of symbols it still expects, and uses one lookahead token plus a table to decide, without ever backtracking, which production to apply.
The stack means the opposite of LR's
This is the distinction worth fixing firmly. A shift-reduce parser's stack holds what it has already recognised, and it works from the tokens toward the start symbol. An LL parser's stack holds what it still expects to see, and it works from the start symbol toward the tokens.
So the LL stack, read from the top down, is a live prediction about the rest of the input — revised each time a non-terminal is expanded.
| LL(1) | LR(1) | |
|---|---|---|
| Direction | top-down | bottom-up |
| Stack holds | what is expected | what is recognised |
| Derivation | leftmost, forwards | rightmost, backwards |
| Left recursion | must be removed | handled naturally |
| Power | weaker | strictly stronger |
| By hand | easy — recursive descent | impractical |
Two moves, and that is all
- 1Non-terminal on top: look up
table[A][lookahead], pop A, and push the production's right-hand side in reverse so its leftmost symbol ends up on top. - 2Terminal on top: it must equal the lookahead. Pop it and advance the input. If it does not match, that is a syntax error.
- 3Empty stack and empty input: accept.
Pushing in reverse is the detail people get wrong. The stack is last-in-first-out, and the leftmost symbol of the production must be processed first.
Where ε-productions come in
When T' is on top and the lookahead is +, there is no multiplication ahead — so T' must vanish. The table cell holds T' → ε: pop and push nothing.
That cell is populated from FOLLOW(T'), not FIRST. It is the only reason FOLLOW sets are computed at all, and it is why grammars with ε-productions need both sets.
Recursive descent
The table-driven version above and a hand-written recursive-descent parser are the same algorithm. Each non-terminal becomes a function; the call stack replaces the explicit stack; a switch on the lookahead replaces the table lookup.
That equivalence is why LL parsing survives despite being weaker than LR: the parser is readable, debuggable ordinary code, error messages can be written by hand exactly where they are needed, and no tool is required. Several major production compilers use recursive descent for precisely these reasons.
Advantages and disadvantages
Advantages
- Linear time with no backtracking, one lookahead token per decision.
- Maps directly onto recursive descent, which is readable and easy to debug.
- Errors are detected at the earliest possible token, and messages can be hand-written.
Disadvantages
- Cannot handle left recursion — the grammar must be rewritten, obscuring its structure.
- Common prefixes must be left factored.
- Strictly weaker than LR; many real language grammars are not LL(1).
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.