最近我一直在玩很多不是 LL(1) 的语法，其中许多可以转换为 LL(1) 的语法。
但是，我从未见过 的例子。明确的语言 那不是 LL(1)。换句话说，一种语言的任何明确语法都不是 LL(1))，我也不知道如果我不小心偶然发现了一个，我将如何证明我找到了一个。
有谁知道如何证明特定的明确语言不是 LL(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)。在发现无法解决的冲突后，您必须以某种方式利用它并创建证明。
关于parsing - 寻找不是 LL(1) 的语言？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6855666/