How to prove that a grammar is LL(k) for k>1

614 views Asked by At

I have this exercise which gives me a grammar and asks to prove that it is not an LL(1). All good with that part, though afterwards it asks me if that grammar can be an LL(k)(for k>1) or not. What procedure do I follow to determine that?

1

There are 1 answers

0
Apalala On

For a given k and a non-left-recursive grammar, all you have to do is to build the LA(k) table (by algorithms readily available everywhere). If there is no ambiguity, the grammar is LL(k), and the language is too.

Knowing if there exists a k for which a given language is LL(k) is undecidable. You'd have to try one value of k after the other until you succeed, or the universe runs out.