29 Oct 1999 02:31:53 -0400

Related articles |
---|

LR-regular parsers for dummies ? dvandeun@vub.ac.be (1999-10-28) |

Re: LR-regular parsers for dummies ? laski@ics.uci.edu (Ziemowit Laski) (1999-10-29) |

Re: LR-regular parsers for dummies ? chrisd@reservoir.com (Chris Dodd) (1999-10-29) |

Re: LR-regular parsers for dummies ? dvandeun@vub.ac.be (1999-10-31) |

Re: LR-regular parsers for dummies ? world!cfc@uunet.uu.net (Chris F Clark) (1999-10-31) |

Re: LR-regular parsers for dummies ? world!cfc@uunet.uu.net (Chris F Clark) (1999-10-31) |

From: | Ziemowit Laski <laski@ics.uci.edu> |

Newsgroups: | comp.compilers |

Date: | 29 Oct 1999 02:31:53 -0400 |

Organization: | Compilers Central |

References: | 99-10-142 |

Keywords: | parse, LR(1) |

Dirk van Deun wrote:

*> I have started reading a 1971 paper ``LR-regular grammars -- an*

*> Extension of LR(k) Grammars'', not once but several times.*

*> Essentially, I drown in it: my short-term memory for notations,*

*>*

*> Does anyone remember this concept ?*

I also had difficulties with the Culik & Cohen paper, but the

quintessence of LRR is (I *think*) the following: You start out with

the typical LR(k) grammars amenable to directional parsing; then, for

lookahead, instead of allowing only k tokens, you allow arbitrary

*regular expressions* of tokens, and hence unbounded lookahead. These

regular expressions are handled by a separate finite state automaton.

Once the FSA is done, you can then decide which token is really next,

rewind the stream, and shift it in as usual.

The lookahead thingy means you really no longer have a directional

parser. If I remember correctly, the authors claimed to be able to

handle most or all context-free languages with this, along with *some*

context-sensitive ones. But IMHO, this is really not worth the

candle. If you really need to handle nondeterministic CFLs, you might

be better off using nondirectional methods such as CYK or Tomita.

Regards,

Zem Laski

UC Irvine

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.