📘 LR(1) Parsers: Automaton and Parsing Table

(Exam-ready, simple explanation with steps, items, diagrams, and key points)

---

🧠 1. What is LR(1) Parser?

✅ Definition

An LR(1) parser is a bottom-up parsing technique that:

• Scans input Left to right (L)
• Produces Rightmost derivation in reverse (R)
• Uses 1 lookahead symbol (1)

👉 Full form:

LR(1) = Left-to-right scan + Rightmost derivation (reverse) + 1 lookahead

---

⭐ Key Idea

LR(1) parser uses:

• LR(1) items (with lookahead symbols)
• More precise decisions than LR(0) and SLR(1)
• Very powerful parsing method

---

🧠 2. LR(1) Item (Very Important)

✅ Definition

An LR(1) item is written as:

[A → α • β, a]

Where:

• A → αβ is production
• • shows parsing position
• a is lookahead symbol

---

📌 Meaning

👉 “We expect to reduce A → αβ only if next input is a”

---

🔄 3. Closure Operation (LR(1))

Rule:

If:

[A → α • B β, a]

Then for every production:

B → γ

Add:

[B → • γ, b]

Where:

• b ∈ FIRST(βa)

---

⭐ Key Point

👉 Lookahead makes LR(1) very precise

---

🔧 4. GOTO Operation (LR(1))

If:

[A → α • X β, a]

Then:

GOTO(I, X) = [A → α X • β, a]

---

📊 5. LR(1) Automaton

✅ Definition

An LR(1) automaton is a DFA of LR(1) item sets.

👉 It contains:

• States = LR(1) item sets
• Transitions = GOTO function

---

🔹 Construction Steps

Step 1: Augment Grammar

S' → S

---

Step 2: Start State

I0 = CLOSURE([S' → • S, $])

---

Step 3: Build States

• Apply GOTO for all symbols
• Repeat until no new states

---

📌 Concept Diagram

I0 --S--> I1
I0 --C--> I2
I1 --+--> I3

---

🧪 6. Example Grammar

S → CC
C → cC | d

---

Step 1: Augment Grammar

S' → S

---

Step 2: Start Item

[S' → • S, $]

---

Step 3: LR(1) Item Example

[S → • CC, $]
[C → • cC, c/d/$]
[C → • d, c/d/$]

---

📊 7. LR(1) Parsing Table

✅ Structure

State	ACTION (terminals)	GOTO (non-terminals)
	c	d	$	S	C

---

🔧 8. Table Construction Rules

---

🔹 1. SHIFT

If:

[A → α • a β, b]

Then:

ACTION[i, a] = SHIFT j

---

🔹 2. REDUCE (Important LR(1) rule)

If:

[A → α •, a]

Then:

ACTION[i, a] = REDUCE A → α

👉 Only for that specific lookahead a

---

🔹 3. ACCEPT

If:

[S' → S •, $]

Then:

ACTION[i, $] = ACCEPT

---

🔹 4. GOTO

GOTO[i, A] = j

---

📊 9. Why LR(1) is Powerful

✔ Uses exact lookahead symbol ✔ Avoids unnecessary reductions ✔ Removes most conflicts ✔ Handles complex grammars

---

⚠️ 10. Advantages

✔ Very powerful parser ✔ No ambiguity in decisions ✔ No shift/reduce conflicts (in most cases) ✔ Used as theoretical base for LALR

---

❌ 11. Disadvantages

❌ Large number of states ❌ Complex parsing table ❌ Memory expensive ❌ Hard to construct manually

---

⚖️ 12. Comparison

Feature	LR(0)	SLR(1)	LR(1)
Lookahead	None	FOLLOW	Specific symbol
Power	Low	Medium	Very High
States	Few	Medium	Many
Conflicts	Many	Some	Very few
Complexity	Low	Medium	High

---

🎯 13. Important Exam Questions

👉 Very frequently asked:

• Define LR(1) parser
• What is LR(1) item?
• Construct LR(1) automaton
• Explain LR(1) parsing table
• Difference between LR(0), SLR, LR(1)
• Why LR(1) is more powerful
• Closure and GOTO in LR(1)

---

📝 14. Short Notes (Quick Revision)

🔵 LR(1)

• Bottom-up parser
• Uses 1 lookahead symbol
• Very precise

---

🔵 LR(1) Item

• [A → α • β, a]
• Includes lookahead

---

🔵 Automaton

• DFA of LR(1) item sets

---

🔵 Parsing Table

• ACTION + GOTO
• Uses lookahead for decisions

---

📊 15. Final Summary Table

Aspect	LR(1) Parser
Type	Bottom-up
Lookahead	1 (exact symbol)
Basis	LR(1) items
Power	Very high
Table	ACTION + GOTO
Automaton	DFA of item sets
Conflicts	Minimal
Complexity	High

---

✅ Final Conclusion

• LR(1) parser is the most powerful classical parsing method
• It uses LR(1) items with lookahead symbols
• Its automaton is a DFA of item sets
• It produces very accurate parsing decisions but large tables

---