Re: LR(1) Parsing : Error Handling & Recovery

Chris Dodd <cdodd@acm.org>
Sat, 26 Jul 2014 21:16:19 +0000 (UTC)

          From comp.compilers

Related articles
[18 earlier articles]
Re: LR(1) Parsing : Error Handling & Recovery cdodd@acm.org (Chris Dodd) (2014-07-21)
Re: LR(1) Parsing : Error Handling & Recovery DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2014-07-21)
Re: LR(1) Parsing : Error Handling & Recovery drikosev@otenet.gr (Evangelos Drikos) (2014-07-21)
Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-07-21)
Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-21)
Re: LR(1) Parsing : Error Handling & Recovery gneuner2@comcast.net (George Neuner) (2014-07-25)
Re: LR(1) Parsing : Error Handling & Recovery cdodd@acm.org (Chris Dodd) (2014-07-26)
Re: LR(1) Parsing : Error Handling & Recovery DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2014-07-28)
Re: LR(1) Parsing : Error Handling & Recovery cdodd@acm.org (Chris Dodd) (2014-07-29)
Re: LR(1) Parsing : Error Handling & Recovery monnier@iro.umontreal.ca (Stefan Monnier) (2014-08-06)
Re: LR(1) Parsing : Error Handling & Recovery drikosev@otenet.gr (Evangelos Drikos) (2014-08-26)
Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-08-29)
Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-09-03)
| List of all articles for this month |

From: Chris Dodd <cdodd@acm.org>
Newsgroups: comp.compilers
Date: Sat, 26 Jul 2014 21:16:19 +0000 (UTC)
Organization: A noiseless patient Spider
References: 14-07-023 14-07-024 14-07-030 14-07-031 14-07-041 14-07-046 14-07-060
Keywords: LL(1), parse
Posted-Date: 26 Jul 2014 18:46:46 EDT

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



Post a followup to this message

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