parsing - 检查语法歧义

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

这是一个模棱两可的语法。