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

> There may be errors in my reasoning, but I guess I am pretty close now.


Yes, you have the fundamental understanding and have even worked
through the details for the reverse case. And, the intent of the
exercise was exactly to show you that the extra A's as the "end of the
rule", and thus not in the conflicting context, don't affect the
grammar's class (and thus don't effect the language's class). That's
really about all there is to LL grammars, you can look at the *starts*
of the rules that can appear together at some point during the parse
and count the number of tokens it takes to distinguish them, and then
you know the k for the grammar.


To figure out the k for the language, you have to determine if there
is any way to rearrange the rules to eliminate those conflicts. If
the conflicting rules are part of the same recursive cycle (in your
sample grammar s->a->s->a... are a recursive cycle, since you can
derive an a from an s (technically you can derive a string which
contains the non-terminal a, not a string which is exactly a), and
from that derive another s, etc.), the rearrangement is probably not
possible. If the conflicting rules are part of separate paths, then
the necessary rearrangement to lower the k of the grammar can probably
be done. Thus, the following language is LL(1) despite the grammar
itself being LL(k+1). I will leave it as the obligatory "exercise for
the reader" to find the LL(1) grammar.


s: a | b:
a: A^k A;
b: A^k B;


Here is a slightly more subtle variant that you should consider. What
k is this language? What does the grammar with the smallest k for the
language look like?


s: a | b:
a: A^k a | A;
b: A^k b | B;


> Let me ask one more question though. What is this C in rule a for?


The C in the rule is to end the recursion. However, I believe it is
unnecessary, as the empty alternative of "s" can also terminate the
recursion. A basic rule of thumb is that in a recursive cycle of
rules (e.g. s->a->s->a...) there must be at least one rule in the
cycle which has a non-recursive alternative. Otherwise, the grammar
doesn't describe any finite strings and there aren't any legal finite
inputs to the grammar. Your grammar has two non-recursive
alternatives s->empty and a->C, so it is "doubly safe" ;-). As a
result, the a->C alternative is not neceesary for the grammar to be
correct, nor does it effect what language class the grammar is in.


Hope this helps,
-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.