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

Oliver Zeigermann <oliver@zeigermann.de>
22 Jan 2004 23:12:28 -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)
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: Oliver Zeigermann <oliver@zeigermann.de>
Newsgroups: comp.compilers
Date: 22 Jan 2004 23:12:28 -0500
Organization: T-Online
References: 04-01-027 04-01-033 04-01-071 04-01-080 04-01-111
Keywords: LL(1), parse
Posted-Date: 22 Jan 2004 23:12:27 EST

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


Post a followup to this message

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