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?
How to prove that a grammar is LL(k) for k>1
605 views Asked by Alex At
1
For a given
k
and a non-left-recursive grammar, all you have to do is to build theLA(k)
table (by algorithms readily available everywhere). If there is no ambiguity, the grammar isLL(k)
, and the language is too.Knowing if there exists a
k
for which a given language isLL(k)
is undecidable. You'd have to try one value ofk
after the other until you succeed, or the universe runs out.