葛萊巴赫正規形式

不同的形狀，不同的承諾

你剛認識了喬姆斯基正規形式（CNF），其中每條規則不是 A → BC（兩個變數）就是 A → a（一個終端符號），你也看到了它的回報：每棵剖析樹都變成二元的、推導有固定長度，而這既驅動了 CYK 剖析演算法，也驅動了上下文無關幫浦引理。葛萊巴赫正規形式（GNF）是它的兄弟——同一個上下文無關文法的另一種標準化形狀——但它給的承諾完全不同。在 GNF 中，每一條規則都形如 A → a α，其中 `a` 是單一個終端符號，α（alpha）是零個或多個變數（非終端符號）所組成的字串。右側永遠以一個真正的字母開頭，後面再選擇性地接一些變數。

好好盯著那個形狀，因為整篇都從它流出。你產出的第一個符號永遠是終端符號——絕不是變數。所以你套用任何規則的那一刻，就無可挽回地確定了輸出多一個字母。對比 CNF：規則 A → BC 完全不產出終端符號，只是又給出兩個要展開的東西。GNF 拒絕在純粹的記帳上空轉；它逼你在每一步都花掉一個字母。

為什麼開頭的終端符號這麼值錢

GNF 重要的第一個理由是：它讓由上而下剖析既簡單又誠實。想像你由左到右讀輸入，試著建造一次最左推導——總是展開最左邊的變數。對 GNF 文法，展開任一變數都會立刻吐出一個終端符號。你只需檢查：那個終端符號是否與下一個輸入字母相符？若符合，消耗它並繼續；若不符，那條規則就是猜錯了。每一步都既消耗輸入又做出選擇，所以剖析永遠不會在原地打轉。

更深的理由是所有由上而下剖析的致命敵人：左遞迴。像 E → E + T 這樣的規則，把 E 展開成某個仍以 E 開頭的東西。一個天真的由上而下剖析器，試圖展開 E，會把它再展開成 E、再一次，永遠往下降卻從不讀一個字母——一個不消耗任何輸入的無窮迴圈。GNF 對此在結構上免疫。因為每個右側都以終端符號開頭，沒有任何推導能在一步之後讓變數成為它的最左符號。在 GNF 中，左遞迴不只是不被鼓勵；它根本連寫都寫不出來。

GNF 與下推自動機

GNF 也給出通往下推自動機（PDA）最乾淨的橋——那台帶著一疊盤子、而你永遠只碰最上面盤子的有限狀態機。回想文法與 PDA 的等價：一個文法可由一台 PDA 模擬，它把最左推導中尚未展開的部分放在堆疊上。對任意文法，單一個 PDA 動作可能只是改寫堆疊符號而不讀任何輸入。GNF 讓模擬變緊：因為每條規則都先吐出恰好一個終端符號，PDA 就能在每一個動作上都恰好讀一個輸入字母。

把訣竅明說出來。建一台只有單一控制狀態的 PDA。要處理規則 A → a α：當堆疊頂端是變數 A、且下一個輸入字母是 `a` 時，機器彈出 A、消耗 `a`，並把 α 的各變數推入（反向推，使第一個變數最後落在頂端）。每個動作都讀一個字母，並把 A 換成那條規則所承諾的其餘部分。當堆疊正好在輸入耗盡的同時清空，輸入即被接受。因為讀取與堆疊操作在每個動作上同時發生，一個有 n 條規則的 GNF 文法就以美妙而機械的方式變成一台 PDA。

A GNF grammar for { a^n b^n : n >= 1 }, then a stack trace on 'aabb'

  S -> a S B   |   a B
  B -> b

(every right side starts with a terminal: 'a' or 'b')

Leftmost derivation of aabb:

  S
  => a S B        (S -> a S B)        ate 'a'   stack: S B
  => a a B B      (S -> a B)          ate 'a'   stack: B B
  => a a b B      (B -> b)            ate 'b'   stack: B
  => a a b b      (B -> b)            ate 'b'   stack: (empty) -> ACCEPT

Every single step consumed exactly one input letter -- that is the GNF guarantee.

一個迷你 GNF 文法，以及一次同時也是 PDA 執行的最左推導：每步消耗一個終端符號，堆疊映照著尚未展開的變數。

轉換如何運作（其概念）

你不必背下完整演算法就能爬這座階梯，但看一眼它的形狀是值得的。標準構造從一個已是喬姆斯基正規形式的文法開始，把變數排序為 A1、A2、…、Ak，然後逼出一個單向的流動：它改寫規則，使得每當一條規則的右側以一個變數開頭時，那個變數的編號高於規則的左側。一旦每條規則都以終端符號或更高編號的變數開頭，編號最高的那些變數就已經以終端符號起頭，於是你由後往前代入，把終端符號推到其他所有人的最前面。

清理並轉換：依正確順序移除無用符號、epsilon 產生式與單位產生式，再把文法化為喬姆斯基正規形式，使每條規則為 A → BC 或 A → a。
把變數編號為 A1、…、Ak（任一固定順序），並改寫規則，直到每條右側以變數開頭的規則都以更高編號的變數開頭——這正是在移除左遞迴，常需引入新的輔助變數。
由後往前代入：編號最高的變數已只能以終端符號開頭；把它的規則代入次高者，如此一路向下到 A1，直到每條規則都以終端符號開頭。
以相同方式整理輔助變數，把它們以終端符號開頭的規則代入，使整個文法最終都成為 A → a α 形式。

注意第 2 步——讓變數永遠只指向更高編號的變數——正是摧毀左遞迴的引擎，也正是你接下來會詳細研讀的左遞迴消除技巧。第 3、4 步的代入正是開頭終端符號出現之處。這兩種正規形式並非對手；CNF 通常是你抵達 GNF 的發射台。

誠實的代價

現在來看警告，因為 GNF 並非免費。轉換可能造成真正的文法膨脹：把一個變數的規則代入另一個，會把它們的選項彼此相乘，所以一個有 v 個變數的文法，其規則數可能暴增——標準構造可能產生量級約 v^3 甚或更糟的新產生式。漂亮的 A → a α 形狀，底下可能墊著一份遠比你起初更大的規則集合。小巧與整潔朝相反方向拉扯。

更重要的是，轉換改變了剖析樹。你接受的字串相同——語言不變，這正是正規形式的全部用意——但 GNF 賦予一個字串的結構，通常與你原本那個有意義的文法所給的結構毫不相似。新引入的輔助變數與重排的規則意味著：GNF 剖析樹很適合有效率地證明某字串在語言中，卻不堪作為你交給在意優先級與結合性的編譯器的那種剖析樹。把 GNF 當作理論與剖析的工具，而非你親手撰寫的文法。

最後，存在性定理本身才是真正的獎賞，即使你從不執行那個演算法：每一個不含 epsilon 的上下文無關語言都有一個葛萊巴赫正規形式文法。光是這個事實，就讓理論學者得以假設任何 CFL 都能被一台每步讀一個字母的 PDA 配對，也是證明「文法與 PDA 描述的正是同一類語言」最乾淨的途徑。形狀是一種方便；而「形狀永遠存在」這個保證，才是定理。