如何检查这个语法是否有歧义？
How to check if this grammar is ambiguous or not?
我无法确定这个语法是否有歧义。我如何检查它是否有歧义？
G = ({S,A,B}, {0,1}, P, S}
P:
S → 0B | 1A
A → 0 | 0S | 1AA
B → 1 | 1S | 0BB
如果给定的输入字符串存在不止一个最左边的推导或不止一个最右边的推导或不止一个解析树，则称该语法是有歧义的。如果语法没有二义性，则称为无二义性。
因此，让我们尝试从上面的语法中重现 0011。
0011 示例：
S->OB->00BB->001B->0011
1100 示例：
S->1A->11AA->110A->1100
如果解析这个输入字符串，似乎只产生一个最左推导或最右推导。所以语法没有歧义。
您想要的是一种算法，对于给定的上下文无关语法，它可以告诉您它是否有歧义。然而，事实证明，这样的算法是不存在的。
一种方法是应用一种已知仅适用于明确语法子集的解析器构造技术。
- 如果构造成功，那么你肯定知道语法没有歧义。
- 如果构造失败，那么您仍然不知道：语法可能有歧义，或者它可能没有歧义但超出了该技术可以处理的子集。不过，构造失败的方式或许能让你洞察问题
例如，如果您为您的文法构造 LR(0) 自动机，您会得到 2 个有冲突的状态，因此这是不确定的。但是你知道，如果它 是 歧义，那么任何证明歧义的句子都必须至少涉及其中一个状态。 （任何避免这些状态的句子都可以被确定性地解析。）所以你可以专注于语法的那个区域。
另一种方法是使用启发式方法。例如。生产 B -> 0BB 看起来可能会引起歧义。 （让两个 B 紧挨着彼此有点可疑。）所以你会专注于 BB 并询问是否有某种方法可以导出 XYZ 形式，其中两个 Bs 'fight' 在 Y 上。如果有一个推导 where
B -> X and B -> YZ
还有另一个地方
B -> XY and B -> Z
（当然 Y 是非空的）然后你可以用它来证明歧义。
我无法确定这个语法是否有歧义。我如何检查它是否有歧义？
G = ({S,A,B}, {0,1}, P, S}
P:
S → 0B | 1A
A → 0 | 0S | 1AA
B → 1 | 1S | 0BB
如果给定的输入字符串存在不止一个最左边的推导或不止一个最右边的推导或不止一个解析树，则称该语法是有歧义的。如果语法没有二义性，则称为无二义性。
因此，让我们尝试从上面的语法中重现 0011。
0011 示例： S->OB->00BB->001B->0011
1100 示例： S->1A->11AA->110A->1100
如果解析这个输入字符串，似乎只产生一个最左推导或最右推导。所以语法没有歧义。
您想要的是一种算法，对于给定的上下文无关语法，它可以告诉您它是否有歧义。然而，事实证明，这样的算法是不存在的。
一种方法是应用一种已知仅适用于明确语法子集的解析器构造技术。
- 如果构造成功，那么你肯定知道语法没有歧义。
- 如果构造失败，那么您仍然不知道：语法可能有歧义，或者它可能没有歧义但超出了该技术可以处理的子集。不过，构造失败的方式或许能让你洞察问题
例如，如果您为您的文法构造 LR(0) 自动机，您会得到 2 个有冲突的状态，因此这是不确定的。但是你知道，如果它 是 歧义，那么任何证明歧义的句子都必须至少涉及其中一个状态。 （任何避免这些状态的句子都可以被确定性地解析。）所以你可以专注于语法的那个区域。
另一种方法是使用启发式方法。例如。生产 B -> 0BB 看起来可能会引起歧义。 （让两个 B 紧挨着彼此有点可疑。）所以你会专注于 BB 并询问是否有某种方法可以导出 XYZ 形式，其中两个 Bs 'fight' 在 Y 上。如果有一个推导 where
B -> X and B -> YZ
还有另一个地方
B -> XY and B -> Z
（当然 Y 是非空的）然后你可以用它来证明歧义。