📘 LR(0) Automaton and Parsing Table

(in simple language with definitions, construction steps, diagrams, and examples)

---

🧠 1. LR(0) Automaton

✅ Definition

An LR(0) automaton is a finite state machine (DFA) constructed from LR(0) items of a grammar. It is used to guide bottom-up (shift-reduce) parsing.

👉 It shows:

• States (sets of items)
• Transitions between states

---

📌 2. LR(0) Item (Revision)

A production with a dot (•):

A → α • β

👉 Dot shows how much of the production is already seen.

---

🔧 3. Two Important Functions

🔹 1. Closure

If:

A → α • B β

Then include:

• All productions of B with dot at start

---

🔹 2. GOTO

Moves dot over a symbol:

A → α • X β  →  A → α X • β

---

🔄 4. Construction of LR(0) Automaton

📌 Step-by-step Procedure

---

🔹 Step 1: Augment Grammar

Add new start symbol:

S' → S

---

🔹 Step 2: Start State (Closure of S')

I0 = CLOSURE(S' → • S)

---

🔹 Step 3: Compute GOTO

For each state and symbol:

GOTO(I, X)

---

🔹 Step 4: Repeat

Continue until no new states are generated.

---

📊 5. Example Grammar

S → CC
C → cC | d

---

🔹 Augmented Grammar

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

---

🌳 6. LR(0) Automaton (Conceptual Diagram)

States:

I0 → I1 → I2 → ...

Transitions:

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

👉 Each state = set of LR(0) items

---

📌 7. LR(0) Parsing Table

✅ Definition

An LR(0) parsing table is a table that tells the parser:

• When to shift
• When to reduce
• When to accept
• Where to go next

---

📊 Structure

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

---

🔧 8. Table Entries

🔹 1. Shift

If:

A → α • a β

Then:

ACTION[i, a] = Shift j

---

🔹 2. Reduce

If:

A → α •

Then:

ACTION[i, a] = Reduce A → α
(for all terminals)

---

🔹 3. Accept

If:

S' → S •

Then:

ACTION[i, $] = ACCEPT

---

🔹 4. GOTO

If:

GOTO(I, A) = j

Then:

GOTO[i, A] = j

---

🧪 9. Example (Simple Table Idea)

Grammar:

S → CC
C → cC | d

---

🔹 ACTION/GOTO Table (Simplified)

State	c	d	$	S	C
0	S3	S4		1	2
1			ACC
2	S3	S4			5
3	S3	S4			6
4	R C→d	R C→d	R
5			R S→CC

Legend:

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

---

🔄 10. How LR(0) Parsing Works

Steps:

1. Push initial state (0)

2. Read input symbol

3. Check ACTION table:

   • Shift → push state
   • Reduce → pop symbols & push non-terminal

4. Use GOTO for next state

5. Accept at final state

---

⚠️ 11. Problems in LR(0)

❌ 1. Shift/Reduce Conflict

• Cannot decide shift or reduce

❌ 2. Reduce/Reduce Conflict

• Multiple reductions possible

👉 That’s why LR(0) is weak

---

📊 12. Advantages

✔ Simple concept ✔ Foundation of LR parsing ✔ Easy automaton construction

---

❌ 13. Disadvantages

❌ Too many conflicts ❌ Not suitable for real compilers ❌ No lookahead symbol

---

⚖️ 14. LR(0) vs SLR vs CLR

Feature	LR(0)	SLR(1)	CLR(1)
Lookahead	None	FOLLOW set	Full lookahead
Conflicts	Many	Fewer	Almost none
Power	Weak	Medium	Very strong
Use	Theory	Some use	Real compilers

---

🎯 15. Important Exam Questions

👉 Frequently asked:

• What is LR(0) automaton?
• Construct LR(0) items and automaton
• Define closure and GOTO
• Draw LR(0) parsing table
• Explain shift-reduce parsing using LR(0)
• Why LR(0) is not used in practice

---

📝 16. Short Notes (Quick Revision)

🔵 LR(0) Automaton

• DFA of LR(0) items
• Uses closure + GOTO

---

🔵 LR(0) Parsing Table

• ACTION + GOTO table
• Guides parsing decisions

---

📊 17. Final Summary Table

Aspect	LR(0) Automaton	LR(0) Parsing Table
Definition	DFA of items	Parsing decision table
Components	States + transitions	ACTION + GOTO
Purpose	Show grammar states	Drive parsing
Construction	Closure + GOTO	From automaton
Output	State diagram	Table format
Use	Basis of LR parsing	Shift-reduce parsing

---

✅ Final Conclusion

• LR(0) automaton represents grammar as a DFA of item sets
• LR(0) parsing table converts this DFA into shift-reduce decisions
• It is simple but has many conflicts, so it is mainly used as a foundation for SLR, CLR, and LALR parsing

---