CD Notes

LR Parsers: Canonical LR Parsing for Complex Language Syntax

Complete guide to LR(1) parsers: item sets, lookahead computation, DFA construction, parsing table generation, shift-reduce decisions, conflict resolution, and modern compiler toolchain applications.

Introduction

An LR(1) parser (Left-to-right, Rightmost derivation, 1 lookahead) is a powerful bottom-up parser that can handle a large class of context-free grammars. It's the most general shift-reduce parser with single lookahead.

Why LR(1)?

1. Canonical	Complete lookahead information
2. Powerful	Accepts all unambiguous LR grammars
3. Practical	Efficient table-driven implementation
4. Industry standard	YACC/Bison use LALR variant

LR(1) Items

An LR(1) item extends LR(0) with lookahead:

Example

[A → α • β, a] Where: - A → α • β is the core (position in production) - a is the lookahead terminal (what can follow this item) Interpretation: - Parser has seen α - Expects to see β next - When complete, lookahead a triggers reduction

LR(1) State Construction

CLOSURE for LR(1) Items

closure({[A	α • Bβ, a]}) =
All items [A	α • Bβ, b] where:
- [A	α • Bβ, a] is in set, OR
- For [A	α • Bβ, b] in set:
- For each production B	γ:
Add [B	• γ, c] where c ∈ FIRST(βa)

GOTO for LR(1) Items

Example

goto(I, X) = closure({[A → αX • β, a] | [A → α • Xβ, a] ∈ I})

Example: LR(1) Item Set Construction

Augmented Grammar

S' → E

E → E + T | T

T → T * F | F

F → ( E ) | id

Initial Item Set I₀:

[S' → • E, $]

[E → • E + T, {$, +, )}]

[E → • T, {$, +, )}]

[T → • T * F, {$, +, ), *}]

[T → • F, {$, +, ), *}]

[F → • ( E ), {$, +, ), *}]

[F → • id, {$, +, ), *}]

Lookahead computation

[S' → • E, $]: E followed by $

[E → • E + T, x]: First, see E; if E → E + T, then +

...

LR(1) Parsing Table Construction

Algorithm

- If [A	α • aβ, b] in state and goto(state, a) = s:
- If [A	α •, a] in state (reduce item):
ACTION[state, a] = reduce (A	α)
- If [S'	S •, $] in state:

Example Parsing Table (Simplified)

st	id	+	*	(	$
0	s3			s4
1		s5			acc
2		r2	s6		r2

Parsing Algorithm

Example

def parse(tokens): stack = [0] # State stack value_stack = [] # Attribute/value stack token_index = 0 while True: state = stack[-1] token = tokens[token_index] if token_index < len(tokens) else EOF action = ACTION[state, token.type] if action.type == "shift": stack.append(token.type) value_stack.append(token.value) stack.append(action.next_state) token_index += 1 elif action.type == "reduce": production = action.production # A → X₁...Xₖ rhs_count = len(production.rhs) # Pop 2*rhs_count entries (states and values) for _ in range(2 * rhs_count): stack.pop() # Compute semantic action (attributes) reduced_value = semantic_action(production, value_stack[-rhs_count:]) value_stack = value_stack[:-rhs_count] value_stack.append(reduced_value) # Determine next state state = stack[-1] non_terminal = production.lhs next_state = GOTO[state, non_terminal] stack.append(non_terminal) stack.append(next_state) elif action.type == "accept": return value_stack[-1] elif action.type == "error": raise SyntaxError(f"State {state}, token {token}")

Conflict Detection and Resolution

Shift-Reduce Conflicts

Problem in state

[A → α •, a] (reduce)

[B → β • aγ, b] (shift)

Both valid on lookahead a

Resolution

- Shift: [B → β • aγ, b] takes precedence

- Reduce: [A → α •, a] takes precedence

- Operator precedence: Use grammar declarations

Reduce-Reduce Conflicts

Problem in state

[A → α •, a] (reduce by A → α)

[B → β •, a] (reduce by B → β)

Cannot decide which production

Resolution

- Grammar likely ambiguous (MUST FIX)

- Use precedence rules (rarely acceptable)

- Use semantic predicates

Advantages of Canonical LR(1)

Strengths ✓

1. Most powerful	Accepts all unambiguous LR-grammars
2. Accurate lookahead	Item-specific, not global
3. Fewer conflicts	More grammars parse without conflicts
4. Precise	Detects parsing ambiguities
5. Complete	Full item sets capture all distinctions

Limitations ✗

1. Table size	Larger than SLR or LALR
2. Computation	More complex state generation
3. States	More states than SLR (sometimes 10x)
4. Memory	Can be prohibitive for very large grammars
5. Generation time	Slower compiler-compiler execution

LR(1) vs SLR vs LALR

Comparison

Aspect │ SLR │ LALR │ LR(1)

──────────────────┼─────────┼─────────┼─────────

Grammar class │ Smaller │ Medium │ Largest

States │ Fewest │ Medium │ Most

Table size │ Smaller │ Medium │ Largest

Lookahead │ Global │ Merged │ Per-item

Conflicts │ More │ Few │ Fewest

Practical use │ Rare │ Common │ Rare

Tools │ None │ Yacc │ Few

Real applications

- Most languages: LALR (good balance)

- Simple languages: SLR

- Complex languages or research: LR(1)

Quick Revision Notes

LR(1) item: [A → α • β, a] with lookahead a
CLOSURE: Add items for non-terminals after •, with lookahead FIRST(βa)
GOTO: Move • over symbol X, take closure
Canonical LR(1): Full item set construction with all lookaheads
Parsing table: ACTION (shift/reduce/accept) + GOTO (next state)
Shift-reduce conflict: Resolvable with precedence
Reduce-reduce conflict: Unresolvable (indicates ambiguity)

Interview Q&A

Q1: What does the lookahead symbol in an LR(1) item represent?

A: The lookahead indicates which tokens can appear when this item is complete (ready to reduce). It's the FIRST token of what comes after this production in derivations. This prevents reducing in situations where the production should continue.

Q2: Why is LR(1) more powerful than SLR?

A: SLR uses global FOLLOW sets for all occurrences of a non-terminal. LR(1) computes item-specific lookahead. This lets LR(1) distinguish cases where SLR cannot, reducing conflicts and accepting more grammars.

Q3: How does the lookahead propagation work in canonical LR(1)?

A: When adding [B → • γ, a] to closure of [A → α • Bβ, b], the lookahead a comes from FIRST(βb)—what can start the material after B in context of [A → α • Bβ, b].

Q4: Can LR(1) handle ambiguous grammars?

A: No, ambiguity creates conflicts in the parsing table. LR(1) detects ambiguity but cannot resolve it. You must disambiguate the grammar or add conflict resolution directives (precedence rules).

Q5: Why are LR(1) parsing tables so large?

A: Each state has item-specific lookahead, creating more distinct item sets than SLR. For large grammars, tables can have thousands of states, each with entries for all terminals/non-terminals.

Q6: What's the relationship between LR(1) and LALR?

A: LALR merges LR(1) states with identical cores (ignoring lookahead), then unions their lookaheads. This reduces states while keeping most conflict-resolution power. LALR is "LR(1) compressed" for practical use.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for LR Parsers: Canonical LR Parsing for Complex Language Syntax.

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, parser, lr parsers: canonical lr parsing for complex language syntax

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

PreviousLL(1) Parser: Single Lookahead Predictive Parsing from First Principles NextParse Trees in Compiler Design

CD Notes

LR Parsers: Canonical LR Parsing for Complex Language Syntax

Complete guide to LR(1) parsers: item sets, lookahead computation, DFA construction, parsing table generation, shift-reduce decisions, conflict resolution, and modern compiler toolchain applications.

Introduction

Why LR(1)?

1. Canonical	Complete lookahead information
2. Powerful	Accepts all unambiguous LR grammars
3. Practical	Efficient table-driven implementation
4. Industry standard	YACC/Bison use LALR variant

LR(1) Items

An LR(1) item extends LR(0) with lookahead:

Example

LR(1) State Construction

CLOSURE for LR(1) Items

closure({[A	α • Bβ, a]}) =
All items [A	α • Bβ, b] where:
- [A	α • Bβ, a] is in set, OR
- For [A	α • Bβ, b] in set:
- For each production B	γ:
Add [B	• γ, c] where c ∈ FIRST(βa)

GOTO for LR(1) Items

Example

goto(I, X) = closure({[A → αX • β, a] | [A → α • Xβ, a] ∈ I})

Example: LR(1) Item Set Construction

Augmented Grammar

S' → E

E → E + T | T

T → T * F | F

F → ( E ) | id

Initial Item Set I₀:

[S' → • E, $]

[E → • E + T, {$, +, )}]

[E → • T, {$, +, )}]

[T → • T * F, {$, +, ), *}]

[T → • F, {$, +, ), *}]

[F → • ( E ), {$, +, ), *}]

[F → • id, {$, +, ), *}]

Lookahead computation

[S' → • E, $]: E followed by $

[E → • E + T, x]: First, see E; if E → E + T, then +

...

LR(1) Parsing Table Construction

Algorithm

- If [A	α • aβ, b] in state and goto(state, a) = s:
- If [A	α •, a] in state (reduce item):
ACTION[state, a] = reduce (A	α)
- If [S'	S •, $] in state:

Example Parsing Table (Simplified)

st	id	+	*	(	$
0	s3			s4
1		s5			acc
2		r2	s6		r2

Parsing Algorithm

Example

Conflict Detection and Resolution

Shift-Reduce Conflicts

Problem in state

[A → α •, a] (reduce)

[B → β • aγ, b] (shift)

Both valid on lookahead a

Resolution

- Shift: [B → β • aγ, b] takes precedence

- Reduce: [A → α •, a] takes precedence

- Operator precedence: Use grammar declarations

Reduce-Reduce Conflicts

Problem in state

[A → α •, a] (reduce by A → α)

[B → β •, a] (reduce by B → β)

Cannot decide which production

Resolution

- Grammar likely ambiguous (MUST FIX)

- Use precedence rules (rarely acceptable)

- Use semantic predicates

Advantages of Canonical LR(1)

Strengths ✓

1. Most powerful	Accepts all unambiguous LR-grammars
2. Accurate lookahead	Item-specific, not global
3. Fewer conflicts	More grammars parse without conflicts
4. Precise	Detects parsing ambiguities
5. Complete	Full item sets capture all distinctions

Limitations ✗

1. Table size	Larger than SLR or LALR
2. Computation	More complex state generation
3. States	More states than SLR (sometimes 10x)
4. Memory	Can be prohibitive for very large grammars
5. Generation time	Slower compiler-compiler execution

LR(1) vs SLR vs LALR

Comparison

Aspect │ SLR │ LALR │ LR(1)

──────────────────┼─────────┼─────────┼─────────

Grammar class │ Smaller │ Medium │ Largest

States │ Fewest │ Medium │ Most

Table size │ Smaller │ Medium │ Largest

Lookahead │ Global │ Merged │ Per-item

Conflicts │ More │ Few │ Fewest

Practical use │ Rare │ Common │ Rare

Tools │ None │ Yacc │ Few

Real applications

- Most languages: LALR (good balance)

- Simple languages: SLR

- Complex languages or research: LR(1)

Quick Revision Notes

LR(1) item: [A → α • β, a] with lookahead a
CLOSURE: Add items for non-terminals after •, with lookahead FIRST(βa)
GOTO: Move • over symbol X, take closure
Canonical LR(1): Full item set construction with all lookaheads
Parsing table: ACTION (shift/reduce/accept) + GOTO (next state)
Shift-reduce conflict: Resolvable with precedence
Reduce-reduce conflict: Unresolvable (indicates ambiguity)

Interview Q&A

Q1: What does the lookahead symbol in an LR(1) item represent?

Q2: Why is LR(1) more powerful than SLR?

Q3: How does the lookahead propagation work in canonical LR(1)?

A: When adding [B → • γ, a] to closure of [A → α • Bβ, b], the lookahead a comes from FIRST(βb)—what can start the material after B in context of [A → α • Bβ, b].

Q4: Can LR(1) handle ambiguous grammars?

A: No, ambiguity creates conflicts in the parsing table. LR(1) detects ambiguity but cannot resolve it. You must disambiguate the grammar or add conflict resolution directives (precedence rules).

Q5: Why are LR(1) parsing tables so large?

A: Each state has item-specific lookahead, creating more distinct item sets than SLR. For large grammars, tables can have thousands of states, each with entries for all terminals/non-terminals.

Q6: What's the relationship between LR(1) and LALR?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for LR Parsers: Canonical LR Parsing for Complex Language Syntax.

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, parser, lr parsers: canonical lr parsing for complex language syntax

Continue learning this concept

PreviousLL(1) Parser: Single Lookahead Predictive Parsing from First Principles NextParse Trees in Compiler Design