Chapter 6

LL(1) Predictive Parsing

Replace manual lookahead logic with a parsing table. One table entry tells you exactly which production to apply — no guessing, no backtracking.

L = Left-to-right scan L = Leftmost derivation 1 = One symbol lookahead
Section 1

Why LL(1)?

Recursive descent works but has a problem — each function needs hand-written lookahead logic. LL(1) automates this.

Aspect Recursive Descent LL(1) Predictive
Lookahead logic Hand-written in every function Automatically derived from grammar
Decision mechanism if(peek()=='+') scattered everywhere Single table lookup: M[NT, terminal]
Stack management Implicit (call stack) Explicit (you control the stack)
Automation Must write parser by hand Parser can be generated from grammar
Conflicts detectable? No — silent ambiguities Yes — duplicate table entries are conflicts
📋

The Parsing Table M

M[A, a] tells us which production to use when A is on top of the stack and a is the current input token.

🔑

Built From FIRST + FOLLOW

The table entries are derived from two fundamental sets: FIRST (what a string can start with) and FOLLOW (what can follow a non-terminal).

⚡

Linear Time Parsing

With the table built, parsing is O(n) — each input token is consumed exactly once, and each stack operation is O(1) table lookup.

The Grammar We'll Use:
E → T E'    E' → + T E' | ε    T → F T'    T' → * F T' | ε    F → (E) | id

This is the left-recursion-free expression grammar from Chapter 5.
Section 2

FIRST Set Computation

FIRST(α) = all terminals that can appear as the first symbol of any string derived from α.

Definition: FIRST(X) for a symbol X is:
  • If X is a terminal: FIRST(X) = {X}
  • If X → ε: add ε to FIRST(X)
  • If X → Y₁Y₂…Yₙ: add FIRST(Y₁)–{ε}. If ε ∈ FIRST(Y₁), add FIRST(Y₂)–{ε}, etc.
  • If all Yᵢ can derive ε, add ε to FIRST(X)
FIRST Sets (current state)
Current Rule Being Applied
Press Next to begin computing FIRST sets step by step.
Step Log

✅ Final FIRST Sets

FIRST(E)
id (
FIRST(E')
+ ε
FIRST(T)
id (
FIRST(T')
* ε
FIRST(F)
id (
Notice that FIRST(E) = FIRST(T) = FIRST(F) = {id, (} — because every expression ultimately starts with a factor, and factors start with either id or (.
Section 3

FOLLOW Set Computation

FOLLOW(A) = all terminals that can appear immediately after A in any sentential form.

FOLLOW Sets (current state)
Current Rule Being Applied
Press Next to begin computing FOLLOW sets step by step.
Step Log

✅ Final FOLLOW Sets

FOLLOW(E)
) $
FOLLOW(E')
) $
FOLLOW(T)
+ ) $
FOLLOW(T')
+ ) $
FOLLOW(F)
* + ) $
Section 4

LL(1) Table Construction

For each production, determine which table cells to fill using FIRST and FOLLOW sets.

Algorithm: For each production A → α
  1. For each terminal a in FIRST(α): set M[A, a] = A → α
  2. If ε ∈ FIRST(α): for each terminal b in FOLLOW(A): set M[A, b] = A → α
  3. If ε ∈ FIRST(α) and $ ∈ FOLLOW(A): set M[A, $] = A → α
Parsing Table M (being filled)
id + * ( ) $
E
E'
T
T'
F
Insertion Reason
Press Next to begin filling the LL(1) table.
Insertions Log
Section 5

Complete LL(1) Parsing Table

The finished table used by the predictive parser during simulation.

NT \ Terminal 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)
Blue cells (E→TE', T→FT', etc.): filled because the terminal is in FIRST of the right-hand side.
Gray cells (E'→ε, T'→ε): filled because ε is in FIRST of the RHS, so FOLLOW determines which columns get the ε-production.
No Conflicts! Each cell has at most one entry — this grammar is LL(1). If any cell had two entries, the grammar would not be LL(1) and we'd need to transform it (or use LR parsing).
Section 6

Stack Simulation: Parsing id + id * id

Watch the explicit stack and parsing table work together to recognize the input.

Algorithm: Push $ then the start symbol (E) onto the stack.
• If top = current token → Match (pop both)
• If top is a non-terminal → Apply M[top, token] (pop NT, push RHS in reverse)
• If top = $ and input = $ → Accept!
Stack (top → right) Input Action
Current Step Explanation
Press Next to start the simulation.
← 5. Recursive Descent 7. LR(0) →