歧義，以及如何把它除掉

當一個字串有兩棵樹

在第 2 篇導覽裡你學到：剖析樹是「上下文無關文法如何建出一個字串」的真實紀錄，而你替換變數的順序——最左或最右——並不重要，因為最左推導與最右推導描述的是同一棵樹。那個承諾悄悄假設了「只有一棵樹可描述」。當某文法的語言裡，某個單一字串擁有兩棵真正不同的剖析樹時，這文法就被稱為 歧義的（ambiguous）。不是只在替換順序上不同的兩個推導——那種無害——而是形狀不同的兩棵樹。

如果這字串怎樣都會被接受，你又何必在意？因為剖析樹不只是「成員資格的證明」——它是「意義的骨架」。當你之後走訪這棵樹去計算數值、做型別檢查、或翻成機器碼時，是樹的「形狀」決定了答案。同一字串有兩種形狀，就意謂兩種意思，而編譯器沒辦法默默挑一個。成員問題問的是「這字串在語言裡嗎？」；歧義問的卻是「這字串恰好只有一種結構嗎？」——一個嚴格更難、也更有趣的問題。

教科書裡的元兇是算術。看看這個過於天真的文法 E -> E + E | E * E | a，你第一次嘗試時很可能會這麼寫，因為它顯然生成了所有對的字串。現在剖析 a + a * a。一棵樹先加後乘，算出 (a + a) * a；另一棵先乘，算出 a + (a * a)。在同一個文法之下，兩者都是「同一個字串」的合法剖析樹。文法完全沒告訴你它指的是哪一個——而對數字來說，那兩個答案不相等。這文法作為一個字串「集合」是正確的，作為「結構」的指引卻毫無用處。

同一字串的兩幅圖

把這兩棵樹並排看一看很值得，因為「形狀」本身就是這個臭蟲。下面是 a + a * a 在 E -> E + E | E * E | a 之下的兩棵剖析樹。每一棵都從樹根往下讀：最靠近樹根的運算子是「最後」才套用的（因此綁得最鬆），而最深處的運算子最先套用。左邊那棵把 + 放在樹根，於是乘法發生在內部、綁得更緊；右邊那棵把 * 放在樹根，於是加法先發生。我們要的是第一種讀法、而非第二種，但文法兩種都允許。

string:  a + a * a        (grammar:  E -> E + E | E * E | a)

  Tree 1: a + (a * a)        Tree 2: (a + a) * a
  ------------------         ------------------
          E                          E
        / | \                      / | \
       E  +  E                    E  *  E
       |    /|\                   /|\    |
       a   E * E                 E + E   a
           |   |                 |   |
           a   a                 a   a

  root operator = applied LAST = binds loosest
  Tree 1 multiplies first (correct);  Tree 2 adds first (wrong)

一個字串，兩棵合法的剖析樹。樹根上的運算子最後才套用，所以樹 1（+ 在樹根）先做乘法，正是我們要的意思。歧義文法讓兩者並存。

解藥：把優先順序與結合性編進文法

修法是：不再讓文法自己挑，而是把答案烤進它的結構裡。天真文法少了兩件事，兩者都得編進去。其一，優先順序（precedence）：乘法應比加法綁得更緊，所以 a + a * a 必須讀成 a + (a * a)。其二，結合性（associativity）：a - a - a 應指 (a - a) - a，向左分組，而非 a - (a - a)。訣竅是：每個優先層級引入一個變數，並讓綁得鬆的運算子在樹裡坐在綁得緊的之「上」，逼出我們要的形狀。

分層去建，綁得最鬆的運算子放在最外層。一個表達式 E 是用 + 連起來的若干「項（term）」；一個項 T 是用 * 連起來的若干「因子（factor）」；一個因子 F 是最小單位，一個 a 或一個括起來的表達式。因為 E 只能拆成 T（絕不直接拆成 *-規則），每個 + 必然落在樹裡比每個 * 更高的位置，這恰恰就是優先順序。要釘死結合性，就讓遞迴往一邊倒：寫成 E -> E + T（左遞迴），於是 a + a + a 被逼成 (a + a) + a，向左分組。如今再也沒有選擇餘地——恰好一棵樹存活。

Ambiguous (one level, free choice):
    E -> E + E | E * E | ( E ) | a

Unambiguous (layered: + loosest, * tighter, () tightest):
    E -> E + T | T          # + groups left, binds loosest
    T -> T * F | F          # * groups left, binds tighter
    F -> ( E ) | a          # parentheses / atoms bind tightest

Now a + a * a has ONLY this tree:
        E
      / | \
     E  +  T
     |    /|\
     T   T * F
     |   |   |
     F   F   a
     |   |
     a   a            => a + (a * a), as intended

每個優先層級一個變數，逼得每個 + 都在每個 * 之上；左遞迴則逼出向左分組。分層後的文法生成同一個語言，但如今每個字串恰好只有一棵剖析樹。

懸置的 else，以及你贏不了的時候

算術不是唯一的肇事者。真實語言裡最有名的例子是 懸置的 else（dangling else）：在像 S -> if C then S | if C then S else S | other 這樣的規則下，字串「if C then if C then a else b」是歧義的——這個 else 是接到內層的 if、還是外層的 if？真實語言會頒布一條規則（「else 接到最近、尚未配對的 if」），然後重寫文法去強制它，把敘述拆成「已配對」與「未配對」兩種，使一個 else 永遠無法越過更近的 if 去伸手。這是和先前一樣的藥：當光禿禿的文法給了選擇，就重構它，讓只有「想要的那棵樹」可被推導。

但這裡有個這一階非說不可的、嚴酷而誠實的真相：有時候你贏不了。若某個上下文無關語言「所有」生成它的上下文無關文法「都」是歧義的，這語言就被稱為 本質歧義的（inherently ambiguous）——歧義在語言本身，而不只是在一個草率的文法裡。經典例子是字串 a^i b^j c^k 中「i = j 或 j = k」的那個語言。任何文法都得處理這兩種情形，而那些 i = j = k 的字串永遠能用兩種方式建出來——一種把 a 配對到 b，一種把 b 配對到 c——任何重寫都抹不掉那道重疊。所以再多的聰明才智也造不出一個「一棵樹」的文法。

實際上該怎麼做

把這些收攏起來，每當你在第 3 篇導覽裡設計的文法結果允許了兩棵樹時，這就是你會伸手去拿的例行步驟。目的從來不是改動語言——下面每一步都「恰好」保留生成的是哪些字串——而只是讓每個字串的結構變得唯一。

把歧義具體地找出來。找一個有兩棵剖析樹（或兩個相異最左推導）的短字串。對運算子來說，幾乎總是像 a + a * a 或 a - a - a 那類；對敘述來說，就是懸置的 else。光一個見證字串就足以證明文法是歧義的。
依優先順序把運算子排名——哪一個該綁得最緊？接著每個層級造一個變數，從最上面綁得最鬆的（起始變數）一路到最下面綁得最緊的（原子與括號）。
把每個層級接成「只能拆解到下一個更緊的層級」，絕不直接拆成更鬆的運算子。光這一條紀律，就逼得更鬆的運算子在每棵樹裡都坐得更高，這「就是」優先順序。
用遞迴的傾向為每個運算子選定結合性。左遞迴（E -> E + T）向左分組；右遞迴（E -> T + E）向右分組；選與該運算子真實意義相符的那一個（- 與 / 向左倒，^ 向右倒）。
重新測試那個見證字串，再加幾個混合的案例。確認現在恰好只存在一棵樹。記住你永遠無法把這最後的檢查在所有文法上完全自動化，所以要親手推敲，或仰賴一個會拒絕「落在自己乾淨類別之外的文法」的剖析器產生器。

這就是消除歧義的全部技藝：永遠不放寬也不收窄語言，只是雕琢它的文法，直到「結構」變成字串的一個函數、別無其他。手裡握著一個乾淨、非歧義的文法，你就準備好迎接下一篇了——在那裡，同樣的這種分層形狀會以一個工業界的名字重新登場——BNF 與 EBNF——也就是真實語言手冊用來發布這類文法的記號法。