Re: Parsing techniques

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


--

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