上下文無關語言:化簡與正規形式
單位產生式(unit production)
想像手機裡有個聯絡人,內容只寫「請見另一位聯絡人」,而那位又只寫「請見再另一位聯絡人」。一路跟著查下去毫無所獲,直到終於碰到一個真正的電話號碼。單位產生式就是這樣一條規則:它什麼也不做,只是把你轉介給另一個單一變數,本身沒有任何有用內容。
形式上,單位產生式是形如 A -> B 的規則,其中 A 與 B 都是變數(非終端符號)——一個變數改寫成恰好另一個變數,僅此而已。在推導中這只是把當前變數改名:A => B,而你還有事要做。例如在 E -> T, T -> F, F -> a 中,從 E 推導出「a」逼你走 E => T => F => a,前兩步都是單位產生式,除了把你接到 F 之外一無所成。這類鏈常自然出現在編碼優先序的文法中(表達式、項、因子),但對機器而言純屬額外負擔。
單位產生式對定義語言無害,但會用多餘的單子節點塞滿剖析樹,而且在喬姆斯基正規形式中是被禁止的。因此有個清理步驟會移除它們:凡是 A 能透過一串單位產生式到達 B,就把 B 的非單位規則直接複製到 A 上,然後刪掉那些單位規則。這通常在 ε-移除之後進行,因為移除 ε-產生式可能製造出新的單位產生式。
E -> T | E+T, T -> F | T*F, F -> a | (E):其中 E -> T 與 T -> F 是單位產生式。要移除 E -> T,你把 T 的非單位規則 T*F 複製到 E 上,得到 E -> E+T | T*F | F,依此類推,把優先序鏈攤平。
單位產生式 A -> B 是無內容的改名;清理時把 B 的真實規則複製到 A 上。
像 A -> a(單一終端符號)這樣的規則並不是單位產生式——兩邊都必須是變數。A -> a 是合法的,事實上它正是喬姆斯基正規形式允許的兩種形狀之一。
又称
另见