检查语法歧义

Question

以下是我试图查看是否有歧义的一段语法的摘录。

Y->b
Y->Z
Z->bW
W->d
W->?

当我计算第一组语法时，我偶然发现了 Y 中第一个的不规则性。

First(Y) = {b,First(Z)}
First of Z = b so I have the set First(Y)={b,b}.

我想知道的是，这足以证明给出这个证据的语法是否有歧义。或者应该设置为First(Y) = {b}.

Answer 1

要证明一个语法是不明确的，您只需要证明至少有两种不同的方法可以得出结果。

考虑到您的示例，并考虑到您的 edit，您确实有一个模棱两可的语法，因为您可以通过以下方式导出表达式b：

Y -> b
Y -> Z
Z -> bW
Y -> d
W -> ?

第一种方式：

Y -> b

第二种方式：

Y -> Z
Y -> Z -> bW
Y -> Z -> bW -> b?
Y -> Z -> bW -> b? -> b

这是一个歧义的语法。