上下文無關文法的二義性

如果上下文無關文法G對於某個字串w ∈ L(G)有多個推導樹，則稱其為二義文法。對於由該文法生成的某個字串，存在多個最右推導或最左推導。

問題

檢查具有以下產生式規則的文法G：

X → X+X | X*X |X| a

是否為二義文法。

解答

讓我們找出字串"a+a*a"的推導樹。它有兩個最左推導。

推導1 − X → X+X → a +X → a+ X*X → a+a*X → a+a*a

語法樹1 −

推導2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

語法樹2 −

由於對於單個字串"a+a*a"有兩個語法樹，因此文法G是二義的。