上下文无关语法中的歧义

如果上下文无关文法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是有歧义的。