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

fortunatus wrote:
> So that language could be said to be LL(1), in that only an LL(1)
> is required to generate it. One would not say that the
> language is LL(2), even though it is possible to write an LL(2)
> grammar to generate it.
>
>
> As Hans has suggested, a truly LL(2) language would have an LL(2)
> grammer that could not be reduced to an LL(1) grammar.


Yes , as the topic shows...I am searching for an example LL(k)
labguage that is not LL(K-1)...


SLK Mail wrote:
>The following is the reference for the original paper on LL(k). It
>should have a proof of the superset relationship of k to k-1 for the
>LL languages


Unfortunately now i can't access this paper....but i would try to read it....




>S -> a A a
>S -> b A b a
>A -> b
>A ->


>Can you convert this to LL(1)?


Yes, I can...this grammar generates a regular language ....such as
the before example...


S -> a X
S -> b b X
X -> a
X -> b a




Chris Wrote:
>Although, I'm not an LL-language expert, I believe the trick to LL(k)
>languages that aren't LL(k-1) is to have a (center) recursive rule
>that needs k tokens to disambiguate.


I think your example grammar is an LL(2) grammar,and after left
factoring of production that have B on left ...we can obtain an LL(1)
grammar.
but As you have suggested , there is this grammar that I think its
language is not an LL(k) for every k


S := A
S := B
A := a A b
A := c
B := a A b b
B := d


This grammar shows that there are language that have LR(1) grammar
,but have not any LL(K) grammar for every k...

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