📘 Top-Down Parsing and Recursive-Descent Parsing

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

---

🧠 1. Top-Down Parsing

✅ Definition

Top-Down Parsing is a parsing technique in which we start from the start symbol and try to construct the parse tree downwards (root → leaves) to match the input string.

---

📊 Basic Idea

Start Symbol (S)
      ↓
Apply productions
      ↓
Generate input string

---

🔧 How it Works (Step-by-Step)

1. Start with start symbol (S)
2. Replace non-terminals using grammar rules
3. Try to match input string
4. Continue until all terminals match input

---

📌 Example Grammar

E → T + E | T
T → id

---

📌 Input String:

id + id

---

🔄 Parsing Steps

E
⇒ T + E
⇒ id + E
⇒ id + T
⇒ id + id

---

🌳 Parse Tree (Concept)

        E
      / | \
     T  +  E
     |     |
    id    T
          |
         id

---

⭐ Key Points (Exam)

• Builds tree from top to bottom
• Uses leftmost derivation
• Simple but may require backtracking

---

❗ Problem in Top-Down Parsing

• May face left recursion
• May require backtracking
• Not efficient for all grammars

---

🧠 2. Types of Top-Down Parsing

---

🔹 1. Recursive-Descent Parsing (Important)

✅ Definition

A Recursive-Descent Parser is a top-down parser where each non-terminal is implemented as a recursive function.

---

📌 Example Grammar

E → T + E | T
T → id

---

💻 Function Representation

E():
    T()
    match('+')
    E()

T():
    match(id)

---

🔄 Working

For input:

id + id

Steps:

1. Call E()
2. Call T() → matches id
3. Match +
4. Call E() again
5. Match id

---

⭐ Key Features

• Easy to implement
• Uses recursion
• Works well with LL(1) grammar

---

❗ Limitations

• Cannot handle left recursion
• May require backtracking
• Inefficient for complex grammars

---

🔁 3. Backtracking in Top-Down Parsing

❌ Problem Example

A → ab | a

Input:

a

👉 Parser tries:

• ab ❌ fail
• a ✅ success

---

⭐ Key Point

• Backtracking = trying multiple possibilities
• Makes parsing slow

---

⚖️ 4. Top-Down vs Bottom-Up (Important Comparison)

Feature	Top-Down Parsing	Bottom-Up Parsing
Direction	Root → Leaves	Leaves → Root
Approach	Expand start symbol	Reduce input string
Derivation	Leftmost	Reverse rightmost
Complexity	Simple	Complex
Backtracking	Possible	Not needed
Example	Recursive descent	LR parser

---

🧠 5. Why Recursive-Descent is Important

✅ Advantages

• Simple to understand
• Easy to implement in code
• Matches grammar rules directly

---

❌ Disadvantages

• Cannot handle left recursion
• May need backtracking
• Not efficient for large grammars

---

🛠️ 6. How to Make Grammar Suitable for Top-Down Parsing

To use recursive descent parsing, grammar must be:

✔ No left recursion ✔ Left factored ✔ Unambiguous

---

📌 Example Fix

❌ Before:

E → E + T | T

✅ After:

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

---

🎯 7. Important Exam Questions

👉 Frequently asked:

• Define top-down parsing
• What is recursive descent parsing?
• Difference between top-down and bottom-up
• Problems of top-down parsing
• Eliminate left recursion for parsing
• Write recursive functions for grammar
• Parse given string using top-down method

---

📝 8. Short Notes (Quick Revision)

🔵 Top-Down Parsing

• Root to leaf
• Uses leftmost derivation
• May use backtracking

🔵 Recursive Descent Parsing

• Implementation of top-down parsing
• Uses recursive functions
• Simple but limited

---

📊 9. Final Summary Table

Aspect	Top-Down Parsing	Recursive-Descent Parsing
Definition	Builds parse tree from root	Implements parsing using functions
Type	Parsing strategy	Parsing technique
Implementation	Conceptual	Programmatic
Backtracking	Possible	Possible
Grammar requirement	No left recursion	No left recursion
Complexity	Moderate	Simple

---

✅ Final Conclusion

• Top-Down Parsing builds parse trees from the start symbol downward
• Recursive-Descent Parsing is a practical implementation of it
• Both require clean grammar (no left recursion, left factoring)
• Very important for LL(1) parsing systems

---