CD Notes

LL(1) Parser: Single Lookahead Predictive Parsing from First Principles

Master 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.

Fundamentals

An LL(1) parser (Left-to-right scan, Leftmost derivation, 1 lookahead) is a top-down predictive parser that uses a single token lookahead to deterministically choose parsing rules without backtracking.

Why LL(1)?

1. Efficient	Linear O(n) parsing time
2. Simple	Easy to understand and implement
3. Direct	Grammar ↔ Code correspondence
4. Deterministic	No backtracking needed
5. Debuggable	Clear error locations

Prerequisites: FIRST and FOLLOW Sets

Computing FIRST(α)

For a string α:

FIRST(α) contains terminals that can start α
If α ⇒* ε, include ε

1. If α = ε	FIRST(ε) = {ε}
2. If α = a (terminal)	FIRST(a) = {a}
- If ε ∈ FIRST(X)	add FIRST(β) to FIRST(α)
- If ε ∈ FIRST(β)	add ε to FIRST(α)

Computing FOLLOW(A)

For a non-terminal A:

FOLLOW(A) contains terminals that can follow A

Example

Algorithm: 1. Add $ to FOLLOW(start_symbol) 2. Iterate until fixed point: - For each production A → ... Bβ: - Add FIRST(β) - {ε} to FOLLOW(B) - If ε ∈ FIRST(β): - Add FOLLOW(A) to FOLLOW(B)

LL(1) Condition

A grammar is LL(1) if:

For each non-terminal A with productions A → α | β:

1. FIRST(α) ∩ FIRST(β) = ∅

(Different productions start with different tokens)

2. If ε ∈ FIRST(α):

FIRST(α) ∩ FOLLOW(A) = ∅

(ε and non-ε alternatives distinguishable by lookahead)

Parsing Table Construction

LL(1) Parsing Table Algorithm

- Current non-terminal	A
- Lookahead token	a
For each production A	α:
M[A, a] = A	α
M[A, b] = A	α
M[A, $] = A	α

Example: Expression Grammar LL(1) Table

Grammar (LL(1) form)

E → TE'

E' → +TE' | ε

T → FT'

T' → *FT' | ε

F → (E) | id

Parsing Table

┌──────┬────┬────┬────┬────┬────┐

│NT,LA│ 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) │ │ │

└──────┴────┴────┴────┴────┴────┴───┘

Parsing Algorithm

Stack-Based LL(1) Parser

ERROR	expected X, got Lookahead
A	α = M[X, Lookahead]
ERROR	no production for M[X, Lookahead]

Grammar Transformations

Eliminate Left Recursion

Original

A → Aα | β

Transformed

A → βA'

A' → αA' | ε

Result: Right-recursive (LL(1)-compatible)

Factor Common Prefixes

Original

A → αβ | αγ

Transformed

A → αA'

A' → β | γ

Result: LL(1) condition satisfied

Example Parse: id + id

[E, $] id M[E,id]=E	TE'
[TE', $] id M[T,id]=T	FT'
[FT'E', $] id M[F,id]=F	id
[T'E', $] + M[T',+]=T'	ε
[E', $] + M[E',+]=E'	+TE'
[TE', $] id M[T,id]=T	FT'
[FT'E', $] id M[F,id]=F	id
[T'E', $] $ M[T',$]=T'	ε
[E', $] $ M[E',$]=E'	ε

Error Recovery

Panic Mode Recovery

Example

def ll1_parse_with_recovery(tokens): stack = [START, EOF] errors = [] i = 0 while stack: top = stack.pop() token = tokens[i] if i < len(tokens) else EOF if top == token: i += 1 elif top.is_terminal: errors.append(f"Expected {top}, got {token}") # Skip token i += 1 elif table[top, token] exists: production = table[top, token] # Process production else: errors.append(f"No rule for {top}, {token}") # Skip token i += 1 return (success, errors)

Recursive Descent Implementation

python example

def parse_E():
    parse_T()
    parse_E_prime()

def parse_E_prime():
    if lookahead == '+':
        consume('+')
        parse_T()
        parse_E_prime()
    # else: ε

def parse_T():
    parse_F()
    parse_T_prime()

def parse_T_prime():
    if lookahead == '*':
        consume('*')
        parse_F()
        parse_T_prime()
    # else: ε

def parse_F():
    if lookahead == 'id':
        consume('id')
    elif lookahead == '(':
        consume('(')
        parse_E()
        consume(')')
    else:
        error()

Practical Considerations

When LL(1) Suffices

Example

- Most expression grammars - Simple imperative languages - Configuration files - Data interchange formats (JSON-like)

When You Need More Power

Example

- Ambiguous constructs (dangling-else) - Complex operator precedence - Context-dependent syntax - Then: Use LR (LALR, YACC, Bison)

Quick Revision Notes

LL(1): Top-down, single lookahead, no backtracking
FIRST: Terminals that can start derivations
FOLLOW: Terminals that can follow non-terminal
Parsing table: M[NT, terminal] = production to apply
Left recursion: Must eliminate before LL(1)
Common prefixes: Must factor out before LL(1)
Deterministic: Lookahead uniquely determines choice

Interview Q&A

Q1: When would you choose LL(1) over LR parsing?

A: LL(1) for simple languages (configuration files, simple expressions) where grammar is naturally LL(1)-friendly. Use LR for general-purpose languages where you need more power or grammars have ambiguity/precedence requirements.

Q2: What makes a grammar unsuitable for LL(1)?

A: Left recursion, common prefixes, or ambiguous constructs. These can sometimes be fixed via grammar transformation (eliminate recursion, factor prefixes), but not always. If untransformable, use LR.

Q3: How does FOLLOW set help with epsilon productions?

A: If a production can derive epsilon, you need to know what tokens can follow the non-terminal to decide whether to apply that epsilon production or another. FOLLOW provides exactly this information.

Q4: Can you have an LL(1) parser for a grammar with dangling-else?

A: No, without disambiguation. Dangling-else is inherently ambiguous. You need either: grammar restructuring (rare), or use LR parsing with conflict resolution directives (common).

Q5: What's the maximum grammar size practical for LL(1)?

A: No hard limit, but LL(1) becomes tedious for large complex grammars. Most practical compilers use LR (typically LALR via YACC/Bison) for languages of any reasonable complexity.

Q6: How do you debug an LL(1) parsing failure?

A: Check: 1) No left recursion, 2) FIRST sets disjoint, 3) FIRST/FOLLOW disjoint when epsilon possible, 4) Parsing table has all entries filled (no conflicts). Tools like 'lli' or grammar checkers help identify issues.

Continue the lesson path

Study next in this module

4 connected lessons

01Syntax 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.02Syntax 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.03Syntax AnalysisIntroduction to Parsing in Compiler DesignComprehensive introduction to syntax analysis covering the role of parsers, parsing techniques classification, grammar representation, and the relationship between parsers and lexers.04Syntax AnalysisParse Trees in Compiler DesignGuide to parse trees covering construction, relationship to derivations, concrete vs abstract syntax trees, annotated parse trees, and their role in syntax-directed translation.

PreviousLALR Parser: Practical LR(1) With State Merging for Efficiency NextLR Parsers: Canonical LR Parsing for Complex Language Syntax

CD Notes

LL(1) Parser: Single Lookahead Predictive Parsing from First Principles

Fundamentals

Why LL(1)?

1. Efficient	Linear O(n) parsing time
2. Simple	Easy to understand and implement
3. Direct	Grammar ↔ Code correspondence
4. Deterministic	No backtracking needed
5. Debuggable	Clear error locations

Prerequisites: FIRST and FOLLOW Sets

Computing FIRST(α)

For a string α:

FIRST(α) contains terminals that can start α
If α ⇒* ε, include ε

1. If α = ε	FIRST(ε) = {ε}
2. If α = a (terminal)	FIRST(a) = {a}
- If ε ∈ FIRST(X)	add FIRST(β) to FIRST(α)
- If ε ∈ FIRST(β)	add ε to FIRST(α)

Computing FOLLOW(A)

For a non-terminal A:

FOLLOW(A) contains terminals that can follow A

Example

Algorithm: 1. Add $ to FOLLOW(start_symbol) 2. Iterate until fixed point: - For each production A → ... Bβ: - Add FIRST(β) - {ε} to FOLLOW(B) - If ε ∈ FIRST(β): - Add FOLLOW(A) to FOLLOW(B)

LL(1) Condition

A grammar is LL(1) if:

For each non-terminal A with productions A → α | β:

1. FIRST(α) ∩ FIRST(β) = ∅

(Different productions start with different tokens)

2. If ε ∈ FIRST(α):

FIRST(α) ∩ FOLLOW(A) = ∅

(ε and non-ε alternatives distinguishable by lookahead)

Parsing Table Construction

LL(1) Parsing Table Algorithm

- Current non-terminal	A
- Lookahead token	a
For each production A	α:
M[A, a] = A	α
M[A, b] = A	α
M[A, $] = A	α

Example: Expression Grammar LL(1) Table

Grammar (LL(1) form)

E → TE'

E' → +TE' | ε

T → FT'

T' → *FT' | ε

F → (E) | id

Parsing Table

┌──────┬────┬────┬────┬────┬────┐

│NT,LA│ 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) │ │ │

└──────┴────┴────┴────┴────┴────┴───┘

Parsing Algorithm

Stack-Based LL(1) Parser

ERROR	expected X, got Lookahead
A	α = M[X, Lookahead]
ERROR	no production for M[X, Lookahead]

Grammar Transformations

Eliminate Left Recursion

Original

A → Aα | β

Transformed

A → βA'

A' → αA' | ε

Result: Right-recursive (LL(1)-compatible)

Factor Common Prefixes

Original

A → αβ | αγ

Transformed

A → αA'

A' → β | γ

Result: LL(1) condition satisfied

Example Parse: id + id

[E, $] id M[E,id]=E	TE'
[TE', $] id M[T,id]=T	FT'
[FT'E', $] id M[F,id]=F	id
[T'E', $] + M[T',+]=T'	ε
[E', $] + M[E',+]=E'	+TE'
[TE', $] id M[T,id]=T	FT'
[FT'E', $] id M[F,id]=F	id
[T'E', $] $ M[T',$]=T'	ε
[E', $] $ M[E',$]=E'	ε

Error Recovery

Panic Mode Recovery

Example

Recursive Descent Implementation

python example

def parse_E():
    parse_T()
    parse_E_prime()

def parse_E_prime():
    if lookahead == '+':
        consume('+')
        parse_T()
        parse_E_prime()
    # else: ε

def parse_T():
    parse_F()
    parse_T_prime()

def parse_T_prime():
    if lookahead == '*':
        consume('*')
        parse_F()
        parse_T_prime()
    # else: ε

def parse_F():
    if lookahead == 'id':
        consume('id')
    elif lookahead == '(':
        consume('(')
        parse_E()
        consume(')')
    else:
        error()

Practical Considerations

When LL(1) Suffices

Example

- Most expression grammars - Simple imperative languages - Configuration files - Data interchange formats (JSON-like)

When You Need More Power

Example

- Ambiguous constructs (dangling-else) - Complex operator precedence - Context-dependent syntax - Then: Use LR (LALR, YACC, Bison)

Quick Revision Notes

LL(1): Top-down, single lookahead, no backtracking
FIRST: Terminals that can start derivations
FOLLOW: Terminals that can follow non-terminal
Parsing table: M[NT, terminal] = production to apply
Left recursion: Must eliminate before LL(1)
Common prefixes: Must factor out before LL(1)
Deterministic: Lookahead uniquely determines choice

Interview Q&A

Q1: When would you choose LL(1) over LR parsing?

Q2: What makes a grammar unsuitable for LL(1)?

Q3: How does FOLLOW set help with epsilon productions?

Q4: Can you have an LL(1) parser for a grammar with dangling-else?

A: No, without disambiguation. Dangling-else is inherently ambiguous. You need either: grammar restructuring (rare), or use LR parsing with conflict resolution directives (common).

Q5: What's the maximum grammar size practical for LL(1)?

A: No hard limit, but LL(1) becomes tedious for large complex grammars. Most practical compilers use LR (typically LALR via YACC/Bison) for languages of any reasonable complexity.

Q6: How do you debug an LL(1) parsing failure?

Continue the lesson path

Study next in this module

4 connected lessons

PreviousLALR Parser: Practical LR(1) With State Merging for Efficiency NextLR Parsers: Canonical LR Parsing for Complex Language Syntax