📘 LR Parsing and LR(0) Parsers

(in simple language with definitions, working, items, tables, examples, diagrams, and key exam points)

---

🧠 1. LR Parsing

✅ Definition

LR Parsing is a bottom-up parsing technique that reads input:

• L → Left to right scanning
• R → Rightmost derivation in reverse

👉 So LR means:

“Scan input left-to-right and produce rightmost derivation in reverse.”

---

⭐ Key Idea

LR parser builds the parse tree: 👉 from bottom (input) to top (start symbol)

---

📊 2. Why LR Parsing is Important?

✔ Most powerful deterministic parsing method ✔ Used in real compilers ✔ Handles large class of grammars ✔ No backtracking

---

🔧 3. Types of LR Parsers

Type	Meaning
LR(0)	Simplest LR parser
SLR(1)	Simple LR with FOLLOW sets
CLR(1)	Canonical LR (most powerful)
LALR(1)	Look-Ahead LR (used in practice)

---

🧠 4. LR(0) Parser

✅ Definition

An LR(0) parser is a bottom-up parser that uses:

• No lookahead symbol (0 lookahead)
• LR(0) items
• State machine (DFA of items)

---

📌 5. LR(0) Items

✅ Definition

An LR(0) item is a production with a dot (•) showing parsing position.

---

📌 Example Grammar

E → E + T
E → T
T → id

---

🔄 LR(0) Items

For production:

E → E + T

Items:

E → • E + T
E → E • + T
E → E + • T
E → E + T •

---

⭐ Key Point

👉 Dot shows how much of production is parsed

---

🧠 6. Closure Operation

✅ Definition

Closure adds all possible productions for a non-terminal after dot.

---

📌 Rule

If:

A → α • B β

Then add:

• All productions of B with dot at start

---

🔧 7. GOTO Operation

✅ Definition

GOTO moves the dot over a symbol.

---

📌 Example

If:

E → E • + T

After GOTO(+):

E → E + • T

---

📊 8. LR(0) Automaton (Concept)

LR(0) parser uses a DFA:

States (Items) → Transitions → Parsing Table

---

📌 9. LR(0) Parsing Table

Two parts:

Part	Meaning
ACTION	shift/reduce/accept
GOTO	next state

---

🧪 10. Example Grammar

E → E + T | T
T → id

---

Step 1: Augment Grammar

E' → E

---

Step 2: LR(0) Items (Simplified Idea)

States are built using:

• Closure
• GOTO

---

Step 3: Parsing Table (Conceptual)

State	id	+	$	E	T
0	S5			1	2
1		S6	ACC
2		R2	R2
5		R3	R3

Legend:

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

---

🔄 11. LR(0) Parsing Process

Steps:

1. Start with initial state (0)

2. Read input left to right

3. Use ACTION table:

   • shift → push state
   • reduce → apply rule

4. Use GOTO for transitions

5. Accept when input is fully parsed

---

⚠️ 12. Limitations of LR(0)

❌ Too weak ❌ Cannot handle many grammars ❌ Shift-reduce conflicts common ❌ No lookahead (big issue)

---

📊 13. LR(0) vs Other Parsers

Feature	LR(0)	SLR(1)	CLR(1)
Lookahead	None	1	1
Power	Weak	Medium	Very Strong
Conflicts	Many	Fewer	Almost none
Use	Theory	Some use	Compiler design

---

🎯 14. Important Exam Concepts

👉 Frequently asked:

• Define LR parsing
• What is LR(0) parser?
• What is LR(0) item?
• Closure and GOTO functions
• Construct LR(0) parsing table
• Advantages and disadvantages
• Difference between LR(0), SLR, CLR

---

📝 15. Short Notes (Quick Revision)

🔵 LR Parsing

• Bottom-up method
• Left-to-right scanning
• Rightmost derivation (reverse)

---

🔵 LR(0) Parser

• No lookahead
• Uses item sets
• ACTION + GOTO tables

---

🔵 LR(0) Item

• Production with dot

---

📊 16. Final Summary Table

Aspect	LR Parsing	LR(0) Parser
Definition	Parsing technique	Simplest LR parser
Direction	Bottom-up	Bottom-up
Lookahead	Depends on type	None
Method	LR family	LR(0) items
Strength	Very powerful	Weak
Components	Stack, table	Items, DFA
Use	Compiler design	Theoretical basis

---

✅ Final Conclusion

• LR parsing is the most powerful bottom-up parsing technique
• LR(0) is the simplest version but has limitations
• It uses items, closure, GOTO, and parsing tables
• Forms the foundation of SLR, CLR, and LALR parsers

---