An example LL(K) language that is not LL(K-1) ?
klyjikoo
I think any LL(K) grammar without semantic actions can be transformed into an
LL(1) grammar...
But i found in resourses that LL(K) is stronger than LL(K-1) ....
I search a lot for an example that can show this...but not found any
and i am currently confusing about this issue.
sue kelly
Hans Aberg
The book by Waite and Goos, "Compiler Construction", sec 5.3, p. 124,
gives an example of an LL(3) grammar that isn't LL(2). They say LL(k)
grammars were introduced by P. M. Lewis and R. E. Stearns, "Property
Grammars and Table Machines", Information and Control 14(6), 524-549
(1969). So if they do not give example, perhaps someone citing them.
Hans
Chariton Karamitas
I don't think your assumption that any LL(k) can be transformed into
an LL(k-1) is correct. The 'k' in LL(k) is assumed to be the supremum
of lookahead symbols that you need in order to parse your input. So,
suppose you have an LL(2) grammar, then you cannot convert it to an
LL(1) since the LL(1) equivalent won't have disjoint FIRST/FOLLOW sets!
I am not yet very experienced when it comes to compilers, so, if my
answer is wrong correct me please! :-)
Regards
./ck
--
Chariton Karamitas
Undergraduate Student
Electrical Engineering and Computer Engineering Department
Fuculty of Engineering
Aristotle University of Thessaloniki, Greece
klyjikoo
> I don't think your assumption that any LL(k) can be transformed into
> an LL(k-1) is correct. The 'k' in LL(k) is assumed to be the supremum
> of lookahead symbols that you need in order to parse your input. So,
> suppose you have an LL(2) grammar, then you cannot convert it to an
> LL(1) since the LL(1) equivalent won't have disjoint FIRST/FOLLOW sets!
> I am not yet very experienced when it comes to compilers, so, if my
> answer is wrong correct me please! :-)n
Thanks to Hans, Consider this example :
1) Z := X
2) X := Y
3) X := bYa
4) Y := c
5) Y := ca
> The book by Waite and Goos, "Compiler Construction", sec 5.3, p. 124,
> gives an example of an LL(3) grammar that isn't LL(2)
After substitution of production 4 and 5 in production 2 and 3 ...the
following grammar can obtained:
Z := X
X := c
X := c a
X := b c a
X := b c a a
Now after left factoring....the following grammar can obtained...that
is an LL(1) grammar:
Z := X
X := c A
A := eps
A := a
X := b c a B
B := eps
B := a
Chris F Clark
languages that aren't LL(k-1) is to have a (center) recursive rule
that needs k tokens to disambiguate.
Something like:
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
I think you'll find this grammar is LL(3), although I was trying to
make an LL(2) language, and the language may be in fact LL(2).
The language is S: A+; A: b S d | b a S a d | a c; Where b and d are
the parenthesis of the language, but they have a 1 token and 2 token (
b a matching a d ) form. The use of "a c"+ as the center element of
the recursion keeps the forms ambiguous, since b a could be b a c d or
b a a c a d, and why I think this particular grammar is LL(3).
And, the reason the rule must be center recursive for the problem to
occur is that non-recursive (and left-recursive or right-recursive)
rules can be turned into regular expressions, which are all LL(1).
The point being that you need to have a situation where you need k
tokens (of leading symbols in a rule) to determine what to push onto
the stack for the grammar to be LL(k).
Hope this helps,
-Chris
******************************************************************************
Chris Clark email: christoph...@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
------------------------------------------------------------------------------
Kaz Kylheku
>
>> I don't think your assumption that any LL(k) can be transformed into
>> an LL(k-1) is correct. The 'k' in LL(k) is assumed to be the supremum
>> of lookahead symbols that you need in order to parse your input. So,
>> suppose you have an LL(2) grammar, then you cannot convert it to an
>> LL(1) since the LL(1) equivalent won't have disjoint FIRST/FOLLOW sets!
>
>> I am not yet very experienced when it comes to compilers, so, if my
>> answer is wrong correct me please! :-)n
>
> Thanks to Hans, Consider this example :
>
> 1) Z := X
> 2) X := Y
> 3) X := bYa
> 4) Y := c
> 5) Y := ca
This grammar generates only a finite set of strings. So it gives a
regular language, which can be described by the regular expression
(cca|bca|bcaa).
It would be astonishing if a regular language could not be described by
a LL(1) grammar.
:)
fortunatus
You have indeed offered an example of and LL(2) grammar that is
equivalent to an LL(1) grammar.
However both grammars (if the derivation is correct) accept the same
language.
So that language could be said to be LL(1), in that only an LL(1)
grammar is required to generate it. One would not say that the
language is LL(2), even though it is possible to write an LL(2)
grammar to generate it.
As Hans has suggested, a truly LL(2) language would have an LL(2)
grammer that could not be reduced to an LL(1) grammar.
(As an analogy: it is possible to write a CFG to generate a Regular
language. In that case the CFG could be converted to an RE. The CFG
just would not have any important recursions that produce anything
more complex than simple repitition.)
SLK Mail
should have a proof of the superset relationship of k to k-1 for the
LL languages.
Rosenkrantz, D.J. and R.E. Stearns (1970). "Properties of
Deterministic Top-Down Grammars," Inf. and Control, 17 (3), pp
226-256.
You may be thinking of the fact that LR(k) is reducible to LR(1). Not
so for LL because it cannot postpone parsing decisions, making it more
dependent on the lookahead than LR.
Example:
S -> a A a
S -> b A b a
A -> b
A ->
Can you convert this to LL(1)?
More info about LL(k) can be found in the FAQ and links on the
SLK Parser Generator site: http://members.cox.net/slkpg/
Chris F Clark
> Example:
>
> S -> a A a
> S -> b A b a
> A -> b
> A ->
>
> Can you convert this to LL(1)?
Yes, there is no recursion in this grammar, therefore the language is
trivially regular and thus trivally, LL(1).
The language is: S: aa | aba | bba | bbba;
Now, if you replaced all A's in the grammar with S's (or add the rule
A -> S), making it recursive. I'm not so quick to jump to such a
conclusion. The language wouldn't be left-factored in that case, so
there would be work to do generally.
Note, you only get a non-regular context free language when you
intersect a regular language (languages with fixed strings, and left,
and right recursion only) with a Dyck language (a language that
describes balanced parethesized expressions, i.e. uses what I call
center recursion).
Thus, any LL(2) language will have at least one rule that has central
recursion. Otherwise, if there is no recursion, or it is all left or
right recursion (either direct or indirect), the language will be
regular and thus LL(1).
klyjikoo
> So that language could be said to be LL(1), in that only an LL(1)
> language is LL(2), even though it is possible to write an LL(2)
> grammar to generate it.
>
>
> As Hans has suggested, a truly LL(2) language would have an LL(2)
> grammer that could not be reduced to an LL(1) grammar.
Yes , as the topic shows...I am searching for an example LL(k)
labguage that is not LL(K-1)...
SLK Mail wrote:
>The following is the reference for the original paper on LL(k). It
>should have a proof of the superset relationship of k to k-1 for the
>LL languages
Unfortunately now i can't access this paper....but i would try to read it....
>S -> a A a
>S -> b A b a
>A -> b
>A ->
>Can you convert this to LL(1)?
Yes, I can...this grammar generates a regular language ....such as
the before example...
S -> a X
S -> b b X
X -> a
X -> b a
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.
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...
SLK Mail
S -> b A b a
A -> b
A ->
The example grammar I gave is the classic example from the literature
of a grammar that is LL(2), but not strong LL(2). Since it is not
strong LL(2), it clearly is not LL(1).
Your grammar is in fact strong LL(3):
S: aa | aba | bba | bbba;
If you think it is LL(1), provide the parse table.
If you think it is a language rather than a grammar, provide an LL(1)
grammar that recognizes it.
Kaz Kylheku
> S -> a A a
> S -> b A b a
> A -> b
> A ->
>
> The example grammar I gave is the classic example from the literature
> of a grammar that is LL(2), but not strong LL(2). Since it is not
> strong LL(2), it clearly is not LL(1).
>
> Your grammar is in fact strong LL(3):
Grammars aren't LL anything; languages are.
Sometimes it is said that a grammar fails to be LL(1), even though the
language it generates is actually LL(1).
This is just a very inaccurate way of saying that that a particular
parser construction method fails to generate a table without conflicts
for that grammar.
That parser construction method works with grammars which meet certain
restrictions; those restrictions also imply that the language generated
by a grammar is an LL(1) language. Thus this construction method is
associated with LL(1) languages. But it does not handle LL(1) languages
through all possible grammars by which they may be manifested; only
through grammars written in the restricted form.
> S: aa | aba | bba | bbba;
>
> If you think it is LL(1), provide the parse table.
The LL(1) parser construction method does not handle this
LL(1) language by means of the above grammar; we must find
another grammar.
> If you think it is a language rather than a grammar, provide an LL(1)
> grammar that recognizes it.
The language is eye-gougingly regular. There is no regular
language that also isn't LL(1).
S: aa | aba | bba | bbba
can be described by the regular expression [ab]b?ba, and can
be transformed into a grammar like this:
S: a X | b X /* [ab]... */
X: Y | b Y /* b?... */
Y: ba /* ba */
Each nonterminal corresponds to a group of regular expression
derivatives. X is the derivative of the expression after consuming
an "a" or "b". Y is the derivative after consuming an optional "b".
Chris F Clark
> 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)
klyjikoo
> Actually, I htink you have made a slight typo, and want the B rule to
> recurse on B not A
Yes, I had a mistake... I want the B rule to recurse on B .
>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
Your example also shows the difference between LR(k) and LL(k) grammars,
similar to my example...
Chris F Clark
Yes, you are correct, the above language is not LL(2) as I thought,
because both forms of recursion can pile up an indefinitely long
string of b characters before the central "a c" string, the language
cannot be parsed with an LL(k) grammar, becuase you cannot tell
strictly from the prefix what kind of recursion you have.
Obviously, the construction of a language that is precisely LL(2) is
more subtle than I thought. I still know you need at least one
central recursion in the language (otherwise, if the language has only
left recursion or right recursion, it is regular), but how you get it
so that two tokens are required to decipher the recursion rather than
just one (without requiring unbounded numbers of tokens), is something
I clearly don't have an intuition for, and I don't have a parsing text
handy here.
Sorry,