Sat, 23 May 1992 05:40:38 GMT

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) |

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*

*>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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.