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

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

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