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

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

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