自动机语法中的歧义

如果对于给定的输入字符串，存在不止一个最左导数或不止一个最右导数或不止一个解析树，则文法是不明确的。如果语法不是模棱两可的，那么就将其称为模棱两可。

如果语法有歧义，则对编译器构造不利。没有任何方法可以自动检测并消除歧义，但是我们可以通过重写整个语法而不会歧义来消除歧义。

范例1：

让我们考虑带有生成规则的语法G

E → I
E → E + E
E → E * E
E → (E)
I → ε | 0 | 1 | 2 | ... | 9

解：

对于字符串“ 3 * 2 5”，上述语法可以通过最左侧的派生生成两个解析树：

由于单个字符串“ 3 * 2 5”有两个解析树，因此语法G是模棱两可的。

范例2：

检查给定的语法G是否模棱两可。

E → E + E
E → E - E
E → id

解：

从上面的语法中，字符串“ id id-id”可以通过两种方式得出：

第一个最左导数

E → E + E
   → id + E
   → id + E - E
   → id + id - E
   → id + id- id

第二最左导数

E → E - E
   → E + E - E
   → id + E - E
   → id + id - E
   → id + id - id

由于单个字符串“ id id-id”的最左边有两个推导，因此语法G是不明确的。

范例3：

检查给定的语法G是否模棱两可。

S → aSb | SS
S → ε

解：

对于字符串“ aabb”，上述语法可以生成两个解析树

由于单个字符串“ aabb”有两个解析树，因此语法G是模棱两可的。

范例4：

检查给定的语法G是否模棱两可。

A → AA
A → (A)
A → a

解：

对于字符串“ a（a）aa”，上述语法可以生成两个解析树：

由于单个字符串“ a（a）aa”有两个解析树，因此语法G是不明确的。