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

Oliver Zeigermann <oliver@zeigermann.de>
7 Jan 2004 01:01:22 -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)? cfc@shell01.TheWorld.com (Chris F Clark) (2004-01-09)
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)
[5 later articles]
| List of all articles for this month |
From: Oliver Zeigermann <oliver@zeigermann.de>
Newsgroups: comp.compilers
Date: 7 Jan 2004 01:01:22 -0500
Organization: T-Online
Keywords: LL(1), parse, question
Posted-Date: 07 Jan 2004 01:01:22 EST

Experts!


Theory books tell me for every k there are languages that are LL(k+1),
but not LL(k). An example is the language described by this grammar
(upper case letters are terminals, lower case are non-terminals, A^k
means A repeated k times):


s : A s a | ;


a : A^k B s | C ;


I understand this grammar is LL(k+1), but what makes me sure there is no
way to rewrite it to be LL(k) or even less?


Cheers and thanks in advance,


Oliver

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.