如何证明语法是模棱两可的？S -> (S)|SS|()

Question

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

S -> (S)|SS|()

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

Answer 1

证明语法模棱两可的最简单方法是找到具有两个不同解析树的句子。(或者两个不同的最右边的推导，这是完全相同的事情。或者，如果您愿意，可以使用两个不同的最左派生。

S → S S | X总是模棱两可的(对于任何X(，因为句子X X X有两个不同的解析树：

         S            S
        /           / 
       S   S        S   S
      /   /       /    
     X   S   S    S   S   X
         |   |    |   |
         X   X    X   X