What is Handle

Estudies4you
Which sub string is to be replaced when so many sub strings match right sides of productions?
The Handle
What is Handle?
A sub string which is the right side of a production such that replacement of that sub string by the production left side leads eventually to a reduction to the start symbol, by the reverse of a right most derivation
Technically, a handle of a right sentential form Î³ is a production A  → Î² and a position of γ where the string β may be found and replace by A to produce the previous right sentential form in the right most derivation of γ
That means if S ⇒*  Î±A ($S\text{ }\Rightarrow _{rm}^{*}$ )        Ï‰ ⇒ αβω ($\omega {{\Rightarrow }_{rm}}\alpha \beta \omega $)then A → β in the position following α is a handle of αβω


Important Points on Handles


The string after the handle contains only terminals

All matched sub strings are not handles(That is why d is not replaced in the example discussed earlier)

If the grammar is unambiguous, then every right sentential form of the grammar has exactly one handle

The bottom up parsing simply involves finding and reducing handles

Example of Handle
Consider the following CFG
D TL;
Tint
T→float
T→char
L→L,id
L→id
The parsing table for the input string int id,id; is shown on the table
Input String
Handle
Action
Int id,id;
int
Reduce T→int
T id,id;
Id
Reduce L→id
T L,id;
L, id
Reduce L→L,id
TL;
TL;
Reduce D→TL
D
-
Accepted

Handle Pruning 

Let ω be the string that has to be parsed. If ω is a sentence of the grammar, then ω = γn
Where γn is nth right sentential form of some yet unknown right most derivation
\[S={{\gamma }_{0}}\underset{rm}{\mathop \Rightarrow }\,{{\gamma }_{1}}\underset{rm}{\mathop \Rightarrow }\,{{\gamma }_{2}}\underset{rm}{\mathop \Rightarrow }\,.....{{\gamma }_{n-1}}\underset{rm}{\mathop \Rightarrow }\,{{\gamma }_{n}}\omega \] 


  • To reconstruct this derivation in reverse order, locate the handle βn is γn and replace βn by the left side of some production   An→βn to obtain the (n-1)th right sentential form
  • Repeat the process of finding handles and replace them with their left hand sides until a right sentential form consisting of only the start symbol S is produced. This is called Handle Pruning
  • Simple handle pruning is used to perform reverse operation in right most derivation
  • Some more examples to show the working of shift reduce parsing

Example 1:
Consider the grammar E → E+T, E→ T, T → T*F, T → F, F → id and parsing of id*id
The technique is shown
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
The way in which handles are found using the right most derivation is described below
                E ⇒ T
                  ⇒ T * F
                  ⇒ T * id
                  ⇒ F * id

                  ⇒ id * id (Handles are Underlined)

Example 2:
Consider the grammar E → E + E, E → E, E → E * E, E → (E), E → id and parsing of id + id * id
The technique goes like this
Right Sentential Form
Handle
Reducing Production
id1 + id2 * id3
id1
E → id
E + id2 * id3
id2
E → id
E + E * id3
id3
E → id
E + E * E
E * E
E → E * E
E + E
E + E
E → E + E
E


The way in which handles are found using the right most derivation is described below
E ⇒ E + E
⇒ E + E * E
⇒ E + E * id
⇒ E + id * id
⇒ id + id * id (handles are underlined)
To Top