Re: What is the trick of languages being LL(k+1), but not LL(k)?

cgweav@aol.com (Clayton Weaver)
16 Jan 2004 22:56:51 -0500

          From comp.compilers

Related articles
What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-07)
Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-12)
Re: What is the trick of languages being LL(k+1), but not LL(k)? cfc@shell01.TheWorld.com (Chris F Clark) (2004-01-12)
Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-16)
Re: What is the trick of languages being LL(k+1), but not LL(k)? cgweav@aol.com (2004-01-16)
Re: What is the trick of languages being LL(k+1), but not LL(k)? cfc@world.std.com (Chris F Clark) (2004-01-17)
Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-22)
Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-22)
Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-02-01)
Re: What is the trick of languages being LL(k+1), but not LL(k)? cgweav@aol.com (2004-02-04)
Re: What is the trick of languages being LL(k+1), but not LL(k)? cgweav@aol.com (2004-04-15)
| List of all articles for this month |

From: cgweav@aol.com (Clayton Weaver)
Newsgroups: comp.compilers
Date: 16 Jan 2004 22:56:51 -0500
Organization: AOL http://www.aol.com
References: 04-01-062
Keywords: parse, LL(1), theory
Posted-Date: 16 Jan 2004 22:56:51 EST

>My question was, why is the *language* described by this grammar
>LL(k+1), but not LL(k):
>
>s : A s a | ;
>
>a : A^k B s | C ;
>
>It is obvious this grammar is LL(k+1), but why is the *language*?


Do you mean "the Hopkins reason"?
(<http://www.uwm.edu/~whopkins/cs/CompFAQ.txt>


As Hopkins points out, the reason why a language can be described as
belonging to any specific category (like "ll(k)" for some value of k)
within a formal taxonomy of languages is really algebraic, and
"grammar type that can parse it without conflicts" is only one of
several possible taxonomies for categorizing formal languages, but one
might sum it up informally as "the language is ll(k+1) if it cannot be
described by an ll(k) grammar without parse conflicts but can be
described by an ll(k+1) grammar without parse conflicts".


Clark already provided you more-or-less with the proof in the case of
your specific example.


Regards,


Clayton Weaver
<mailto: cgweav@aol.com>


Post a followup to this message

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