移除單位產生式(removing unit productions)
若聯絡人 A 寫「請見 B」,B 寫「請見 C」,而 C 終於列出一個真正的號碼,你可以把那個號碼直接寫進 A,替大家省時間。移除單位產生式對文法做的正是這種短路:你追蹤每一條變數對變數的改名鏈,把真正帶有內容的規則複製到最上層,這樣就能刪掉那些改名。
這個方法使用單位對(unit pair)。若 A 僅用單位產生式就能推導出 B,則 (A, B) 是一個單位對——包括平凡的 (A, A)。你藉由跟蹤鏈來計算所有單位對:若 (A, B) 是單位對且 B -> C 是單位產生式,則 (A, C) 也是。接著,對每個單位對 (A, B),把 B 的每條非單位規則加到 A 上;亦即若 B -> alpha 本身不是單位產生式,就加入 A -> alpha。最後刪掉所有單位產生式。所得文法產生相同語言,但不含任何「變數 -> 單一變數」形狀的規則。
這個步驟排在 ε-產生式移除之後,理由很具體:消除 ε-產生式可能把一條兩符號規則變成單變數規則(例如 A -> BC 而 B 可空,會產生 A -> C,一條全新的單位產生式),所以你必須先清掉 epsilon,否則會留下單位產生式。移除單位產生式是喬姆斯基正規形式所必需。它可能增加規則數,因為每個變數會繼承它能透過改名到達的一切的非單位規則,但其增長相較於 epsilon 與 CNF 二元化步驟而言是溫和的。
E -> E+T | T, T -> T*F | F, F -> (E) | a。單位對包含 (E,T)、(E,F)、(T,F)。把非單位規則向上複製:E -> E+T | T*F | (E) | a, T -> T*F | (E) | a, F -> (E) | a。改名 E->T、T->F 消失了;語言不變。
每個變數吸收它能透過改名到達的一切的真實規則,然後那些改名消失。
在 ε-移除之後、刪除無用符號之前進行單位移除。移除單位可能暴露新的非生成或不可達符號,因此無用符號的處理應放在清理的最後一步。