# Re: Operator precedence and Recursive Descent

## graham@maths.su.oz.au (Graham Matthews)Sat, 23 May 1992 05:40:38 GMT

From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... parrt@ecn.purdue.edu (1992-05-11)
Operator precedence and Recursive Descent stt@inmet.com (1992-05-22)
Re: Operator precedence and Recursive Descent graham@maths.su.oz.au (1992-05-23)
Re: Operator precedence and Recursive Descent man@labrea.zko.dec.com (1992-05-26)
| List of all articles for this month |

 Newsgroups: comp.compilers From: graham@maths.su.oz.au (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
> 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)
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

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

Post a followup to this message