# 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.