|left- or right-recursion in LALR-grammars? firstname.lastname@example.org (Markus Mottl) (1999-02-26)|
|Re: left- or right-recursion in LALR-grammars? email@example.com (Torben Mogensen) (1999-03-02)|
|Re: left- or right-recursion in LALR-grammars? firstname.lastname@example.org (Markus Mottl) (1999-03-04)|
|From:||Torben Mogensen <email@example.com>|
|Date:||2 Mar 1999 14:06:14 -0500|
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' -> [ exp ] lval'
you avoid the conflict, as [ is no longer in FOLLOW(lval).
Torben Mogensen (firstname.lastname@example.org)
Return to the
Search the comp.compilers archives again.