查找不是LL（1）的語言？

Question

我一直在玩很多最近不是LL（1）的語法，其中很多可以轉換成LL（1）的語法。

但是，我從來沒有見過不是LL（1）的明確語言的示例。換句話說，語言的任何明確的語法不是LL（1）），我也不知道如果我意外地偶然發現了一個，我將如何去證明我找到了一個語言。

有誰知道如何證明一個特定的毫不含糊的語言不是LL（1）？

Answer 1

我考慮的問題了一會兒，然後發現此語言在Wikipedia：

S -> A | B 
A -> 'a' A 'b' | ε 
B -> 'a' B 'b' 'b' | ε 

他們聲稱通過以上不能由LL（k）文法描述文法描述語言。你只問了LL（1），這很簡單。只有第一個符號，你不知道序列是'ab'還是'aab'（或者任何更多的遞歸），因此你不能選擇正確的規則。所以語言絕對不是LL（1）。

此外，對於該語法生成​​的每個序列，只有一個派生樹。所以語言是明確的。

問題的第二部分有點困難。證明語言是LL（1）比相反（沒有描述語言的LL（1）語法）容易得多。我認爲你只是創建一個描述語言的語法，然後嘗試使其成爲LL（1）。在發現無法解決的衝突之後，您不得不利用它並創建一個證明。