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

klyjikoo <klyjikoo@gmail.com> writes:


> Chris F Clark <cfc@shell01.TheWorld.com> wrote:
>>the following grammar should work:
>>
>>
>> S := A
>> A := B C
>> B := b A d // 1 form of recursion
>> B := b b A a d // other form of recursion, note the slight difference
>> B := a c
>> C := A
>> C := epsilon
>
>
> Your example also shows the difference between LR(k) and LL(k) grammars,
> similar to my example...


Yes, you are correct, the above language is not LL(2) as I thought,
because both forms of recursion can pile up an indefinitely long
string of b characters before the central "a c" string, the language
cannot be parsed with an LL(k) grammar, becuase you cannot tell
strictly from the prefix what kind of recursion you have.


Obviously, the construction of a language that is precisely LL(2) is
more subtle than I thought. I still know you need at least one
central recursion in the language (otherwise, if the language has only
left recursion or right recursion, it is regular), but how you get it
so that two tokens are required to decipher the recursion rather than
just one (without requiring unbounded numbers of tokens), is something
I clearly don't have an intuition for, and I don't have a parsing text
handy here.


Sorry,
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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