编程语言导论/歧义
编译器和解释器使用语法来构建它们将用来处理程序的数据结构。因此，理想情况下，给定的程序应该只由一个推导树描述。然而，根据语法的设计方式，歧义是可能的。如果由语法生成的语言中的某些短语具有两个不同的推导树，则语法是歧义的。例如，下面我们一直用作运行示例的语法是歧义的。
<exp> ::= <exp> "+" <exp>
| <exp> "*" <exp>
| "(" <exp> ")"
| "a" | "b" | "c"
为了看到此语法是歧义的，我们可以观察到它可以为字符串“a * b + c”推导出两个不同的语法树。下图显示了这两个不同的推导树。
有时，语法中的歧义会影响我们从该语法推导出的句子的含义。例如，我们的英语语法是歧义的。句子“The professor saw the student with the glasses”有两个可能的推导树，如侧图所示。在上方的树中，介词短语“with the glasses”修饰动词。换句话说，眼镜是教授用来观察学生的工具。另一方面，在底部的推导树中，相同的介词表达式修饰“the student”。在这种情况下，我们可以推断出教授看到了一个可能在被观察时戴着眼镜的特定学生。
编译器中歧义的一个特别著名的例子发生在if-then-else结构中。歧义的发生是因为许多语言允许不使用“else”部分的条件子句。让我们考虑一下我们可以用来推导出条件语句的一组典型的生成规则。
<cmd> ::= if <bool> then <cmd>
| if <bool> then <cmd> else <cmd>
在偶然发现一个类似于下面代码的程序时，我们不知道“else”子句是与最外层的“then”还是与最内层的“then”配对的。在 C 语言以及大多数语言中，编译器通过将“else”与最接近的“then”配对来解决此歧义。因此，根据此语义，下面的程序将在 a > b 且 c <= d 时打印值 2。
if (a > b) then if (c > d) then print(1) else print(2)
但是，将“else”与最接近的“then”配对的决定是任意的。语言设计者本可以选择将“else”块与最外层的“then”块配对，例如。事实上，我们上面看到的语法是歧义的。我们通过为同一个句子生成两个推导树来证明这种歧义，就像我们在下面的示例图中所做的那样。
正如我们在上面三个例子中所看到的，我们可以通过为同一个句子提供两个不同的解析树来证明语法是歧义的。然而，确定给定语法是否为歧义的问题通常是不可判定的。在这种情况下，主要挑战是某些语法可以生成无限多个不同的句子。为了证明语法是歧义的，我们必须从所有这些句子中（并且有无限多个句子）选择一个可以由两个不同的推导树生成的句子。由于潜在候选者的数量可能是无限的，因此我们不能简单地遍历它们来尝试确定它是否具有两个推导树。