Re: LR-regular parsers for dummies ?

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

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