5.3 IMPLEMENTATION


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 5.1.

Table 5.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 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.

EXAMPLE 5.1
start example

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.

Table 5.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

end example
 



Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net