上下文無關語言:化簡與正規形式

文法化簡(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。

修剪死變數及提到它們的規則,而不改變所產生的語言。

化簡保持語言不變,但可能改變剖析樹。若語意動作附在被刪除的規則上,必須移到別處,否則語意會遺失。

又称
grammar cleanupgrammar normalization preprocessing文法清理文法淨化