📘 LL(1) Grammars and Non-Recursive Predictive Parsing

(in simple language with definitions, steps, diagrams, table construction, and key exam points)

---

🧠 1. LL(1) Grammar

✅ Definition

An LL(1) grammar is a grammar that can be parsed:

• L → Left to right scanning of input
• L → Leftmost derivation
• 1 → One lookahead symbol is enough

👉 So, LL(1) means:

“Predict the correct production using only 1 input symbol lookahead.”

---

⭐ Key Idea

LL(1) parser is a top-down predictive parser with no backtracking.

---

📊 2. Conditions for LL(1) Grammar (Very Important)

A grammar is LL(1) if:

---

🔹 1. No Left Recursion

❌ Bad:

E → E + T | T

✔ Fixed:

E → T E'

---

🔹 2. Left Factored

❌ Bad:

A → ab | ac

✔ Fixed:

A → aA'
A' → b | c

---

🔹 3. FIRST & FOLLOW Condition (Most Important)

For:

A → α | β

Grammar is LL(1) if:

✔ Condition 1:

FIRST(α) ∩ FIRST(β) = ∅

✔ Condition 2 (if ε exists):

FIRST(α) ∩ FOLLOW(A) = ∅

---

⭐ Key Point (Exam)

👉 No ambiguity + no overlap in FIRST/FOLLOW = LL(1)

---

🧠 3. Predictive Parsing

✅ Definition

Predictive parsing is a top-down parsing method that:

• Uses LL(1) grammar
• Uses a parsing table
• Does not use backtracking

---

🔧 4. Non-Recursive Predictive Parsing

✅ Definition

A Non-Recursive Predictive Parser uses:

• A stack
• A parsing table
• Input buffer

👉 It does NOT use recursion (unlike recursive descent).

---

📊 5. Structure of Predictive Parser

Input Buffer → [Stack + Parsing Table] → Output

---

🔹 Components

1. Stack

• Stores grammar symbols
• Starts with $S

---

2. Input Buffer

• Contains input string + $

---

3. Parsing Table (M)

• Guides production selection

---

📌 6. Algorithm (Very Important)

Step-by-step:

1. Initialize stack:

   $ S
   

2. Read input string with $

3. Repeat:

   • If top of stack = input symbol → pop & move input
   • If top is non-terminal → use parsing table
   • If mismatch → error

---

🧪 7. Example Grammar

E → T E'
E' → + T E' | ε
T → id

---

🔵 FIRST & FOLLOW (Needed)

FIRST:

FIRST(E) = {id}
FIRST(E') = {+, ε}
FIRST(T) = {id}

FOLLOW:

FOLLOW(E) = {$}
FOLLOW(E') = {$}
FOLLOW(T) = {+, $}

---

📊 8. LL(1) Parsing Table

Non-Terminal	id	+	$
E	E → T E'
E'		E' → + T E'	E' → ε
T	T → id

---

🔄 9. Parsing Example

Input:

id + id $

---

Stack Process (Simplified)

Stack	Input	Action
$E	id+id$	E → T E'
$E'T	id+id$	T → id
$E'T	id+id$	match id
$E'	+id$	E' → +T E'
$E'T+	+id$	match +
...	...	continues

✔ Accept when both reach $

---

⚠️ 10. Errors in Predictive Parsing

• Missing table entry → error
• Stack-input mismatch → error
• Grammar not LL(1) → cannot parse

---

📌 11. Advantages

✔ No backtracking ✔ Fast parsing ✔ Easy implementation ✔ Deterministic

---

❌ 12. Disadvantages

❌ Cannot handle left recursion ❌ Cannot handle ambiguous grammar ❌ Requires grammar transformation

---

🎯 13. Important Exam Questions

👉 Very frequently asked:

• Define LL(1) grammar
• Conditions for LL(1) grammar
• Construct predictive parsing table
• Explain non-recursive predictive parsing
• Difference between recursive and non-recursive parsing
• Steps of predictive parser algorithm

---

📝 14. Short Notes (Quick Revision)

LL(1)

• Left to right input
• Leftmost derivation
• 1 lookahead symbol

---

Predictive Parsing

• Uses stack + table
• No backtracking
• Top-down method

---

Non-Recursive Parser

• Stack-based
• Table-driven
• Efficient

---

📊 15. Final Summary Table

Feature	LL(1) Grammar	Predictive Parsing
Meaning	Grammar type	Parsing technique
Lookahead	1 symbol	1 symbol
Method	Rules	Stack + table
Backtracking	No	No
Requirement	FIRST & FOLLOW	Parsing table
Efficiency	High	High
Use	Grammar design	Syntax analysis

---

✅ Final Conclusion

• LL(1) grammar is designed for predictive parsing
• Non-recursive predictive parsing uses a stack + parsing table
• It is fast, deterministic, and widely used in compilers

---