Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From: George Neuner <gneuner2@comcast.net>
Newsgroups: comp.compilers
Subject: Re: LR(1) Parsing : Error Handling & Recovery
Date: Fri, 25 Jul 2014 21:58:49 -0400
Organization: A noiseless patient Spider
Lines: 34
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <14-07-060@comp.compilers>
References: <14-07-023@comp.compilers> <14-07-024@comp.compilers> <14-07-030@comp.compilers> <14-07-031@comp.compilers> <14-07-041@comp.compilers> <14-07-046@comp.compilers>
NNTP-Posting-Host: news.iecc.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 8bit
X-Trace: miucha.iecc.com 1406342328 34820 2001:470:1f07:1126:0:676f:7373:6970 (26 Jul 2014 02:38:48 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Sat, 26 Jul 2014 02:38:48 +0000 (UTC)
Keywords: parse, theory
Posted-Date: 25 Jul 2014 22:38:48 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:1350

On Mon, 21 Jul 2014 06:07:55 +0000 (UTC), Chris Dodd <cdodd@acm.org>
wrote:

>George Neuner <gneuner2@comcast.net> wrote in news:14-07-041@comp.compilers:
>> LL(k) always can be refactored to single token lookahead, but it
>> causes an explosion of grammar states.  E.g., given a single LL(3)
>> rule, an equivalent set of LL(1) rules must match every valid
>> combination of tokens at +1, +2 and +3.
>
>Not true -- LL(k+1) languages are a strict superset of LL(k) languages, so
>there exist LL(k) grammars that cannot be refactored to a smaller k.

Yes and no.

For every LL(k) grammar where both k and the set T of tokens is fixed,
there is an equivalent LL(1) grammar.  In the worst case, the
equivalent LL(1) grammar will have k**T rules.

Only where k or T is unbounded, so that the power set of {n:1<=n<=k}
lookahead tokens for some rule is not enumerable, can you not derive
an equivalent in LL(1).

The problem is that an LL({n:1<n<=k}) rule explodes multiplicatively
into an n-level tree of LL(1) rules, with each branch at each level
m<=n having to cover follow(m).

Meaning that it is effectively unworkable for any but small k.

Fortunately, for any reasonable LL(k>1) grammar, k will be bounded and
small, and the grammar will contain just a handful of rules requiring
the maximum k lookahead.  Most rules will be LL({n:1<=n<k}) where n is
very small.

George