left- or right-recursion in LALR-grammars?

Hello,


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


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]

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