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

>(<http://www.uwm.edu/~whopkins/cs/CompFAQ.txt>
>
>OK, I really read (and understood most of) this article - and I really
>found nothing related to my question nor anything new to me. I *must*
>have missed the point. I have not even found anything related to what
>you called "the Hopkins reason"! Could you please clarify? Have you
>given the wrong link? Am I simply an idiot?
>
>Thanks in advance and cheers :)


Recap:


You asked why a language was ll(k+1) rather than ll(k), and gave an
example grammar for a language.


Chris Clark explained where ambiguity would result when trying to
parse that example grammar with an ll(k) parser, and explained how an
ll(k+1) parser could resolve it without conflict.


You explained that you understood why the example *grammar* was
ll(k+1), but not why the *language* was ll(k+1).


I pointed you at Hopkins, who explains in the very beginning of his
document that:


"The underlying theme of this article is that formal languages,
automata, and grammars are all methods for algebraically describing
objects which reside in one of a hierarchy of (not so well-known)
algebraic systems that range from DIOIDS to QUANTALES."


Without yanking the whole chain of symbolic inference in that document
into this post, it is still clear that the same algebraic reasoning
from which one could infer that your grammar will have conflicts if
you attempt to parse it with an ll(k) parser (but not with an ll(k+1)
parser) also holds for the language whose constraints are expressed by
that grammar.


At any rate, here is another take on the field of Rewriting Systems
(which in the Wolfram resource hierarchy is treated as a branch of
discrete mathematics):


<http://library.wolfram.com/infocenter/MathSource/5109/>


The main point is, if you understand why the grammar is ll(k+1), then
you also understand why the language is ll(k+1). To assert that a
language whose constraints can be expressed by an "ll(k+1)" grammar
but not by an "ll(k)" grammar is thus an "ll(k+1)" language is merely
categorizing the language by grammar type. Whatever combinatorial
invariants are implied by the grammar hold for the set of valid
strings that is the language as well.


In sum, he question is like asking why a 6-centimer long stick is "a
6-centimeter stick". It's a 6-centimer stick because someone measured
it and that's how long it was. It could also be a "sun-bleached dry
stick" or "a stick of driftwood", but those alternate categorizations
would not necessarily be useful if you were trying to decide if a
drawer was wide enough to put it in sideways.


If you what want to know is how you make a ruler for grammars, feel
free to explore the discipline of discrete mathematics with particular
attention to rewriting systems.


HTH,
Clayton Weaver

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