📘 Shift-Reduce Conflicts (Compiler Construction)

In bottom-up parsing (especially LR parsing), a shift-reduce conflict is one of the most important problems asked in exams.

---

🧠 1. Definition

✅ Shift-Reduce Conflict

A shift-reduce conflict occurs in parsing when the parser is unable to decide whether to:

• 🔹 Shift (move the next input symbol to the stack) OR
• 🔹 Reduce (replace symbols on stack using a grammar rule)

👉 This happens for the same state and input symbol in the parsing table.

---

📌 2. Simple Meaning

👉 The parser is confused:

“Should I read more input (shift) or reduce what I already have?”

---

🔧 3. Where it Occurs?

• LR(0) parsing
• SLR(1) parsing
• Bottom-up (shift-reduce) parsing
• Especially in ambiguous grammars

---

📊 4. Example Grammar

E → E + E
E → E * E
E → id

---

Input:

id + id * id

---

⚠️ 5. Conflict Situation

At a certain parser state:

Stack contains:

E + E

Next input symbol:

Now parser faces:

❓ Choices:

• Shift * (to handle multiplication first)
• Reduce E + E → E

👉 ❌ Conflict arises

---

🌳 6. Why Shift-Reduce Conflict Happens

Main Reasons:

🔹 1. Ambiguous Grammar

Example:

E → E + E | E * E | id

👉 No clear precedence or associativity

---

🔹 2. Missing Operator Precedence

Parser doesn’t know:

• * has higher priority than +

---

🔹 3. Incomplete LR(0) Information

LR(0) has no lookahead, so it cannot decide correctly.

---

🧠 7. Intuition

👉 Shift-reduce conflict means:

“Should I complete a rule now OR wait for more input?”

---

📊 8. Example Table Situation

State	Input	Action
i	+	Shift / Reduce ❌

👉 Both actions are possible → conflict

---

🔄 9. Types of Shift-Reduce Conflict

🔹 1. Genuine Conflict

• Grammar is truly ambiguous
• Cannot be fixed without changing grammar

---

🔹 2. Artificial Conflict

• Caused by poor grammar design

• Can be fixed using:

  • Precedence rules
  • Left factoring
  • Removing ambiguity

---

🛠️ 10. How to Resolve Shift-Reduce Conflict

---

✅ 1. Remove Ambiguity

Rewrite grammar:

❌ Ambiguous:

E → E + E | E * E | id

✅ Fixed:

E → E + T | T
T → T * F | F
F → id

---

✅ 2. Use Operator Precedence

• * has higher priority than +

---

✅ 3. Use Associativity Rules

• Left associativity:

a - b - c → (a - b) - c

---

✅ 4. Use SLR / CLR Parsing

• LR(1) uses lookahead → fewer conflicts
• CLR is most powerful → avoids most conflicts

---

⚖️ 11. Shift vs Reduce Decision

Situation	Action
Input should continue	Shift
Rule complete	Reduce
Unclear grammar	Conflict ❌

---

📌 12. Real-Life Analogy

👉 Imagine reading a sentence:

• Shift = “read next word”
• Reduce = “understand current phrase”

Conflict =

“Should I continue reading or interpret what I already have?”

---

🎯 13. Key Exam Points

👉 Very important:

• Definition of shift-reduce conflict
• Causes of conflict
• Example grammar
• How to resolve conflict
• Difference between shift and reduce
• Why LR(0) causes conflicts

---

📝 14. Short Notes (Quick Revision)

🔴 Shift-Reduce Conflict

• Parser cannot decide shift or reduce
• Occurs in bottom-up parsing

🔵 Causes

• Ambiguous grammar
• Missing precedence
• LR(0) limitation

🟢 Solution

• Rewrite grammar
• Use precedence rules
• Use LR(1) parsing

---

📊 15. Final Summary Table

Aspect	Shift	Reduce	Conflict
Meaning	Move input to stack	Apply grammar rule	Decision problem
Purpose	Read input	Simplify stack	Parsing issue
Problem	None alone	None alone	Happens in LR parsing
Cause	N/A	N/A	Ambiguity / LR(0)
Solution	N/A	N/A	Grammar fix / LR(1)

---

✅ Final Conclusion

• A shift-reduce conflict is a major issue in bottom-up parsing
• It occurs when the parser cannot decide between shift or reduce
• It is mainly caused by ambiguous grammar or lack of lookahead
• It is solved using grammar rewriting and advanced LR parsers (SLR, CLR, LALR)

---