无歧义文法

如果文法不包含歧义，则文法可以无歧义，这意味着对于给定的输入字符串，它不包含多个最左推导或多个最右推导或多个解析树。

为了将有歧义的文法转换为无歧义的文法，我们将应用以下规则

1. 如果在产生式规则中使用左结合运算符（+、-、*、/），则在产生式规则中应用左递归。 左递归意味着右侧最左边的符号与左侧的非终结符相同。 例如，

2. 如果在产生式规则中使用右结合运算符（^），则在产生式规则中应用右递归。 右递归意味着左侧最右边的符号与右侧的非终结符相同。 例如，

示例 1

考虑文法 G 如下所示

确定文法 G 是否有歧义。 如果 G 有歧义，则构造一个等价于 G 的无歧义文法。

解决方案

让我们推导字符串 "aab"

由于存在两个不同的解析树用于推导相同的字符串，因此给定的文法是有歧义的。

无歧义文法将是

示例 2

证明给定的文法是有歧义的。 此外，找到一个等价的无歧义文法。

解决方案

给定的文法是有歧义的，因为我们可以推导出字符串 aa 的两个不同的解析树。

无歧义文法是

示例 3

证明给定的文法是有歧义的。 此外，找到一个等价的无歧义文法。

解决方案

让我们推导字符串 "id + id * id"

由于存在两个不同的解析树用于推导相同的字符串，因此给定的文法是有歧义的。

无歧义文法将是

示例 4

检查给定的文法是否有歧义。 此外，找到一个等价的无歧义文法。

解决方案

给定的文法是有歧义的，因为字符串 aab 的推导可以用以下字符串表示

无歧义文法将是