Re: An example LL(K) language that is not LL(K-1) ?

On 2010-02-06, SLK Mail <slkpg@cox.net> wrote:
> S -> a A a
> S -> b A b a
> A -> b
> A ->
>
> The example grammar I gave is the classic example from the literature
> of a grammar that is LL(2), but not strong LL(2). Since it is not
> strong LL(2), it clearly is not LL(1).
>
> Your grammar is in fact strong LL(3):


Grammars aren't LL anything; languages are.


Sometimes it is said that a grammar fails to be LL(1), even though the
language it generates is actually LL(1).


This is just a very inaccurate way of saying that that a particular
parser construction method fails to generate a table without conflicts
for that grammar.


That parser construction method works with grammars which meet certain
restrictions; those restrictions also imply that the language generated
by a grammar is an LL(1) language. Thus this construction method is
associated with LL(1) languages. But it does not handle LL(1) languages
through all possible grammars by which they may be manifested; only
through grammars written in the restricted form.


> S: aa | aba | bba | bbba;
>
> If you think it is LL(1), provide the parse table.


The LL(1) parser construction method does not handle this
LL(1) language by means of the above grammar; we must find
another grammar.


> If you think it is a language rather than a grammar, provide an LL(1)
> grammar that recognizes it.


The language is eye-gougingly regular. There is no regular
language that also isn't LL(1).


    S: aa | aba | bba | bbba


can be described by the regular expression [ab]b?ba, and can
be transformed into a grammar like this:


    S: a X | b X /* [ab]... */
    X: Y | b Y /* b?... */
    Y: ba /* ba */


Each nonterminal corresponds to a group of regular expression
derivatives. X is the derivative of the expression after consuming
an "a" or "b". Y is the derivative after consuming an optional "b".

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