left- or right-recursion in LALR-grammars?

Markus Mottl <mottl@miss.wu-wien.ac.at>
26 Feb 1999 12:12:05 -0500

          From comp.compilers

Related articles
left- or right-recursion in LALR-grammars? mottl@miss.wu-wien.ac.at (Markus Mottl) (1999-02-26)
Re: left- or right-recursion in LALR-grammars? torbenm@diku.dk (Torben Mogensen) (1999-03-02)
Re: left- or right-recursion in LALR-grammars? mottl@miss.wu-wien.ac.at (Markus Mottl) (1999-03-04)
| List of all articles for this month |

From: Markus Mottl <mottl@miss.wu-wien.ac.at>
Newsgroups: comp.compilers
Date: 26 Feb 1999 12:12:05 -0500
Organization: University of Economics and Business Administration, Vienna, Austria
Keywords: yacc, parse, question


I have just recently played around with different LALR grammars for the
same language. I wondered, what differences exist between the resulting

In one I used left-recursion only, in the other right-recursion. It is
clear that left-recursion has the big advantage of having an upper bound
for the stack space. But besides this, I observed that the otherwise not
recommendable right-recursive version needed less nonterminals/productions
and also less shifts/reductions to parse the same source (of course:
it needed more stack space). So what I would like to know:

    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 guess that most people have taken the "safe way" and have applied left
recursion in their projects. Still, it would be interesting to see,
whether there are some "real" projects, where right-recursion is used
as basic principle.

Best regards,
Markus Mottl

Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
[I use both, depending on which makes it easier to build the data structures
I need. Left recursion works fine for lists of statements, but I find that
right recursion makes it easier to build linked lists of arguments and
the like. I don't worry about blowing the stack in single statements, only
in top level rules that iterate over an entire program. -John]

Post a followup to this message

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