JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

喬姆斯基正規形式

把每條規則都削成兩種形狀之一——一個變數恰好分裂成兩個變數，或一個變數生出一個終端符號——糾結的文法就變成一台整齊的二元剖析樹機器。正是這份整齊，讓 CYK 剖析器與上下文無關幫浦引理得以運作。

一個文法、兩種規則形狀、沒有例外

讀完前一篇，你已學會把一個上下文無關文法擦乾淨——剔除無用符號、移除 epsilon 產生式、移除單位產生式，全都按正確的順序進行。清理過後規則雖然合法，卻仍參差不齊：某條規則可能是 A → b C D e，另一條 A → x，又一條 A → B。喬姆斯基正規形式（CNF）是下一個、更嚴格的步驟。它要求「每一條」產生式都符合僅僅兩種死板形狀之一，不留任何殘餘。

被允許的兩種形狀是：(1) A → B C，一個變數恰好分裂成「兩個」變數（絕不是終端符號、不是一個、不是三個）；以及 (2) A → a，一個變數恰好生出「一個」終端符號。有一個受嚴格控管的例外：若空字串 epsilon 屬於該語言，則允許起始符號 S 有單一規則 S → ε——而且此時禁止 S 出現在任何規則的右側，這樣這個逃生口便絕不會滲漏進文法的其餘部分。這就是完整的定義。沒有像 A → b C 這樣的混合規則、沒有長規則、沒有單位規則 A → B、其他地方也沒有任何脫隊的 epsilon。

何必費這勁？因為每棵剖析樹都變成二元樹

回報是幾何性的。回想剖析樹那篇所說：一個內部節點的子節點拼出某規則的右側。在 CNF 中每條內部規則都是 A → B C，所以每個內部節點恰好有「兩個」本身也是內部節點的子節點；而每條規則 A → a 造出一個恰有一個子節點（一個葉終端符號）的節點。結果是：每棵剖析樹在其分枝部分都是嚴格的二元樹，真正的字母則作為葉節點懸在底部。沒有節點會散開成三、五或七個子節點——永遠是乾淨的二路分裂。

這種二元形狀把一棵樹的大小精確地釘死，而這份精確對證明來說是黃金。在 CNF 文法中，長度為 n（n 至少為 1）的字串的推導恰好需要 2n - 1 步：n - 1 次套用二元規則 A → B C 以建出分枝，加上 n 次套用 A → a 以兌現葉節點。再也不用猜一棵樹可能多高或多茂密——算術是固定的。一旦 n 夠大，這種樹裡又長又瘦的路徑就被強迫出現，而單單這個事實，正是上下文無關幫浦引理背後的引擎。

把這個連結講白。上下文無關幫浦引理說：每個上下文無關語言都有一個常數 p，使得任何長度至少為 p 的字串都能切成五段 u v x y z，其中中段 v x y 很短、v 與 y 合起來非空，而幫浦——同步重複 v 與 y——會讓你仍留在語言之中。那個 p 從哪來？從一個 CNF 文法。若一個字串夠長，它的二元剖析樹必定很高；一條又高又瘦的分枝在單一條根到葉的路徑上必定重複某個變數 A（這是偽裝過的鴿籠原理）。那個重複的 A 是一個你可以一再執行的迴圈——而「再執行一次」正是幫浦 v 與 y。

以及為何 CYK 能在立方時間內判定成員資格

第二個重大回報是剖析。CYK 演算法回答成員資格問題——這個特定字串 w 在語言中嗎？——而它「要求」文法處於喬姆斯基正規形式。它整套策略仰賴那個二元分裂：因為頂層規則必定是 S → B C，字串 w 必定斷成一個由 B 生成的左半與一個由 C 生成的右半。CYK 不去猜斷在哪裡；它嘗試「每一個」分裂點，並把結果記在一張表裡，於是它絕不重算同一個子問題。這張填表的過程，正是動態規劃的核心。

  1. 長度為 1 的格子：對輸入的每個單一字母 w[i]，記下每個帶有規則 A → w[i] 的變數 A。這是唯一用到終端規則 A → a 的地方——用來播下表的種子。
  2. 較長的跨段：要填一個長度為 L 之子字串的格子，嘗試把它切成左半與右半的每一種方式。若某個變數 B 能生成左半、C 能生成右半，「且」文法有規則 A → B C，那麼 A 就能生成整個跨段。記下 A。
  3. 從短跨段往上建到整個字串。字串 w 在語言中，恰當且唯當起始符號 S 落入頂層格子——那個涵蓋整個 w 的格子。逆向讀這張表，便能重建出一棵實際的剖析樹。

數一數工作量：大約有 n^2 / 2 個子字串要考慮，而填每一個會嘗試至多 n 個分裂點，於是長度為 n 的字串花費 O(n^3) 時間（把文法大小當作固定常數）。這就是那個著名的立方上界。它是一個具體而誠實的證明，說明上下文無關語言的成員資格是可判定的——而且不只可判定，還是多項式時間。在一個參差不齊的文法上，這套機械連型別都對不上；正是 CNF 的二元形狀，才讓「切成兩部分」這個迴圈成為可能。

如何轉換：四個動作，依序進行

把任何清理過的文法轉成喬姆斯基正規形式是一份簡短的食譜，而「順序」之所以重要，原因和第二篇裡一樣——若你倒著做，較後的步驟可能重新製造出較早步驟移除掉的那些規則。前三個動作是你已經熟悉的清理；最後兩個則重塑倖存下來的東西。我們把它們打包成下面四個概念性動作。

  1. 先清理（並加一個全新的起始符號）。引入一個新的起始符號 S0 → S，使起始符號絕不出現在任何規則的右側；接著移除 epsilon 產生式、再移除單位產生式、再移除無用符號——正是前一篇那套有紀律的順序。這之後，文法不再有 A → ε（可能 S0 → ε 除外），也不再有 A → B。
  2. 把終端符號從長規則中抽出來。任何右側長度為 2 或以上、卻摻入了某個終端符號 a 的規則都不合法（例如 A → a B）。對每個終端符號 a，發明一個專屬變數 Ta，配上單一規則 Ta → a，並把長規則內部的 a 替換成 Ta。如此 A → a B 變成 A → Ta B 與 Ta → a——兩者都是合法形狀。
  3. 把長右側拆成二元鏈。像 A → B C D E 這樣的規則符號仍太多。用全新的輔助變數一次切下兩個：A → B X1、X1 → C X2、X2 → D E。新變數 X1、X2 的存在只為承接剩下的尾巴，把一條寬規則變成一串嚴格的 A → B C 規則。
  4. 檢查殘餘。在動作 2 與 3 之後，每條規則要嘛是 A → B C（兩個變數）、要嘛是 A → a（一個終端符號），若 epsilon 在語言中則加上那條被容忍的孤零零 S0 → ε。那就是喬姆斯基正規形式。其餘什麼都不必再動。
Start (already epsilon/unit/useless-cleaned):
    S -> a S b | a b

Step 2  (pull terminals out: Ta -> a,  Tb -> b):
    S  -> Ta S Tb | Ta Tb
    Ta -> a
    Tb -> b

Step 3  (binarise the length-3 rule  S -> Ta S Tb):
    S  -> Ta X1
    X1 -> S Tb
    S  -> Ta Tb
    Ta -> a
    Tb -> b

Now every rule is  A -> B C  or  A -> a .   This is CNF.
把 S -> a S b | a b（即 a^n b^n 的文法）轉成喬姆斯基正規形式：一趟終端符號抽取，再一趟二元化。輔助變數 X1 承接剩下的「S Tb」尾巴。

誠實的代價：膨脹與一棵被壓平的樹

現在來談課本有時含糊帶過的警告。這些轉換不是免費的。光是移除 epsilon 產生式就可能讓規則數量大致平方成長，因為一條含 k 個可空符號的規則會展開成至多 2^k 個變體（那些符號的每個子集，要嘛保留要嘛丟棄）。終端符號抽取與二元化兩趟又添加更多輔助變數。標準的保證是：最終 CNF 文法的大小是原文法的多項式——但那個常數可能很討厭，而粗心的順序（尤其是在移除 epsilon 規則之前先移除單位規則）能讓情況劇烈惡化。這就是正規形式膨脹，它是真實存在的。

更微妙的代價是剖析樹會「改變」。你那美麗的原始文法或許曾把一個算術表達式分組成：每個加號坐在一個整齊的節點上，帶三個子節點——運算元、加號、運算元。二元化之後，像 X1 這樣的輔助變數會把自己接插進樹裡，於是一個本來是單一扁平節點的運算子，變成一小段由雙子節點構成的階梯。所生成的字串完全相同，字串的集合——語言——也原封不動，但你從樹上讀出的結構「形狀」，已不再是你當初設計的形狀。果實存活了；輪廓沒有。

所以把喬姆斯基正規形式當成一個「內部」工具，而非用來欣賞的最終產品。它是 CYK 演算法堅持要的輸入格式，也是讓幫浦引理得以被證明的槓桿——這兩件工作都只在乎語言被保留、分枝是二元的，而不在乎樹漂不漂亮。當你真正想要一棵對編譯器有意義的樹時，你會用自己精心設計的文法去剖析，把 CNF 留給證明與判定器。下一篇轉向另一種正規形式——Greibach 正規形式，它的每條規則都以一個終端符號開頭——它不是為二元樹而生，而是為由上而下的剖析以及與下推自動機的乾淨連結而生。