CD Notes

Predictive Parsers: Lookahead-Guided Top-Down Parsing

Comprehensive guide to predictive parsing techniques using lookahead tokens, FIRST and FOLLOW sets, parsing tables, and practical implementations with detailed examples and parse tree diagrams.

What is Predictive Parsing?

Predictive parsing is a top-down parsing technique that uses a single lookahead token to determine which production rule to apply without backtracking. Also known as LL(1) parsing (Left-to-right scan, Leftmost derivation, 1 lookahead token), it's fundamental to modern compiler construction.

Key Characteristics

Single lookahead token guides parsing decisions
No backtracking required
Deterministic parsing - each state + lookahead = unique action
Efficient execution - O(n) parsing time
Natural fit for recursive descent implementation

FIRST Sets: Computing Possible Starting Symbols

The FIRST set of a string contains all terminals that can appear as the first symbol in any derivation from that string.

FIRST Set Algorithm

1. If A	ε, add ε to FIRST(A)
2. If A	aα, add a to FIRST(A)
3. If A	Bα:

Example: Computing FIRST Sets

E	TE'
E'	+TE' \| ε
T	FT'
T'	*FT' \| ε
F	(E) \| id

ASCII Diagram: FIRST Set Derivation Tree

Example

E / \ T E' / \ \ F T' + ← First symbol is 'T' or '+' or 'id' / \ id (E) FIRST(E) = {id, (}

FOLLOW Sets: Computing Possible Following Symbols

The FOLLOW set of a non-terminal A contains all terminals that can appear immediately after A in some sentential form derivable from the start symbol.

FOLLOW Set Algorithm

Initialization

- Add $ to FOLLOW(Start symbol)

Iteration (repeat until no changes)

- For each production A → α Bβ:

- Add FIRST(β) - {ε} to FOLLOW(B)

- If ε ∈ FIRST(β):

- Add FOLLOW(A) to FOLLOW(B)

Example: Computing FOLLOW Sets

E	TE'
E'	+TE' \| ε
T	FT'
T'	*FT' \| ε
F	(E) \| id

LL(1) Grammar Conditions

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

No Left Recursion: No production leads to A → A α (direct or indirect)
No Common Prefixes: For each non-terminal, no two alternatives share a common FIRST symbol
FIRST-FOLLOW Disjointness: For alternatives A → α | β, FIRST(α) ∩ FIRST(β) = ∅

Test for LL(1)

For each non-terminal A with productions A	α₁ \| α₂ \| ... \| αₙ:
Condition 1	FIRST(αᵢ) ∩ FIRST(αⱼ) = ∅ for i ≠ j
Condition 2	If ε ∈ FIRST(αᵢ), then:
A	aA \| a
A	aB \| bC

Parsing Table Construction

The predictive parsing table M[A, a] specifies which production to use when:

Current non-terminal to expand: A
Lookahead token: a

Parsing Table Algorithm

For each production A	α:
M[A, a] = A	α
M[A, b] = A	α
M[A, $] = A	α

Example: Expression Grammar Parsing Table

	(	id	+	*	$
E	E→TE'	E→TE'
E'			E'→+TE'		E'→ε
T	T→FT'	T→FT'
T'			T'→ε	T'→*FT'	T'→ε
F	F→(E)	F→id

Predictive Parsing Algorithm

The predictive parser maintains:

Stack: stores symbols to be processed (starts with $ and start symbol)
Input: source code tokens + $
Lookahead: current input token

Algorithm

ERROR	expected X, found Lookahead
if M[X, Lookahead] = X	Y₁Y₂...Yₖ:
ERROR	no production for M[X, Lookahead]

Parse Example: id + id * id

Step 1	Stack=[E,$], Input=id+id*id$, Lookahead=id
M[E,id] = E	TE'
Step 2	Stack=[TE',$], Input=id+id*id$, Lookahead=id
M[T,id] = T	FT'
Step 3	Stack=[FT'E',$], Input=id+id*id$, Lookahead=id
M[F,id] = F	id
Step 4	Match id with Lookahead=id
Step 5	Stack=[T'E',$], Input=+id*id$, Lookahead=+
M[T',+] = T'	ε
Step 6	Stack=[E',$], Input=+id*id$, Lookahead=+
M[E',+] = E'	+TE'

Parse Tree Visualization

Example

E / \ T E' / \ \ F T' +TE' | | / \ id ε T E' / \ \ F T' ε | | id ε Derived: id + id * id

Error Recovery Strategies

Panic Mode Recovery

Example

On error: 1. Skip tokens until synchronized token found 2. Synchronized tokens: {;, }, FOLLOW(current)) 3. Resume parsing from known state

Error Production

Grammar augmented with error productions

S → error recovery_expr

Example

statement → assignment

| error NEWLINE

Recursive Descent Implementation

Example

class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def current_token(self): if self.pos < len(self.tokens): return self.tokens[self.pos] return Token(EOF, "$") def advance(self): self.pos += 1 def expect(self, token_type): if self.current_token().type == token_type: self.advance() else: raise SyntaxError(f"Expected {token_type}") def parse_expr(self): self.parse_term() while self.current_token().type == PLUS: self.advance() self.parse_term() def parse_term(self): self.parse_factor() while self.current_token().type == STAR: self.advance() self.parse_factor() def parse_factor(self): if self.current_token().type == ID: self.advance() elif self.current_token().type == LPAREN: self.expect(LPAREN) self.parse_expr() self.expect(RPAREN) else: raise SyntaxError("Expected factor")

Advantages and Limitations

Advantages ✓

Fast: Linear time O(n) parsing
Simple: Easy to implement and understand
Intuitive: Natural correspondence with grammar
Error handling: Good locality for error recovery
Integration: Straightforward attribute computation

Limitations ✗

Grammar restrictions: Requires LL(1) grammar (no left recursion)
Limited lookahead: Single token insufficient for some languages
Grammar transformation: Left recursion elimination required
Conflicts: Cannot handle ambiguous grammars

Comparison with Other Parsing Techniques

Aspect	LL(1)	LR(1)	LALR
Direction	Left-to-right	Left-to-right	Left-to-right
Derivation	Leftmost	Rightmost	Rightmost
Lookahead	1	1	1
Grammar class	Smaller	Larger	Intermediate
Table size	Smaller	Larger	Medium
Implementation	Recursive descent	Table-driven	Table-driven
Error handling	Good	Moderate	Moderate

Quick Revision Notes

FIRST(α) = terminals that can start α; if α ⇒* ε, include ε
FOLLOW(A) = terminals that can follow A in sentential forms
LL(1) condition: No ambiguity in FIRST/FOLLOW computation
Parsing table M[A,a] = production to use when seeing A with lookahead a
Stack-based algorithm: Push symbols right-to-left, match terminals, expand non-terminals
Left recursion elimination: A → Aα | β → A → βA'α where A' → αA' | ε
Common prefix removal: A → αβ | αγ → A → αA' where A' → β | γ

Interview Q&A

Q1: What is the key difference between FIRST and FOLLOW sets?

A: FIRST(X) contains terminals that can start derivations from X (looks forward), while FOLLOW(A) contains terminals that can immediately follow A in sentential forms (looks at what comes after). FIRST is about the beginning of strings, FOLLOW is about what comes next.

Q2: Why must we eliminate left recursion before predictive parsing?

A: Left recursion causes infinite recursion in predictive parsers because when expanding A, we again encounter A, leading to stack overflow. We convert A → Aα | β into A → βA' and A' → αA' | ε, which right-associates the recursion, allowing proper termination.

Q3: Can LL(1) parse all context-free languages?

A: No. LL(1) can only parse LL(1) grammars, which are a subset of context-free languages. Languages requiring more than one lookahead or right recursion may not have LL(1) grammars. However, many can be transformed into LL(1) form.

Q4: What happens if two alternatives for a non-terminal have overlapping FIRST sets?

A: The parser cannot uniquely decide which production to use, causing a parsing conflict. The grammar is not LL(1). Solutions include: grammar restructuring, factoring out common prefixes, or using a more powerful parsing technique like LALR.

Q5: How do you handle epsilon productions in FIRST/FOLLOW computation?

A: For FIRST: include ε if the production derives it. For FOLLOW: if A → αBβ and ε ∈ FIRST(β), add FOLLOW(A) to FOLLOW(B). This ensures we capture tokens that can follow B when β is empty.

Q6: What is the relationship between recursive descent and predictive parsing?

A: Recursive descent is a procedural implementation of predictive parsing. Each non-terminal becomes a procedure that uses lookahead and FIRST/FOLLOW information to decide which production rule to apply. The call stack implicitly handles the parsing stack.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Predictive Parsers: Lookahead-Guided Top-Down Parsing.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, analysis, predictive, parser

Continue learning this concept

Syntax AnalysisCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationComprehensive exploration of CLR parser construction: complete item sets, lookahead propagation algorithms, full DFA generation, parsing tables, comparison with SLR/LALR, practical compiler implementation.Syntax AnalysisLALR Parser: Practical LR(1) With State Merging for EfficiencyMaster LALR parsing: state merging techniques, lookahead merge rules, DFA construction, parsing table generation, conflict detection, comparison with SLR/CLR, industry standard compiler implementation.Syntax AnalysisLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesMaster LL(1) parsing: grammar conversion to LL(1) form, FIRST/FOLLOW computation, parsing table construction, parse decisions, error recovery, practical recursive descent implementation with examples.Syntax AnalysisLR Parsers: Canonical LR Parsing for Complex Language SyntaxComplete guide to LR(1) parsers: item sets, lookahead computation, DFA construction, parsing table generation, shift-reduce decisions, conflict resolution, and modern compiler toolchain applications.Syntax AnalysisRecursive Descent Parsers: Procedural Approach to Top-Down ParsingMaster recursive descent parsing: grammar transformation, procedure generation, backtracking mechanisms, error recovery, implementation patterns, and practical compiler design with ASCII automata diagrams.Syntax AnalysisShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax AnalysisDeep exploration of shift-reduce parsing: stack operations, reduction strategies, action tables, conflict types and resolution, relationship to LR parsing, practical implementations with complete examples.

PreviousParse Trees in Compiler Design NextRecursive Descent Parsers: Procedural Approach to Top-Down Parsing

CD Notes

Predictive Parsers: Lookahead-Guided Top-Down Parsing

Comprehensive guide to predictive parsing techniques using lookahead tokens, FIRST and FOLLOW sets, parsing tables, and practical implementations with detailed examples and parse tree diagrams.

What is Predictive Parsing?

Key Characteristics

Single lookahead token guides parsing decisions
No backtracking required
Deterministic parsing - each state + lookahead = unique action
Efficient execution - O(n) parsing time
Natural fit for recursive descent implementation

FIRST Sets: Computing Possible Starting Symbols

The FIRST set of a string contains all terminals that can appear as the first symbol in any derivation from that string.

FIRST Set Algorithm

1. If A	ε, add ε to FIRST(A)
2. If A	aα, add a to FIRST(A)
3. If A	Bα:

Example: Computing FIRST Sets

E	TE'
E'	+TE' \| ε
T	FT'
T'	*FT' \| ε
F	(E) \| id

ASCII Diagram: FIRST Set Derivation Tree

Example

E / \ T E' / \ \ F T' + ← First symbol is 'T' or '+' or 'id' / \ id (E) FIRST(E) = {id, (}

FOLLOW Sets: Computing Possible Following Symbols

The FOLLOW set of a non-terminal A contains all terminals that can appear immediately after A in some sentential form derivable from the start symbol.

FOLLOW Set Algorithm

Initialization

- Add $ to FOLLOW(Start symbol)

Iteration (repeat until no changes)

- For each production A → α Bβ:

- Add FIRST(β) - {ε} to FOLLOW(B)

- If ε ∈ FIRST(β):

- Add FOLLOW(A) to FOLLOW(B)

Example: Computing FOLLOW Sets

E	TE'
E'	+TE' \| ε
T	FT'
T'	*FT' \| ε
F	(E) \| id

LL(1) Grammar Conditions

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

No Left Recursion: No production leads to A → A α (direct or indirect)
No Common Prefixes: For each non-terminal, no two alternatives share a common FIRST symbol
FIRST-FOLLOW Disjointness: For alternatives A → α | β, FIRST(α) ∩ FIRST(β) = ∅

Test for LL(1)

For each non-terminal A with productions A	α₁ \| α₂ \| ... \| αₙ:
Condition 1	FIRST(αᵢ) ∩ FIRST(αⱼ) = ∅ for i ≠ j
Condition 2	If ε ∈ FIRST(αᵢ), then:
A	aA \| a
A	aB \| bC

Parsing Table Construction

The predictive parsing table M[A, a] specifies which production to use when:

Current non-terminal to expand: A
Lookahead token: a

Parsing Table Algorithm

For each production A	α:
M[A, a] = A	α
M[A, b] = A	α
M[A, $] = A	α

Example: Expression Grammar Parsing Table

	(	id	+	*	$
E	E→TE'	E→TE'
E'			E'→+TE'		E'→ε
T	T→FT'	T→FT'
T'			T'→ε	T'→*FT'	T'→ε
F	F→(E)	F→id

Predictive Parsing Algorithm

The predictive parser maintains:

Stack: stores symbols to be processed (starts with $ and start symbol)
Input: source code tokens + $
Lookahead: current input token

Algorithm

ERROR	expected X, found Lookahead
if M[X, Lookahead] = X	Y₁Y₂...Yₖ:
ERROR	no production for M[X, Lookahead]

Parse Example: id + id * id

Step 1	Stack=[E,$], Input=id+id*id$, Lookahead=id
M[E,id] = E	TE'
Step 2	Stack=[TE',$], Input=id+id*id$, Lookahead=id
M[T,id] = T	FT'
Step 3	Stack=[FT'E',$], Input=id+id*id$, Lookahead=id
M[F,id] = F	id
Step 4	Match id with Lookahead=id
Step 5	Stack=[T'E',$], Input=+id*id$, Lookahead=+
M[T',+] = T'	ε
Step 6	Stack=[E',$], Input=+id*id$, Lookahead=+
M[E',+] = E'	+TE'

Parse Tree Visualization

Example

E / \ T E' / \ \ F T' +TE' | | / \ id ε T E' / \ \ F T' ε | | id ε Derived: id + id * id

Error Recovery Strategies

Panic Mode Recovery

Example

On error: 1. Skip tokens until synchronized token found 2. Synchronized tokens: {;, }, FOLLOW(current)) 3. Resume parsing from known state

Error Production

Grammar augmented with error productions

S → error recovery_expr

Example

statement → assignment

| error NEWLINE

Recursive Descent Implementation

Example

Advantages and Limitations

Advantages ✓

Fast: Linear time O(n) parsing
Simple: Easy to implement and understand
Intuitive: Natural correspondence with grammar
Error handling: Good locality for error recovery
Integration: Straightforward attribute computation

Limitations ✗

Grammar restrictions: Requires LL(1) grammar (no left recursion)
Limited lookahead: Single token insufficient for some languages
Grammar transformation: Left recursion elimination required
Conflicts: Cannot handle ambiguous grammars

Comparison with Other Parsing Techniques

Aspect	LL(1)	LR(1)	LALR
Direction	Left-to-right	Left-to-right	Left-to-right
Derivation	Leftmost	Rightmost	Rightmost
Lookahead	1	1	1
Grammar class	Smaller	Larger	Intermediate
Table size	Smaller	Larger	Medium
Implementation	Recursive descent	Table-driven	Table-driven
Error handling	Good	Moderate	Moderate

Quick Revision Notes

FIRST(α) = terminals that can start α; if α ⇒* ε, include ε
FOLLOW(A) = terminals that can follow A in sentential forms
LL(1) condition: No ambiguity in FIRST/FOLLOW computation
Parsing table M[A,a] = production to use when seeing A with lookahead a
Stack-based algorithm: Push symbols right-to-left, match terminals, expand non-terminals
Left recursion elimination: A → Aα | β → A → βA'α where A' → αA' | ε
Common prefix removal: A → αβ | αγ → A → αA' where A' → β | γ

Interview Q&A

Q1: What is the key difference between FIRST and FOLLOW sets?

Q2: Why must we eliminate left recursion before predictive parsing?

Q3: Can LL(1) parse all context-free languages?

Q4: What happens if two alternatives for a non-terminal have overlapping FIRST sets?

Q5: How do you handle epsilon productions in FIRST/FOLLOW computation?

A: For FIRST: include ε if the production derives it. For FOLLOW: if A → αBβ and ε ∈ FIRST(β), add FOLLOW(A) to FOLLOW(B). This ensures we capture tokens that can follow B when β is empty.

Q6: What is the relationship between recursive descent and predictive parsing?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Predictive Parsers: Lookahead-Guided Top-Down Parsing.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, analysis, predictive, parser

Continue learning this concept

PreviousParse Trees in Compiler Design NextRecursive Descent Parsers: Procedural Approach to Top-Down Parsing