Re: Operator precedence and Recursive Descent

(Tucker Taft) writes:
>There has been some discussion of the problem of "recursive plunge" when a
>language has many levels of operator precedence. We found a neat trick
>that solves this problem in the "lcc" compiler recently made available by
>David Hanson.
>It works best in recursive descent parsers because it is so easy to pass
>additional parameters:
> 1) Have exactly one function for parsing operator expressions
> 2) Pass it the precedence at which to stop accumulating operators


There are numerous ways of doing this. I once wrote a one routine
expression parser. I don't remember exact details (it was a while back)
but from memory it worked something like this .. I had a table of operator
precedences. The routine built a parse tree by re-ordering the parse tree
if the just seen operator was of higher precedence than (I think) the root
of the existing parse tree.


If I remember rightly the re-ordering was very efficient as it always
involved doing the following steps :-


b) new_node =


                        latest_operator
                  / \
                / \
              / \
old_root.right_hand_side rhs of latest_operator


b) new_root =


                  old_root.operator
                / \
old_root.left_hand_side new_node


So the whole rotuine worked like


(initial parser tree = first operand)
a) read an operator
b) read an operand
c) re-order tree
d) goto a)


So for example say we have the expression


        a + b * c


The routine builds the tree


        +
      / \
    a b


Then the rotuine sees '* c' and re-orders the tree as follows,


new_node = *
                                / \
                              b c


new_root = +
                                / \
                              a new_node


which is the required tree.


As I remember it there were a few complications to the scheme (eg:
unary operators and ternary operators) but not many. New operators
could be added by simply adding to the operator precedence table.


graham
--
Graham Matthews
Pure Math, Uni.Sydney, Oz
graham@maths.su.oz.au
--

Return to the comp.compilers page.
Search the comp.compilers archives again.