2 Mar 1999 14:06:14 -0500

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) |

From: | Torben Mogensen <torbenm@diku.dk> |

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 (torbenm@diku.dk)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.