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}。

score 5 · Accepted Answer

文法があいまいであることを証明するには、結果に到達するための少なくとも2つの異なる方法があることを証明する必要があります。

あなたの例を考えて、そしてあなたの編集を考えると、あなたは次の方法で式を導き出すことができるので、あいまいな文法を持っていますb：

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

最初の方法：

Y -> b

2番目の方法：

Y -> Z
Y -> Z -> bW
Y -> Z -> bW -> bϵ
Y -> Z -> bW -> bϵ -> b

これはあいまいな文法です。

1 に答える 1