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

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

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