如何证明一个语法是二义性的？S -> (S)|SS|()

Question

我对语法相当陌生，想知道是否有人可以帮助我使用解析树确定下面的语法是如何不明确的？我知道它需要有两个可以创建的不同字符串。

S -> (S)|SS|()

我可以将其转换为乔姆斯基范式和格雷巴赫，但这些的歧义让我感到困惑。

Answer 1

证明语法二义性的最简单方法是找到具有两个不同解析树的句子。（或者两个不同的最右推导，这是完全相同的事情。或者，如果您愿意，两个不同的最左推导。）

\n

S \xe2\x86\x92 S S | X总是不明确的（对于任何X），因为句子X X X有两个不同的解析树：

\n

         S            S\n        / \\          / \\\n       S   S        S   S\n      /   / \\      / \\   \\\n     X   S   S    S   S   X\n         |   |    |   |\n         X   X    X   X\n

\n