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

Chris F Clark wrote:
>
> What
> k is this language? What does the grammar with the smallest k for the
> language look like?
>
> s: a | b:
> a: A^k a | A;
> b: A^k b | B;


I am a friend of EBNF so I guess I can rewrite it to


s : a | b ;
a : ( A^k )* A ;
b : ( A^k )* B ;


can't I? Which you can left factor to:


s : ( A^k )* ( a | b ) ;
a : A ;
b : B ;


or to keep it in recursive BNF style the grammar may look like this


s : s1 s2 ;
s1 : A^k s1 | ;
s2 : a | b ;
a : A ;
b : B ;


Now, to decide if you need a further cycle in ( A^k )* or A shall be
matched in rule a one token of lookahead is not enough. When the parser
sees a single A of lookahead it can not decide what to do. Thus the
grammar is LL(2). Besides, if rule a looked like


a : (A^l) ;


the grammar would be LL(l+1). Interesting....


Another interesting thing is the lookahead does not seem to be affected
by the k in A^k (just noticed we used k with two different meanings
(1) as the lookahead (2) the amount of A's in A^k; that's why I added
the explicite reference here). Thus even the grammar for k=1


s : ( A )* ( a | b ) ;
a : A ;
b : B ;


is LL(2) as well. Much more even this grammar is LL(2):


s : ( A )* A ;


but certainly not the language as I could rewrite it to


s : ( A )* ;


which again is LL(1). So the trick is the alternative at the rightmost
side of rule s: (a | b). In my intuition this means the last A in a row
of A's shall be treated specially. To see if it will be the last one,
just to look at the next A is not enough, but you will have to look
ahead one more token which might be another A or the end of your word.


This is not specific to any grammar, but to the language, thus the
language is LL(2) as well.


Does this make any sense?


Oliver

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