動機
一個文法中可能含有永遠不會對終結符單詞有貢獻的符號、僅僅把一個非終結符改名為另一個非終結符的產生式,以及會消失的非終結符。去掉這些特徵,能使後續的構造(例如喬姆斯基(Chomsky)範式)更容易理解。但也很容易刪得過多:刪去全部空產生式會失去空單詞;只在某一個位置刪除可空符號,則會遺漏有效的推導。
我們將給出明確的有限構造,並證明兩個方向的語言包含關係。這些構造保持的是語言,而不一定保持語法分析樹、歧義性或推導長度。它們只是預處理工具,因此其假設條件以及對空單詞的特殊處理都至關重要。
定義
定義 2.5.1
(可空非終結符、空產生式與單位產生式)
設 為有限上下文無關文法,其終結符字母表與非終結符字母表互不相交。當 時,稱非終結符 是可空的(nullable)。右部為 的產生式稱為空產生式,形如 (其中 為非終結符)的產生式稱為單位產生式。
首先引入一個新的開始符號 ,它不出現在任何舊產生式中。加入 。若 可空,則再加入 。新的開始符號不出現在任何右部中。這個預備文法與舊文法生成相同的語言:第一條新規則把推導交給 ,第二條規則只加入了一個本來就已被生成的空單詞。
可空集合按最小不動點求得。先標記每條空產生式的左部。然後反覆進行:若 的某個產生式的右部完全由已標記的非終結符構成,則標記 。終結符不是可空的。有限文法只有有限個非終結符,所以標記過程必然終止。
定理
定理 2.5.2
(空產生式的消除)
從帶新開始符號的文法出發,可以構造出生成相同語言的文法,其中除了可能有 之外沒有空產生式,並且 不出現在任何右部中。
定理 2.5.3
(單位產生式的消除)
從有限文法出發,可以構造出與之等價且沒有單位產生式的文法。若其唯一的空產生式是受保護的 ,且 不出現在任何右部中,則該性質得以保持。
證明
計算可空非終結符
證明
(可空標記的正確性)
每個標記都是可靠的:標記規則把右部所有符號已知的空推導組合在一起。反過來,若 能推導出空單詞,考慮一棵有限的推導樹。其根處的產生式不能含有終結符,而且每個子非終結符都有一棵更小的、推導出空單詞的樹。對樹高作歸納可知,這些子節點最終都會被標記,於是 也會被標記。
這個證明無需猜測就能處理循環。僅有規則 並不會令 被標記:不動點從沒有任何無依據的標記開始。若有 、 以及 ,則先標記 ,再標記 。循環依賴需要一個有限的基礎推導來確立可空性。
消除空產生式
對每條產生式 ,獨立地對每個作為可空非終結符的 的出現選擇保留或刪除,從而生成一個右部。所有終結符的出現以及不可空的非終結符都必須保留。把每個生成的非空右部都作為 的產生式加入,並去除重複項。刪去所有空右部,然後當且僅當原來的開始符號可空時,恢復 。特別要注意,刪除某個重複出現的非終結符的一次出現,與刪除它的另一次出現是不同的選擇,儘管所得的右部可能相同。
證明
(消除空產生式的構造保持語言不變)
為證明每個新推導產生的都是舊單詞,把每條生成的產生式替換為它所來自的舊產生式,並對每個被省略的可空出現插入一個空推導。受保護的空產生式是合理的,因為 原本就可空。因此每個新的終結符單詞都屬於原來的語言。
對於另一方向的包含關係,取一棵生成非空終結符單詞的舊推導樹。刪去每個其終結符產出為空的子樹。在每個保留下來的非終結符處,被刪去的子節點都是可空的出現,所以它餘下的右部正是所生成的備選右部之一。保留根以及其產出對非空單詞有貢獻的子節點。這樣便得到生成同一單詞的新樹。若舊單詞為空,則由受保護的 產生它。兩個方向的包含關係合起來就證明了定理。
證明透視
刪除一個符號相當於表示一整個空推導
由新到舊的包含關係較容易;由舊到新的包含關係才帶有思想。舊樹中的某個可空出現可能位於一棵產出為空的大子樹之上,但新文法無法保留一個其子樹已經消失的非終結符,所以必須在父節點處把這次出現刪去。這就是為甚麼每個出現都獨立地選擇刪除或保留:舊樹逐個出現地決定哪些子節點的產出為空。論證依靠兩個假設。標記過程所提供的、通往空單詞的有限推導,在由新到舊的方向上把空推導放回去,從而證明刪除是合理的。受保護的開始規則則處理唯一無法由任何非空右部表示的單詞,即空單詞本身。沒有這條受保護的規則,構造就會丟失 ,例題中 的情形說明了這一點。
一個含有 個可空出現的右部,在去重之前至多有 種刪除選擇。這可能令單條產生式的規模出現指數膨脹。證明某個構造會終止,並不自動意味著其輸出具有多項式規模的界。
消除單位產生式
在非終結符上建立一個有向圖,對每條單位產生式 連一條邊 。對每個 ,找出所有經由零條或多條單位邊可達的 (包括 本身)。對每條非單位產生式 ,加入 。最後刪去所有單位產生式。單位環不構成困難:圖的可達性只涉及有限個頂點,而且多次複製同一條產生式沒有任何影響。
證明
(消除單位產生式的構造保持語言不變)
就可靠性而言,新加入的 模擬了舊的從 到 的單位路徑,隨後接上 。就完備性而言,取一棵舊推導樹,把每條極大的單位節點鏈壓縮到緊隨其後的第一條非單位產生式。相應的圖可達性使得該非單位產生式被複製到了鏈的起始非終結符。每個有限的終結符推導在每條被壓縮的鏈之後都有這樣一條產生式,所以得到的樹產生同一個單詞。
若 不出現在任何右部中,則除 之外沒有非終結符含有指向 的單位邊。因此只有 能通過單位邊到達受保護的 的源頭,複製步驟不會引入不受保護的空產生式。這就是新開始符號這一限制有用而非裝飾的原因。
單位圖中的零長度路徑至關重要。它保證 已有的每條非單位產生式都被複製回 ,即使 沒有任何出邊。若先刪除全部產生式再僅沿正長度路徑複製,就可能誤刪普通的生成終結符的規則。另一種實現方式是保留所有已有的非單位產生式,僅顯式地沿正長度路徑複製;去除重複後,兩種描述給出相同的集合。
反例模式
先消除單位產生式,並不能保證它們不再出現
斷言:單位產生式一旦消除,再消除空產生式就不會把它們帶回來。取 、、。這裏沒有單位產生式,所以消除單位產生式甚麼也不改變。只有 可空,從 刪去它便加入 ,這是新的單位產生式,而語言仍是 。補救辦法就是本節採用的次序:先消除空產生式,再消除單位產生式,此例便把 複製成 。
即使有些非終結符從開始符號不可達,該構造仍保持終結符語言。這些多餘的規則可以由隨後的有用符號處理步驟去除。把單位消除與可達性分開,可以簡化證明:單位圖可以對每個非終結符進行處理,而無需先判定它是否參與從開始符號出發的推導。
刪除無用符號
若非終結符能推導出某個終結符單詞(可以是空單詞),則稱其為可產生的(productive)。計算可產生的非終結符的方法是:只要 的某條產生式僅含終結符和已標記的可產生非終結符,就標記 。空右部符合這一條件。刪除每條含有不可產生非終結符的產生式,並刪除不可產生的符號。終結符推導不可能用到這樣的符號,因此這不會刪去任何終結符單詞。
若開始符號是可產生的,則在餘下的文法中計算從它可達的符號:從開始符號出發,沿著左部已被到達的產生式的右部出現進行。刪除不可達的產生式和符號。餘下的產生式中的每個符號都是可達的,且餘下的每個非終結符都是可產生的。從開始符號出發的終結符推導從不經過不可達的符號,所以語言不變。
順序對於「最終文法沒有無用非終結符」這一論斷是重要的。某個符號可能僅通過後來因含不可產生符號而被丟棄的產生式才可達;在可產生性過濾之後重新計算可達性,便能去掉這個新孤立出來的符號。若開始符號不可產生,則語言為空。用一個沒有任何產生式的開始符號單獨表示它;此時開始符號必然不可產生,所以不要聲稱這種空語言的表示中所有非終結符都是可產生的。
反例模式
僅僅可達並不意味著有用
對於 、、,在原文法中 與 都是可達的,但 不能推導出終結符單詞。刪去 這條產生式後, 變為不可達;化簡後的非空語言文法可以直接使用 。
例題詳解
例題 2.5.4
(重複出現的可空符號)
設 ,。 與 都是可空的。產生式 生成非空備選 ;刪除任一個出現都得到同樣的備選 。保留 ,並使用新開始符號來保護空單詞。所得語言為 ,與原來完全相同。
例題 2.5.5
(一個單位環)
對於 ,,,單位圖使 與 互相可達,並使兩者都從 可達。 每個都得到分別生成 和 的兩條非單位產生式。刪去單位產生式後,開始符號的語言仍為 。
例題 2.5.6
(為甚麼需要受保護的開始符號)
若 ,不加補償就刪去空規則會失去 。引入 。可空刪除在 之外加入 ,而單位消除把這些非單位備選複製到 。所得的開始符號仍然推導出 中的每個單詞,包括空單詞,同時沒有任何舊的非終結符需要空規則。
例題 2.5.7
(空語言)
對於 ,,兩個非終結符都不是可產生的:沒有任何有限推導能產生終結符單詞。其語言為空。帶新開始符號 且沒有任何產生式的文法即表示該語言。僅僅發現 是可達的,並不會令它成為可產生的。
常見錯誤
常見錯誤
(可空符號的每個出現都是各自獨立的選擇)
一個非終結符可以在右部中出現多次,並且在修剪後的樹中每個出現各自獨立地存在或不存在。若只對每個符號名稱作一次全局決定,就可能遺漏產生式。例如,若 且 可空,則只保留第一個出現或只保留第二個出現,會產生不同的備選 與 。
常見錯誤
(單位產生式指的是整條右部)
單位鏈是由整條產生式 構成的序列,而不是在其他符號之中含有一個非終結符的產生式。規則 不是單位產生式。類似地,僅有單位環並不能生成終結符單詞;被複製的是有限鏈末端的可產生備選。
常見錯誤
(語言相同並不表示語法分析樹相同)
最後,語言等價並不意味著語法分析結構相同。複製和修剪產生式可能把原本不同的推導合併。不要用這一保持語言的證明去推斷語法分析樹的數量或歧義性得以保持。
總結
可空不動點識別出有限的空推導。刪除可空出現的任意組合並保護開始符號,可以保持每個單詞,包括空單詞。隨後,單位可達性用非單位出口取代單位鏈。先做可產生性過濾再做可達性過濾,便去除了未使用的結構,而空語言另作處理。每一步都有雙向的證明,而不是純粹句法上的論證。
練習
快速檢查
(對於 ,,,列出由 生成的非空備選,並說明開始符號是否需要受保護的空產生式。)
獨立地刪除每個可空的出現,再捨棄空的結果。
解答 · 答案
備選為 、 和 。同時刪去兩者會得到空右部,該右部在此被省略。由於 與 都可空, 也可空,所以新開始符號必須保留其受保護的空產生式。
快速檢查
(對於 ,,,給出一個等價的、無單位產生式的開始產生式。)
沿著從 出發的單位邊走。
解答 · 答案
單位圖中有一條從 到 的路徑。複製非單位產生式 ,得到 。自環 不會帶來額外的終結符產生式。
快速檢查
(解釋為甚麼文法 ,, 的語言為空,儘管每個非終結符都是可達的。)
哪些產生式可以作為可產生性標記的起點?
解答 · 答案
沒有任何含終結符的產生式或空右部可以作為可產生性標記的起點。沒有任何非終結符能推導出終結符單詞。可達性只說明符號出現在可能的推導中,並不保證推導能以終結符結束。
快速檢查
(在 中( 可空),列出通過刪除 的出現所生成的所有互不相同的非空備選。)
共有兩個出現,所以有四種刪除方式。
解答 · 答案
備選為 、、 和 。由於終結符 從不被刪除,它們都是非空的。兩種只刪除一個出現的情形,分別在於被保留的非終結符所處的位置。