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

## Chris F Clark <cfc@shell01.TheWorld.com>

Fri, 05 Feb 2010 18:12:01 -0500

*From comp.compilers*

| List of all articles for this month |

**From: ** | Chris F Clark <cfc@shell01.TheWorld.com> |

**Newsgroups: ** | comp.compilers |

**Date: ** | Fri, 05 Feb 2010 18:12:01 -0500 |

**Organization: ** | The World Public Access UNIX, Brookline, MA |

**References: ** | 10-02-020 |

**Keywords: ** | LL(1) |

**Posted-Date: ** | 06 Feb 2010 09:56:12 EST |

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

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.