LL(1) Parsing

Put it all together — learn how an LL(1) parser uses a parsing table built from FIRST and FOLLOW sets to parse any LL(1) grammar in linear time without backtracking.

What Does LL(1) Mean?

LL(1) is a notation that describes a class of parsers and grammars:

L (first): read input Left to right
L (second): build a Leftmost derivation
(1): use 1 token of lookahead to make every decision

An LL(1) parser is a table-driven predictive parser that uses exactly one token of lookahead to decide which production to apply. It never backtracks.

Why "1 Token of Lookahead"?

Compare LL(k) parsers with different lookahead values:

Example

LL(0): No lookahead — must pick a production blindly. Almost no real grammars.

LL(1): One token lookahead — sufficient for most practical grammars.

LL(2): Two tokens lookahead — handles more grammars, but tables are larger.

LL(k): k tokens — theoretically any context-free language, but impractical.

LL(1) is the sweet spot: powerful enough for most languages, and the parsing table is small and fast.

The Two Key Components

An LL(1) parser requires:

A grammar that is LL(1) — no left recursion, no common prefixes, and no conflict in the parsing table.
A parsing table M[A][a] — a 2D table indexed by (non-terminal, terminal) that tells the parser exactly which production to use.

Building the LL(1) Parsing Table

Algorithm: For each production A → α in the grammar:

Example

1. For each terminal a ∈ FIRST(α) − {ε}:

Add A → α to M[A][a]

2. If ε ∈ FIRST(α):

For each terminal b ∈ FOLLOW(A): (including $)

Add A → α to M[A][b]

3. All empty entries in M are errors.

Full Example — Arithmetic Expression Grammar

Grammar:

Example

E → T E'

E' → + T E' | ε

T → F T'

T' → * F T' | ε

F → ( E ) | id

FIRST sets:

Example

FIRST(E) = { (, id }

FIRST(E') = { +, ε }

FIRST(T) = { (, id }

FIRST(T') = { *, ε }

FIRST(F) = { (, id }

FOLLOW sets:

Example

FOLLOW(E) = { $, ) }

FOLLOW(E') = { $, ) }

FOLLOW(T) = { +, $, ) }

FOLLOW(T') = { +, $, ) }

FOLLOW(F) = { *, +, $, ) }

Filling the table:

Production	FIRST of RHS	FOLLOW of LHS	Table entries added
E → T E'	{ (, id }	—	M[E][(] = E→TE', M[E][id] = E→TE'
E' → + T E'	{ + }	—	M[E'][+] = E'→+TE'
E' → ε	{ ε } → use FOLLOW	{ $, ) }	M[E'][$] = E'→ε, M[E'][)] = E'→ε
T → F T'	{ (, id }	—	M[T][(] = T→FT', M[T][id] = T→FT'
T' → * F T'	{ * }	—	M[T'][] = T'→FT'
T' → ε	{ ε } → use FOLLOW	{ +, $, ) }	M[T'][+] = T'→ε, M[T'][$] = T'→ε, M[T'][)] = T'→ε
F → ( E )	{ ( }	—	M[F][(] = F→(E)
F → id	{ id }	—	M[F][id] = F→id

Complete Parsing Table:

Example

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)

Every cell has at most one entry — this grammar is LL(1).

The LL(1) Parsing Algorithm

The parser uses a stack to track what still needs to be matched, and the parsing table to decide what to do next.

Algorithm

Example

Push $ onto the stack

Push start symbol S onto the stack

a = next input token

loop:

X = top of stack

if X == $ and a == $:

accept — parse successful ✓

if X is a terminal:

if X == a:

pop X from stack

a = next input token ← match

else:

error() ← expected X, got a

if X is a non-terminal:

if M[X][a] == X → Y₁ Y₂ … Yₖ:

pop X from stack

push Yₖ, Yₖ₋₁, …, Y₁ ← push in REVERSE order

else:

error() ← no production for (X, a)

Important: Push symbols in reverse order so Y₁ ends up on top of the stack (leftmost is processed first).

Step-by-Step Trace — Parsing "id + id * id"

Input: id + id * id $

Example

Stack Input Action

──────────────────────────────────────────────────────────

E $ id + id * id $ M[E][id] = E→TE' → expand

T E' $ id + id * id $ M[T][id] = T→FT' → expand

F T' E' $ id + id * id $ M[F][id] = F→id → expand

id T' E' $ id + id * id $ top=id, input=id → match

T' E' $ + id * id $ M[T'][+] = T'→ε → expand to ε (pop)

E' $ + id * id $ M[E'][+] = E'→+TE' → expand

+ T E' $ + id * id $ top=+, input=+ → match

T E' $ id * id $ M[T][id] = T→FT' → expand

F T' E' $ id * id $ M[F][id] = F→id → expand

id T' E' $ id * id $ top=id, input=id → match

T' E' $ * id $ M[T'][*] = T'→*FT' → expand

* F T' E' $ * id $ top=*, input=* → match

F T' E' $ id $ M[F][id] = F→id → expand

id T' E' $ id $ top=id, input=id → match

T' E' $ $ M[T'][$] = T'→ε → expand to ε (pop)

E' $ $ M[E'][$] = E'→ε → expand to ε (pop)

$ $ top=$ and input=$ → Accept ✓

LL(1) Conflicts — When a Grammar Is NOT LL(1)

A grammar is not LL(1) if its parsing table has a cell with more than one production. This is called a conflict.

Type 1 — FIRST/FIRST Conflict

Two productions for the same non-terminal start with the same terminal.

Example

S → a b | a c

Both productions start with a. When we see a, we cannot decide which to use.

Example

M[S][a] = { S→ab, S→ac } ← TWO entries — conflict!

Fix: Left-factor the grammar.

Example

S → a S'

S' → b | c

Now M[S'][b] = S'→b and M[S'][c] = S'→c — no conflict.

Type 2 — FIRST/FOLLOW Conflict

A non-terminal has both an ε-production and a production that starts with a terminal in FOLLOW.

Example

A → a | ε

If a ∈ FOLLOW(A), then when we see a, we cannot decide:

Use A → a (match the 'a')
Use A → ε (let 'a' be matched by whoever follows A)

Example

M[A][a] = { A→a, A→ε } ← conflict!

This usually means the grammar is inherently ambiguous for LL(1) parsing and needs to be redesigned.

Checking LL(1) Conditions

A grammar is LL(1) if and only if:

Example

For every non-terminal A with two productions A → α and A → β:

Condition 1: FIRST(α) ∩ FIRST(β) = ∅

(no terminal starts both productions)

Condition 2: At most one of α and β can derive ε.

Condition 3: If β ⟹* ε, then FIRST(α) ∩ FOLLOW(A) = ∅

(if β can vanish, α must not start with something in FOLLOW(A))

If all three conditions hold for every pair of productions, the grammar is LL(1).

Worked Example — Full LL(1) Parse

Let's work through a complete example from grammar to parse.

Grammar:

Example

S → ( S ) S | ε

This grammar generates all strings of balanced parentheses (including the empty string).

Step 1 — FIRST sets:

Example

FIRST(S) = FIRST( ( S ) S ) ∪ FIRST(ε)

= { ( } ∪ { ε }

= { (, ε }

Step 2 — FOLLOW sets:

Example

S is the start symbol → add $ to FOLLOW(S)

From S → ( S ) S:

First S inside: β = ) S

FIRST() S) = { ) } → add ) to FOLLOW(first S)

) is not ε-deriving, so stop here.

Second S inside: β = ε (it's at the end)

add FOLLOW(S) to FOLLOW(second S) → add { $, ) } to FOLLOW(S)

FOLLOW(S) = { $, ) }

Step 3 — Build parsing table:

Example

Production S → ( S ) S :

FIRST of RHS = { ( } → M[S][(] = S → ( S ) S

Production S → ε :

ε in FIRST → use FOLLOW(S) = { $, ) }

M[S][$] = S → ε

M[S][)] = S → ε

Parsing table:

Example

( ) $

────────────────────────────────────────

S S→(S)S S→ε S→ε

Step 4 — Parse "(())"

Example

Stack Input Action

─────────────────────────────────────────────

S $ ( ( ) ) $ M[S][(] = S→(S)S → expand

( S ) S $ ( ( ) ) $ match (

S ) S $ ( ) ) $ M[S][(] = S→(S)S → expand

( S ) S ) S $ ( ) ) $ match (

S ) S ) S $ ) ) $ M[S][)] = S→ε → expand to ε (pop)

) S ) S $ ) ) $ match )

S ) S $ ) $ M[S][)] = S→ε → expand to ε (pop)

) S $ ) $ match )

S $ $ M[S][$] = S→ε → expand to ε (pop)

$ $ Accept ✓

The parse correctly recognises "(())" as a valid balanced-parenthesis string.

Summary

Example

Step 1: Eliminate left recursion

Step 2: Left-factor common prefixes

Step 3: Compute FIRST sets

Step 4: Compute FOLLOW sets

Step 5: Build parsing table M[A][a]

Step 6: Check for conflicts (if conflict → grammar is not LL(1))

Step 7: Run the stack-based algorithm on the input

What Does LL(1) Mean?

LL(1) is a notation that describes a class of parsers and grammars:

L (first): read input Left to right
L (second): build a Leftmost derivation
(1): use 1 token of lookahead to make every decision

An LL(1) parser is a table-driven predictive parser that uses exactly one token of lookahead to decide which production to apply. It never backtracks.

Why "1 Token of Lookahead"?

Compare LL(k) parsers with different lookahead values:

Example

LL(0): No lookahead — must pick a production blindly. Almost no real grammars.

LL(1): One token lookahead — sufficient for most practical grammars.

LL(2): Two tokens lookahead — handles more grammars, but tables are larger.

LL(k): k tokens — theoretically any context-free language, but impractical.

LL(1) is the sweet spot: powerful enough for most languages, and the parsing table is small and fast.

The Two Key Components

An LL(1) parser requires:

A grammar that is LL(1) — no left recursion, no common prefixes, and no conflict in the parsing table.
A parsing table M[A][a] — a 2D table indexed by (non-terminal, terminal) that tells the parser exactly which production to use.

Building the LL(1) Parsing Table

Algorithm: For each production A → α in the grammar:

Example

1. For each terminal a ∈ FIRST(α) − {ε}:

Add A → α to M[A][a]

2. If ε ∈ FIRST(α):

For each terminal b ∈ FOLLOW(A): (including $)

Add A → α to M[A][b]

3. All empty entries in M are errors.

Full Example — Arithmetic Expression Grammar

Grammar:

Example

E → T E'

E' → + T E' | ε

T → F T'

T' → * F T' | ε

F → ( E ) | id

FIRST sets:

Example

FIRST(E) = { (, id }

FIRST(E') = { +, ε }

FIRST(T) = { (, id }

FIRST(T') = { *, ε }

FIRST(F) = { (, id }

FOLLOW sets:

Example

FOLLOW(E) = { $, ) }

FOLLOW(E') = { $, ) }

FOLLOW(T) = { +, $, ) }

FOLLOW(T') = { +, $, ) }

FOLLOW(F) = { *, +, $, ) }

Filling the table:

Production	FIRST of RHS	FOLLOW of LHS	Table entries added
E → T E'	{ (, id }	—	M[E][(] = E→TE', M[E][id] = E→TE'
E' → + T E'	{ + }	—	M[E'][+] = E'→+TE'
E' → ε	{ ε } → use FOLLOW	{ $, ) }	M[E'][$] = E'→ε, M[E'][)] = E'→ε
T → F T'	{ (, id }	—	M[T][(] = T→FT', M[T][id] = T→FT'
T' → * F T'	{ * }	—	M[T'][] = T'→FT'
T' → ε	{ ε } → use FOLLOW	{ +, $, ) }	M[T'][+] = T'→ε, M[T'][$] = T'→ε, M[T'][)] = T'→ε
F → ( E )	{ ( }	—	M[F][(] = F→(E)
F → id	{ id }	—	M[F][id] = F→id

Complete Parsing Table:

Example

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)

Every cell has at most one entry — this grammar is LL(1).

The LL(1) Parsing Algorithm

The parser uses a stack to track what still needs to be matched, and the parsing table to decide what to do next.

Algorithm

Example

Push $ onto the stack

Push start symbol S onto the stack

a = next input token

loop:

X = top of stack

if X == $ and a == $:

accept — parse successful ✓

if X is a terminal:

if X == a:

pop X from stack

a = next input token ← match

else:

error() ← expected X, got a

if X is a non-terminal:

if M[X][a] == X → Y₁ Y₂ … Yₖ:

pop X from stack

push Yₖ, Yₖ₋₁, …, Y₁ ← push in REVERSE order

else:

error() ← no production for (X, a)

Important: Push symbols in reverse order so Y₁ ends up on top of the stack (leftmost is processed first).

Step-by-Step Trace — Parsing "id + id * id"

Input: id + id * id $

Example

Stack Input Action

──────────────────────────────────────────────────────────

E $ id + id * id $ M[E][id] = E→TE' → expand

T E' $ id + id * id $ M[T][id] = T→FT' → expand

F T' E' $ id + id * id $ M[F][id] = F→id → expand

id T' E' $ id + id * id $ top=id, input=id → match

T' E' $ + id * id $ M[T'][+] = T'→ε → expand to ε (pop)

E' $ + id * id $ M[E'][+] = E'→+TE' → expand

+ T E' $ + id * id $ top=+, input=+ → match

T E' $ id * id $ M[T][id] = T→FT' → expand

F T' E' $ id * id $ M[F][id] = F→id → expand

id T' E' $ id * id $ top=id, input=id → match

T' E' $ * id $ M[T'][*] = T'→*FT' → expand

* F T' E' $ * id $ top=*, input=* → match

F T' E' $ id $ M[F][id] = F→id → expand

id T' E' $ id $ top=id, input=id → match

T' E' $ $ M[T'][$] = T'→ε → expand to ε (pop)

E' $ $ M[E'][$] = E'→ε → expand to ε (pop)

$ $ top=$ and input=$ → Accept ✓

LL(1) Conflicts — When a Grammar Is NOT LL(1)

A grammar is not LL(1) if its parsing table has a cell with more than one production. This is called a conflict.

Type 1 — FIRST/FIRST Conflict

Two productions for the same non-terminal start with the same terminal.

Example

S → a b | a c

Both productions start with a. When we see a, we cannot decide which to use.

Example

M[S][a] = { S→ab, S→ac } ← TWO entries — conflict!

Fix: Left-factor the grammar.

Example

S → a S'

S' → b | c

Now M[S'][b] = S'→b and M[S'][c] = S'→c — no conflict.

Type 2 — FIRST/FOLLOW Conflict

A non-terminal has both an ε-production and a production that starts with a terminal in FOLLOW.

Example

A → a | ε

If a ∈ FOLLOW(A), then when we see a, we cannot decide:

Use A → a (match the 'a')
Use A → ε (let 'a' be matched by whoever follows A)

Example

M[A][a] = { A→a, A→ε } ← conflict!

This usually means the grammar is inherently ambiguous for LL(1) parsing and needs to be redesigned.

Checking LL(1) Conditions

A grammar is LL(1) if and only if:

Example

For every non-terminal A with two productions A → α and A → β:

Condition 1: FIRST(α) ∩ FIRST(β) = ∅

(no terminal starts both productions)

Condition 2: At most one of α and β can derive ε.

Condition 3: If β ⟹* ε, then FIRST(α) ∩ FOLLOW(A) = ∅

(if β can vanish, α must not start with something in FOLLOW(A))

If all three conditions hold for every pair of productions, the grammar is LL(1).

Worked Example — Full LL(1) Parse

Let's work through a complete example from grammar to parse.

Grammar:

Example

S → ( S ) S | ε

This grammar generates all strings of balanced parentheses (including the empty string).

Step 1 — FIRST sets:

Example

FIRST(S) = FIRST( ( S ) S ) ∪ FIRST(ε)

= { ( } ∪ { ε }

= { (, ε }

Step 2 — FOLLOW sets:

Example

S is the start symbol → add $ to FOLLOW(S)

From S → ( S ) S:

First S inside: β = ) S

FIRST() S) = { ) } → add ) to FOLLOW(first S)

) is not ε-deriving, so stop here.

Second S inside: β = ε (it's at the end)

add FOLLOW(S) to FOLLOW(second S) → add { $, ) } to FOLLOW(S)

FOLLOW(S) = { $, ) }

Step 3 — Build parsing table:

Example

Production S → ( S ) S :

FIRST of RHS = { ( } → M[S][(] = S → ( S ) S

Production S → ε :

ε in FIRST → use FOLLOW(S) = { $, ) }

M[S][$] = S → ε

M[S][)] = S → ε

Parsing table:

Example

( ) $

────────────────────────────────────────

S S→(S)S S→ε S→ε

Step 4 — Parse "(())"

Example

Stack Input Action

─────────────────────────────────────────────

S $ ( ( ) ) $ M[S][(] = S→(S)S → expand

( S ) S $ ( ( ) ) $ match (

S ) S $ ( ) ) $ M[S][(] = S→(S)S → expand

( S ) S ) S $ ( ) ) $ match (

S ) S ) S $ ) ) $ M[S][)] = S→ε → expand to ε (pop)

) S ) S $ ) ) $ match )

S ) S $ ) $ M[S][)] = S→ε → expand to ε (pop)

) S $ ) $ match )

S $ $ M[S][$] = S→ε → expand to ε (pop)

$ $ Accept ✓

The parse correctly recognises "(())" as a valid balanced-parenthesis string.

Summary

Example

Step 1: Eliminate left recursion

Step 2: Left-factor common prefixes

Step 3: Compute FIRST sets

Step 4: Compute FOLLOW sets

Step 5: Build parsing table M[A][a]

Step 6: Check for conflicts (if conflict → grammar is not LL(1))

Step 7: Run the stack-based algorithm on the input