📘 Bottom-Up Parsing: Reductions and Shift-Reduce Parsing

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

---

🧠 1. Bottom-Up Parsing

✅ Definition

Bottom-Up Parsing is a parsing technique in which we start from the input string (leaves) and gradually reduce it to the start symbol (root).

👉 It works by:

“Reducing a string to the start symbol using grammar rules.”

---

📊 Basic Idea

Input String → Reductions → Start Symbol (S)

---

⭐ Key Concept

Bottom-up parsing builds the parse tree: 👉 from leaves → root

---

🔄 2. Reductions

✅ Definition

A reduction is the process of replacing a substring of input (handle) with a non-terminal using a production rule.

---

📌 Example Grammar

E → E + T
E → T
T → id

---

📌 Input String

id + id

---

🔄 Reduction Steps

We reduce step-by-step:

id + id
⇒ T + id        (id → T)
⇒ T + T         (id → T)
⇒ E + T         (T → E)
⇒ E             (E + T → E)

---

⭐ Key Points (Exam)

• Reduction = reverse of derivation
• Always replaces handle
• Moves from string → start symbol

---

🧠 3. Handle (Very Important)

✅ Definition

A handle is a substring that:

• Matches the RHS of a production
• Can be reduced to its LHS
• Represents one step in reverse derivation

---

📌 Example

E → E + T

In:

E + T

👉 Handle = E + T

---

⭐ Key Point

👉 Finding handle = core of bottom-up parsing

---

🔧 4. Shift-Reduce Parsing

✅ Definition

Shift-Reduce Parsing is a bottom-up parsing technique that uses:

• Shift operation
• Reduce operation
• Stack

---

📊 5. Working of Shift-Reduce Parser

🔹 Components

• Input Buffer
• Stack
• Parser actions

---

📌 Basic Diagram

Input → [Shift-Reduce Parser Stack] → Output

---

🔄 6. Actions in Shift-Reduce Parsing

---

🔹 1. SHIFT

👉 Move input symbol to stack

Example:

Input: id + id
Stack: id

---

🔹 2. REDUCE

👉 Replace stack symbols using grammar rule

Example:

id → T

---

🔹 3. ACCEPT

👉 Input successfully parsed

---

🔹 4. ERROR

👉 Invalid input

---

🧪 7. Example (Step-by-Step)

Grammar:

E → E + T
E → T
T → id

---

Input:

id + id

---

Shift-Reduce Process

Step	Stack	Input	Action
1		id+id$	shift
2	id	+id$	reduce id → T
3	T	+id$	reduce T → E
4	E	+id$	shift +
5	E +	id$	shift id
6	E + id	$	reduce id → T
7	E + T	$	reduce E + T → E
8	E	$	ACCEPT

---

🌳 8. Parse Tree Idea

Bottom-up parsing builds:

Leaves → Root

Example:

      E
     / \
    E   T
        |
        id

---

⚠️ 9. Problems in Shift-Reduce Parsing

❌ 1. Shift-Reduce Conflict

• Cannot decide shift or reduce

❌ 2. Reduce-Reduce Conflict

• Multiple reduction options

👉 These are handled by LR parsers

---

⚖️ 10. Shift-Reduce vs Top-Down Parsing

Feature	Bottom-Up (Shift-Reduce)	Top-Down
Direction	Leaves → Root	Root → Leaves
Approach	Reduce input	Expand grammar
Method	Handles	Productions
Backtracking	Not needed	Possible
Power	More powerful	Less powerful

---

🎯 11. Advantages

✔ Handles larger class of grammars ✔ No backtracking ✔ Efficient parsing ✔ Used in real compilers

---

❌ 12. Disadvantages

❌ Complex implementation ❌ Conflicts (shift/reduce) ❌ Hard to debug

---

📌 13. Important Exam Questions

👉 Very frequently asked:

• Define bottom-up parsing
• What is reduction?
• Explain handle in parsing
• Steps of shift-reduce parsing
• Solve shift-reduce parsing example
• Difference between shift and reduce
• Parse given string using bottom-up method

---

📝 14. Short Notes (Quick Revision)

🔵 Bottom-Up Parsing

• Starts from input
• Ends at start symbol

🔵 Reduction

• Replace handle with LHS

🔵 Shift-Reduce Parsing

• Uses stack
• SHIFT + REDUCE operations

---

📊 15. Final Summary Table

Aspect	Bottom-Up Parsing	Shift-Reduce Parsing
Definition	Builds tree from input	Stack-based bottom-up parsing
Method	Reductions	Shift + Reduce
Direction	Leaves → Root	Leaves → Root
Key Idea	Reduce string	Use stack operations
Components	Handles	Stack, input buffer
Complexity	Moderate	Moderate
Use	Syntax analysis	Real compiler parsing

---

✅ Final Conclusion

• Bottom-up parsing builds the parse tree from input to start symbol
• Reduction is the reverse of derivation
• Shift-reduce parsing is the most basic bottom-up method
• It is powerful but may face conflicts

---