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

SLK Mail <slkpg@cox.net> writes:


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


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.