2.3.3 LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a string

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

For S → A B C, A → a | ε, B → b | ε, C → c, what is FOLLOW(A)? from Lesson 2.3.2
Left factor S → a b | a c. from Lesson 2.2
Under longest match, how is <= tokenized, and what does a * state in a transition diagram mean? from Lesson 1.2.2

1 · The Story

📖

The chart on the wall

Kabir pins a chart on the wall. One row per category, one column per possible next word (plus a column for $). In each cell he writes the rule to use. He fills it from the starter and follower lists: rule “A → α” goes in the columns of α’s starters; if α can be empty, also in the columns of A’s followers.

Chetan now never guesses. He keeps a to-do pile of things still to find, starting with $ at the bottom and the start category on top. If the top is a word, it must equal the next word: cross both off. If the top is a category, look up the chart under the next word, take the category off the pile, and put that rule’s parts on the pile, first part on top.

If a cell ever holds two rules, the chart cannot decide with one word, and this rulebook cannot be used this way.

2 · Predict First

🤔

In the chart for E → T E′, E′ → + T E′ | ε, …, which cells hold E′ → ε? Write your guess down. The answer is in the vault.

3 · Core Concept

Building the LL(1) parsing table

For each production A → α:

for each terminal a in FIRST(α), put A → α in M[A, a];
if ε ∈ FIRST(α), put A → α in M[A, b] for each b in FOLLOW(A) (including $).

Empty cells are errors. “LL(1)” means: scan input Left to right, produce a Leftmost derivation, using 1 token of lookahead.

The LL(1) test

A grammar is LL(1) if and only if no cell gets two productions. Equivalently, for every pair of alternatives A → α | β:

FIRST(α) ∩ FIRST(β) = ∅;
at most one of α, β can derive ε;
if β ⇒* ε, then FIRST(α) ∩ FOLLOW(A) = ∅.

Consequences: a left-recursive grammar, an ambiguous grammar, or a grammar needing left factoring is never LL(1).

The table-driven parser

Stack initially: $ S (S on top). Input: w $. Repeat with X = top of stack, a = current token:

X = a = $: accept.
X is a terminal: if X = a, pop and advance (match); otherwise error.
X is a nonterminal: if M[X, a] = X → Y₁ … Yₖ, pop X and push Yₖ … Y₁ (Y₁ on top), output the production; if M[X, a] is empty, error.

The outputs, in order, form the leftmost derivation. Error recovery (brief): panic mode skips input tokens until one in a synchronizing set, usually FOLLOW of the nonterminal on top, appears.

Story → compiler term

In the story	In the compiler
the chart on the wall	LL(1) parsing table M[A, a]
rule in the columns of its starters	A → α in M[A, a] for a ∈ FIRST(α)
empty rules under the followers	A → ε in M[A, b] for b ∈ FOLLOW(A)
the to-do pile	the parser stack ($ S)
crossing off a word	match
two rules in one cell	LL(1) conflict: the grammar is not LL(1)

4 · Visual

Column 1	`+`	`*`	`(`	`)`	`id`	`$`
`E`			E → T E'		E → T E'
`E'`	E' → + T E'			E' → ε		E' → ε
`T`			T → F T'		T → F T'
`T'`	T' → ε	T' → * F T'		T' → ε		T' → ε
`F`			F → ( E )		F → id

LL(1) table for the transformed expression grammar: 13 filled cells, no conflicts.

Stack	Input	Action
`$ E`	`id + id * id $`	output E → T E'
`$ E' T`	`id + id * id $`	output T → F T'
`$ E' T' F`	`id + id * id $`	output F → id
`$ E' T' id`	`id + id * id $`	match id
`$ E' T'`	`+ id * id $`	output T' → ε
`$ E'`	`+ id * id $`	output E' → + T E'
`$ E' T +`	`+ id * id $`	match +
`$ E' T`	`id * id $`	output T → F T'
`$ E' T' F`	`id * id $`	output F → id
`$ E' T' id`	`id * id $`	match id
`$ E' T'`	`* id $`	output T' → * F T'
`$ E' T' F *`	`* id $`	match *
`$ E' T' F`	`id $`	output F → id
`$ E' T' id`	`id $`	match id
`$ E' T'`	`$`	output T' → ε
`$ E'`	`$`	output E' → ε
`$`	`$`	accept

5 · Worked Examples

Example 1 Easy

Build the LL(1) table for S → A A, A → a A | b and parse a b b.

Solution

Column 1	`a`	`b`	`$`
`S`	S → A A	S → A A
`A`	A → a A	A → b

Stack	Input	Action
`$ S`	`a b b $`	output S → A A
`$ A A`	`a b b $`	output A → a A
`$ A A a`	`a b b $`	match a
`$ A A`	`b b $`	output A → b
`$ A b`	`b b $`	match b
`$ A`	`b $`	output A → b
`$ b`	`b $`	match b
`$`	`$`	accept

FIRST(aA) = {a}, FIRST(b) = {b}: no clash, so the grammar is LL(1). Chetan never consults a cell with two rules.

Example 2 Medium

Parse id + id * id with the table above. How many rows does the trace have, and what is the output?

Solution

The trace above has 17 rows, the last one being accept. The productions output, in order, are exactly the leftmost derivation of id + id * id in the transformed grammar.

Example 3 GATE

Which are LL(1)? G1: S → A a A b | B b B a, A → ε, B → ε. G2: S → i E t S S′ | a, S′ → e S | ε, E → b. G3: S → a B | a C, B → b, C → c.

Solution

G1 is LL(1): FIRST(AaAb) = {a}, FIRST(BbBa) = {b}, disjoint; A and B have only ε, placed under FOLLOW = {a, b}.

G2 is not: S′ → e S and S′ → ε both land in M[S′, e], because e ∈ FIRST(eS) and e ∈ FOLLOW(S′). This is the dangling else; parsers resolve it by choosing S′ → e S.

G3 is not: both alternatives start with a (it needs left factoring).

Column 1	`i`	`a`	`e`	`b`	`$`
`S`	S → i E t S S'	S → a
`S'`			S' → ε S' → e S		S' → ε
`E`				E → b

6 · Shortcuts

⚡

Fast LL(1) test: for each nonterminal, (1) FIRST sets of its alternatives disjoint; (2) if an alternative is nullable, FOLLOW(A) disjoint from the FIRST of every other alternative. Valid when: deciding LL(1) without drawing the whole table.

⚡

Instant “no”: left recursion, ambiguity, or two alternatives with the same first symbol. Valid when: MCQs and MSQs that list candidate grammars.

7 · GATE Traps

⚠️

An ε-production goes under FOLLOW(A), not under ε (there is no ε column).
$ is a column; ε-productions of nonterminals that can end the input appear there.
The stack gets the right side pushed in reverse so that its first symbol is on top.
Every LL(1) grammar is unambiguous, but an unambiguous grammar need not be LL(1).
A conflict-free table is the definition of LL(1); a single double entry means not LL(1).

8 · Memory Hook

🧠

LL(1) = Left-to-right, Leftmost, 1 look. Fill by FIRST; ε fills by FOLLOW; one cell, one rule.

9 · Connect the Dots

Top-down parsing is now complete. Chapter 2.4 turns the method around: instead of guessing from the start symbol down, the parser reads tokens onto a stack and builds the tree from the leaves up, which copes with left recursion and with many more grammars.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markTable

In the LL(1) table of E → T E′, E′ → + T E′ | ε, T → F T′, T′ → * F T′ | ε, F → ( E ) | id, the entry M[T′, +] is:

(A) T′ → * F T′
(B) T′ → ε
(C) error (empty)
(D) E′ → + T E′

Q2NAT2 marksTable

How many non-empty cells does the LL(1) table of S → X Y z, X → x X | ε, Y → y Y | ε have?

Numerical answer: ________

Q3MSQ2 marksLL(1) test

Which grammars are LL(1)?

(A) S → A c | B d, A → a | ε, B → b | ε
(B) S → A | B, A → a | ε, B → b | ε
(C) S → a S b S | b S a S | ε
(D) S → a A B | b A, A → c A | ε, B → d | ε

Q4NAT1 markTrace

Parsing a b b with the LL(1) parser for S → A A, A → a A | b: how many rows does the stack trace have, including the final accept?

Numerical answer: ________

Q5MCQ1 markFacts

Which grammar can be LL(1)?

(A) a left-recursive grammar
(B) an ambiguous grammar
(C) a grammar whose alternatives start with different terminals and has no ε-productions
(D) a grammar with two alternatives starting with the same terminal

11 · Rule Card

M[A, a] ∋ A → α for a ∈ FIRST(α); if ε ∈ FIRST(α), for every b ∈ FOLLOW(A) (incl. $).
LL(1) ⇔ no cell has two productions.
Never LL(1): left-recursive, ambiguous, not left-factored.
Parser: stack $ S; terminal on top → match; nonterminal → replace by right side reversed; $ $ → accept.
Outputs form the leftmost derivation; empty cell = error (panic mode: skip to FOLLOW).

12 · Concept Ledger

LL(1)LL(1) parsing table M[A, a]LL(1) conflicttable-driven predictive parserparser stacksynchronizing set (panic mode)

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up

{ b, c }.
S → a S′, S′ → b | c.
As one token relop LE; * means retract one character before returning.

Predict First

The cells under FOLLOW(E′) = { ), $ }: M[E′, )] and M[E′, $]. ε-rules go under the followers, because when E′ produces nothing, the next token must be something that comes after E′.