📘 SLR(1) Parsers: Automaton and Parsing Table

(Exam-ready, simple explanation with steps, diagrams, and examples)

---

🧠 1. What is SLR(1) Parser?

✅ Definition

An SLR(1) (Simple LR) parser is a bottom-up parser that uses:

• LR(0) automaton
• FOLLOW sets (1-symbol lookahead indirectly)
• ACTION + GOTO parsing table

👉 Full form:

Simple LR (1 lookahead via FOLLOW sets)

---

⭐ Key Idea

SLR(1) = LR(0) automaton + FOLLOW sets to resolve reduce decisions.

---

📊 2. Why SLR(1) is Needed?

LR(0) has problems: ❌ Too many shift-reduce conflicts ❌ No lookahead information

👉 SLR fixes this using: ✔ FOLLOW sets ✔ Better reduce decisions

---

🧠 3. SLR(1) Parser Components

1. LR(0) Automaton
2. FOLLOW sets
3. Parsing Table (ACTION + GOTO)
4. Stack + Input buffer

---

🔧 4. Construction Steps of SLR(1) Parser

---

🔹 STEP 1: Augment Grammar

Add new start symbol:

S' → S

---

🔹 STEP 2: Build LR(0) Items

Create items using:

• Closure
• GOTO

👉 This forms LR(0) automaton

---

🔹 STEP 3: Compute FOLLOW Sets

Used for reduce decisions

---

🔹 STEP 4: Construct Parsing Table

Fill ACTION and GOTO tables

---

📌 5. Grammar Example

S → CC
C → cC | d

---

🔹 Step 1: Augmented Grammar

S' → S
S → CC
C → cC | d

---

🔹 Step 2: FOLLOW Sets

FOLLOW(S) = { $ }
FOLLOW(C) = { c, d, $ }

---

🧠 6. SLR(1) Parsing Table Rules

---

🔹 1. SHIFT

If:

A → α • a β

Then:

ACTION[i, a] = SHIFT j

---

🔹 2. REDUCE (Important SLR rule)

If:

A → α •

Then:

ACTION[i, a] = REDUCE A → α
for all a ∈ FOLLOW(A)

👉 This is the main difference from LR(0)

---

🔹 3. ACCEPT

If:

S' → S •

Then:

ACTION[i, $] = ACCEPT

---

🔹 4. GOTO

If:

GOTO(I, A) = j

Then:

GOTO[i, A] = j

---

🌳 7. LR(0) Automaton (Used in SLR)

States are built using:

• Items
• Closure
• GOTO

👉 Example transitions:

I0 --c--> I1
I0 --d--> I2
I0 --C--> I3

---

📊 8. SLR(1) Parsing Table (Example Format)

State	c	d	$	S	C
0	S1	S2		3	4
1	S1	S2			5
2	R C→d	R C→d	R C→d
3			ACC

Legend:

• S = Shift
• R = Reduce
• ACC = Accept

---

🔄 9. How SLR(1) Parsing Works

---

Steps:

1. Push state 0 on stack

2. Read input

3. Use ACTION table:

   • SHIFT → push state
   • REDUCE → pop symbols, push LHS
   • ACCEPT → stop

4. Use GOTO for transitions

---

⚠️ 10. Advantages of SLR(1)

✔ Simple to construct ✔ Uses LR(0) automaton ✔ More powerful than LR(0) ✔ Reduces many conflicts

---

❌ 11. Limitations

❌ Still has conflicts in complex grammars ❌ Not as powerful as CLR(1) ❌ Uses FOLLOW sets → sometimes too broad

---

⚖️ 12. LR(0) vs SLR(1)

Feature	LR(0)	SLR(1)
Lookahead	None	FOLLOW set
Conflicts	Many	Reduced
Power	Weak	Medium
Table	Simple	Better
Use	Theory	Basic parsing

---

🎯 13. Important Exam Questions

👉 Very frequently asked:

• Define SLR(1) parser
• Construct SLR parsing table
• Difference between LR(0) and SLR(1)
• Why SLR is better than LR(0)
• Role of FOLLOW in SLR
• Build LR(0) automaton for SLR

---

📝 14. Short Notes (Quick Revision)

🔵 SLR(1)

• Simple LR parser
• Uses FOLLOW sets
• Uses LR(0) automaton

---

🔵 Key Idea

• Reduce only when next input ∈ FOLLOW(A)

---

🔵 Components

• LR(0) automaton
• ACTION table
• GOTO table

---

📊 15. Final Summary Table

Aspect	SLR(1) Parser
Full form	Simple LR (1)
Type	Bottom-up
Basis	LR(0) + FOLLOW
Lookahead	1 (indirect)
Strength	Medium
Tables	ACTION + GOTO
Conflicts	Reduced vs LR(0)
Use	Syntax analysis

---

✅ Final Conclusion

• SLR(1) parser improves LR(0) using FOLLOW sets
• It reduces shift-reduce conflicts
• It is simple but not the most powerful LR method
• Forms the foundation for understanding CLR and LALR parsing

---