我最近一直在玩很多不是 LL(1) 的语法，其中许多可以转换为 LL(1) 的语法。
但是，我从未见过不是 LL(1)的明确语言的示例。换句话说，一种语言的任何明确语法都不是 LL(1))，我也不知道如果我不小心偶然发现了一种语言，我将如何证明我找到了一种语言。
有谁知道如何证明一种特定的明确语言不是 LL(1)？
问问题
2912 次
1 回答
5
我想了一会儿这个问题，然后在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)。在发现无法解决的冲突后，您必须以某种方式利用它并创建证明。
于 2011-07-28T23:18:37.390 回答