Re: LR(k) parsers

"Terence Parr" <>
Thu, 30 Sep 1993 19:00:57 GMT

          From comp.compilers

Related articles
LR(k) parsers (1993-09-21)
Re: LR(k) parsers (Terence Parr) (1993-09-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: "Terence Parr" <>
Keywords: parse, LR(1)
Organization: Compilers Central
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.

Terence Parr
U of MN

Post a followup to this message

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