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: Chris Dodd <cdodd@acm.org>
Newsgroups: comp.compilers
Subject: Re: LR(1) Parsing : Error Handling & Recovery
Date: Sat, 26 Jul 2014 21:16:19 +0000 (UTC)
Organization: A noiseless patient Spider
Lines: 20
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <14-07-062@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> <14-07-060@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: miucha.iecc.com 1406414806 3054 2001:470:1f07:1126:0:676f:7373:6970 (26 Jul 2014 22:46:46 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Sat, 26 Jul 2014 22:46:46 +0000 (UTC)
Keywords: LL(1), parse
Posted-Date: 26 Jul 2014 18:46:46 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:1352

George Neuner <gneuner2@comcast.net> wrote
> 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.

This is simply not true.  A counter-example from Kurki-Suonio
<ftp://ftp.math.utah.edu/pub/tex/bib/idx/bit/9/3/225-238.html>
<http://www.springerlink.com/openurl.asp?genre=article&issn=0006-
3835&volume=9&issue=3&spage=225>
is:

    S ::= aSA | \epsilon
    A ::= aabS | c

This grammar (and the language) is LL(2), but there does not exist an
equivalent LL(1) grammar.  Here k=2 (fixed) and T = {a, b, c} (also fixed)

Chris Dodd
cdodd@acm.org