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

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.


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: 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.