文法中的歧义

如果存在多个最左推导或多个最右推导或给定输入字符串存在多个解析树，则称语法具有歧义。如果语法没有歧义，则称为无歧义。

如果语法存在歧义，则不利于编译器构建。没有方法可以自动检测和消除歧义，但我们可以通过重新编写整个语法来消除歧义。

示例 1

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

解决方案

对于字符串 "3 * 2 + 5"，上述语法可以通过最左推导生成两棵解析树

由于对于单个字符串 "3 * 2 + 5" 存在两棵解析树，因此语法 G 存在歧义。

示例 2

检查给定的语法 G 是否存在歧义。

解决方案

从上面的语法字符串 "id + id - id" 可以通过两种方式推导

第一个最左推导

第二个最左推导

由于对于单个字符串 "id + id - id" 存在两个最左推导，因此语法 G 存在歧义。

示例 3

检查给定的语法 G 是否存在歧义。

解决方案

对于字符串 "aabb"，上述语法可以生成两棵解析树

由于对于单个字符串 "aabb" 存在两棵解析树，因此语法 G 存在歧义。

示例 4

检查给定的语法 G 是否存在歧义。

解决方案

对于字符串 "a(a)aa"，上述语法可以生成两棵解析树

由于对于单个字符串 "a(a)aa" 存在两棵解析树，因此语法 G 存在歧义。