Re: Parsing techniques

Terence Parr <>
9 Dec 1996 00:09:41 -0500

          From comp.compilers

Related articles
[5 earlier articles]
Re: Parsing techniques (1996-12-01)
Re: Parsing techniques (1996-12-01)
Re: Parsing techniques (1996-12-01)
Re: Parsing techniques (1996-12-03)
Re: Parsing techniques (Ron House) (1996-12-07)
Re: Parsing techniques (1996-12-09)
Re: Parsing techniques (Terence Parr) (1996-12-09)
Re: Parsing techniques (Terence Parr) (1996-12-09)
Re: Parsing techniques (1996-12-15)
| List of all articles for this month |

From: Terence Parr <>
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:
> (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

Best regards,


Post a followup to this message

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