5.2 A HANDLE OF A RIGHT SENTENTIAL FORM

5.1 WHAT IS BOTTOM-UP PARSING?

Bottom-up parsing can be defined as an attempt to reduce the input string w to the start symbol of a grammar by tracing out the right-most derivations of w in reverse. This is equivalent to constructing a parse tree for the input string w by starting with leaves and proceeding toward the root ”that is, attempting to construct the parse tree from the bottom, up. This involves searching for the substring that matches the right side of any of the productions of the grammar. This substring is replaced by the left-hand-side nonterminal of the production if this replacement leads to the generation of the sentential form that comes one step before in the right-most derivation. This process of replacing the right side of the production by the left side nonterminal is called "reduction". Hence, reduction is nothing more than performing derivations in reverse. The reason why bottom-up parsing tries to trace out the right-most derivations of an input string w in reverse and not the left-most derivations is because the parser scans the input string w from the left to right, one symbol/token at a time. And to trace out right-most derivations of an input string w in reverse, the tokens of w must be made available in a left-to-right order. For example, if the right-most derivation sequence of some w is:

then the bottom-up parser starts with w and searches for the occurrence of a substring of w that matches the right side of some production A ’ ² such that the replacement of ² by A will lead to the generation of ± _{n ˆ’ 1} . The parser replaces ² by A, then it searches for the occurrence of a substring of ± _{n ˆ’ 1} that matches the right side of some production B ’ ³ such that replacement of ³ by B will lead to the generation of ± _{n ˆ’ 2} . This process continues until the entire w substring is reduced to S , or until the parser encounters an error.

Therefore, bottom-up parsing involves the selection of a substring that matches the right side of the production, whose reduction to the nonterminal on the left side of the production represents one step along the reverse of a right-most derivation. That is, it leads to the generation of the previous right-most derivation. This means that selecting a substring that matches the right side of production is not enough; the position of this substring in the sentential form is also important.

Tip  

The substring should occur in the position and sentential form that is currently under consideration and, if it is replaced by the left-side nonterminal of the production, that it leads to the generation of the previous right-hand sentential form of the currently considered sentential form. Therefore, finding a substring that matches the right side of a production, as well as its position in the current sentential form, are both equally important. In order to take both of these factors into account, we will define a "handle" of the right sentential form.