動機
同一個單詞在上下文無關文法中可能有許多不同的推導,樸素的推導搜尋可能反覆回答相同的問題。換個思路:詢問哪些變元能夠推導出輸入的每一個連續子串。當文法的產生式具有受限的形式時,每棵非平凡的語法分析樹都會分解為兩棵較小的子樹。以子串為索引的表可以重用這些較小的答案,從而無需枚舉全部推導即可判定成員關係。
下面的算法通常稱為 CYK 算法。它的輸入是一個符合指定範式的文法和一個單詞;範式轉換是配套筆記中另行給出的構造。成員判定的答案只針對這個文法和這個單詞,並不涉及兩個任意上下文無關文法是否等價的問題。
定義
設 為有限上下文無關文法。假設每個產生式都具有如下形式之一:,其中 為變元;或 ,其中 為終結符。可以另外容許 ,但此時 不得出現在任何產生式的右側。這就是本文採用的範式約定。對於非空單詞 ,令 表示能夠推導出子串 的變元集合,其中 。
表按子串長度遞增的次序計算。令 。對於 ,當且僅當存在 滿足 ,以及產生式 使得 且 時,把 放入 。對於非空單詞,當且僅當 時接受。對於空單詞,當且僅當存在例外產生式 時接受。
定理
定理 2.3.1
(子串成員關係的正確性)
對於每個非空輸入以及所有 ,計算所得的集合 恰好由滿足 的變元 組成。因此該算法能夠判定文法是否生成該輸入。
定理 2.3.2
(資源界)
對於 ,逐一檢查每個劃分和每個二元產生式的直接實現使用 次基本的產生式檢查,以及 個布爾表項。對成功的表項保存回溯指標後,當輸入被接受時可以重構出一棵語法分析樹。
證明思路或證明
證明
(對長度的歸納與資源計數)
對子串長度進行歸納。長度為一時,變元只能透過終結符產生式推導出單個終結符:二元產生式會產生兩棵非空的變元子樹,而在所述範式下兩者都不能推導出空單詞。因此初始化是精確的。
對於較長的子串,任何語法分析樹的根變元都必須使用二元產生式 。它的兩個子節點產生所得產物的兩個非空且相鄰的部分,由此得到某個劃分 。由歸納假設, 和 出現在對應的較短子串的集合中,所以表中包含 。反過來,若表利用 和某個劃分插入了 ,則歸納假設給出兩部分的推導;先應用該產生式,再應用這兩個推導,就得到整個子串的推導。這就證明了兩個方向的包含關係。例外的空起始規則絕不會出現在非空子樹中,因為起始變元不出現在任何右側。
共有 個子串,每個子串至多有 個劃分位置。在每個劃分處檢查全部二元產生式,共得到 次檢查;終結符的初始化在這個界之內,至多相差通常的讀入輸入以及常數規模的邊界項。布爾表對每個變元和每個子串各有一個表項。對於每個被插入的變元,保存其終結符產生式,或保存一個成功的產生式及其劃分。所記錄的子節點的產物都較短,所以遞歸地沿指標前進必然終止,並給出一棵語法分析樹。每個表項一個指標只足以重構一棵樹,並不足以表示所有可能的分析。
證明透視
範式的每個假設用在哪裏
歸納是對長度 的強歸納,並要求每個劃分都產生兩個嚴格較短的非空區間。三個假設共同保證這一點。形式 使長度為一的樹的根必為終結符規則、較長的樹的根必為二元規則,不必處理第三種形狀。沒有單位產生式,也沒有除 以外的 規則,表示二元規則的子節點不可能推導出空單詞,因此兩個區間都非空,也都短於 。起始變元不得出現在右側,則使 不會出現在任何非空的樹中。唯一不顯然的一步是反向包含:表項是一份證書,每個被插入的變元都帶有兩份較短的證書。只要去掉其中任何一個假設,表中就可能漏掉分析樹放在該處的變元(見「常見錯誤」中的單位產生式例子)。
例題詳解
例題 2.3.3
(兩個符號的單詞)
設產生式為 、、,輸入 得到 和 。唯一的劃分把 插入 。因此 被接受,根產生式為 ,並帶有兩個終結符子節點。
例題 2.3.4
(較長的嵌套推導)
使用 、、、。對於 ,中間的兩個符號 使 進入 。隨後子串 經由 使 進入 。最後,開頭的 與該 使 進入 。所得語法分析樹的產物為 。
例題 2.3.5
(空的表項)
對於第一個文法和輸入 ,每個長度為一的集合都含有 。沒有任何產生式帶有兩個 子節點,所以 為空, 不在其中。算法拒絕該輸入;這一結論來自整個表的構造,而不是僅僅因為沒有找到某一個特定的推導。
常見錯誤
反例模式
只檢驗第一個劃分
斷言:要填 ,只需檢驗劃分 ,因為能推導出 的變元必定透過第一個劃分推導。取 、、、、,輸入 。該單詞確實被生成:。只用劃分 時,得到 和 ,而且不存在形如 的規則,故 ,輸入被錯誤地拒絕。劃分 則給出 (由 )和 ,所以 。修正後的說法就是遞推式本身: 是對所有滿足 的 取聯集。
常見錯誤
(對含單位產生式的文法直接用表算法)
取 、,輸入 。該單詞確實被生成(),但初始化只給出 ,因為 不是產生式,而遞推式不會回頭處理長度為一的情形。於是 ,單詞被錯誤地拒絕。表算法只對已處於所述範式的文法才是精確的;要先消去單位產生式(這裏把 改為 )。
常見錯誤
(把一棵保存下來的分析樹當作無歧義的證明)
取 和 。此時 ,且 同時來自 和 ,即兩棵不同的樹 與 。只保存一個回溯指標只會重構其中一棵。表給出的樹說明單詞屬於該語言,卻不能說明不存在其他的樹。
一個表項可以包含多個變元,一個變元也可以有多個有效的回溯指標。只保存第一個成功的指標,可以保持成員判定的結果以及一棵分析樹,但會丟失關於其他分析的資訊。例外的空單詞必須單獨處理:所示的表中沒有對應長度為零的子串的單元格。
執行表算法
直接實現可以為每個三元組 保存一個布爾標誌。首先把所有標誌初始化為假。對每個輸入位置掃描終結符產生式,並設定相應的長度為一的標誌。然後對長度 ,考慮每個滿足 的 、每個劃分 以及每個產生式 。如果 和 的標誌都為真,就把 的標誌設為真,並可選擇把該產生式和劃分保存為見證。
處理長度 時,任一劃分處的兩個子串長度都小於 。因此更新所讀取的全部標誌都已取得最終值。同一長度的各單元格之間的次序無關緊要。把標誌設為真是單調的:一旦找到了推導,之後失敗的劃分就不得把它重設為假。等價地說,數學上的更新是對所有成功組合取聯集,而不是依據最後檢查的那個組合進行賦值。
例題 2.3.6
(同一單元格的不同劃分)
考慮產生式 、、、、、、。對於輸入 ,根 可以使用 並在第一個字元之後劃分: 推導出 , 推導出 。它也可以使用 並在第二個字元之後劃分: 推導出 , 推導出 。兩者都把同一個變元插入 。一個回溯指標只給出一棵分析樹;若兩個都保留,則能保留根節點兩種分解方式的選擇。
文法中可能含有不能推導出任何終結符串的符號、重複的產生式,或從 不可達的變元。這些符號可以出現在文法的表示中,但不會使歸納論證失效。只有當某個變元得到終結符產生式或一對經過驗證的較短表項的支持時,表項中才包含它。刪去不可達或不產生終結符串的符號可以改進實現,但它並不是本表算法正確性的前提。
回溯指標與歧義性
長度為一的表項的回溯指標記錄產生式 。對於較長的表項,它記錄產生式 、劃分 ,以及兩個子表項。要重構以 為根、涵蓋 的樹,建立一個標記為 的節點,沿著它的指標前進,並在各自指定的區間上遞歸地構造兩個子節點。在每個內部節點處,兩個區間都非空、互不相交且相鄰;它們的聯集就是父節點的區間。因此從左到右讀出的葉子標記恰好還原輸入單詞。
這張表在兩個方向上都是成員關係的證書。如果 出現在最後的單元格中,則指標給出一棵可以局部檢驗的語法分析樹:每個內部節點都使用文法中的一個產生式,每個葉子都與輸入吻合。如果 不出現,則正確性證明顯示不存在任何語法分析樹。單獨一條失敗的搜尋路徑不能給出這樣的否定結論,但在範式假設下,表已經考慮了所有可能的劃分位置和產生式。
歧義文法可以為一個單詞給出多於一棵語法分析樹。僅憑成員關係無法判定歧義性,而一棵重構出的樹也不能說明不存在其他的樹。如果保留每個成功的回溯指標,所得的共享結構可以表示多種分析,但把它們逐一列出所需的空間可能遠大於布爾表。若要斷言枚舉所有分析的代價,就需要計算輸出的規模,並仔細處理共享的子結構。
範式的作用
帶有單位產生式 的文法不適用所示的遞推式。例如,若 且 ,則對於輸入 ,初始化會插入 ,卻不會插入 。同樣,二元推導內部的空產生式可能使某個子節點的產物為空,而這無法用分成兩個非空區間的劃分來表示。把算法原封不動地用於這樣的文法可能產生假的否定結果。要麼先用經過證明的保持語言的方法把文法轉換為規定的形式,要麼改用明確處理這些規則的另一種算法。
範式轉換即使保持語言不變,也可能改變文法及其語法分析樹。回溯指標所給出的樹是轉換後文法的樹。如果應用需要原文法中的樹,轉換過程還必須保留足夠的對應關係,以便把該樹翻譯回去;僅有所生成的語言相等,本身並不能確定這樣的翻譯。配套的構造證明了語言層面的轉換,而本單元證明的是對已處於所需形式的文法的成員判定。
空單詞的約定之所以單獨處理,是因為沒有可填入表中的非空子串。在受保護的起始規則之下, 是起始變元推導出空單詞的唯一方式。如果另一種範式約定容許其他空產生式,則特殊檢驗必須相應調整。對於非空單詞, 可以出現在根處,但它不得出現在右側這一禁止條件,阻止了例外的空規則被用作子節點。
理解複雜度的陳述
長度迴圈中,長度為 的單元格有 個,每個單元格有 個候選劃分。因此單元格與劃分的配對數為 。在每個配對處至多掃描 個二元產生式,就得到所述的三次上界。這個界計算的是一種簡單的實現;按子節點符號為產生式建立索引可能有用,但其數據結構和預處理必須在另外的分析中計入。
空間界計算的是布爾成員標誌。直接的稠密表為 個非空區間中的每一個分配 個標誌。回溯指標需要索引和產生式編號,其位元長度取決於輸入的表示方式;說有 個表項,並不自動等同於有這麼多個位元。稀疏表示在某些輸入上可以節省空間,但其最壞情形的表現和查找代價取決於所選的數據結構。
對於已處於範式的文法,複雜度關於文法規模和輸入長度是多項式的。若從另一種文法出發,則總量中要計入轉換的時間和規模。該定理並沒有說可能的語法分析樹的數目是多項式的:一張緊湊的表可以共享大量部分推導,而完整的樹的數目則可能大得多。
總結
範式把非空單詞的分析歸結為單個終結符,或歸結為分成兩個非空子串的二元劃分。歸納法使表是精確的;整個單詞的單元格中是否含有起始變元決定成員關係,而保存的見證可以重構出一棵語法分析樹。
練習
快速檢查
(對於 、、,計算單詞 的表,並判定其是否屬於該語言。)
先填兩個長度為一的單元格。
解答 · 答案
單字元單元格為 和 。沒有任何二元產生式的子節點依次為 ,所以 ,, 被拒絕。
快速檢查
(對於例題中較長的那個文法,找出一個使 進入子串 所對應單元格的劃分。)
取輸入 和單元格 。
解答 · 答案
把 劃分為 和 。前一部分由 推導(故 ),後一部分由 推導(故 ),所以可以應用 。
快速檢查
(如果在所述範式下不含 ,空單詞會被接受嗎?)
哪些產生式可能產生空的產物?
解答 · 答案
不會。其他所有產生式的產物都非空,而可選的例外規則是唯一的空產生式。
快速檢查
(若只要求一棵分析樹,為甚麼每個變元和單元格只保存一個成功的回溯指標是安全的?)
想想一個指標證明了甚麼。
解答 · 答案
每個保存的指標都證明了對應變元在該子串上的一個推導。沿著較短子串的指標遞歸地前進,就構造出一棵完整的分析樹;對於這個輸出而言,其他推導是不必要的。