Handle and Handle Pruning

Introduction to Handle and Handle Pruning

• Handle: A substring that matches the right side of a production in a grammar.
• Handle Pruning: The process of replacing the handle with the corresponding left-hand non-terminal.

Example Grammar

• Given Grammar Productions:
  • S → AAB
  • E → ABCDE
  • A → ABC
  • B → D
  • D → d

Input String

• The input string for the example: ABBCDE

Steps to Find Handle and Reduction

• First Column: Right Sentential Form
• Second Column: Handle
• Third Column: Reducing Production

1. Initial Input: ABBCDE

   • Substring "A" is not available on the right side.
   • Substring "B" is available.
   • Handle: B
   • Reduction: A → B
   • Remaining Input: BCDE

2. Next Steps:

   • Consider substring ABC
   • This is available on the right side: A → ABC
   • Reduce ABC to A
   • Remaining Input: AADE

3. Further Reductions:

   • B → D is the next reduction.
   • Remaining Input: AAB
   • Recognize AAB as start symbol: S → AAB.

Bottom-Up Parsing

• Bottom-Up Parsing generates the rightmost derivation in reverse order.
• Why Right Sentential Form?:
  • Expanding rightmost non-terminals.
  • Scanning input from left to right produces leftmost derivation.

Another Example: Expression Grammar

• Productions:
  • E → E + T
  • T → T * F
  • F → (E) | id
• Input String: id * id

Steps for Expression Grammar

1. Initial Input: id * id
   • Handle: id (reducing id to F)
   • Remaining Input: F * id
2. Next Reduction:
   • Handle: F → T
   • Remaining Input: T * id
3. Final Reduction:
   • Handle: T → E

Summary of Handle and Handle Pruning

• Handle matches the right-hand side of a production.
• Reducing means converting a handle to its corresponding non-terminal.
• Handle Pruning enables the rightmost derivation in reverse order.
• Right Sentential Form corresponds to the bottom-up parsing approach.