找一个不是LL(1)的语言？

Question

我最近一直在玩很多不是LL(1)的语法,其中很多都可以转换成LL(1)的语法.

但是,我从未见过一个不是LL(1)的明确语言的例子.换句话说,对于该语言的任何明确语法都不是LL(1)的语言,我也不知道如果我不小心偶然发现了一个语言,我将如何证明我找到了一个.

有谁知道如何证明一种特定的明确语言不是LL(1)？

Answer 1

我思考了这个问题一段时间，然后在维基百科上找到了这种语言：

\n\n

S -> A | B\nA -> \'a\' A \'b\' | \xce\xb5\nB -> \'a\' B \'b\' \'b\' | \xce\xb5\n

\n\n

他们声称上述文法描述的语言不能用 LL(k) 文法描述。您只询问了 LL(1)，这非常简单。只有第一个符号，您不知道序列是“ab”还是“aab”（或任何更多的递归序列），因此您无法选择正确的规则。所以该语言绝对不是LL(1)。

\n\n

此外，对于该文法生成的每个序列，只有一棵推导树。所以语言是明确的。

\n\n

你问题的第二部分有点难。证明该语言是 LL(1) 比证明相反的语言要容易得多（没有描述该语言的 LL(1) 语法）。我认为你只需创建一个描述该语言的语法，然后尝试将其设为 LL(1)。在发现无法解决的冲突后，您必须以某种方式利用它并创建证明。

\n