左遞迴與左因子分解

剖析器為何撞上一面牆

在本級稍早，你曾把文法逼進嚴謹的形狀：給 CYK 演算法用的喬姆斯基正規形式，以及Greibach 正規形式——後者的每條規則都以終端符號開頭，使由上而下的機器在遞迴之前總是先確定一個真正的字母。本鞘的最後一篇要處理兩種較小、較銳利的手術——左遞迴消除與左因子分解——真實的剖析器仰賴它們。它們不是完整的正規形式；它們是針對「天真的由上而下剖析器卡住的兩種非常特定方式」所做的定點修復。和 Greibach 一樣，它們關乎控制規則「左」緣發生什麼事，因為一個由左到右的剖析器最先讀到的就是左緣。

想像最簡單的由上而下策略，遞迴下降：為了匹配一個非終端符號 A，你查看 A 的規則、挑一條，然後由左到右嘗試匹配它的右側，為每個符號呼叫一個小程序。它是個有禮貌的讀者，邊掃描輸入邊展開一個最左推導。現在餵它規則 E -> E + T。為了匹配 E，這個程序的第一個動作是……呼叫自己去匹配 E，而輸入指標原地不動。這個呼叫又從呼叫自己開始，永無止境。沒有任何字母被消耗掉。這就是左遞迴這個病症：一個能推導出以自己開頭之字串的非終端符號，A =>* A 某物。

消除左遞迴：把迴圈翻轉過來

修復方法是對規則做一段乾淨的代數運算，而且它從不改變語言。看清 A -> A α | β 真正生成什麼：一個 β，後面黏上任意多個 α。所以那些字串是 β、βα、βαα、βααα……——一個 β 後跟零或多個 α。那不過就是 β (α)星，一個披著遞迴偽裝的左緣迴圈。一旦你「看出」它是個迴圈，你就能用「把遞迴改移到右邊」的方式重建同一組字串，而那是由上而下剖析器能處理的：先消耗 β，再一次剝下一個 α。

處理「直接（立即）左遞迴」的機械配方：把所有 A 規則分成左遞迴的那些 A -> A α1 | A α2 | …，以及其餘的 A -> β1 | β2 | …。引入一個全新的輔助非終端符號 A'（讀作「A 撇」）。把它們替換成 A -> β1 A' | β2 A' | … 與 A' -> α1 A' | α2 A' | … | ε。現在每個非遞迴的起頭 βi 都會啟動剖析，A' 接著選擇性地接上那些 αi 尾巴，並在迴圈停止時以空字串產生式 A' -> ε 收尾。遞迴如今坐落在 A' 的右緣，所以剖析器在遞迴之前總是先讀到一個真正的前綴。

Left-recursive (top-down parser loops forever):

    E -> E + T | T
    T -> T * F | F
    F -> ( E ) | id

After removing left recursion (E', T' are fresh helpers):

    E  -> T E'
    E' -> + T E' | epsilon
    T  -> F T'
    T' -> * F T' | epsilon
    F  -> ( E ) | id

Same language, e.g. id + id * id still parses --
but now every rule's left edge consumes input or ends.

經典算術表達式文法在消除左遞迴前後的樣子。模式 A -> A a | b 變成 A -> b A'、A' -> a A' | epsilon。

還有個更微妙的表親：「間接」左遞迴，這裡沒有單一規則以 A 開頭，但一條鏈做到了，例如 A -> B x 且 B -> A y，於是 A =>* A y x。標準療法是固定一個非終端符號的次序 A1, A2, …, An 並逐一掃過：對每個 Ai，凡是某條 Ai 規則開頭出現較早的 Aj（j < i），就把那個 Aj 的所有右側代入，這會逼得 Ai 的所有左遞迴變成立即的，接著套用上面的直接配方。整輪掃完之後，沒有任何非終端符號還是左遞迴的了。這基本上就是驅動「轉換到 Greibach 正規形式」的同一套機械。

左因子分解：在岔路口別再猜了

第二種病不一樣。假設 A -> if E then S | if E then S else S。兩個選項都以相同的一長串「if E then S」開頭。一個預測式剖析器想靠偷看下一個輸入符號就選對規則——但這裡兩條規則開頭一模一樣，所以一個符號的前瞻什麼也告訴不了它。天真的剖析器只好「猜」一條分支、一路走下去，若發現走錯就回溯再試另一條——既慢，又超出乾淨的單一字符前瞻 LL(1) 剖析器的能力。左因子分解藉由「在選項真正分岔之前拒絕承諾」來移除這個猜測。

找出某個非終端符號的兩條或更多選項所共享的「最長共同前綴」：A -> γ β1 | γ β2 | …，其中 γ 是共享的前段，βi 則是其後相異的部分（任何 βi 甚至可以是空的）。
把 γ 恰好提取一次，並把決定延後給一個全新的輔助符號 A'：將那些規則替換成 A -> γ A' 與 A' -> β1 | β2 | …。
現在剖析器匹配共同的 γ 時毫無選擇可言，「之後」才看下一個符號去在那些 βi 之間挑選——到那時它們已真正相異，所以單一字符的前瞻就夠了。若仍有共享前綴則重複，因為一輪過後底下可能露出新的共同前綴。

套用在這個例子上：A -> if E then S A'、A' -> else S | ε。剖析器現在無條件地匹配「if E then S」，然後偷看一次：若下一個字符是「else」就走那條分支，否則走空的那條。猜測消失了，單一字符前瞻乾淨地做出決定。（這個例子本身，懸吊 else，在另一個意義上也確實是歧義的——一個「else」該掛到哪個「if」——但那和左因子分解所解決的前瞻問題是兩回事；因子分解修的是剖析器的選擇，不是樹的形狀。）

誠實的隱憂：樹變了，文法還會膨脹

代價在此，而它正是糾纏本鞘每一種轉換的同一道警告。這些改寫保留「語言」——所生成的字串集合分毫不差，不多不少——但它們「不」保留剖析樹。消除左遞迴之後，「a - b - c」那棵自然左傾的樹（它編碼了由左到右的分組，((a-b)-c)）被一棵穿過輔助符號 A' 的右傾樹所取代。文法仍接受相同的字串，但它賦予這些字串的「結構」已經翻轉了。如果你的樹承載著意義——比方說，減法向左結合——你就必須在事後重建那份意義，因為文法不再免費把它交給你。

第二道誠實的隱憂是大小。帶有重複共同前綴的左因子分解，以及「把較早的非終端符號代入較晚者」的間接左遞迴消除，兩者都可能造成爆炸：規則的數目會膨脹，最壞情況下遠比原文法的大小增長得快。這和轉換到 CNF 或 GNF 是同一個主題——嚴謹、對剖析器友善的形狀，是用一個更大、更難讀的文法換來的。它是由工具做「一次」的轉換，而不是你會用手去維護的東西。

退一步看：正規形式把我們帶到了哪裡

看看本鞘建起了什麼。你學到了「為何」一個整潔的文法值得這番功夫；如何按正確順序剔除無用符號、空字串產生式與單一產生式；CNF——它的二元樹驅動了 CYK 成員資格測試與上下文無關幫浦引理；GNF——它「終端符號優先」的規則映照了下推自動機的步法；以及現在這兩種由上而下的手術——消除左遞迴讓剖析器永不空轉、左因子分解讓它永遠不必猜。它們合起來，是從上下文無關文法這個抽象概念通往「一個機器真能驅動的文法」的橋樑。

從這全部五篇帶走一句話：正規形式改變的是文法的「形狀」，從不改變語言，而且常以剖析樹與文法大小為代價。這唯一的權衡——交出可讀性與結構，換取一個演算法嚼得動的嚴謹形式——就是這些轉換存在的全部理由，也是一個剖析器產生器在建造你的剖析器之前默默套用它們的理由。接下來，階梯將把文法拋在身後，給它們配一台對應的機器：下推自動機，一個帶著一疊盤子、你只能碰最上面那一個的有限控制器——那正是上下文無關語言所需要的記憶量，一塊盤子也不多。