Re: Recursive descent parsing is better than LL(1)

Barton Christopher Massey <bart@cs.uoregon.edu> writes:
>I would like to prove or disprove the following conjectures:
> LL(1) Transformability: There exists an algorithm which, given any grammar G
> which is unambiguous and describes an LL(1) language L(G), produces an LL(1)
> grammar G' for the language L(G).
> LL(1) Decidability: There exists an algorithm which, given any grammar G
> which is unambiguous and describes a language L(G), decides whether L(G) is
> an LL(1) language.
>it seems most likely to me that LL1T is true, but I'm skeptical about LL1D.


Bill Purvis <W.Purvis@daresbury.ac.uk> writes:
>... SID... accepts a fairly arbitrary BNF description... produce an LL(1)
>grammar (assuming that the language is LL(1). - the first conjecture.
>...I suspect that in practical terms it probably covers the second conjecture.


jan@klikspaan.si.hhs.nl writes:
>I present a simple contra-example:
> S -> A | B
> A -> `x' A `y' | `a'
> B -> `x' B `z' | `b'
>...`SID may also report failure because
>its attempt to transform the grammar causes it to loop.'


tchannon@black.demon.co.uk (Tim Channon) writes:
>Is this a valid LL(1) solution? S = 'x' {'x'|'a'|'b'} ('y'|'z') | 'a' | 'b'.


Jan's example causes SID problems, so SID may establish LL1T but can't
establish LL1D. I believe this is because his example is not LL(1), but
no-one has said so explicitly so far and I can't find the example in the
Dragon book - is it a well-known example?


To shorten the grammars/languages, I am using the following notation:
x^n means x repeated n times, [ab] or a|b means a or b
Thus Jan's original language is:
x^n a y^n | x^n b z^n for n>=0
Tim's version is:
x [xab]^n [yz] | a | b
which is not the same at all. Maybe he meant:
x^n [ab] [yz]^m | a | b for n,m>=1
i.e. x^n [ab] [yz]^m for n,m>=0
which is closer but still not right.


A slightly simpler example, with (I think) the same characteristics as the
original is:
x^n y^n | x^n z^n i.e. x^n ( y^n | z^n ) for n>=0
This and Jan's original are LR(1), but I believe that they are not LL(n) for
any finite n, as we have to negotiate an indefinitely long string of x-s
before we can chose whether to accept y-s or z-s, but we also have to have
been counting the x-s (i.e. selecting/stacking the "correct" non-terminal
symbol) to be able to accept the right number of y-s or z-s. By contrast:
x^n [yz]^n
and:
x^n (y^m | z^m).
are both LL(1).


--

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