Automata Theory 简明教程

Ambiguity in Context-Free Grammars

如果某个无上下文文法 G 对于某个字符串 w ∈ L(G) 有多个派生树，则称其为 ambiguous grammar 。从该文法生成的某个字符串存在多个最右或最左派生。

If a context free grammar G has more than one derivation tree for some string w ∈ L(G), it is called an ambiguous grammar. There exist multiple right-most or left-most derivations for some string generated from that grammar.

Problem

检查产生规则为 −

Check whether the grammar G with production rules −

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

的文法 G 是否模糊。

is ambiguous or not.

Solution

让我们找出字符串“a+a*a”的派生树。它有两个最左派生。

Let’s find out the derivation tree for the string "a+a*a". It has two leftmost derivations.

Derivation 1 −X → X+X → a X → a X*X → a+a*X → a+a*a

Derivation 1 − X → X+X → a X → a X*X → a+a*X → a+a*a

Parse tree 1 −

Derivation 2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

Parse tree 2 −

由于对于单个字符串“a+a*a”有两个解析树，文法 G 是模糊的。

Since there are two parse trees for a single string "a+a*a", the grammar G is ambiguous.