CD Notes

SLR Parser: Simple LR Parsing with Efficient Automata

Deep dive into SLR (Simple LR) parsing: construction of DFA states, parsing tables, shift-reduce actions, reduction rules, conflict resolution, and practical compiler implementation with real-world examples.

Introduction to SLR Parsing

SLR (Simple LR) parsing is a bottom-up parsing technique that uses deterministic finite automata (DFA) to track parser states and lookahead information. It's the simplest form of LR parsing, making it practical for many programming languages while maintaining computational efficiency.

What Makes SLR "Simple"?

Simpler lookahead: Uses FOLLOW sets instead of item-specific lookahead
Fewer states: Smaller DFA compared to canonical LR(1)
Smaller tables: More manageable parsing tables
Faster generation: Quicker compiler-compiler execution
Practical: Sufficient for most programming language syntax

LR(0) Items and Item Sets

An LR(0) item is a production with a dot (•) marking how much of the production we've seen:

Production: E	T + E
[E	• T + E] (start)
[E	T • + E] (after seeing T)
[E	T + • E] (after seeing T +)
[E	T + E •] (complete - reduce)

Core Item Sets Construction

Algorithm: CLOSURE(I)

for each [A	α • Bβ] in closure(I)
for each production B	γ
add [B	• γ] to closure(I)

Algorithm: GOTO(I, X)

Example

goto(I, X): J = ∅ for each [A → α • Xβ] in I add [A → αX • β] to J return closure(J)

Example: Expression Grammar Item Sets

Grammar

E → E + T | T

T → T * F | F

F → ( E ) | id

Item Set 0 (initial)

[E' → • E] (augmented start)

[E → • E + T]

[E → • T]

[T → • T * F]

[T → • F]

[F → • ( E )]

[F → • id]

Item Set 1 = goto(I0, E):

[E' → E •] (accept)

[E → E • + T]

Item Set 2 = goto(I0, id):

[F → id •] (reduce)

Item Set 4 = goto(I0, T):

[E → T •] (reduce)

[T → T • * F]

DFA Construction for SLR Parsing

Complete DFA Generation Algorithm

Example

C = {closure({[S' → • S]})} // Initial state repeat for each item set I in C for each symbol X (terminal/non-terminal) J = goto(I, X) if J not empty and J not in C add J to C until no new sets added

Example: Simple Expression Grammar DFA

/	\
/	\

SLR Parsing Table Construction

The SLR parsing table has two parts:

ACTION[state, terminal]: shift to state S, reduce by production r, accept
GOTO[state, non-terminal]: shift to state S after reduction

Table Construction Algorithm

if [A	α • aβ] in I and goto(I, a) = J:
if [A	α •] (complete) and A ≠ S':
ACTION[state(I), a] = reduce (A	α)
if [S'	S •]:

Example SLR Parsing Table

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

SLR Parsing Algorithm

Stack-Based Parsing

Example

Stack = [0] // Start with initial state Input = tokens + $ Lookahead = nextToken() while true: state = top of stack if ACTION[state, Lookahead] = shift j: push Lookahead onto stack push j onto stack Lookahead = nextToken() else if ACTION[state, Lookahead] = reduce A → X₁X₂...Xₖ: pop 2k items from stack state = top of stack push A onto stack push GOTO[state, A] onto stack else if ACTION[state, Lookahead] = accept: return ACCEPT else: return ERROR (syntax error)

Parsing Example: 2 + 3 * 4

0 2 2 + 3 * 4 $ reduce F	id (pop 1)
0 5 5 + 3 * 4 $ reduce T	F (pop 1)
0 4 4 + 3 * 4 $ reduce E	T (pop 1)
0 1 6 + 2 2 * 4 $ reduce F	id
0 1 6 + 5 5 * 4 $ reduce T	F
0 1 6 + 9 8 * 2 2 4 $ reduce F	id
0 1 6 + 9 8 11 11 $ (end) reduce T	T*F
0 1 1 $ reduce E	E+T (pop 3)

Conflict Resolution in SLR

Shift-Reduce Conflicts

Problem: [A	α • aβ] and [B → γ •] both in same state
S	L = R
S	R
L	* R \| id
R	L
[S	L • = R] (shift on =)
[R	L •] (reduce on any token)

Reduce-Reduce Conflicts

Problem: [A	α •] and [B → β •] both in same state
Expr	Term
Expr	Term List
List	ε

Resolution Strategies

Example

1. Use operator precedence (for shift-reduce) - Shift for higher precedence - Reduce for lower precedence 2. Use associativity (for shift-reduce) - Left associative: reduce - Right associative: shift 3. Grammar transformation (preferred) - Restructure to eliminate conflicts

Why SLR is "Simple"

SLR vs Canonical LR(1)

Aspect	SLR(1)	Canonical LR(1)
Lookahead info	FOLLOW sets	Item-specific
Item set creation	Core only	Full lookahead
Number of states	Smaller	Larger
Table size	Smaller	Larger
Conflicts	More common	Fewer
Grammar coverage	Smaller	Larger
Implementation	Simpler	Complex

When SLR Conflicts Occur

SLR conflicts happen when:

Grammar has ambiguity that FOLLOW can't distinguish
Insufficient lookahead - need more than FOLLOW info
Same non-terminal productions with overlapping terminals

Practical Implementation

SLR Parser Generator Pseudocode

Example

def build_slr_parser(grammar): # 1. Compute augmented grammar augmented_grammar = augment(grammar) # 2. Build item sets item_sets = build_item_sets(augmented_grammar) # 3. Compute FIRST and FOLLOW first_sets = compute_first(augmented_grammar) follow_sets = compute_follow(augmented_grammar) # 4. Build parsing tables action_table = {} goto_table = {} for state, items in enumerate(item_sets): for item in items: if item.is_shift_item(): # ACTION[state, symbol] = shift next_state pass elif item.is_reduce_item(): # ACTION[state, follow_symbol] = reduce for symbol in follow_sets[item.lhs]: action_table[(state, symbol)] = ("reduce", item) elif item.is_accept_item(): # ACTION[state, $] = accept action_table[(state, "$")] = ("accept", None) return action_table, goto_table

Advantages and Limitations

Advantages ✓

Simple and efficient state construction
Smaller tables than canonical LR(1)
Practical for most programming languages
Good balance of power and simplicity
Fast parser generation

Limitations ✗

More conflicts than LR(1) or LALR
Smaller class of grammars than LR(1)
May require grammar transformation
FOLLOW-based lookahead sometimes insufficient

Quick Revision Notes

LR(0) item: Production with dot marking parse position
Item set: Closure of items reachable from initial item
goto(I, X): Moves dot over symbol X; includes closure
SLR reduction: Uses FOLLOW(A) for all occurrences of A
Parsing table: ACTION (shift/reduce/accept) and GOTO (state transitions)
Shift-reduce conflict: Both actions possible for same lookahead
Reduce-reduce conflict: Multiple reduce options (grammar usually ambiguous)

Interview Q&A

Q1: What is the key advantage of SLR over LL(1) parsing?

A: SLR is bottom-up and can handle left recursion directly without grammar transformation. LL(1) requires eliminating left recursion first. SLR also accepts a larger class of grammars, making it more flexible for real programming languages.

Q2: Why does SLR use FOLLOW sets for reducing instead of item-specific lookahead?

A: Using FOLLOW sets simplifies the construction and reduces the number of states. While this causes more conflicts in some cases, it's still practical for most languages and significantly faster to generate than canonical LR(1) which computes item-specific lookahead.

Q3: How do shift-reduce conflicts differ from reduce-reduce conflicts?

A: Shift-reduce conflicts are often resolvable using precedence/associativity rules, and may represent valid language constructs (like the dangling-else problem). Reduce-reduce conflicts almost always indicate ambiguous grammar and cannot be resolved without grammar restructuring.

Q4: Can all context-free grammars be parsed by SLR?

A: No. SLR can parse a subset of LR-grammars. Some grammars generate shift-reduce or reduce-reduce conflicts in SLR parsing tables but are conflict-free in LALR or canonical LR(1). The grammar must be specifically SLR-compatible.

Q5: What happens when you encounter a shift-reduce conflict in SLR table generation?

A: The conflict indicates ambiguity in the grammar. Solutions include: 1) Use operator precedence/associativity declarations, 2) Transform the grammar to eliminate ambiguity, 3) Switch to LALR or canonical LR(1) parsing, or 4) Accept the conflict if it represents desired behavior (rare).

Q6: Why is SLR called "Simple" LR rather than just another LR variant?

A: SLR is called "Simple" because it uses simpler lookahead computation (FOLLOW sets derived once globally) rather than computing lookahead information for each specific item occurrence. This makes the algorithm simpler, tables smaller, and generation faster than canonical LR(1).

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for SLR Parser: Simple LR Parsing with Efficient Automata.

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

PreviousShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax Analysis NextTop-Down Parsing Techniques in Compiler Design

CD Notes

SLR Parser: Simple LR Parsing with Efficient Automata

Introduction to SLR Parsing

What Makes SLR "Simple"?

Simpler lookahead: Uses FOLLOW sets instead of item-specific lookahead
Fewer states: Smaller DFA compared to canonical LR(1)
Smaller tables: More manageable parsing tables
Faster generation: Quicker compiler-compiler execution
Practical: Sufficient for most programming language syntax

LR(0) Items and Item Sets

An LR(0) item is a production with a dot (•) marking how much of the production we've seen:

Production: E	T + E
[E	• T + E] (start)
[E	T • + E] (after seeing T)
[E	T + • E] (after seeing T +)
[E	T + E •] (complete - reduce)

Core Item Sets Construction

Algorithm: CLOSURE(I)

for each [A	α • Bβ] in closure(I)
for each production B	γ
add [B	• γ] to closure(I)

Algorithm: GOTO(I, X)

Example

goto(I, X): J = ∅ for each [A → α • Xβ] in I add [A → αX • β] to J return closure(J)

Example: Expression Grammar Item Sets

Grammar

E → E + T | T

T → T * F | F

F → ( E ) | id

Item Set 0 (initial)

[E' → • E] (augmented start)

[E → • E + T]

[E → • T]

[T → • T * F]

[T → • F]

[F → • ( E )]

[F → • id]

Item Set 1 = goto(I0, E):

[E' → E •] (accept)

[E → E • + T]

Item Set 2 = goto(I0, id):

[F → id •] (reduce)

Item Set 4 = goto(I0, T):

[E → T •] (reduce)

[T → T • * F]

DFA Construction for SLR Parsing

Complete DFA Generation Algorithm

Example

Example: Simple Expression Grammar DFA

/	\
/	\

SLR Parsing Table Construction

The SLR parsing table has two parts:

ACTION[state, terminal]: shift to state S, reduce by production r, accept
GOTO[state, non-terminal]: shift to state S after reduction

Table Construction Algorithm

if [A	α • aβ] in I and goto(I, a) = J:
if [A	α •] (complete) and A ≠ S':
ACTION[state(I), a] = reduce (A	α)
if [S'	S •]:

Example SLR Parsing Table

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

SLR Parsing Algorithm

Stack-Based Parsing

Example

Parsing Example: 2 + 3 * 4

0 2 2 + 3 * 4 $ reduce F	id (pop 1)
0 5 5 + 3 * 4 $ reduce T	F (pop 1)
0 4 4 + 3 * 4 $ reduce E	T (pop 1)
0 1 6 + 2 2 * 4 $ reduce F	id
0 1 6 + 5 5 * 4 $ reduce T	F
0 1 6 + 9 8 * 2 2 4 $ reduce F	id
0 1 6 + 9 8 11 11 $ (end) reduce T	T*F
0 1 1 $ reduce E	E+T (pop 3)

Conflict Resolution in SLR

Shift-Reduce Conflicts

Problem: [A	α • aβ] and [B → γ •] both in same state
S	L = R
S	R
L	* R \| id
R	L
[S	L • = R] (shift on =)
[R	L •] (reduce on any token)

Reduce-Reduce Conflicts

Problem: [A	α •] and [B → β •] both in same state
Expr	Term
Expr	Term List
List	ε

Resolution Strategies

Example

Why SLR is "Simple"

SLR vs Canonical LR(1)

Aspect	SLR(1)	Canonical LR(1)
Lookahead info	FOLLOW sets	Item-specific
Item set creation	Core only	Full lookahead
Number of states	Smaller	Larger
Table size	Smaller	Larger
Conflicts	More common	Fewer
Grammar coverage	Smaller	Larger
Implementation	Simpler	Complex

When SLR Conflicts Occur

SLR conflicts happen when:

Grammar has ambiguity that FOLLOW can't distinguish
Insufficient lookahead - need more than FOLLOW info
Same non-terminal productions with overlapping terminals

Practical Implementation

SLR Parser Generator Pseudocode

Example

Advantages and Limitations

Advantages ✓

Simple and efficient state construction
Smaller tables than canonical LR(1)
Practical for most programming languages
Good balance of power and simplicity
Fast parser generation

Limitations ✗

More conflicts than LR(1) or LALR
Smaller class of grammars than LR(1)
May require grammar transformation
FOLLOW-based lookahead sometimes insufficient

Quick Revision Notes

LR(0) item: Production with dot marking parse position
Item set: Closure of items reachable from initial item
goto(I, X): Moves dot over symbol X; includes closure
SLR reduction: Uses FOLLOW(A) for all occurrences of A
Parsing table: ACTION (shift/reduce/accept) and GOTO (state transitions)
Shift-reduce conflict: Both actions possible for same lookahead
Reduce-reduce conflict: Multiple reduce options (grammar usually ambiguous)

Interview Q&A

Q1: What is the key advantage of SLR over LL(1) parsing?

Q2: Why does SLR use FOLLOW sets for reducing instead of item-specific lookahead?

Q3: How do shift-reduce conflicts differ from reduce-reduce conflicts?

Q4: Can all context-free grammars be parsed by SLR?

Q5: What happens when you encounter a shift-reduce conflict in SLR table generation?

Q6: Why is SLR called "Simple" LR rather than just another LR variant?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for SLR Parser: Simple LR Parsing with Efficient Automata.

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

Continue learning this concept

PreviousShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax Analysis NextTop-Down Parsing Techniques in Compiler Design

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3

State	id	+	*	(	)	$	E	T	F
0	s2			s3			1	4	5
1		s6				acc
2		r5	r5		r5	r5
3	s2			s3			7	4	5
4		r2	s8		r2	r2
5		r4	r4		r4	r4
6	s2			s3				9	5
7		s6			s10
8	s2			s3					11
9		s6				r1
10		r6	r6		r6	r6
11		r3	r3		r3	r3