📘 Eliminating Ambiguity, Left Recursion, and Left Factoring

(in simple language with examples, diagrams, and key points)

---

🧠 1. Eliminating Ambiguity

✅ What is Ambiguity?

A grammar is ambiguous if a string has more than one parse tree.

---

📌 Example (Ambiguous Grammar)

E → E + E | E * E | id

String:

id + id * id

👉 Two interpretations:

• (id + id) * id ❌
• id + (id * id) ❌

---

❗ Problem

Ambiguity causes:

• Confusion in meaning
• Wrong evaluation order
• Parsing difficulty

---

✅ How to Eliminate Ambiguity

We rewrite grammar using precedence rules.

---

📌 Unambiguous Grammar

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

---

🎯 Meaning

• * has higher precedence than +
• Correct evaluation is enforced

---

⭐ Key Points (Exam)

• Ambiguity = multiple parse trees
• Remove using precedence-based grammar
• Very important for expression parsing

---

🔁 2. Left Recursion

✅ Definition

A grammar is left recursive if a non-terminal calls itself as the first symbol on RHS.

---

📌 Example

A → Aα | β

👉 Here:

• A → Aα (left recursion ❌)

---

❗ Problem with Left Recursion

• Causes infinite recursion
• Not suitable for top-down parsing (LL parser)

---

🔄 Types of Left Recursion

🔹 1. Immediate Left Recursion

A → Aα | β

---

🔹 2. Indirect Left Recursion

A → Bα
B → Aβ

---

🛠️ 3. Eliminating Left Recursion

---

✅ Rule (Important)

If:

A → Aα | β

Then convert to:

A → βA'
A' → αA' | ε

---

📌 Example

Given:

A → A a | b

---

After Removal:

A → b A'
A' → a A' | ε

---

⭐ Key Points (Exam)

• Needed for LL(1) parsing
• Eliminates infinite loops
• Converts grammar into top-down form

---

🔄 3. Left Factoring

✅ Definition

Left factoring is a technique used when multiple productions of a non-terminal start with the same prefix.

---

📌 Example

A → αβ1 | αβ2

👉 Common prefix = α

---

❗ Problem

Parser cannot decide which rule to choose.

---

🛠️ 4. Removing Left Factoring

---

✅ Rule

A → αA'
A' → β1 | β2

---

📌 Example

Given Grammar:

A → id + T | id - T

---

Step 1: Common prefix = id

---

After Left Factoring:

A → id A'
A' → + T | - T

---

⭐ Key Points (Exam)

• Removes common prefixes
• Helps in predictive parsing
• Avoids backtracking

---

⚖️ 5. Comparison Table

Concept	Problem	Solution	Purpose
Ambiguity	Multiple parse trees	Rewrite grammar	Clear meaning
Left Recursion	Infinite recursion	Remove recursion	Enable top-down parsing
Left Factoring	Common prefixes	Factor out prefix	Avoid backtracking

---

🔗 6. Relationship Between Concepts

Ambiguity → Fix grammar structure  
Left Recursion → Fix parsing issue  
Left Factoring → Improve decision making

---

🧪 7. Combined Example

Original Grammar:

A → A a | A b | c

---

Step 1: Remove Left Recursion

A → c A'
A' → a A' | b A' | ε

---

Step 2: (If needed) Left Factoring applied similarly

---

🎯 8. Important Exam Questions

👉 Very frequently asked:

• Define ambiguity with example
• Eliminate ambiguity from grammar
• Remove left recursion (direct/indirect)
• Explain left factoring
• Convert grammar into LL(1) form
• Difference between all three

---

📝 9. Short Notes (Quick Revision)

🔴 Ambiguity

• Multiple parse trees
• Removed using precedence grammar

🔵 Left Recursion

• A → Aα
• Removed using transformation

🟢 Left Factoring

• Common prefix problem
• Used for predictive parsing

---

📊 10. Final Summary Table

Feature	Ambiguity	Left Recursion	Left Factoring
Problem	Multiple meanings	Infinite recursion	Common prefixes
Affects	Parsing clarity	Top-down parsing	Predictive parsing
Solution	Rewrite grammar	Remove recursion	Factor prefixes
Used in	Expression grammar	LL(1) design	LL(1) design
Importance	Very High	Very High	Very High

---

✅ Final Conclusion

• Ambiguity causes multiple interpretations ❌
• Left recursion blocks top-down parsing ❌
• Left factoring improves parsing decisions ✅
• All three are essential for designing LL(1) grammars

---