29 Oct 1999 02:36:42 -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: | Chris Dodd <chrisd@reservoir.com> |

Newsgroups: | comp.compilers |

Date: | 29 Oct 1999 02:36:42 -0400 |

Organization: | Bay Area Internet Solutions |

References: | 99-10-142 |

Keywords: | parse |

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,*

*> symbols and abstractions runs out long before I reach some kind*

*> of intuitive insight.*

The intuition behind this is fairly simple, provided you already

understand LR parser construction and LR parsing in general.

The basic idea is to `resolve' shift-reduce and reduce-reduce

conflicts in the parser with a state machine that scans ahead in the

input and decides which action to take. The method works by

constructing an RE for each of the conflicting actions, and then

building a DFA that recognizes them simultanueously; whichever RE

matches is the action to take. If more than one could match (the REs

are not disjoint), then the grammar is not LR-regular. Intuitively,

the RE for each action recognizes the (arbitrarily large) lookahead

for which the action is valid. An LR(1) parser can be seen as an

LR-reqular parser for which all the REs are restricted to 1 character.

*> I'm starting to suspect that either the whole idea was useless,*

*> or that nobody ever understood the paper and the idea got*

*> forgotten :-)*

Its not at all clear if its all that useful. In my experience, real

grammars tend to be either LR(1) (in which case the extra power isn't

needed) or ambiguous (in which case it doesn't help).

Chris Dodd

chrisd@reservoir.com

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.