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 αβω
Example 2:
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;
T→int
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 \]
\[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)
0 comments:
Post a Comment