有限自動機只記得有限個狀態之一,足以判斷奇偶等性質。但巢狀結構提出不同問題:哪個右括號配對哪個左括號?文法可以遞歸描述這種結構。要嚴謹使用描述,必須同時證明每個生成字串都有效,以及每個有效字串都能生成。
另一項分別也很重要:語言是字串的集合,分析樹則解釋某個字串的結構。兩個文法可以生成完全相同的字串,卻賦予它們不同數目的分析樹。平衡括號提供了一個小例子,讓我們完整證明正確性、歧義、確定性語法分析及計數之間的關係。
文法每次改寫一個非終結符
定義 8.1.1
(上下文無關文法、推導與分析樹)
上下文無關文法是四元組 : 是有限非終結符集合; 是與 不相交的有限終結符字母表; 是起始符號; 是有限產生式集合,每式為 ,其中 、。
一步推導把某次出現的 換成產生式右側,周圍符號保持不變。語言 包含所有由 經有限步可得的純終結符字串。空字串為 ,長度是零,並非額外的終結符。
分析樹是記錄產生式的有序樹。內部非終結符的子節點依次拼出所選右側。由左至右讀取終結符葉子,得到該樹生成的字串。空產生式貢獻空字串,繪圖時可用 葉表示。
產生式左側只有一個非終結符,所以它在哪裏出現,都能使用相同規則,這就是「上下文無關」的意思。推導記錄改寫的先後次序,分析樹則記錄巢狀結構。
先獨立定義甚麼是平衡
定義 8.1.2
(平衡值與平衡字串)
字母表只含 ( 和 )。對前綴 定義平衡值
即左括號數減右括號數。令 包含所有每個前綴平衡值均非負,且最終 的字串 。空字串屬於 。
反例模式
總數相等,不保證巢狀結構正確
())( 有兩個左括號和兩個右括號,最終平衡值為零。但前綴 ()) 的平衡值是 ,已有一個右括號找不到可用的左括號。因此它不屬於 。
(()()) 各個非空前綴的平衡值為 ,所以是平衡字串。前綴條件與最終相等,缺一不可。
一個看來自然的文法是
三條規則分別表示連接兩個平衡字串、包住一個平衡字串、或使用空字串。這些操作保留平衡,但只憑此觀察,仍只證明了語言相等的一個方向。
命題 8.1.3
(第一個文法的可靠性)
生成的每個字串都平衡:。
證明
(對分析樹作歸納)
對有限分析樹作歸納。空產生式生成 ,符合條件。若根使用 ,而子樹生成平衡 ,則 的平衡值由 1 開始,讀取 期間至少為 1,最後的右括號令它回到零。
若根使用 ,兩子樹生成平衡 。位於 內的前綴非負;讀完 時平衡值為零,繼續進入 的前綴便具有 對應的平衡值,最後仍為零。因此全部產生式保留性質,。
首次回到零,決定唯一分解
命題 8.1.4
(首次回零分解)
每個非空的 都有唯一的分解 ,其中 。顯示的右括號是 的前綴平衡值首次回到零的位置,並且 與 都比 短。
證明
(在首次回零處分割)
取非空 。它必須以 ( 開始,否則首個前綴已為 。最終平衡值為零,所以存在第一個正位置,使平衡值回到零。該位置是右括號,從而分解為
顯示的外層括號在首次回零處結束。內部 平衡:其前綴平衡值是 對應平衡值減一;首次回零之前,這些值均非負,而且 最終為零。後綴 由一個零平衡前綴之後開始,繼承其餘前綴條件,因此亦平衡。
都比 短。首次回零的位置也保證這個分解唯一:對任何滿足 的分解 , 的每個前綴的平衡值都至少為 ,所以顯示的右括號就是首次回零處。
概念視角幾何
把平衡字串看作高度路徑
把 ( 看作上升一步,) 看作下降一步。於是 就是路徑在前綴 之後的高度,而字串屬於 ,恰好當路徑從不低於高度零並在高度零結束。在這幅圖像中,首次回零就是路徑第一次回到橫軸,所以 把路徑切成一道拱(即 的路徑上移一步)以及隨後 的路徑。對這類路徑計數,就是下面的遞推式所解決的計數問題。
考慮
命題 8.1.5
(生成平衡字串的兩個文法)
設 如上,則 。
證明
(對字串長度作強歸納)
對字串長度作強歸納。空字串使用 。非空平衡 有首次回零分解 。由歸納假設,較短的平衡字串 都可由 推導。先使用 ,再代入兩個推導,即生成 。
與前面相同的可靠性論證亦證明 只生成平衡字串,所以 。此外, 能以 模擬 的每個非空產生式,因此也生成全部平衡字串。結合可靠性,得到 。
例題 8.1.6
(首次回零把巢狀部分與後綴分開)
(())() 的前綴平衡值是 。首次回零在第四位,所以 、。外層括號只包住第一個 (),第二個 () 則屬於後綴。
在 中,一個完整最左推導為
每步都改寫最左邊尚存的非終結符。空產生式不可省略:它們終止最內層字串及最後的後綴。
改寫次序不同,不一定代表有歧義
定義 8.1.7
(有歧義的文法)
若某個生成字串具有兩棵不同的分析樹,文法便有歧義。等價地,該字串有兩個不同的最左推導。只找到兩個任意推導並不足夠,因為同一棵樹可按不同次序展開。
常見錯誤
(不同的改寫次序不等於不同的樹)
例如在 作 後,可以先展開內部非終結符,也可以先展開後綴。中途字串或會不同,但仍可能描述同一棵樹。
例題 8.1.8
(有歧義文法中 () 的兩棵樹)
對 () 確實有歧義。一棵樹在根使用 ,內部使用空產生式。另一棵在根使用 ,左子樹生成 (),右子樹生成 。根產生式不同,便是同一字串的兩棵不同樹。再連接更多空字串,可產生更多樹,卻沒有新增終結符字串。
命題 8.1.9
(首次回零文法沒有歧義)
每個平衡字串在 中恰有一棵分析樹。
證明
(對字串長度歸納)
對長度歸納。只有空產生式能生成空字串,因為另一條規則會加入可見的一對括號,所以空字串只有一棵樹。
非空字串的根必須使用 。若兩子樹生成 ,可靠性保證它們平衡。因此,根產生式的右括號必定是整個字串首次回零的位置。字串本身已唯一決定該位置,以及 。
兩者都較短,歸納假設各自給出唯一子樹,所以整棵樹唯一。 沒有歧義,即使 以有歧義的方式生成完全相同的語言。
證明透視
為何首次回零決定整棵樹
歸納假設只用在兩個子樹上,它們嚴格較短。容易漏掉的一步是根產生式被迫選定: 不生成任何符號,所以非空字串必須以 開始。不明顯的一步是把關於樹的命題轉為關於字串的命題:無論給出哪棵樹,其根產生式的右括號都位於平衡值首次回零之處,而該位置只由字串本身決定。因此同一字串的兩棵樹不可能有不同的 與 。同一論證對 失效,因為 沒有這樣的錨點:連接的分割點可以是任何平衡值為零的位置,而空產生式可以插入任何地方。
常見錯誤
(文法有歧義不等於語言有歧義)
因此,歧義是特定文法的性質。證明一個文法有歧義,不等於證明其語言沒有任何無歧義文法;本例兩個文法已清楚展示這個分別。
用下方固定平衡字串示例比較:兩種改寫次序描述同一棵首次回零樹;歧義文法內的兩棵不同樹則見證歧義。
有限狀態為何不能記住所有深度
定理 8.1.10
(平衡字串語言不是正則語言)
語言 不是正則語言:沒有確定型有限自動機能識別它。
證明
(相同狀態、相同後綴、相同答案)
假設某個有 個狀態的 DFA 識別 。考慮由 個左括號構成的前綴,其中 。共有 個前綴,必有兩個長度 的前綴到達相同狀態。
對兩者都接上恰好 個右括號。第一個字串左右括號各 個,且先左後右,因此平衡。第二個有 個左括號但只有 個右括號,並不平衡。
由同一狀態讀同一後綴,DFA 必須給出相同接受結果,造成矛盾。因此 不是正則語言。此論證對每個固定有限狀態數都成立。
證明透視
有限性在碰撞論證的何處用到
有限性只用到一次,就是鴿籠步驟: 個前綴不可能到達 個互不相同的狀態。不明顯的一步是選擇的次序:先固定由左括號組成的前綴,在知道碰撞的一對之後才選後綴,因此後綴依賴於 。論證之所以封閉,是因為 DFA 的未來行為只取決於當前狀態,相同的狀態無法區分 與 。去掉有限性,論證立即失效:計數器有無界多個取值,可以區分所有前綴 。
只有一類括號時,一個可無界增長的非負計數器就能記錄尚未配對的左括號。下推自動機可用堆疊高度表示同一數量。這不違反 DFA 論證:計數器或堆疊可隨輸入增長,DFA 的狀態數卻固定。若有多類括號,只記高度還不足以核對類型。
判斷成員資格,或返回唯一結構
第一個函數檢查獨立的前綴定義。第二個實現 :None 表示空產生式,(inside, suffix) 表示 的兩個非終結符子樹。因此返回 None 是空字串的有效分析結果,不是失敗值。無效字串會引發 ValueError。
def is_balanced(text):
balance = 0
for symbol in text:
if symbol == "(":
balance += 1
elif symbol == ")":
balance -= 1
else:
return False
if balance < 0:
return False
return balance == 0
def parse_balanced(text):
position = 0
def parse_S():
nonlocal position
if position == len(text) or text[position] == ")":
return None
if text[position] != "(":
raise ValueError("expected opening parenthesis")
position += 1
inside = parse_S()
if position == len(text) or text[position] != ")":
raise ValueError("missing closing parenthesis")
position += 1
suffix = parse_S()
return (inside, suffix)
tree = parse_S()
if position != len(text):
raise ValueError("unmatched closing parenthesis")
return tree
每個終結符只被消耗一次;每個遞歸調用不是消耗一對括號,就是返回空子樹。因此,語法分析時間為字串長度的線性級,樹及遞歸空間最壞亦為線性級。此教學實現對很長字串受 Python 遞歸深度限制。迭代的成員檢查不需遞歸,但計數器仍要有足夠位元表示當前深度,而非固定有限狀態集合。
例題 8.1.11
(在兩個無效字串上運行分析器)
取 ())。位置 的 parse_S() 消耗 (;內層調用在位置 返回 None,因為 text[1] 是 );接著消耗右括號,位置 的後綴調用同樣返回 None,因為 text[2] 是 )。此時已建出樹 (None, None),但 position 是 而 len(text) 是 ,所以最後的檢查會因右括號沒有配對而拋出 ValueError。
取 (()。外層調用消耗第一個 (;內層調用消耗第二個 (,遇到 ),並建出 (None, None)。回到外層調用時,position 等於 len(text),所以檢查右括號失敗,ValueError 報告缺少右括號。相對地,parse_balanced("") 返回 None:這是空字串的有效分析結果,不是錯誤。
以唯一分解計算字串數目
命題 8.1.12
(平衡字串的遞推式)
令 為含 對括號的平衡字串數。則 ,而當 時, 等於 時 之和。
證明
(以唯一的首次回零分解計數)
令 為含 對括號的平衡字串數。空字串只有一個,所以 。非空字串 中,若 含 對, 便含 對。分解唯一,因此不會遺漏或重複計數:
得到 、、、,即 Catalan 數的開頭。
常見錯誤
(計算字串不等於計算分析樹)
此式計算不同字串,不是 的任意推導樹;對有歧義樹計數會回答另一個問題。
有:這些數目就是 Catalan 數,而且每個數約為前一個的四倍。
自然延伸的下一個問題
這些數目有公式嗎?
有:這些數目就是 Catalan 數,而且每個數約為前一個的四倍。
這個遞推式有封閉公式 ,可用其他方法證明。例如 、,與上面的數值相符。比值 趨近於 ,所以平衡字串的數目大約按 增長,只差一個多項式因子。
練習與詳解
快速檢查
(同時檢查兩個平衡條件)
、(()())、())(、(() 哪些平衡?對每個被拒字串,指出負平衡前綴或非零最終平衡值。
解答 · 答案
空字串及 (()()) 平衡。())( 的前綴 ()) 平衡值為 ,即使全串最終為零也無效。(() 沒有負前綴,但最終為 1,仍有一個左括號未配對。
快速檢查
(找出唯一分解與分析樹)
求 (())() 的首次回零分解。以 None 表示空子樹、(inside, suffix) 表示非空子樹,寫出分析器的返回樹。
解答 · 答案
首次回零在第四位,內部與後綴都為 (),各有樹 (None, None)。完整樹為 ((None, None), (None, None)),根描述第一對外層括號及餘下後綴。
快速檢查
(分清歧義與改寫次序)
在 使用 後,兩個推導以相反次序展開兩個非終結符,最後得到相同字串與相同樹。這是否證明有歧義?甚麼樣的一對例子才足夠?
解答 · 答案
不足夠:它們只是按不同次序展開同一棵樹。必須給出同一字串的兩棵不同分析樹,或兩個不同最左推導。首次回零的唯一性證明排除了 出現這種例子。
快速檢查
(展示真正歧義,而不改變語言)
對 ,描述兩種不同根產生式如何生成 ()。這是否證明平衡括號語言沒有無歧義文法?
解答 · 答案
一棵樹的根使用包圍規則,內部為空。另一棵根使用連接,左側生成 ()、右側為空。根規則不同,證明兩樹不同。但 是同一語言的無歧義文法,所以不能從 有歧義推論語言沒有無歧義描述。
快速檢查
(從相同 DFA 狀態導出矛盾)
若兩個及五個左括號的前綴到達同一 DFA 狀態,接上哪個共同右括號後綴,能令一個屬於平衡語言而另一個不屬於?為何 DFA 仍必須給相同答案?
解答 · 答案
接上兩個右括號。第一個字串平衡,第二個仍有三個未配對左括號。DFA 的後續行為只依當前狀態,所以相同狀態再讀相同後綴,接受結果必須相同,不能同時識別正確。
快速檢查
(計算字串,不是有歧義的樹)
由 用遞推式求 ,並列出 的五個字串。為何這不是 的分析樹數?
解答 · 答案
。五個三對字串為 ((()))、(()())、(())()、()(())、()()()。它們是不同終結符字串; 對同一字串可有多樹,包括額外連接空字串的樹,因此樹數不等於這個字串數。