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

I'm sorry I phrased my response wrong. And, the response is phrased
wrongly. It does not start off talking about the language as I
originally intended. Trying to be terse, which is always a problem
for me, I put the words rule and grammar at the start of the post,
even though I read your question and was intending to reply about the
*language*.


I know you were asking about languages and not grammars, and I thought
I explained why there was *no LL(k) grammar* (and thus an LL(k+1)
language) had specifically to do with that rule. That it is that rule
which poses the rewriting problem that causes the grammar to be
LL(k+1) and that no grammar can escape the LL(k+1)-ness of that rule,
which is what makes the language LL(k+1).


Said another way, I meant to say that the reason the language is
LL(k+1) is there is no way to rewrite that rule even as a set of
different rules such that you have an LL(k) grammar.


As you know, a language is LL(k) iff there is a grammar that is LL(k),
and there can be no grammar that is LL(k) that has that rule in it
within a conflicting context (where there is some other rule (or
rules) that may also swallow the A's that begin the rule) and that has
specially do to the nature of that rule and the k A's at the
beginning. And, just to be clear, you cannot eliminate that rule (nor
substitue any equivalent rules that need less than k+1 tokens of left
context) and have the same language. So, since that rule requires k+1
tokens of left context, any grammar (with the rule or any equivalent
rules) must be LL(k+1). Thus, the language must be LL(k+1).


I didn't mean to antagonize you by implying you were cheating, and
tried to provide you the answer you needed assuming that you were *not
cheating*. However, your question is very close to questions that get
asked in automata classes, which tend to get run in the spring
semester. I'm also sorry if I trivialized your question--if it truly
was trivial I wouldn't have bothered answering.


It's just that the answer *seems* trivial once you understand it (or
at least the answer can be phrased so that it seems trivial). While
languages are not grammars and grammars are not the consituent rules
that make up the grammar, it is in the rules themselves that the
properties of languages arise. Thus, to understand a language, you
can translate that expression to an understanding of the individual
rules of a specific grammar that defines that language. So, I
apologize if the way I answered the question didn't answer your
question precisely. I think the answer is there (or here).


If you want to explore the ramificiations of what I am saying, try
rewriting the grammar to another one where the resulting grammar is
LL(k). Use whatever tricks you like, left factoring, recursion
removal, algebraic substitutions. If you preserve the actual language
that the grammar describes, your grammar will be LL(k+1). And, the
reason why, has to do with that one rule and how it interacts with its
conflicting context.


Now, trying to give your question the dignity that it deserves. If
the LL(k+1) rule is not used in a "k" conflicting context, that is not
all the tokens at the start of the rule are necessary to prune away
any alternate interpretations, then the grammar may be LL(k), even
though looking at that one rule might imply that it is not. However,
the rule in question was used in a k conflicting context, so the
language is LL(k+1). Ask yourself, what is the k conflicting context
and what other sentence (fragments) might be matched by the sequences
of k A's?


I tried to explain how to get at that by reversing the grammar. In
particular, the reverse of the grammar has left-recursion and is thus
not an LL grammar, but the *language* that the grammar describes is
another matter. Is the language LL(k), and if so for what k? That
is, once you've removed the left-recursion from the grammar, can you
come up with an LL(k) grammar. When you understand the answer to
that, you will understand how my first answer addressed your question.
I will give you a hint, by inspection I know there is an LL(k) grammar
for the reverse of the language and know what k is appropriate for
that grammar.


Perhaps this is more helpful....
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
19 Bronte Way #33M voice : (508) 435-5016
Marlboro, MA 01752 USA fax : (508) 251-2347 (24 hours)

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