Re: Parsing techniques

Terence Parr <parrt@MageLang.com>
9 Dec 1996 00:09:41 -0500

          From comp.compilers

Related articles
[5 earlier articles]
Re: Parsing techniques jon@mauney.com (1996-12-01)
Re: Parsing techniques miano@worldnet.att.net (1996-12-01)
Re: Parsing techniques jlilley@empathy.com (1996-12-01)
Re: Parsing techniques icedancer@ibm.net (1996-12-03)
Re: Parsing techniques house@usq.edu.au (Ron House) (1996-12-07)
Re: Parsing techniques grosch@cocolab.sub.com (1996-12-09)
Re: Parsing techniques parrt@MageLang.com (Terence Parr) (1996-12-09)
Re: Parsing techniques parrt@MageLang.com (Terence Parr) (1996-12-09)
Re: Parsing techniques sjmeyer@crl.com (1996-12-15)
| List of all articles for this month |

From: Terence Parr <parrt@MageLang.com>
Newsgroups: comp.compilers
Date: 9 Dec 1996 00:09:41 -0500
Organization: MageLang Institute
References: 96-11-15796-11-157 96-12-024 96-12-031
Keywords: parse, LR(1)

Ken Walter wrote:
> jlilley@empathy.com (John Lilley) writes:
> > Does anyone else have experience regarding LALR(k>1)? I'd like to
> > know for sure...


I believe Josef Grosch (SP?) and his COCO parser generator does
some flavor of LR with k>1 (he decoded my thesis, which outlined k>1
lookahead for all LR and LL derivatives).


> I had a LR(k) parser that only did "k" for the "states" that were not
> LR(1), that where not LALR(1), that were not LR(0). Only needed this
> at a few point in my Algol68 parser, so no explosion.


Yes, one must modulate the lookahead to get a decent parser size.
Frank DeRemer (inventor of SLR, LALR) said as much in his early papers
on this (late 60's, early 70's).


> Actually it didn't look at "strings" of length k, but at the kth
> token. I found that usually the strings were identical before that.


This isn't LR(k)--it's what I call "Linear Approximate LR(k)" because
you have reduced the O(|T|^k) of each lookahead set to O(|T| x k)
where |T| is the size of the token set (vocabulary). Full k>1
lookahead must consider sequence information, hence, the
exponentiality. Linear approximate lookahead considers lookahead at
particular depths rather than sequences.


You can do full lookahead usually by using a trick. When a decision
is not linear approximate (i.e., it requires full LL or LR k>1
lookahead), the decision is usually MOSTLY linear approximate. Hence,
a hybrid decision consisting of the linear approximate decision plus a
test for the k-tuples that render the decision non-linear approximate
yields a full LL(k)/LR(k) decision at nearly linear cost for most
grammars. This is extremely important if you want to have real k>1
lookahead.


Best regards,
Terence


--


Post a followup to this message

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