5.2 A HANDLE OF A RIGHT SENTENTIAL FORM
A handle of a right sentential form γ is a production A → β and a position of β in γ. The string β will be found and replaced by A to produce the previous right sentential form in the right-most derivation of γ. That is, if S → αAβ → αγβ, then A → γ is a handle of αγβ, in the position following α. Consider the grammar:
and the right-most derivation:
The handles of the sentential forms occurring in the above derivation are shown in Table 1.
Table 1: Sentential Form Handles
|
Sentential Form
|
Handle
|
|
id + id * id
|
E → id at the position preceding +
|
|
E + id * id
|
E → id at the position following +
|
|
E + E * id
|
E → id at the position following*
|
|
E + E * E
|
E → E * E at the position following +
|
|
E + E
|
E → E + E at the position preceding the end marker
|
Therefore, the bottom-up parsing is only an attempt to detect the handle of a right sentential form. And whenever a handle is detected, the reduction is performed. This is equivalent to performing right-most derivations in reverse and is called "handle pruning".
Therefore, if the right-most derivation sequence of some w is S → α1 → α2 → α3 → … → αn−1 → w, then handle pruning starts with w, the nth right sentential form, the handle βn of w is located, and βn is replaced by the left side of some production An → βn in order to obtain αn−1. By continuing this process, if the parser obtains a right sentential form that consists of only a start symbol, then it halts and announces the successful completion of parsing.
EXAMPLE 1
Consider the following grammar, and show the handle of each right sentential form for the string (a,(a, a)).
The right-most derivation of the string (a, (a, a)) is:
Table 2 presents the handles of the sentential forms occurring in the above derivation.
Table 2: Sentential Form Handles
|
Sentential Form
|
Handle
|
|
(a, (a, a))
|
S → a at the position preceding the first comma
|
|
(S, (a, a))
|
L → S at the position preceding the first comma
|
|
(L, (a, a))
|
S → a at the position preceding the second comma
|
|
(L, (S, a))
|
L → S at the position preceding the second comma
|
|
(L, (L, a))
|
S → a at the position following the second comma
|
|
(L, (L, S))
|
L → L, S, at the position following the second left bracket
|
|
(L, (L))
|
S → (L) at the position following the first comma
|
|
(L, S)
|
L → L, S, at the position following the first left bracket
|
|
(L)
|
S → (L) at the position before the endmarker
|
|
