|LR(k) parsers email@example.com (1993-09-21)|
|Re: LR(k) parsers firstname.lastname@example.org (Terence Parr) (1993-09-30)|
|From:||"Terence Parr" <email@example.com>|
|Date:||Thu, 30 Sep 1993 19:00:57 GMT|
Nandakumar Sankaran writes:
> I am looking for LR(k) parsers that are publicly available. I have
> rummaged thru the compilers list and have been unable to find one.
This is because computing k-token lookahead is an exponential problem in
theory. As usual, much can be done in practice, but requires what can be
termed "polynomial approximations to exponential k-token lookahead" to get
anything beyond 1-token lookahead. My Ph.D. thesis describes how this can
be done (paper coming soon to a theatre near you). Also, ANTLR applies
this theory to build LL(k) for k>1 if you want to take a look (send mail
> [Isn't the usual approach to mangle the grammar until it's LR(1)? -John]
Unfortunately, yes, this is the case. However, my techniques for
approximating k-token lookahead are equally valid for LL and LR based
parsing; it's just that I don't use LR parsers and don't want to code up a
LR(k)-based parser generator.
U of MN
Return to the
Search the comp.compilers archives again.