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,


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

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