正規形式轉換的膨脹(the blowup of normal-form conversion)
把一份隨意的食譜翻成死板、逐行的機器格式會讓它變長,而且讀起來不再像廚師的原作。把文法轉成正規形式有同樣的兩種代價:文法可能變大,有時大得多;而剖析樹改變形狀,使任何釘在舊規則上的語意鬆脫飄走。這個條目就是對這些代價的誠實清算。
大小膨脹:每個清理或塑形步驟都可能讓規則倍增。移除 ε-產生式可能把一條含 k 個可空變數的規則變成多達 2^k 條規則。單位產生式移除四處複製繼承來的規則。CNF 二元化增加輔助變數並拆分長規則。Greibach 正規形式通常是最嚴重的:移除左遞迴並代入以把終端符號放到前頭,可能讓文法膨脹一個很大的多項式倍甚至更糟,往往遠超 CNF 的增長。對 CNF 而言,增長通常被原大小的某個多項式所界定,但常數與確切界限取決於構造,而草率的轉換可能不必要地龐大。
語意膨脹:每個正規形式轉換都會重寫剖析樹。一條曾產生有意義節點的規則(譬如帶兩個運算元的算術運算子)被輔助變數與二元拆分取代,於是原本的推導結構消失了。若你把語意動作——型別檢查、建構抽象語法樹、計算數值——附在原規則上,這些動作必須重新接到新規則上,或以其他方式找回,否則語意會悄悄遺失。這就是為什麼正式的編譯器常用原始(可能左遞迴)文法剖析,而把 CNF 主要保留給理論用途與 CYK 成員測試,而不去轉換工作中的文法。
一條規則 A -> B C D E,若 B、C、D、E 四者皆可空,在 ε-移除時會展開成每一種出現變數的子集:2^4 = 16 條規則(減去全空的那條)。再疊上 CNF 二元化與輔助變數的增加,一個精簡的源文法就能膨脹成大得多的正規形式文法。
光是可空變數就能造成指數級的規則增長;CNF 與 GNF 還會再加上倍數。
正規形式轉換絕不改變語言,但確實改變文法大小與剖析樹形狀。把附在舊規則上的任何語意動作當成你必須明確遷移的東西,而不是當成能免費撐過轉換的東西。