動機
有限自動機無法匹配任意深度的嵌套,因為匹配需要不受限制的計數。上下文無關文法直接描述嵌套結構:像 這樣的規則表示,一個平衡塊是一個左括號、一個平衡塊、一個右括號,再接一個平衡塊。下推自動機是與之對應的機器,即帶有後進先出堆疊的有限控制器。本節證明兩者在一個方向上的精確聯繫——從文法到堆疊機器——然後證明一個為該語言類劃定邊界的泵引理。
泵引理顯式使用喬姆斯基(Chomsky)範式作為前提;配套筆記範式與堆疊計算中隱藏的文法給出該前提及 NPDA 到文法的完整證明。本節從文法到機器的證明不依賴反向構造。
定義
定義 2.4.1
(上下文無關文法與推導)
上下文無關文法(CFG)是 ,其中 是有限的變元集, 是與 不相交的有限字母表, 是有限的規則集,記作 , 是起始變元。若 由 把某個變元出現 按規則 替換為 而得,記作 ; 是其自反傳遞閉包。語言為 ,若一個語言等於某個 CFG 的 ,則稱它是上下文無關語言。若每一步都替換最左邊的變元,則該推導稱為最左推導。
定義 2.4.2
(語法分析樹、產出與歧義)
語法分析樹以起始變元為根,每個內部節點標記為一個變元,其子節點依次拼出某條規則的右部,葉子標記為終結符或 ;其產出是沿葉子讀出的字。 的每個字都是某棵語法分析樹的產出;每一步展開最左邊尚未展開的變元,每棵分析樹就給出一個最左推導。若某個字有兩棵不同的分析樹(等價地,兩個不同的最左推導),則稱該文法是有歧義的。
定義 2.4.3
(非確定型下推自動機(空堆疊接受))
NPDA 是 ,其中 是有限集, 是初始堆疊符號, 的有限子集。格局是 :狀態、尚未讀入的輸入,以及堆疊內容(堆疊頂部在左)。若 ,,則 。若對某個 有 ,則機器以空堆疊接受 。
這一約定是一種選擇。按終態接受是另一種常見約定;兩者等價是標準定理,此處不予證明,因此下面所有關於 NPDA 的陳述都指空堆疊接受。
定理
定理 2.4.4
(兩個基本文法)
(a) 文法 恰好生成 。(b) 稱 上的字平衡,如果其左括號與右括號個數相等,且每個前綴中左括號不少於右括號。文法 恰好生成全部平衡字,並且每個平衡字恰有一棵分析樹。
定理 2.4.5
(從文法到堆疊機器)
設 是 CFG。定義 :只有一個狀態 ,堆疊字母表為 ,初始堆疊符號為 ,轉移為:對 ,;對 ,;再無其他轉移。則 以空堆疊接受的恰好是 。
定理 2.4.6
(上下文無關語言對並、連接與星號封閉)
若 是上下文無關語言,則 、 與 也是。
定理 2.4.7
(上下文無關語言的泵引理)
假設範式定理成立:每個上下文無關語言 都有一個喬姆斯基範式的文法(每條規則形如 或 ),它生成 。在此假設下,若 是上下文無關語言,則存在 ,使每個滿足 的 都可寫成 ,其中 ,,且對每個 有 。
證明思路
證明
(基本文法:對推導的歸納)
基本文法。 (a) 對推導長度歸納:從 推出的終結符字要麼立即使用 ,要麼以 開始,其餘推導從 產出 ,所以該字為 。反之, 由 次使用 再使用 得到。
(b) 可靠性對推導長度歸納: 的產出是一個括號、一個平衡字、一個括號和一個平衡字,這些構造保持前綴條件。完備性對長度歸納。設 非空且平衡;它以左括號開頭。令 為使前綴的兩種括號個數相等的最小正長度,由於 本身個數相等,它存在。對小於 的正前綴長度,左括號個數嚴格多於右括號,所以第 個符號是右括號,且長度為 的前綴的多出量恰為一。於是 ,其中 (第 至第 位)兩種括號個數相等且每個前綴多出量非負,而 平衡,因為 之後的前綴多出量非負,而長度為 的前綴多出量為零。 與 都更短,故應用歸納假設。唯一性:非空 的任何分析樹根處必用 ,而分解 ( 平衡)被迫取為第一次回到零的位置,因為平衡的 後接一個右括號恰在該處首次回到零。對長度歸納即得各子樹唯一。
證明
(從文法到 NPDA:兩個包含方向)
從文法到 NPDA。 的每個字都被接受。 取最左推導 ,寫 ,其中 為終結符串, 為空或以變元開頭。最左推導從不修改終結符前綴,所以 (某個 )。我們斷言對每個 有 。 時顯然。歸納步驟中,,所用規則為 。規則轉移把堆疊上的 替換為 ,然後寫 ( 為終結符串, 以變元開頭或為空),轉移 把 的符號與輸入逐個匹配彈出,這是可行的,因為 。當 時,堆疊為空且輸入已讀完。
每個被接受的字都屬於 。 我們證明:若 ,,且 ,則 。對 作強歸納。若 為終結符,唯一可用的轉移是用輸入符號 彈出 ,所以 。若 為變元,第一步是規則轉移到 ,其中 。若 ,堆疊已為空,。否則,每一步只檢查並替換堆疊頂部符號,恰好移除一個符號並壓入若干符號,所以堆疊的高度每步至多下降一。令 為堆疊首次等於 的時刻。在 到 的這段時間裏,高度始終高於 ,所以 從未被觸及,這一段是從 到 的計算,其中 是這一段讀入的輸入。於是 ,每段都短於 ,由歸納假設 。故 。對 應用即得結論。
證明
(對聯集、連接與星號的封閉性)
封閉性。 重新命名後設變元集不相交,起始變元分別為 。取新的 ,並併入規則:並用 ,連接用 ,星號用 。由於變元集不相交,從 與 出發的兩個子推導互相獨立地演化。這分別給出 、 與 ,最後一個對 的使用次數歸納。
證明
(由語法分析樹的高度推出泵引理)
泵引理。 設 是 的範式文法,有 個變元,令 。在分析樹中,每個內部節點要麼有兩個變元子節點,要麼有一個終結符子節點。因此對高度 (最長根到葉路徑上的邊數)歸納可知,高度為 的樹至多有 個葉子。取 的 及其分析樹。它的高度滿足 ,所以最長路徑上至少含 個變元節點。在這條路徑最低的 個變元節點中,由鴿巢原理有兩個帶有同一變元 ;設為 (在上)與 (在下)。 處的子樹高度至多為 ,所以其產出 ( 為 子樹的產出)滿足 。由於 有兩個子節點,其中一個指向 ,另一個子節點的產出非空(此完整分析樹的旁支均有非空終結字作為產出),且落在 或 內,所以 。把 處的子樹換成 處子樹的副本,得 ;把 處的子樹反覆換成 處子樹的副本,得 。
證明透視
上下文無關泵引理中的依賴關係
證明建立在三個支撐上。第一,範式假設使樹成為二叉的,從而把高度界轉化為葉子數界,並保證有一個旁支貢獻非空產出;沒有它,像 或 這樣的規則可能使 為空。第二,鴿巢原理作用於同一條最長路徑上的變元,這決定了 。第三,同一變元 出現在兩個節點,意味著下方節點的子樹可以替換上方節點的子樹,或被其替換,而結果仍是合法的分析樹。論證以讀出各部分產出作結。
反例模式
上下文無關語言對交與補不封閉
斷言(錯誤):若 與 是上下文無關的,則 也是。取 與 ,可由 、、 及其鏡像生成。兩者都是上下文無關的,但 ,由泵引理它不是上下文無關的(見關於 的例題)。補也不封閉:若該類對補封閉,又因它對並封閉,則 將是上下文無關的。修正:對並、連接與星號封閉是成立的;與正則語言求交也封閉,但此處不證明。
概念視角結構
堆疊作為最左句型中尚未展開的部分
在模擬過程中,最左句型 被分成已消耗的終結符前綴 與放在堆疊上的待處理部分 。因此堆疊恰好包含推導仍需展開或與輸入匹配的內容。規則轉移就是推導的展開,彈出轉移則是把終結符與輸入核對。這就是該構造只需一個狀態的原因:全部控制資訊都在堆疊內容裏。
例題
例題 2.4.8
((())() 的最左推導與分析結構)
用 :。根處的規則把該字分解為 ,其中 ,; 的子推導是第二到第四步, 的子推導是最後三步。由第一個定理的唯一性部分,不存在其他分析樹。
例題 2.4.9
(表達式文法的歧義)
對 ,字 有兩個最左推導: 把它分組為 ,而 把它分組為 。兩棵不同的樹給出不同的解讀,這對求值很重要。以下構造透過把和、積與原子分層,修復這種歧義。我們既要證明終結符字的集合不變,又要證明每個字只剩一棵樹。歧義屬於文法:同一個語言也可能有無歧義的文法。
保持表達式語言不變,修復文法歧義
一句「先乘後加」並沒有改變原文法的產生式;它的兩棵分析樹仍然存在。要讓文法本身規定這個約定,可用三個變元,以 為起始變元:
這裏 表示表達式, 表示項, 表示因子。終結符字母表仍是 。這些規則不含括號、一元運算符或空表達式。記
所以 、 和 屬於 ,而 、 和 不屬於。 的情形就是單獨的字 。
定理 2.4.10
(相同的表達式語言,唯一的分析樹)
原來的單變元表達式文法與分層文法都恰好生成 。分層文法無歧義:它把乘法安排在項的內部,並使連續的加法及連續的乘法均向左結合。
證明
(分層文法生成相同的單詞)
語言相等。 對原文法,按分析樹歸納可知每個產出都在 中:葉子產生式給出 ,而用任一運算符連接兩個 中的字,所得仍在 中。反過來,對 中一個字的運算符個數歸納。沒有運算符時,該字為 。對於更長的字,切出最後一個運算符及最後一個 ,寫成 。按照 選擇 或 ,對左邊的 用歸納假設,右邊推出 。這就證明了原文法語言的兩個包含方向。
對分層文法, 只生成 ,而 恰好生成非空的乘積 :每用一次 ,就加上最後一個因子; 則結束遞歸。這裏 指把「一個字面上的乘法符號後接 」這個雙符號塊重複 次;括號只是記號,不是終結符。 的分析樹則對應一個由 分隔的非空項序列,因為 每次加上最後一項。每個 中的字都有這種分解:在所有 處切開,再把餘下的各塊讀成乘積。這給出它的分層推導。反之,這些產生式只會生成以 開頭和結尾、運算元與運算符交替出現的字。因此,分層文法的語言也恰好是 。
修復後的文法為甚麼只有一棵分析樹
證明
(分層文法的語法分析樹唯一)
對於 ,產出 的樹是唯一確定的。對於一個 字,按乘法符號的個數歸納證明唯一性。沒有乘法時,只能取 。至少有一個乘法時,根處必用 。由於右側 恰好產出一個 ,根處的乘法符號必是字中最後一個 。於是左側子串被唯一確定,且比原字少一個乘法符號。由歸納假設,它有唯一的 樹;右側的 樹也唯一確定。
接著按一個 字中加法符號的個數歸納。沒有加法時,根處不可能用 ,所以只能用 ,而 樹的唯一性已經證明。有加法時,根處不可能用 ,因為項不含 。因此必用 ;其中的 必須是最右邊的加法符號,因為右側的項不能再含 。這同時確定了左右兩個子串。左邊少了一個加法符號,由歸納假設有唯一的 樹;右邊根據前一段有唯一的 樹。因此每個字至多有一棵樹。語言相等的證明已經保證至少有一棵,無歧義性得證。
證明透視
根處的切分必須被迫唯一,而不只是可行
語言相等的論證告訴我們怎樣構造一棵樹,但這本身不能排除另一棵。唯一性依賴右側子節點的限制:因子只是一個 ,項則不能含加法。這些限制迫使項的根乘法位於最後一個乘法符號,表達式的根加法位於最後一個加法符號。隨後歸納處理被唯一確定的較小部分。證明沒有預先假設所希望的優先次序約定,而是從產生式推出該約定。
例題 2.4.11
(先確定根處的切分,再展開樹)
對於 ,最右邊的 迫使根處切成 。在左側表達式中,剩下的 迫使切分為 。乘積 只有一棵 樹。所以最終分組為 ;這裏展示的括號用來描述樹,不是額外加入的終結符。若每個 都取值 ,該樹給出 。 對應的樹會給出 ,但它被排除,因為 子樹不能生成 。
同樣, 在根處切成 ,而 作為項切成 。這些都是左結合的樹。雖然普通加法與乘法滿足結合律,這些特定的重新分組會給出相同數值,但數值相同並不使兩棵樹成為同一棵樹。文法規定語法結構,並不依賴這種代數上的巧合。
甚麼差異才真正說明有歧義?
反例模式
兩種推導次序可能描述同一棵樹
對於 、、,推導 與 確實不同。它們只是以不同次序展開互不依賴的兄弟節點,描述的卻是同一棵樹:根為 ,子節點為 ,終結符葉子為 。只有第一個推導是最左推導。這個文法無歧義。要證明歧義,必須給同一個字找出兩棵不同的樹,或者兩個不同的最左推導;僅有兩個任意展開次序還不夠。
左遞歸也是另一回事。 是左遞歸規則,但上面的證明已經建立無歧義性。若某個樸素分析過程總是優先展開這個遞歸選項,它可能尚未讀取輸入就永遠運行下去。這是該分析過程的問題,並沒有給出第二棵樹。反過來,直接刪除這個選項會丟失所有含 的表達式,也就不能保持語言不變。
快速檢查
((a) 寫出 被迫採用的分組。(b) 保留 ,但把項的規則替換為 ,文法是否仍無歧義?)
解答 · 答案
(a) 先在最後一個 處切開,再在餘下的 處切開,最後處理各項內的乘法。分組為 。(b) 否。字 有一棵左子樹產出 的 樹,也有一棵右子樹產出 的 樹。把任一棵接在 下方,就得到兩棵表達式樹。修復所需的是 右側只能是因子,而不能是任意項;只給層次起不同名字,卻不落實限制,並不足以消除歧義。
例題 2.4.12
(用 M_G 處理 aabb)
對 :。第一、三、五步展開 ,其餘各步彈出一個匹配的終結符,第五步使用 。在恰當的時刻選擇 由非確定性完成;錯誤的選擇,例如過早地用 展開 ,會使堆疊已空而輸入尚未讀完,這不是接受格局。
例題 2.4.13
( 不是上下文無關的)
假設 有泵長度 ,取 。由於 ,因子 不可能同時含有 與 ,因為兩者之間隔著 個 。所以三種字母中至少有一種不在 中出現,而 表明至少有一種字母出現。於是 中出現在 裏的某字母個數增加,而未出現的字母個數不變,三個個數不相等,該字不在 中,與引理矛盾。
常見錯誤
常見錯誤
(歧義屬於文法,而不屬於語言)
常見錯誤之一是把歧義當作語言的性質。它是文法的性質;「固有歧義」才是針對語言的另一個概念。同樣,「上下文無關」並不意味著文法無歧義,也不意味著機器是確定的。一般而言這裏需要非確定性;本節不討論確定型下推自動機。
常見錯誤
(空堆疊接受要同時滿足兩個條件)
本節的 NPDA 以空堆疊接受:接受格局要求輸入耗盡且堆疊同時為空。輸入已全部讀完但堆疊中仍有符號的運行不是接受。
常見錯誤
(要檢查被泵部分的每一種位置)
在對 的泵論證中,長度界 表示 或者落在同一段相同字母之內,或者跨越兩段相鄰的字母塊。完整的論證要處理每一種位置:在每一種位置上, 都沒有觸及某個字母,該字母的個數仍是 ;而泵送至少改變 中出現的某個字母的個數(因為 ),所以三個個數不再相等。只檢查某一種方便的位置並不能證明甚麼。此外,泵引理只能證明一個語言不是上下文無關的,而不能證明它是。
總結
上下文無關文法生成嵌套結構,推導對應於分析樹。分層表達式文法保持終結符語言不變,同時規定唯一的樹,使乘法優先、連續運算向左結合。單狀態堆疊機器模擬最左推導,並以空堆疊接受恰好是該文法的語言;逆向命題見配套範式筆記。上下文無關語言對並、連接與星號封閉,但對交與補不封閉。在範式假設下,泵引理給出 的形式,並表明 在該類之外。
練習
快速檢查
(給出 的文法,並證明兩個包含方向。)
解答 · 答案
用 。從 可達且含變元的句型都形如 ,,因為 增加一個 和一個 , 增加一個 ;最後一步 給出 的 。反之,對 ,先恰好應用 次 ,再恰好應用 次 ,最後應用 。
快速檢查
(證明 不是上下文無關的。)
解答 · 答案
設 為泵長度,。因為 ,它不能同時觸及 和 ,所以四種字母中至少有一種不在 中,且至少有一種在其中。取 泵送會使某一個個數增加而另一個不變,四個個數不再相等,該字不在語言中,矛盾。
快速檢查
(對 CFG ,把每條規則的右部反轉得到 。證明 。)
解答 · 答案
對推導長度歸納,證明對每個變元 和終結符字 , 當且僅當 。長度為一時即規則的定義。對更長的推導, 中的第一條規則 ( 為終結符串)給出 ,其中 ;在 中該規則是反轉後的串,由歸納假設,它產出 ,且每個 由 推出。逆向對稱。
快速檢查
(對 ,列出 接受 的格局序列。)
解答 · 答案
。各步在展開與彈出之間交替,展開 共用了三次。