Operator precedence and Recursive Descent - comp.compilers

Message from discussion Operator precedence and Recursive Descent

Graham Matthews

View profile

More options May 23 1992, 6:40 am

Newsgroups: comp.compilers

From: gra...@maths.su.oz.au (Graham Matthews)

Date: Sat, 23 May 1992 05:40:38 GMT

Local: Sat, May 23 1992 1:40 am

Subject: Re: Operator precedence and Recursive Descent

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

(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
gra...@maths.su.oz.au
--
Send compilers articles to compil...@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.

Reply to author Forward