Mon, 19 Dec 1994 17:22:27 GMT

Related articles |
---|

Problem with infinite left-recursion... cbs@ascinc.com (1994-12-12) |

Re: Problem with infinite left-recursion... jjan@cs.rug.nl (1994-12-14) |

Re: Problem with infinite left-recursion... tophat!mauney@uunet.uu.net (1994-12-14) |

Re: Problem with infinite left-recursion... davidm@Rational.COM (1994-12-19) |

Newsgroups: | comp.compilers |

From: | davidm@Rational.COM (David Moore) |

Keywords: | parse |

Organization: | Rational Software Corporation |

References: | 94-12-086 94-12-107 |

Date: | Mon, 19 Dec 1994 17:22:27 GMT |

cbs@ascinc.com (Casper B. Stoel) writes:

*>I have a problem with left-recursion in my grammar. I am wondering if*

*>there is a 'standard' way of breaking the recursion? Is there an easy*

*>way of breaking up the rule into multiple rules?*

tophat!mauney@uunet.uu.net (Jon Mauney) writes:

*>Most left and right recursion in grammars follows a standard idiom.*

*>To describe a list of A's left-recursively, we typically write*

*> list ::= list A*

*> | A*

*>To describe a list of A's right-recursively, we typically write*

*> list ::= A more-A*

*> more-A ::= A*

*> | empty*

*>Separators go in fairly obvious places, if needed.*

*>Expressions are just lists of operands separated by operators.*

*>If you have a lot of left-recursive rules it is tedious to*

*>change them all, but not difficult.*

Dangerous advice!

Consider the two grammars:

E -> N | E + N | E - N

where N is a terminal meaning any number

E -> N | N + E | N - E

So, the first is left recursive while the second is right recursive.

Let's build the derivation tree for a simple expression: 2-3+4

Left recursive: Right recursive:

E E

| |

----------------- -----------------

| | | | | |

E | N N | E

| | | | | |

------------- | | | | -------------

| | | | | | | | | |

E | N | | | | N | E

| | | | | | | | | |

N | | | | | | | | N

| | | | | | | | | |

2 - 3 + 4 2 - 3 + 4

It is natural to want to collapse the syntax tree down to a semantic tree

in a simple way. One would be doing this, for example, if one spat out

code (for a stack machine say) as one did reductions.

However, if we do this we get two different trees.

With the left recursive tree, we do the subtract first, so the order

of equal precedence operators is left to right. With the right recursive

form the order is right to left. Left recursive gives the answer 3

while right recursive gives -5.

The usual approach is to eliminate left recursion and then left

factor (if needed). See Green Dragon page 177. The left recursive

grammar becomes:

E -> N E1

E1 -> + N E1 | - N E1 | <empty>

Here, we are using the fact that the symbol E does not elide to pump

out one iteration of the tree. Unfortunately, this form makes merely

serves to make the operator ordering more obscure rather than fixing

the original problem.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.