移除無用符號、空字串規則與單一規則

為何要在進入正規形式前先清理？

在前一篇你看到了為何正規形式重要：一個整潔、可預測的文法形狀，能讓後續演算法（剖析、成員測試、證明）假定一個固定的骨架，而不必去應付人類可能寫出的每種怪癖。但你不能把一個未經處理的文法直接倒進喬姆斯基正規形式——它通常夾帶三種雜物，會把轉換機制噎住。本篇就是清理班底：三道具體的文法簡化工序，剝除雜物，卻讓所生成的語言「完全」不變。

三種雜物是：無用符號（在任何真正的推導中都不出力的變數）、空字串產生式（形如 A → ε 的規則，讓一個變數蒸發成無物）、以及單一產生式（形如 A → B 的規則，只是把一個變數改名成另一個，並不展開出任何真正的字母）。它們都不違法——一個上下文無關文法大可同時含有這三者——但每一種都破壞了正規形式所要求的「每條規則都做實事」的整齊形狀。我們一道工序、一道工序地移除它們。

第一道：移除無用符號

一個符號唯有在「某個從起始符號出發、生成真正終端字串的推導」中出現，才算是有用的。要有用，一個變數必須跨過「兩道」彼此獨立的關卡。第一，它必須是可生成的：從它出發，最終能抵達一串純終端符號。一個不可生成符號是死胡同——像 S → A B 裡 A 永遠無法落底成真正的字母，於是 S 也永遠收不了尾。第二，它必須是可達的：從 S 出發，某個推導確實抵達了提及它的句型。一個不可達符號則是一座沒有任何從 S 出發的推導造訪過的孤島。

未能通過「任一」道關卡的符號就是無用符號，可以連同每一條提及它的規則一起刪掉。每道關卡都用一個簡單的「集合增長（不動點）」程序來計算。可生成：先標記每個擁有「右側全是終端符號或 ε」之規則的變數；接著持續標記任何擁有「右側只由已標記符號組成」之規則的變數；重複到再也標不出新東西為止。可達：先標記 {S}，接著標記每個出現在「左側變數已被標記」之規則右側的符號；重複到不動點。

Grammar:   S -> A B | a      A -> a A | a      B -> S B      C -> b

Step 1  generating?   A yes (A -> a),  S yes (S -> a),  C yes (C -> b),
                      B NO  (only rule B -> S B always still has a B; never bottoms out)
        delete B and every rule using it ->   S -> a      A -> a A | a      C -> b

Step 2  reachable from S?   S yes.  From S -> a, nothing else is mentioned.
        A and C are never reached ->   delete them.

Result:    S -> a            (same language { a }, all clutter gone)

B 不可生成（它唯一的規則永遠留著一個 B），所以先走；接著 A 與 C 結果不可達。先做可生成、再做可達，正是讓這一步乾淨的關鍵。

第二道：移除空字串產生式

一個空字串產生式是規則 A → ε：它讓變數 A 悄悄消失，貢獻空字串 epsilon。正規形式容不下一個能在某條右側中途消失的變數，所以我們要把它們除掉。空字串產生式移除的訣竅，是「預見」一個變數可能蒸發的每一處，並事先烤好所有較短的替代版本，這樣我們就再也不需要那套消失把戲。

找出「可空」變數——那些能推導出 ε 的變數。標記任何有規則 A → ε 的 A；接著標記任何擁有「右側完全由已可空變數組成」之規則的 A；重複到不動點。（與先前相同的集合增長思路。）
對每一條既有規則，產生「刪去其右側若干個可空出現處之子集」所得到的每一個版本。規則 B → X A Y（A 可空）會衍生出 B → X A Y 與 B → X Y；若有多個可空出現處，就涵蓋每一種保留或刪除的組合。
刪掉每一條 A → ε 規則。接著丟棄任何會重新引入 A → ε 的「全空」版本，這樣你就絕不會重造你剛移除的東西。
一個誠實的例外：若「原始」語言本身含有 ε（S 能推導出 ε），那麼沒有空字串規則就生不出 ε。標準作法是在一個「全新」的、不出現在任何右側的起始符號 S0 上，保留唯一一條 S0 → ε，這樣那條僅有的、被允許的空字串規則，就絕不會污染任何其他規則。

具體地，取 S → A B、A → a A | ε、B → b。這裡 A 可空。用保留或刪除規則展開 S → A B，得到 S → A B 與 S → B；刪掉 A → ε 後留下 A → a A，又因為 A 可消失，也留下 A → a（A → a A 中刪掉 A 的版本）。清理後的最終文法：S → A B | B、A → a A | a、B → b。把任意字串用兩種文法各追一遍，你會得到相同的語言——但注意文法變大了，而像「b」這樣的字串現在擁有一棵與先前不同、更短的樹。這正是我們在上面註記中接受的代價。

第三道：移除單一產生式

一個單一產生式是形如 A → B 的規則：一個變數直接改寫成「另一個單一變數」、別無他物。它不做真正的生成工作——它是純粹的改名、一個官僚式的轉寄地址。它們串成的鏈（A → B → C → ...）只是在真正的字母出現前把一個記號倒來倒去。移除單一產生式把這些鏈短路掉，使每條規則都產出具體的東西。

機制如下：對每個變數 A，找出「只」用單一產生式能從 A 抵達的每個變數 B——稱這些為單一對 (A, B)。（用同樣的不動點集合增長技巧來算。）接著對每個這樣的對、以及每條「非單一」規則 B → α（右側不是單一變數），把規則 A → α 直接加到 A 上。最後刪掉所有單一產生式。如今 A 一跳就繼承了它經由一連串改名所能抵達的每個具體右側。

範例：S → A、A → B | a、B → b。從 S 出發的單一對是 (S, S)、(S, A)、(S, B)；從 A 出發的是 (A, A)、(A, B)。非單一規則是 A → a 與 B → b。於是 S 繼承 S → a 與 S → b；A 繼承 A → b（它本來就有 A → a）。刪掉單一規則 S → A、A → B。結果：S → a | b、A → a | b、B → b。（A 與 B 如今從 S 不可達，這提醒我們：在最末尾再掃一次無用符號往往是值得的。）語言仍是 { a, b }，再無任何改名。

工序的順序，以及誠實的代價

現在來談把三道工序綁在一起的關鍵——你套用它們的順序並非隨意；做錯順序，一個你已經完成的清理會自己撤銷。標準的安全序列是：(1) 移除空字串產生式、(2) 移除單一產生式、(3) 移除無用符號（先不可生成、再不可達）。其推理是一連串「別讓較早的工作重新引入你已移除的垃圾」：空字串移除可能「製造」出新的單一產生式（從 B → A C 刪掉一個可空符號會留下 B → A），所以空字串先、單一其次。而單一移除可能留下一些從 S 沒有路徑可達的孤立變數，所以無用符號掃除殿後收尾。

對這些轉換的代價要誠實。它們保持語言不變，但「不」免費。文法可能膨脹：空字串移除尤其能把一條含 k 個可空符號的規則炸成至多 2^k 個變體，而繼續轉成喬姆斯基正規形式或格雷巴赫正規形式又會再添更多——教科書對整條流水線的界限大約是文法大小的平方等級，而常數可能很傷。這就是你該預期的正規形式爆量。同等重要的是，剖析樹會改變：清理後的文法生成相同的字串，卻指派給它們不同的樹，所以你附加在原始樹形狀上的任何意義（優先序、結合性）並不會自動被保留。

雜物清除後，你現在擁有一個「每條規則都做實事」的文法：沒有一無所獲的符號、沒有會蒸發的規則、沒有只是改名的規則。這正是「下一篇」所需的起飛台。在第三篇，我們把這個乾淨文法一路推進喬姆斯基正規形式——每條規則要嘛 A → B C（兩個變數）、要嘛 A → a（一個終端符號）——而你將看到，那些嚴格二元的剖析樹，正是驅動 CYK 剖析演算法與上下文無關幫浦引理證明的力量所在。