一個語言，一千種文法
到目前為止，你已能讀懂一個上下文無關文法、追蹤一段推導、畫出一棵剖析樹。但隨著這份自由而來的，是一個令人不安的事實：同一個語言可以由形態天差地別的文法寫出。你可以加進一條從不觸發的無用規則、讓起始符號繞經一串單變數的改名、或在毫無貢獻之處灑入一些生出空字串 ε（epsilon）的規則。這些都不會改變所生成字串的「集合」——卻會大幅改變文法的形狀。
把它想成散文對上報稅表。兩個人可以陳述同一組事實——一個用流暢而帶個人風格的句子，另一個填在僵硬的、印好格子並編號的表格上。兩者都傳達了真相，但只有表格能被機械化處理：因為形狀事先固定，機器確切知道該往哪裡看。文法的正規形式（normal form）就是那張印好的表格。我們不是丟掉雜亂文法的意義；而是把它重新表達，使每條規則都服從一個僵硬的模板，於是演算法就能在它上面行軍而不踩到意外。
所以整個這一階的議程是雙重的，而且順序很重要。第一，化簡：刷掉真正的垃圾——永遠生不出真正字串的符號、起始符號永遠到不了的符號、ε 規則，以及毫無意義的改名規則。第二，轉換：把清理過的文法澆進兩個著名模子之一，喬姆斯基正規形式或 Greibach 正規形式，每一個都是為了讓某個後續的特定演算法能運作而設計的。
我們在清理哪幾種雜亂？
在替模子命名之前，先看化簡所移除的四種垃圾——第二篇會逐一機械化地處理，但你現在就該對它們有感覺。一個無用符號有兩種口味。一個「非生成」符號，無論你怎麼展開它，都永遠無法落地成一個純終端符號的字串——就像一個食譜步驟，呼叫了一種本身沒有食譜的食材。一個「不可達」符號則是起始符號 S 永遠到不了的符號——食譜書裡一道沒有任何別處引用的菜。無論哪種，這符號都是死重量：刪掉它以及每一條碰到它的規則，語言絲毫不變。
另外兩種更微妙，因為它們「確實」有貢獻，只是笨拙。一個 epsilon 產生式是規則 A → ε，讓一個變數消失成虛無；它對「這部分是可選的」這種說法很有用，但會讓推導先變長再縮短，而後續演算法討厭這點。一個單位產生式是右側整個就是一個單一變數的規則 A → B——純粹的官僚作業，把 A 改名成 B 卻不做真正的工作。兩者都可被消除（要付一個我們會誠實交代的代價），一旦它們消失，每條規則就都做著實質的事。
喬姆斯基正規形式：每條規則都是二元的
一旦文法乾淨了，第一個著名模子就是喬姆斯基正規形式（CNF）。規則很簡樸：每條產生式都必須長成 A → B C（一個變數改寫成恰好兩個變數）或 A → a（一個變數改寫成恰好一個終端符號）。一個逃生口：若空字串 ε 在語言中，允許起始符號有單一規則 S → ε，而此後 S 絕不出現在任何規則的右側。這就是整個模板——報稅表上的兩個格子，沒別的了。
為什麼非要把一切逼成成對？因為 A → B C 意味著一棵剖析樹的每個內部節點都恰好有兩個子節點：樹變成了「二元」的。而一棵覆蓋長度 n 字串的二元樹，有著漂亮且可預測的形狀——它在每個節點都能被切成左半與右半。正是這一個結構性承諾，讓 CYK 演算法成為可能：它填一張表，對輸入的每一段問：「哪個變數能藉由把這段切成左半與右半來生成它？」——並在 O(n^3) 時間內判定成員資格。二元的形狀不是裝飾；它是演算法掛載其上的那個鉤子。
同樣的二元形狀在理論這一側還付出第二份紅利。上下文無關的幫浦引理——和正規版一樣，是喬裝的鴿籠原理——需要論證一個夠長的字串會迫使某個變數在某條從根到葉的路徑上重複。一個有界的分支因子（這裡恰好是 2），正是讓你能界定路徑長度並觸發鴿籠的關鍵：一棵夠高的二元樹必然重用某個變數，而那個重複的變數正是你拿來「打幫浦」的。CNF 讓這個計數論證變得乾淨。
Greibach 正規形式：每條規則都以一個字母開頭
第二個模子，Greibach 正規形式（GNF），解決的是另一個問題，因而堅持另一種形狀。每條產生式都必須長成 A → a α，其中 a 是單一終端符號，而 α 是一個（可能為空的）變數字串。關鍵在於：每條規則都恰好吐出「一個」真正的終端符號，就擺在最前面，而那個終端符號是它承諾的第一件事。（同樣地，若空字串在語言中，允許 S → ε。）
為什麼在乎終端符號坐在最前面？因為那正是由上而下剖析所渴求的：一個由左到右讀輸入的剖析器，希望每一步都消耗掉一個輸入字母，這樣它就永遠不會卡在原地空轉而毫無進展。它也提供了一座通往前一階下推自動機的乾淨橋樑。一台 PDA 讀 a^n b^n 的方式，是每遇一個「a」就推進一個盤子、每遇一個「b」就彈出一個；在 GNF 裡，每個推導步驟消耗一個終端符號、並把剩下的變數 α 推上堆疊，於是一個 GNF 文法幾乎可以直接翻譯成一台每一步都恰好讀入一個輸入符號的 PDA。那個前置的終端符號，就是動作的觸發器。
要把一個文法弄進 GNF，乃至要讓由上而下剖析根本能運作，都得先修掉一個惡名昭彰的毛病：左遞迴（left recursion），像 A → A α 這樣、變數立刻又出現在自己最左側的規則。一個天真的由上而下剖析器，面對 A → A α 會把 A 展成 A α、再展成 A α α，永無止境，一個字母也讀不到——一個不消耗任何輸入的無窮迴圈。第五篇會示範如何移除左遞迴（以及如何把共用同一前綴的規則做「左因子分解」）。GNF 那個前置的終端符號，某種程度上就是把左遞迴的療方寫成了法律。
誠實的代價：規模爆炸與失去的樹
現在來談課本有時含糊帶過的部分。這些轉換並非免費，假裝不是這樣是不誠實的。正規形式的規模爆炸是真實的：在最壞情況下，移除 ε 產生式可能讓規則數量指數級地倍增，因為每一個可能消失的變數，都迫使你為其他規則加上「含它」與「不含它」兩種版本。轉成 CNF 可能讓文法大小平方化甚至更糟，而 GNF 的轉換更為嚴酷。所得的文法是正確且對機器友善的，但它可能比你起初那個遠遠更龐大、也遠遠更難讀。
還有第二個、更微妙的代價，每當你在乎的是結構而非僅僅成員資格時，它就要緊。這些轉換會改變剖析樹。新文法生成的字串集合完全相同——語言永遠被保留——但一個字串在 CNF 裡的樹（僵硬地二元、充滿被發明出來的輔助變數），和它在原文法裡的樹幾乎毫無相似之處。如果你原本需要那棵原始的樹去代表某種意義（運算子優先序、表達式的形狀），轉換後的文法不會直接把它交給你。CNF 是用來「高效判定成員資格」的，不是用來找回你當初設計的結構的。
Original grammar: S -> S + S | a
(clear meaning, but ambiguous and left-recursive)
A CNF-style rewrite might invent helpers and pairings:
S -> S P | a
P -> O S
O -> + (read O as the literal '+')
Same language { a, a+a, a+a+a, ... } -- but the parse
trees are now binary and reshaped, no longer the 'flat'
familiar shape, and a brand-new helper variable appeared.穿過這一階的道路
這就是「為什麼」。我們把文法正規化，是因為演算法需要一個固定的形狀才能抓握——一張報稅表，而非自由的散文。喬姆斯基正規形式讓樹變成二元，使 CYK 能在 O(n^3) 內判定成員資格，也使上下文無關幫浦引理的鴿籠計數能走得通。Greibach 正規形式把一個終端符號前置，使由上而下剖析永遠有進展，且幾乎免費地掉出一台 PDA。而我們為這兩者付出可能的指數級規模爆炸與被重塑的樹——這是一筆我們明知而為的交易。
第二篇捲起袖子處理清理本身，按那承重的順序：無用符號、ε 產生式、單位規則。第三篇一步步建出喬姆斯基正規形式；第四篇建出 Greibach 正規形式；第五篇以移除左遞迴與左因子分解收尾——那是讓由上而下剖析根本可行的外科手術。一路上請帶著一句話：正規化從不改變文法生成「哪些」字串，只改變每個字串「如何」被建造——有時還改變規則手冊長到多大。