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.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for LL(1) Parser: Single Lookahead Predictive Parsing from First Principles.

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, ll1, 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 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 AnalysisPredictive Parsers: Lookahead-Guided Top-Down ParsingComprehensive guide to predictive parsing techniques using lookahead tokens, FIRST and FOLLOW sets, parsing tables, and practical implementations with detailed examples and parse tree diagrams.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.

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?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for LL(1) Parser: Single Lookahead Predictive Parsing from First Principles.

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, ll1, parser

Continue learning this concept

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