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

Chris F Clark <cfc@shell01.TheWorld.com>
Sat, 13 Feb 2010 21:33:20 -0500

          From comp.compilers

Related articles
[9 earlier articles]
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-06)
Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-06)
Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-06)
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-10)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-10)
Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-14)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-13)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Sat, 13 Feb 2010 21:33:20 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 10-02-009 10-02-015 10-02-026 10-02-050 10-02-058
Keywords: LL(1)
Posted-Date: 13 Feb 2010 21:57:58 EST

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



Post a followup to this message

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