歧义

你所说的二义性文法是什么意思？

如果对于给定的输入字符串，存在多于一个的最左推导、多于一个的最右推导或多于一个的 分析树，则该文法被称为二义性文法。如果文法不是二义性的，则称为非二义性文法。

示例

对于字符串 aabb，上述文法生成两个分析树

如果文法具有二义性，则不利于 编译器构造。没有方法可以自动检测和消除二义性，但你可以通过重写整个文法来消除二义性。

上下文无关文法中的二义性

如果同一个字符串存在多个左或右推导树，则上下文无关文法是二义性的。因此，单个字符串可以有多个推导树。

二义性的原因

二义性可以通过多种方式引入编程语言，例如

• 当文法没有描述运算符应被求值的结构时，可能会发生这种情况。
• 当文法规则允许多个树序列产生相同的字符串时。

消除文法二义性的方法

以下是消除文法二义性的方法列表

• 通过将复杂规则分解为更小更简单的规则来生成简单的产生式规则。
• 确保它们应用的顺序是明确的。
• 在最后而不是在开头解决左递归问题，这样就不会创建无限循环。

将二义性文法转换为非二义性文法

在给定的非终结符的右侧出现多次的产生式规则是二义性产生式。

例如

 A → A * A

在上面的例子中，它的 R.H.S 上有两个 A。

我们可以通过引入一个非终结符将大多数这些非终结符向下移动分析树，从而将这些类型的二义性产生式转换为非二义性产生式。

让我们看看以下产生式规则：

A → A + A

A -> A ∗ A

A -> (A)  

A -> id

如何将二义性文法转换为非二义性文法。

以下是将二义性文法转换为非二义性文法的步骤列表。

步骤 1: 在第一步中，我们引入了一个非终结符，例如 T，它不能是两个项的另一种组合。

A → A + T

A -> T

T → A * A

 T → (A)

T - > id

步骤 2:  由于我们有产生式规则 A → T。现在，用 T 替换 A 以获得以下规则。

T → T ∗ T

在此步骤中，我们引入了另一个非终结符 B（因子），它不能进一步分解或乘以两个数字。

用 B 替换 T 以获得以下产生式规则，

T → T * B

T -> B

B → (A)

B → id

因此，将有以下非二义性文法，例如

A → A + T

A -> T

T → T * B

T -> B

B → (A)

B -> id

关于编译器中二义性的常见问题

1. 我们可以消除文法的二义性吗？

答案：是的，我们可以消除文法的二义性。可以通过重写整个文法而不带任何二义性来消除它。

2. 二义性文法和非二义性文法之间的区别？

答案