歧義文法（ambiguous grammar）

想像一個句子能用兩種真正不同的方式作句法圖解——「我用望遠鏡看見那個人」（望遠鏡是誰的？）。當文法允許單一字串能以兩種真正不同的結構被建造時，該文法就是歧義的。問題不在字串；問題在於文法對「這是怎麼組合起來的？」給出不只一個答案，而結構正是決定意義的東西。

形式上，若一個上下文無關文法的語言中至少存在一個字串，它有兩棵或以上不同的剖析樹——等價地，有兩個或以上不同的最左推導（或兩個或以上不同的最右推導）——則該文法是歧義的。教科書中的慣犯有：扁平的表達式文法 E → E + E | E * E | a，其中 a + a * a 既可剖析為 (a + a) * a，又可剖析為 a + (a * a)；以及懸置 else（dangling-else），其中「if c1 then if c2 then s1 else s2」可把 else 接到任一個 if。每種不同的剖析樹意味不同的分組，而在編譯器中那意味著不同的計算值或不同的控制流——所以歧義直接敗壞意義。

通常的修補是「消除歧義」：把文法改寫成另一個生成「相同」語言、但每個字串只有唯一剖析樹的文法，典型做法是分層使用非終端符號以把運算子優先序與結合性烤進去，或加入一條（如「else 接到最近的 if」）以結構方式編碼的規則。兩個發人深省的事實使這冷靜下來：有些上下文無關語言是「先天歧義」的——根本不存在任何無歧義文法，無論你多巧妙地改寫；而且沒有任何演算法能判定任意 CFG 是否歧義——CFG 的歧義問題是不可判定的。所以你實務上常能消除歧義，但你既無法總是成功，也無法機械地檢查。