Operator-precedence Parsing

We now look at operator-precedence parsing which is a form of shift-reduce parsing. Two important properties for these shift-reduce parsers is that e does not appear on the right side of any production and no production has two adjacent nonterminals.

We need to define three different precedence relations between pairs of terminals as follows: 

relation        meaning
a <. b          a yields precedence to b
a =. b          a has the same precedence as b
a >. b          a takes precedence over b
Note: When discussing precedence relations, the symbols <., =., and >. have a set of meanings quite different than the relational operators <, ==, and >.

Consider the following grammar: 

E -> E + T | T
T -> T * F | F
F -> id
Suppose we have the following right-sentential string and precedence relations:

right-sentential form: id+id*id

Precedence relations: 

              Input              
              id  +  *  $         Token Class
           id     >. >. >.        id is 0 
           +  <.  >. <. >.        + is 1
   Stack   *  <.  >. >. >.        * is 2
           $  <.  <. <. accept    $ is 3
So here's the deal. We want to identify each handle using the precedence rules and reduce the right-sentential string, based on the precedence relations, to a start (accept) state.

Using Algorithm 4.5 on p. 206, if we look at the string id+id*id and the above precedence relations and output each handle as it is produced substituting a dummy class of 99 for each nonterminal, we would get the following result.

Note: E is a dummy class

Handle     Stack              Input String    Reason
           (top to the right)
           $                  id+id*id$       Initialized
           $id                +id*id$         $ <. id
0          $E                 +id*id$         id >. +
           $E+                id*id$          $ <. + 
           $E+id              *id$            + <. id
0          $E+E               *id$            id >. *
           $E+E*              id$             + <. id
           $E+E*id            $               * <. id
0          $E+E*E             $               id >. $
99 2 99    $E+E               $               * >. $
99 1 99    $E                 $               + > $
RETURN                                        $ =. $
Next we will examine the following grammar: 
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
Douglas J. Ryan / ryandj@pacificu.edu