動機
CYK 算法之所以可行,是因為每棵非空語法分析樹的根都具有特別簡單的形式:它要麼產生一個終結符,要麼把詞分成兩個非空的部分。任意的上下文無關文法未必具有這種結構:它可能含有很長的右部、終結符與非終結符混雜的右部、重新命名規則以及空產生式。要把 CYK 應用到這樣的文法上,我們需要一種轉換,而其證明要說明:為甚麼每個原有的詞仍然有分析樹,又為甚麼不會出現新的詞。
範式是關於語言的陳述,而不是關於保持原有推導的陳述。化簡可能把若干條原有推導合併為同一條規則。如果目標是計算分析樹的數目或證明歧義性,僅有語言等價並不能提供足夠的資訊。因此我們將精確地記錄這一構造究竟保證了甚麼。
定義
定義 2.6.1
(帶保護起始符的喬姆斯基範式)
上下文無關文法由有限且互不相交的變元集與終結符集、有限的產生式集 以及一個起始變元組成。我們採用帶保護起始符的喬姆斯基(Chomsky)範式:每條產生式都具有下列形式之一
其中 是變元, 是終結符,最後一種規則是可選的。新的起始符 不出現在任何右部中,特別地,它不能作為二元規則的子節點。除此之外沒有其他空規則,也沒有變元到變元的單位產生式。產生式集容許為空,此時文法生成空語言。
配套的「文法化簡」單元證明了一個可有效實現的預處理定理:對任意有限的上下文無關文法,可以得到一個與之語言等價的文法,它帶有受保護的新起始符,除可能的 外沒有空產生式,也沒有單位產生式。我們在此使用該定理,並在其後明確說明轉換過程。刪除無用變元對於範式而言是可選的,語言等價的論證並不需要它。
定理
定理 2.6.2
(每個上下文無關語言都具有這種範式)
對每個有限的上下文無關文法 ,存在一個可有效構造的、具有上述帶保護起始符範式的文法 ,滿足 ;當空詞屬於該語言時,空詞同樣包含在內。
定理 2.6.3
(非空範式分析樹的形狀)
在帶保護起始符的範式文法中,長度為 的非空詞的每棵分析樹恰有 個終結符產生式節點和 個二元產生式節點。當 時,其根是一個終結符產生式;當 時,其根是一個二元產生式,且兩個子節點的產出串均非空。
證明
證明:分離終結符並將鏈二元化
證明
(終結符代理與右鏈保持語言不變)
從預處理後的文法出發。每個非空右部的長度至少為一。長度為一的右部必然是終結符,因為單個變元會是單位產生式。受保護的空規則(若存在)本來就是容許的,保持不變。
對於出現在長度至少為二的右部中的每個終結符 ,創建一個新變元 ,其唯一的產生式為 。在每個這樣的長右部中,把 的每次出現替換為 。已有的單終結符規則保持不變。這樣得到的非空規則,其右部要麼是一個終結符,要麼是至少兩個變元組成的序列。替換是同時進行的,並且沒有任何 被用作起始符。
為甚麼這保持語言不變?在舊的分析樹中,把兄弟節點之間出現的每個終結符葉子替換為一個 節點及其子節點 。反之,新分析樹中的每個 節點恰有這一個終結符子節點,把它收縮即可。這些變換都保持從左到右的葉子詞不變。由於這些新變元沒有其他產生式,反向變換不會引入舊規則中原本不存在的選擇。
現在考慮每條長度 的規則
其中每個 都是變元。引入專屬於該規則的新變元 ,並把它替換為鏈
當 時,這恰好是 與 。已有的長度為二的規則保持不變。這條鏈中的每個新變元恰好只有所列出的那一條產生式,且沒有其他舊規則使用它。因此,展開這條鏈必然按順序強制出原來的序列 。反過來,使用原規則的節點可以展開成這條鏈,而不改變其子節點的產出串。這就得到兩個方向上的語言包含關係。
轉換之前,受保護的起始符不可能出現在任何右部中。該過程只插入新的代理變元與鏈變元,所以之後它仍然不可能出現在右部中。該過程也不引入空規則或單位產生式。因此所得文法恰好具有所要求的形式,並且語言相同;當且僅當其受保護的空規則存在時,它才包含 。這就證明了第一個定理。
證明透視
為何新變元使收縮精確成立
必須同時成立兩件事:新文法不多生成任何東西,也沒有遺漏任何東西。「不多生成」用到新變元的唯一性。鏈變元 恰好出現在一條規則的右部,並且只有一條產生式,所以它的任何使用都展開為原序列 ,把完成的鏈收縮就得到舊規則的一次合法使用。若 被兩條規則共用,收縮就可能把一條規則的前段接到另一條規則的後段,這正是下面「一條規則中的四個變元」例題所展示的失敗。「沒有遺漏」是較容易的方向:把每個舊規則節點展開為它的鏈。不明顯的一步屬於簿記:選取專屬於該規則及位置的名稱;論證之所以封閉,是因為收縮由葉子向上、逐個完成的子樹進行。
證明:二叉樹的內部節點比葉子少一個
證明
(計算滿二叉樹的節點數)
對於一個非空的被推導詞,可選的 不可能出現在根以下,因為 不出現在任何右部中;它也不可能用在非空產出串的根上。因此每個節點要麼是二元的,要麼恰有一個終結符子節點。該詞有 個終結符葉子,因此有 個終結符產生式節點。
把每個終結符產生式節點與其終結符子節點收縮為一個葉子。剩下的有根樹是滿二叉樹。設它有 個二元內部節點,數其邊數得 ,故 。特別地,二元規則的子節點不可能推導出空詞:除受保護的起始符外,沒有變元具有空推導。這恰好就是 CYK 所用的「非空劃分」假設。
概念視角組合
把範式分析樹看作詞的括號化
非空分割性質說明,每個二元節點都把詞的一個區間分成左右兩個區間,且兩者都非空。因此,長度為 的詞的範式分析樹,就是對其 個字母的滿二元括號化,並以變元作標記;它的 個二元節點正是作出分割的 個位置。這恰好是 CYK 表所索引的區間結構:一個區間所對應的格,由它兩個部分的格兩兩配對填入。
例題詳解
例題 2.6.4
(混合產生式)
設預處理得到 與 ,其中受保護的起始符為 。引入 與 ,得到臨時規則 。再引入新變元 使之二元化:
兩個文法恰好都只生成 。位於 之下的那個 使用 ;最後一個 使用代理 。它們碰巧有相同的終結符產出,但在分析樹中的角色並不相同。
例題 2.6.5
(空詞與單個字母)
文法 生成 。一個有效的帶保護起始符的範式文法為
根 從不出現在右部中。規則 給出長度為一的情形;二元規則每次在前面添加一個 。若省去 ,恰好會丟失空詞。
例題 2.6.6
(一條規則中的四個變元)
對於 ,使用新變元 以及三條規則 、、。若 分別生成 ,則新的樹按相同順序產出 。如果從某個無關的產生式中重用 ,就會給它增加額外的選擇,從而生成原規則不容許的詞。
例題 2.6.7
(空語言)
如果原文法為 ,則不能推導出任何終結符詞。帶有新起始符且沒有任何產生式的文法已經符合我們的範式,並且生成同樣的空語言。我們不必僅僅為了讓文法看起來非空而人為製造一條終結符產生式。
常見錯誤
反例模式
重新命名不是範式規則
一個誘人的捷徑是把 當作範式規則,並原封不動地運行 CYK。取起始符為 的 、,它生成詞 。只使用 與 兩種形式規則的 CYK 表,會在 的長度為一的格中只填入 ,因為只有 的右部是終結符。起始符 從不進入表中,所以 被拒絕,儘管 。直接刪去單位產生式也不是補救辦法,因為這樣就甚麼也生成不了;已證明的預處理步驟會把它替換為 。
常見錯誤
(在去除空規則與單位產生式之前先二元化)
對於本文所採用的敘述方式,操作順序是重要的。先對規則二元化也是可行的,但之後消去空規則可能產生單位產生式,這些單位產生式同樣必須被去除。這裏我們先引用化簡定理,然後才添加被強制要求的終結符規則與二元規則。該證明並不聲稱這些步驟的任意重新排列無需進一步清理就都能奏效。
常見錯誤
(分析樹的數目不被保持)
它也不聲稱轉換保持分析樹的數目。例如,、、 對於 有兩棵分析樹;當產生式被視為集合時,消去單位產生式可能只給出單一的產生式 。語言保持不變,但新文法上的 CYK 計數表所數的是新文法的樹,而不是舊文法的樹。若要傳遞歧義性資訊,就需要額外的來源記錄和單獨的證明。
把構造讀作算法
含有 個變元的規則被替換為 條二元規則與 個新的鏈變元。因此,在應用預處理定理之後,終結符分離與二元化相對於預處理後文法的總長度只增加線性數量的符號與產生式。這一計算並不意味著具體的預處理過程是線性的或多項式的:展開所有可空位置的選擇,其規模可能相對於原規則長度呈指數增長。採用不同的順序並共用中間變元可以改進規模,但對此的分析不屬於本定理的內容。
實現該構造時,應系統地使用新名字,並保留一個映射,記錄每個人為添加的變元由哪條產生式的哪個位置創建。這個映射支持證明中所述的收縮,也幫助學生重建原語言中的見證詞。它無法恢復在化簡過程中已被合併的重數。在任何分析器的介面處,都應當清楚區分見證詞、一棵分析樹以及全部原有分析樹。
追蹤一條已轉換的推導,有一種有用的方法:在每個人為添加的節點處記錄其產出串。終結符代理恰好貢獻它所命名的字母;鏈變元貢獻分配給它的原產生式的連續後綴。這些局部斷言使我們能夠自葉子向上、逐棵完成的子樹地收縮這些人為節點。當原有的子節點本身有許多種可能的推導時,這一點很有用:它們內部的選擇在收縮中保持不變。該論證既不要求文法無歧義,也不要求其所有變元都是可產出的。不可產出的子節點只是沒有可供收縮的、完整的終結符產出樹。
對第二個定理還有一個簡單的邊界檢查。長度為一的非空詞有 ,因此沒有二元節點。對於兩個字母的詞,恰好有一個二元節點,它的兩個子節點各產生一個終結符。這些計數是完整範式分析樹的性質,並不說明推導中途的任意句型恰好含有 個變元。
另一種範式使每個推導步驟都產生一個字母,代價是需要另一種構造。
通往推廣的路徑
若每條規則都必須以終結符開頭,會怎樣?
另一種範式使每個推導步驟都產生一個字母,代價是需要另一種構造。
Greibach 範式只允許形如 的規則,其中 是終結符, 是(可以為空的)變元字串。每個不含空字串的上下文無關語言都有這樣的文法。由於每一步都產生一個字母,長度為 的字串,其最左推導恰好用 步。所需的構造比上面的更複雜。
總結
首先去除空產生式與單位產生式,同時保護起始符及其可能的空詞。把長規則中的終結符替換為新的終結符代理,再把長變元序列展開為新的二元鏈。樹的展開與收縮證明了語言相等。所得的二叉樹形狀提供了 CYK 所需的非空劃分,但並不自動保持歧義性或分析樹的數目。
練習
練習 2.6.8
(把已化簡的文法 、、 轉換為帶保護起始符的範式,並指出它的語言。)
基礎
解答(3)
- 1
分離長規則中的終結符
加入 ,把 改寫為 。
- 2
把三個變元的序列二元化
引入新變元 ,使用 、。保留 、 與 。
依據: 這條規則的長度為 ,所以需要一個新的鏈變元。
- 3
讀出語言
離開 的唯一方式是 ,之後 。語言為 。
快速檢查
(一棵範式分析樹有七個終結符葉子。它含有多少個二元產生式節點?為甚麼它的非起始變元都不能推導出空詞?)
利用非空詞的節點個數公式。
解答 · 答案
它有六個二元節點。任何非起始節點只由二元規則或終結符規則展開。在有限的分析樹中,這些規則不可能產生空的終結符產出,而唯一容許的空規則屬於受保護的起始符,它不可能作為子節點出現。
快速檢查
(設 、、。給出同一語言的範式文法,並解釋為甚麼它的分析樹數目不同。)
單元消去對兩個根 和 做了甚麼?
解答 · 答案
單規則文法 生成同一個單元素語言。原文法有以 和 為中間根的兩棵不同的樹,而新文法只有一棵。語言相等並不意味著單元消去前後的分析樹之間有一一對應。
練習 2.6.9
(預處理後的文法有 ,且 各有一條單終結符產生式。所述的右鏈構造需要多少個新的鏈變元?寫出這些二元規則。)
核心
解答(2)
- 1
數出鏈變元
長度為五,因此引入三個變元 。
依據: 長度為 的規則需要 個新變元。
- 2
寫出鏈
規則為 、、 與 。每個引入的變元恰好只有所顯示的那條規則。