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

## klyjikoo <klyjikoo@gmail.com>

Sat, 6 Feb 2010 19:12:54 +0330

*From comp.compilers*

| List of all articles for this month |

**From: ** | klyjikoo <klyjikoo@gmail.com> |

**Newsgroups: ** | comp.compilers |

**Date: ** | Sat, 6 Feb 2010 19:12:54 +0330 |

**Organization: ** | Compilers Central |

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

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

**Posted-Date: ** | 10 Feb 2010 01:17:33 EST |

fortunatus wrote:

*> So that language could be said to be LL(1), in that only an LL(1)*

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.