如何检查这个语法是否有二义性？

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. I.e.如果有一个推导在哪里B -> X and B -> YZ

还有另一个地方

B -> XY and B -> Z

（当然，Y 非空）那么你可以用它来证明歧义。

Answer 2

因此，让我们尝试从上面的语法中重现 0011。

0011 示例： S->OB->00BB->001B->0011

1100 的示例： S->1A->11AA->110A->1100

如果解析这个输入字符串，似乎只产生一个最左推导或最右推导。所以语法是明确的。