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

## Kaz Kylheku <kkylheku@gmail.com>

Wed, 10 Feb 2010 17:08:38 +0000 (UTC)

*From comp.compilers*

| List of all articles for this month |

**From: ** | Kaz Kylheku <kkylheku@gmail.com> |

**Newsgroups: ** | comp.compilers |

**Date: ** | Wed, 10 Feb 2010 17:08:38 +0000 (UTC) |

**Organization: ** | A noiseless patient Spider |

**References: ** | 10-02-009 10-02-015 10-02-018 10-02-030 |

**Keywords: ** | LL(1) |

**Posted-Date: ** | 10 Feb 2010 12:21:55 EST |

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".

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.