Re: left- or right-recursion in LALR-grammars?

Markus Mottl wrote:


> Has someone found cases where using right-recursion generally turned
> out to be the better choice? - Since it used less shifts/reductions
> (at least in the example I had tried), it is probably faster unless
> new memory has to be allocated for a larger stack space and unless
> the machine does not start swapping, of course ;-)


> Are right-recursive grammars generally more compact? Is it easier
> to develope/maintain them for larger projects? As far as I know,
> it is more difficult to write grammars containing left-associative
> operators in a "right-recursive" style, but I don't know, whether
> there are other advantages/disadvantages.


I don't think right-recursive grammars are in general more compact
than left-recursive ones, it all depends on the language.


My choice of left or right recursion depends on two factors:


  1) (like John) whatever makes it easier to do attribution,
        e.g. building a list of statements (right recursion).
        If you work in a functional language, it is, however, fairly easy
        to get around this using higher-order functions for attributes.


  2) whatever avoids shift/reduce or reduce/reduce conflicts.
        Sometimes a left recursive formulation needs unbounded look-ahead
        to resolve conflicts, where a right-recursive formulation can work
        with only LALR(1) or SLR(1).


An example of the latter was described in an old posting of mine in
this newsgroup. A simpler version of this example is shown below.


exp -> lval := exp
exp -> id [ exp ] of exp


lval -> id
lval -> lval [ exp ]


The problem is that in the item set


exp -> id · [ exp ] of exp
lval -> id ·


you have a shift/reduce conflict on [, as [ is in FOLLOW(lval). By
rewriting lval to right-recursive form:


lval -> id lval'
lval' ->
lval' -> [ exp ] lval'


you avoid the conflict, as [ is no longer in FOLLOW(lval).


Torben Mogensen (torbenm@diku.dk)

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