Re: Problem with infinite left-recursion...

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

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