Re: LR(k) parsers

"Terence Parr" <parrt@s1.arc.umn.edu>
Thu, 30 Sep 1993 19:00:57 GMT

          From comp.compilers
Related articles
LR(k) parsers nandu@cs.clemson.edu (1993-09-21)
Re: LR(k) parsers parrt@s1.arc.umn.edu (Terence Parr) (1993-09-30)
| List of all articles for this month |
Newsgroups: comp.compilers
From: "Terence Parr" <parrt@s1.arc.umn.edu>
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
to pccts@ecn.purdue.edu).


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