Reduction & Handle Pruning

Reduction & Handle Pruning, Compilers by AHO, LAM

1. Course Code- CSE-3201 Presentation On Reduction & Handle Pruning 1

2. Moderator : Member 1 : Member 2 : Member 3 : Member 4 : Member 5 : 2

3. What is reduction? Key decision for reduction Example of reduction What is Handle? What is Handle Pruning? Example of Handle Pruning 3 Outline

4. Bottom up parsing is the process of “reducing” a string ‘w’ to the start symbol of the grammar. At each reduction step , a specific substring matching the body of a production is replaced by the nonterminal at the head of the production. 4 What is reduction?

5. 5 Key Concern The key concern during bottom-up parsing are about when to reduce and about what production to apply, as the parse proceeds. It will be discuss in example section.

6. GRAMMAR: E -> E + T | T T -> T * F | F F -> ( E ) | id STRING: W = id * id 6 Example

7. i d * id F * id [ F -> id ] T * id [ T -> F] T * F [ F -> id ] T [T -> T*F ] E [ E -> T ] The Parse completes with the reduction of string W to the start symbol E. 7 Example

8. A “Handle” is a substring that matches the body of a production and whose reduction represents one step along the reverse of a rightmost derivation. If, A -> α Then α is the handle 8 What is Handle?

9. 9 What is Handle Pruning? Removing the children of left hand side non terminal from the parse tree is called Handle Pruning. A right most derivation in reverse can be obtained by Handle Pruning. I f S=>αAw=>αβw ◦ then A->β in the position following α is a handle of αβw T he handle of right-sentential form γ is a production A- >β and a position of γ where β may be found , such that replacing β at that position by A produces the previous right sentential form in a rightmost derivation of γ.

10. Steps to Follow: Start with a string of terminals ‘w’ that is to be parsed. Let w is a string of the grammar. w= γn where γn is the n- th right-sentential form of some unknown rightmost derivation. S=γ0=>γ1=>γ2=>… =>γn-1=>γn = w . 10 Handle Pruning

11. Steps to Follow: To rebuild this derivation in reverse order ◦ locate handle βn in γn by production of An -> βn to get right-sentential form γn-1 ◦ handles must be found with specific methods ◦ repeat the process until the start symbol S is found ◦ reverse of reductions = rightmost derivation 11 Handle Pruning

12. GRAMMAR: E -> E + T | T T -> T * F | F F -> ( E ) | id STRING: W = id * id 12 E x ample:

13. Right Sentential Form Handle Reducing Production id1 * id2 id1 F -> id F * id2 F T -> F T * id2 id2 F -> id T * F T * F E -> T * F E * Adding subscripts to the tokens ‘id’ for clarity. 13 E x ample:

14. Thanks All 14