# Re: What is the trick of languages being LL(k+1), but not LL(k)?

## cgweav@aol.com (Clayton Weaver)

16 Jan 2004 22:56:51 -0500

*From comp.compilers*

Related articles |

What is the trick of languages being LL(k+1), but not LL(k)? *oliver@zeigermann.de (Oliver Zeigermann)* (2004-01-07) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *oliver@zeigermann.de (Oliver Zeigermann)* (2004-01-12) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *cfc@shell01.TheWorld.com (Chris F Clark)* (2004-01-12) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *oliver@zeigermann.de (Oliver Zeigermann)* (2004-01-16) |

**Re: What is the trick of languages being LL(k+1), but not LL(k)? ***cgweav@aol.com* (2004-01-16) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *cfc@world.std.com (Chris F Clark)* (2004-01-17) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *oliver@zeigermann.de (Oliver Zeigermann)* (2004-01-22) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *oliver@zeigermann.de (Oliver Zeigermann)* (2004-01-22) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *oliver@zeigermann.de (Oliver Zeigermann)* (2004-02-01) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *cgweav@aol.com* (2004-02-04) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? *cgweav@aol.com* (2004-04-15) |

| List of all articles for this month |

**From: ** | cgweav@aol.com (Clayton Weaver) |

**Newsgroups: ** | comp.compilers |

**Date: ** | 16 Jan 2004 22:56:51 -0500 |

**Organization: ** | AOL http://www.aol.com |

**References: ** | 04-01-062 |

**Keywords: ** | parse, LL(1), theory |

**Posted-Date: ** | 16 Jan 2004 22:56:51 EST |

*>My question was, why is the *language* described by this grammar*

*>LL(k+1), but not LL(k):*

*>*

*>s : A s a | ;*

*>*

*>a : A^k B s | C ;*

*>*

*>It is obvious this grammar is LL(k+1), but why is the *language*?*

Do you mean "the Hopkins reason"?

(<http://www.uwm.edu/~whopkins/cs/CompFAQ.txt>

As Hopkins points out, the reason why a language can be described as

belonging to any specific category (like "ll(k)" for some value of k)

within a formal taxonomy of languages is really algebraic, and

"grammar type that can parse it without conflicts" is only one of

several possible taxonomies for categorizing formal languages, but one

might sum it up informally as "the language is ll(k+1) if it cannot be

described by an ll(k) grammar without parse conflicts but can be

described by an ll(k+1) grammar without parse conflicts".

Clark already provided you more-or-less with the proof in the case of

your specific example.

Regards,

Clayton Weaver

<mailto: cgweav@aol.com>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.