文法化簡(grammar simplification)
整修房子之前你會先清掉雜物:沒人搆得到的破家具、沒有門的房間、接到虛無的電燈開關。文法化簡就是對上下文無關文法做同樣的整理。它移除那些徒增雜亂卻不改變文法產出的規則與符號,留下一個更精簡、卻產生完全相同語言的文法。
化簡是一連串保持語言不變的清理步驟。首先移除 ε-產生式(epsilon-production),即形如 A -> epsilon(空字串)、讓變數消失的規則;接著移除單位產生式(unit production),即僅把一個變數改名為另一個的規則 A -> B;再移除無用符號(useless symbol),它分為兩類:非生成符號(non-generating symbol,永遠無法推導出終端符號字串的變數,是死路)與不可達符號(unreachable symbol,起始符號永遠到不了、因此永不被用到的變數)。塵埃落定後,你得到一個沒有空規則、沒有純改名規則、也沒有累贅的文法,而原語言的每個字串仍可被推導出來。
化簡之所以重要,是因為它是把文法轉成正規形式的前半段。例如喬姆斯基正規形式依定義沒有 ε-規則也沒有單位規則,所以你必須先清掉這些。它也讓文法更小、剖析更快、更容易推理。步驟順序並非隨意:移除 ε-產生式可能製造出新的單位產生式,移除符號也可能製造出新的無用符號,因此各步驟必須謹慎排序(見「化簡步驟的順序」)。
給定 S -> AB | a, A -> a, B -> B, C -> aC,其中 C 從未出現在可達的右側,而 B 只會改寫成自己:B 是非生成符號(它只能永遠變成 B),C 從 S 不可達。清理會刪掉 B、C 以及規則 S -> AB,留下 S -> a, A -> a,產生的同樣是單一字串 a。
修剪死變數及提到它們的規則,而不改變所產生的語言。
化簡保持語言不變,但可能改變剖析樹。若語意動作附在被刪除的規則上,必須移到別處,否則語意會遺失。