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

Oliver Zeigermann <oliver@zeigermann.de>
16 Jan 2004 22:26:41 -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)? 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)
[1 later articles]
| List of all articles for this month |

From: Oliver Zeigermann <oliver@zeigermann.de>
Newsgroups: comp.compilers
Date: 16 Jan 2004 22:26:41 -0500
Organization: T-Online
References: 04-01-027 04-01-033 04-01-071
Keywords: parse, LL(1)
Posted-Date: 16 Jan 2004 22:26:41 EST

Ok, so there is this LL(k) described by this context free, non-LL grammar:


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


Trying to eliminate the indirect left recursion results in (hopefully I
made no mistake):


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


Now eliminating the immediate left recursion results in (now this gets
really confusing, I am almost sure I have made a mistake):


s : C s A s' | s' ;
s' : B A^k s A | ;


a : B A^k a' | C a' ;
a' : s A B A^k | ;


If I made no mistake, this grammar and thus the language is LL(1). OK,
now I see I still have these k A's, but they are not in a conflicting
context, is it this you wanted to tell me? And as in my original grammar
(let me allow to repeat it):


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


there is this conflicting context. My language describes words where
every B is preceeded by k A's and to determine if the B is in the right
position I will have to look ahead those k A's plus the B resulting in
k+1 lookahead, right? I understand there is no way to rewrite this rule
as there can be possibly an infinite number of other A's preceeding
those k A's and that's the conflicting context?


There may be errors in my reasoning, but I guess I am pretty close now.
Sorry, I did not understand the deeper insight your answer showed, I
thought it was just off topic. This was due to the lack of *my* deeper
insight ;)


Let me ask one more question though. What is this C in rule a for?


Thanks :)


Oliver


Post a followup to this message

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