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