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 5.1.
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 A n ’ ² 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.
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 5.2 presents the handles of the sentential forms occurring in the above derivation.
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 |