上下文無關文法歧義性的不可判定性（undecidability of ambiguity）

一個文法是「歧義的」（ambiguous），若它語言中的某個字串有兩棵不同的剖析樹——兩種確實不同的建構方式。歧義對編譯器是壞消息，因為這表示一個句子有不只一種結構意義。所以一個自然的願望是：有個工具，輸入任意文法，回報「歧義」或「無歧義」。這個工具不可能存在：判定一個上下文無關文法是否歧義是「不可判定的」。

要小心區分主張了什麼、沒主張什麼。對一個「特定」字串，你可以列出它所有的剖析樹（只有有限多棵，靠剖析找出）並看看是否有兩棵——這是可判定的。不可判定的是「整個文法層面」的問題：在無限多個字串中，是否「存在任何一個」有兩棵剖析樹？沒有演算法能對每個文法解決它。其證明從波斯特對應問題（PCP）歸約：由任意一個 PCP 實例，可構造一個文法，它歧義「若且唯若」該 PCP 實例「有解」；既然 PCP 不可判定，歧義也必不可判定。

兩個誠實的提醒能讓圖像更清晰。第一，歧義是「文法」的性質、不是「語言」的：同一個語言可以同時有一個歧義文法和一個無歧義文法。第二——而且更糟——有些上下文無關語言是「先天歧義」（inherently ambiguous），意思是它們的「每一個」文法都歧義；對這些語言，再怎麼改寫都救不了你。因為歧義不可判定，剖析器產生器工具無法承諾在一般情形下偵測它；它們改用受限的文法類別（如 LL 或 LR），這些類別的「無衝突」性可以機械化地檢查。