Re: An example LL(K) language that is not LL(K-1) ?

klyjikoo <klyjikoo@gmail.com> writes:


> Chris Wrote:
>>Although, I'm not an LL-language expert, I believe the trick to LL(k)
>>languages that aren't LL(k-1) is to have a (center) recursive rule
>>that needs k tokens to disambiguate.
>
> I think your example grammar is an LL(2) grammar,and after left
> factoring of production that have B on left ...we can obtain an LL(1)
> grammar.


Here is the original grammar:


S := A
A := B C
B := b A d // 1 form of recursion
B := b a A a d // other form of recursion
B := a c
C := A
C := epsilon


There is only 1 production with B on the left. There is nothing to
left factor on that. Perhaps, you mean to left factor the two B rules
that start with b.


S := A
A := B C
B := b D
B := a c
C := A
C := epsilon
D := A d // 1 form of recursion
D := a A a d // other form of recursion


Or perhaps, you want to substitute B in the one place it occurs:


S := A
A := b D C
A := a c C
C := A
C := epsilon
D := A d // 1 form of recursion
D := a A a d // other form of recursion


Or this version (without D):


S := A
A := b A d C
A := b a A a d C
A := a c C
C := A
C := epsilon


which left factors to this:


S := A
A := b E
A := a c C
C := A
C := epsilon
E := A d C
E := a A a d C


In this case, it is the two E rules that have overlapping first sets.
You want to substitute A in the first one to see if it helps?


S := A
A := b E
A := a c C
C := A
C := epsilon
E := b E d C
E := a c C d C
E := a A a d C


Ok, we can left factor the "a" off the last 2 E rules, as in:


S := A
A := b E
A := a c C
C := A
C := epsilon
E := b E d C
E := a F
F := c C d C
F := A a d C


And, presuming no mechanical errors on my part, you are correct. This
is an LL(1) grammar, and thus the language is LL(1). which shows, my
original disclaimer that I am not an LL expert. Picking up my
friendly parsing theory textbook off my desk, it turns out that the
condition requires the the parens be the same token repeated i.e. the
following grammar should work:


S := A
A := B C
B := b A d // 1 form of recursion
B := b b A a d // other form of recursion, note the slight difference
B := a c
C := A
C := epsilon


which becomes:


S := A
A := b A d C
A := b b A a d C
A := a c C
C := A
C := epsilon


then:


S := A
A := b E
A := a c C
C := A
C := epsilon
E := A d C
E := b A a d C


then:


S := A
A := b E
A := a c C
C := A
C := epsilon
E := b E d C
E := a c C d C
E := b A a d C


then:


S := A
A := b E
A := a c C
C := A
C := epsilon
E := b F
E := a c C d C
F := E d C // first={a,b}
F := A a d C // first={a,b}


then, substituting E and A into F so we can left factor


S := A
A := b E
A := a c C
C := A
C := epsilon
E := b F
E := a c C d C
F := b F d C
F := a c C d C d C
F := b E a d C
F := a c C a d C


left factoring:


S := A
A := b E
A := a c C
C := A
C := epsilon
E := b F
E := a c C d C
F := b G
F := a c C H
G := F d C // first = {a, b}
G := E a d C // first = {a, b}
H := d C d C
H := a d C


Ooops, now we've moved the problem to G. We can keep expanding and
left factoring, but the process will continue yielding grammars the
have this same issue. Thus, the language is not LL(1).


> but As you have suggested , there is this grammar that I think its
> language is not an LL(k) for every k
>
> S := A
> S := B
> A := a A b
> A := c
> B := a A b b
> B := d
>
> This grammar shows that there are language that have LR(1) grammar
> ,but have not any LL(K) grammar for every k...


This grammar shows the difference between LR(k) and LL(k) grammars.
In an LR(k) grammar, one can match multiple closing parens (the b
tokens in your case) to the same open paren (the a token in your
case), which in LL(k) grammars, each balanced paren rule must have a
unique prefix that is at most k tokens long.


Actually, I htink you have made a slight typo, and want the B rule to
recurse on B not A. As given, I think it can be rewritten to be LL(1).
First, substitute A and B in S.


S := a A b
S := c
S := a A b b
S := d
A := a A b
A := c


Now, left factor S (a A b is the common prefix to factor off):


S := a A b C
S := c
S := d
A := a A b
A := c
C := b
C := epsilon


This, grammar is LL(1). However, I'm certain the same process would
not have worked were B self-recursive, ala:


S := A
S := B
A := a A b
A := c
B := a B b b
B := d


In this grammar, you have to left factor off an indefinite string of a
tokens to disambiguate the A and B non-terminals.


Hope this helps, (and apologies for my earlier error)
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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