grammar - 如何检查这个语法是否有歧义？

Question

我很难确定这个语法是否有歧义。如何检查它是否有歧义？

G = ({S,A,B}, {0,1}, P, S}

P:

S → 0B | 1A

A → 0 | 0S | 1AA

B → 1 | 1S | 0BB

Answer 1

您想要的是一种算法，对于给定的上下文无关语法，它可以告诉您它是否有歧义。然而，事实证明，这样的算法是不存在的。

一种方法是应用一种已知仅适用于明确语法子集的解析器构造技术。

• 如果构造成功，那么你肯定知道语法没有歧义。
• 如果构造失败，那么您仍然不知道:语法可能有歧义，或者它可能没有歧义但超出了该技术可以处理的子集。但是，构造失败的方式可能会让您深入了解问题。

例如，如果您为语法构建 LR(0) 自动机，您会得到 2 个有冲突的状态，因此这是不确定的。但是您知道，如果它 有歧义，那么任何证明歧义的句子都必须至少涉及其中一个状态。 (任何避免这些状态的句子都可以被确定性地解析。)因此您可以专注于语法的那个区域。

另一种方法是使用启发式方法。例如。产生式 B -> 0BB 看起来可能会引起歧义。 (将两个 B 紧挨着放在一起有点可疑。)所以你会专注于 BB 并询问是否有某种方法可以导出一个形成 XYZ，其中两个 B 为 Y ‘争斗’。如果有一个推导

B -> X   and B -> YZ

还有一个地方

B -> XY  and B -> Z

(当然，Y 是非空的)然后您可以使用它来证明歧义。