上下文无关文法中的歧义

如果上下文无关文法 G 对于某个字符串 w ∈ L(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 具有歧义。