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

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

Wed, 03 Feb 2010 01:15:30 -0500

*From comp.compilers*

| List of all articles for this month |

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

**Newsgroups: ** | comp.compilers |

**Date: ** | Wed, 03 Feb 2010 01:15:30 -0500 |

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

**References: ** | 10-02-009 10-02-015 |

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

**Posted-Date: ** | 05 Feb 2010 17:31:51 EST |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.