如何證明一個文法是LL（k）k> 1

Question

我有這個練習給了我一個語法並要求證明它不是一個LL(1)。所有這一部分都很好，但之後它問我該語法是否可以是LL(k)(for k>1)。我應該遵循什麼程序來確定？

Answer 1

對於給定的k和非左遞歸語法，您所要做的就是構建LA(k)表（通過隨處可用的算法）。如果沒有歧義，語法是LL(k)，語言也是。

知道是否存在k，其給定語言爲LL(k)是不可判定的。你必須在另一個之後嘗試一個值k直到你成功，否則宇宙用完。