SLR(1) parsing in Compiler Design - Step-by-Step Execution

Concept Flow - SLR(1) parsing

Start with Grammar

↓

Construct LR(0) Items

↓

Build Canonical Collection of LR(0) Items

↓

Compute FOLLOW sets for Non-terminals

↓

Create SLR(1) Parsing Table

↓

Parse Input String

↓

Shift, Reduce, Accept or Error

↓

End Parsing

SLR(1) parsing starts from grammar, builds LR(0) items, computes FOLLOW sets, creates parsing table, then parses input by shift/reduce decisions.

Execution Sample

Compiler Design

Grammar:
S -> E
E -> E + T | T
T -> id

Input: id + id

This example shows parsing the input 'id + id' using SLR(1) parsing steps.

Analysis Table

Step	Stack	Input	Action	Reason
1	[0]	id + id$	Shift 5	State 0 with 'id' shifts to state 5
2	[0 5]	+ id$	Reduce T -> id	State 5 has item with dot at end, reduce by T->id
3	[0 3]	+ id$	Reduce E -> T	State 3 reduces by E->T
4	[0 2]	+ id$	Shift 6	State 2 with '+' shifts to state 6
5	[0 2 6]	id$	Shift 5	State 6 with 'id' shifts to 5
6	[0 2 6 5]	$	Reduce T -> id	State 5 reduces by T->id
7	[0 2 6 3]	$	Reduce E -> E + T	State 3 reduces by E->E+T
8	[0 2]	$	Accept	Input fully parsed and stack at accept state

💡 Parsing ends when input is accepted or error occurs; here input accepted at step 8.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
Stack	[0]	[0 5]	[0 3]	[0 2]	[0 2 6]	[0 2 6 5]	[0 2 6 3]	[0 2]	[0 2]
Input	id + id$	+ id$	+ id$	id$	id$	$	$	$	$
Action		Shift 5	Reduce T->id	Reduce E->T	Shift 6	Shift 5	Reduce T->id	Reduce E->E+T	Accept

Key Insights - 3 Insights

Why do we reduce by T -> id at step 2 instead of shifting?

At step 2, the parser is in a state where the dot is at the end of T -> id, meaning the input matches this production fully, so we reduce instead of shifting. See execution_table row 2.

How does FOLLOW set influence reduce actions in SLR(1)?

FOLLOW sets determine where reduce actions are allowed to avoid conflicts. Reductions happen only if the next input symbol is in the FOLLOW set of the production's left side. This is why at step 3 reduction is valid.

What causes the parser to accept the input at step 8?

The parser accepts when the stack and input indicate the start symbol is fully parsed and the input is consumed, as shown in execution_table row 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the next input symbol before action?

A "+"

B "id"

C "$"

D "E"

💡 Hint

Check the 'Input' column at step 4 in execution_table.

At which step does the parser perform the reduction by E -> E + T?

A Step 3

B Step 7

C Step 6

D Step 2

💡 Hint

Look for 'Reduce E -> E + T' in the 'Action' column of execution_table.

If the input was 'id + id + id$', at which step would the first reduction by T -> id occur?

A Step 5

B Step 8

C Step 2

D Step 10

💡 Hint

Refer to variable_tracker for when 'T -> id' reduction happens first.

Concept Snapshot

SLR(1) parsing:
- Build LR(0) items from grammar
- Compute FOLLOW sets for non-terminals
- Create parsing table using LR(0) states and FOLLOW
- Parse input by shift/reduce using table
- Reduce only if next input in FOLLOW of production
- Accept when start symbol parsed and input consumed

Full Transcript

SLR(1) parsing is a method to analyze input strings using a grammar. It starts by creating LR(0) items, which are grammar rules with a dot showing progress. Then it builds a collection of these items representing parser states. Next, it computes FOLLOW sets, which are sets of symbols that can appear after non-terminals. Using these, it creates a parsing table that tells the parser when to shift (read next input) or reduce (apply a grammar rule). The parser reads the input string step by step, updating a stack and deciding actions based on the table. When the input is fully parsed and the stack shows the start symbol, the parser accepts the input. This process helps compilers understand if code matches the grammar rules.

Practice

1. What does the 1 in SLR(1) parsing represent?

easy

A. One grammar rule applied

B. One step shift operation

C. One reduction per state

D. One symbol lookahead during parsing

Solution

1. Step 1: Understand the meaning of lookahead in parsing

   Lookahead means the parser looks at upcoming input symbols to decide the next action.

2. Step 2: Identify what the number 1 specifies in SLR(1)

   The number 1 indicates the parser looks ahead by exactly one symbol to make decisions.

3. Final Answer:

   One symbol lookahead during parsing -> Option D

4. Quick Check:

   SLR(1) means 1 symbol lookahead [OK]

Hint: Remember: number in SLR(n) = lookahead symbols [OK]

Common Mistakes:

• Confusing lookahead with number of grammar rules
• Thinking it means one shift or reduction only
• Assuming it refers to parser states

2. Which of the following is a correct component of the SLR(1) parsing table?

easy

A. ACTION and GOTO tables

B. PREDICT and FOLLOW tables

C. SHIFT and REDUCE stacks

D. FIRST and LAST tables

Solution

1. Step 1: Recall the structure of SLR(1) parsing tables

   SLR(1) parsing uses two main tables: ACTION for parser actions and GOTO for state transitions.

2. Step 2: Identify the correct table names

   Only ACTION and GOTO tables are part of the SLR(1) parsing table, others are unrelated or parts of grammar analysis.

3. Final Answer:

   ACTION and GOTO tables -> Option A

4. Quick Check:

   SLR(1) uses ACTION and GOTO tables [OK]

Hint: ACTION table decides moves; GOTO table changes states [OK]

Common Mistakes:

• Mixing parsing tables with grammar sets like FIRST or FOLLOW
• Confusing stacks with tables
• Assuming PREDICT table exists in SLR(1)

3. Given the grammar:

S -> CC
C -> cC | d

What is the correct ACTION for state 2 on input c in SLR(1) parsing?

medium

A. Reduce by C -> d

B. Shift to state 3

C. Accept input

D. Error

Solution

1. Step 1: Identify state 2's items and possible moves

   State 2 likely has an item expecting c to continue parsing C -> cC, so it should shift on c.

2. Step 2: Determine the action for input c

   Since c can start a new C, the parser shifts to state 3 to parse C -> cC.

3. Final Answer:

   Shift to state 3 -> Option B

4. Quick Check:

   Input 'c' leads to shift in state 2 [OK]

Hint: Shift on terminals that start productions [OK]

Common Mistakes:

• Choosing reduce too early without checking lookahead
• Confusing accept with shift
• Assuming error when shift is valid

4. In an SLR(1) parser, a conflict occurs when:
state 4 has both shift and reduce actions on the same input symbol. What is the likely cause?

medium

A. Grammar is not SLR(1) compatible

B. Parser table was built incorrectly

C. Lookahead symbol is missing

D. Input string is invalid

Solution

1. Step 1: Understand shift-reduce conflicts in SLR(1)

   Shift-reduce conflicts happen when the parser cannot decide whether to shift or reduce on the same input symbol.

2. Step 2: Identify the cause of such conflicts

   This usually means the grammar is not suitable for SLR(1) parsing, i.e., it is not SLR(1) compatible.

3. Final Answer:

   Grammar is not SLR(1) compatible -> Option A

4. Quick Check:

   Shift-reduce conflict = grammar not SLR(1) [OK]

Hint: Conflicts mean grammar is not SLR(1) compatible [OK]

Common Mistakes:

• Blaming parser table construction errors
• Thinking input string causes conflicts
• Assuming missing lookahead causes conflict

5. You have the grammar:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

Why might SLR(1) parsing fail for this grammar, and what is a common solution?

hard

A. Grammar is left-factored; remove left recursion

B. Grammar lacks terminals; add more tokens

C. Grammar is ambiguous; use LALR(1) or LR(1) parsing

D. Grammar is too simple; add more productions

Solution

1. Step 1: Recognize the grammar type

   This grammar is classic expression grammar with ambiguity due to operator precedence and associativity.

2. Step 2: Understand SLR(1) limitations

   SLR(1) parsing often fails on ambiguous grammars because it cannot resolve conflicts with only one symbol lookahead.

3. Step 3: Identify common solutions

   More powerful parsers like LALR(1) or LR(1) handle such grammars by using more precise lookahead and states.

4. Final Answer:

   Grammar is ambiguous; use LALR(1) or LR(1) parsing -> Option C

5. Quick Check:

   Ambiguous grammar needs stronger parser than SLR(1) [OK]

Hint: Ambiguous grammar needs LR(1) or LALR(1) [OK]

Common Mistakes:

• Thinking adding tokens fixes ambiguity
• Confusing left recursion removal with ambiguity
• Assuming grammar simplicity causes failure