Re: Operator precedence and Recursive Descent (Graham Matthews)
Sat, 23 May 1992 05:40:38 GMT

          From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... (1992-05-11)
Operator precedence and Recursive Descent (1992-05-22)
Re: Operator precedence and Recursive Descent (1992-05-23)
Re: Operator precedence and Recursive Descent (1992-05-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Graham Matthews)
Keywords: LL(1), parse
Organization: Sydney University Computing Service, Sydney, NSW, Australia
References: 92-05-059 92-05-128
Date: Sat, 23 May 1992 05:40:38 GMT

(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 =

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

b) new_root =

                / \
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 Matthews
Pure Math, Uni.Sydney, Oz

Post a followup to this message

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