程式語言導論/歧義
編譯器和直譯器使用語法來構建它們將用來處理程式的資料結構。因此，理想情況下，給定的程式應該只由一個推導樹描述。然而，根據語法的設計方式，歧義是可能的。如果由語法生成的語言中的某些短語具有兩個不同的推導樹，則語法是歧義的。例如，下面我們一直用作執行示例的語法是歧義的。
<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”塊配對，例如。事實上，我們上面看到的語法是歧義的。我們透過為同一個句子生成兩個推導樹來證明這種歧義，就像我們在下面的示例圖中所做的那樣。
正如我們在上面三個例子中所看到的，我們可以透過為同一個句子提供兩個不同的解析樹來證明語法是歧義的。然而，確定給定語法是否為歧義的問題通常是不可判定的。在這種情況下，主要挑戰是某些語法可以生成無限多個不同的句子。為了證明語法是歧義的，我們必須從所有這些句子中（並且有無限多個句子）選擇一個可以由兩個不同的推導樹生成的句子。由於潛在候選者的數量可能是無限的，因此我們不能簡單地遍歷它們來嘗試確定它是否具有兩個推導樹。