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

Torben Mogensen <>
2 Mar 1999 14:06:14 -0500

          From comp.compilers

Related articles
left- or right-recursion in LALR-grammars? (Markus Mottl) (1999-02-26)
Re: left- or right-recursion in LALR-grammars? (Torben Mogensen) (1999-03-02)
Re: left- or right-recursion in LALR-grammars? (Markus Mottl) (1999-03-04)
| List of all articles for this month |

From: Torben Mogensen <>
Newsgroups: comp.compilers
Date: 2 Mar 1999 14:06:14 -0500
Organization: Compilers Central
References: 99-02-127
Keywords: yacc, parse

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 (

Post a followup to this message

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