有限自動機只記得有限個狀態之一,足以判斷奇偶等性質。但巢狀結構提出不同問題:哪個右括號配對哪個左括號?文法可以遞歸描述這種結構。要嚴謹使用描述,必須同時證明每個生成字串都有效,以及每個有效字串都能生成。
另一項分別也很重要:語言是字串的集合,分析樹則解釋某個字串的結構。兩個文法可以生成完全相同的字串,卻賦予它們不同數目的分析樹。平衡括號提供了一個小例子,讓我們完整證明正確性、歧義、確定性語法分析及計數之間的關係。
文法每次改寫一個非終結符
定義 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
(首次回零文法沒有歧義)
每個平衡字串在 中恰有一棵分析樹。
證明
(對字串長度歸納)
對長度歸納。只有空產生式能生成空字串,因為另一條規則會加入可見的一對括號,所以空字串只有一棵樹。
非空字串的根必須使用 。若兩子樹生成 ,可靠性保證它們平衡。因此,根產生式的右括號必定是整個字串首次回零的位置。字串本身已唯一決定該位置,以及 。
兩者都較短,歸納假設各自給出唯一子樹,所以整棵樹唯一。 沒有歧義,即使 以有歧義的方式生成完全相同的語言。
證明透視
為何首次回零決定整棵樹
歸納假設只用在兩個子樹上,它們嚴格較短。容易漏掉的一步是根產生式被迫選定: 不生成任何符號,所以非空字串必須以 開始。不明顯的一步是把關於樹的命題轉為關於字串的命題:無論給出哪棵樹,其根產生式的右括號都位於平衡值首次回零之處,而該位置只由字串本身決定。因此同一字串的兩棵樹不可能有不同的 與 。同一論證對 失效,因為 沒有這樣的錨點:連接的分割點可以是任何平衡值為零的位置,而空產生式可以插入任何地方。
常見錯誤
(文法有歧義不等於語言有歧義)
因此,歧義是特定文法的性質。證明一個文法有歧義,不等於證明其語言沒有任何無歧義文法;本例兩個文法已清楚展示這個分別。
用下方固定平衡字串示例比較:兩種改寫次序描述同一棵首次回零樹;歧義文法內的兩棵不同樹則見證歧義。
同一個字、唯一分解與不同剖析樹
檢視前綴平衡及首次回零,按最左或最右次序展開同一棵固定樹,再在歧義文法中構造兩棵真正不同的樹。只改寫次序不同,不足以證明歧義。
所選生成規則: G1: S→(S)S | ε.
各前綴的平衡
只有整數前綴長度代表字。每步遇 ( 加1,遇 ) 減1,實線連接這些離散值。橫線是零平衡,實心圓是所選前綴。非空平衡字的正方形標示首次正長度回零。結尾數量相同不能修補先前負平衡。
所選前綴: ε; 平衡: 0. 整個字的平衡: 0.
| 前綴長度 | 前綴字 | 平衡 |
|---|---|---|
| 0 | ε | 0 |
| 1 | ( | 1 |
| 2 | (( | 2 |
| 3 | (() | 1 |
| 4 | (()) | 0 |
| 5 | (())( | 1 |
| 6 | (())() | 0 |
唯一首次回零分解: w=(u)v; 內部 u=(); 剩餘後綴 v=().
G1:唯一有序剖析樹
S 節點使用所示生成規則,括號是終結葉。虛線 ε 葉表示空產出,不貢獻終結符。子節點由左至右讀;下方文字版保留完整有序階層。
剖析樹產生的字: (())(). 此樹的有序文字版.
此樹的有序文字版: G1:唯一有序剖析樹
- S→(S)S
- ( 左括號
- S→(S)S
- ( 左括號
- S→ε
- ε · 空產出
- ) 右括號
- S→ε
- ε · 空產出
- ) 右括號
- S→(S)S
- ( 左括號
- S→ε
- ε · 空產出
- ) 右括號
- S→ε
- ε · 空產出
每行取代有底線的 S,位置由改寫前字串的1開始計。切換最左/最右保持同一棵樹,可能改變中間形式;G1 空樹在兩種次序都只有一次改寫。
| 步 | 改寫前 | 展開 S 的位置 | 生成規則 | 改寫後 |
|---|---|---|---|---|
| 1 | S | 1 | S→(S)S | (S)S |
| 2 | (S)S | 2 | S→(S)S | ((S)S)S |
| 3 | ((S)S)S | 3 | S→ε | (()S)S |
| 4 | (()S)S | 4 | S→ε | (())S |
| 5 | (())S | 5 | S→(S)S | (())(S)S |
| 6 | (())(S)S | 6 | S→ε | (())()S |
| 7 | (())()S | 7 | S→ε | (())() |
此處最左與最右都展開同一棵固定 G1 樹,中間形式不同並不產生第二棵樹。
- 此字平衡
- 是
- 所選前綴
- ε
- 平衡
- 0
- 整個字的平衡
- 0
- 首次負平衡前綴長度
- 沒有
- 首次回零位置
- 4
- 所選文法的有限剖析樹數目
- 1
- 剖析樹產生的字
- (())()
每個前綴均非負,結尾平衡為零;此字具有所示剖析結構。 平衡: 0; 整個字的平衡: 0. 所選文法的有限剖析樹數目: 1. 此樹使用的 S 生成規則次數: 7.
分開證明語言與剖析樹的結論
平衡字要求每個前綴的左括號不少於右括號,且結尾總數相等。())( 最後總數相等,但長度3前綴平衡為 −1,故無效。(() 從不負平衡,結尾卻為1,也無效。空字同時滿足兩個條件。
非空平衡字首符號是 (,之後首次回零的位置固定與它配對的右括號,得 w=(u)v。在該回零前,外層內部平衡減1後仍非負;後綴從零重新開始,所以 u、v 都平衡且嚴格較短。首次回零唯一決定兩者。使用 S→(S)S 再遞迴 u、v 就構造 G1 樹,空字用 S→ε。
歸納亦證明唯一性。只有空生成可產生空字。非空字的 G1 根必用 S→(S)S,子產出平衡迫使根的右括號正是首次回零。字先決定兩個子產出,歸納再決定各自樹。對 (())(),首次回零在位置4,u=()、v=(),與正文推導一致。先展開內部或先展開後綴,只是安排同一棵樹的不同展開次序。
G0 產生同一平衡語言:包圍平衡字與串接平衡字都保留前綴條件,而首次回零構造可用其包圍及串接規則表達。但它有歧義:() 的一棵樹根用 S→(S),內部為空;另一棵根用 S→SS,把前樹放左,右邊加空樹。結構不同但終結產出相同。所示 G0 見證把此構造一般化;不同 S 生成次數保證是不同有限樹。
歧義屬於特定文法,不自動屬於其語言。G0 可任意增加空後綴包裝,因此每個平衡字有無限多棵有限樹;G1 卻恰有一棵,兩者產生的終結字集合不變。同理,Catalan 遞迴數平衡字,不是在數 G0 歧義樹。本圖在同一文法內比較真正不同的樹作見證,沒有把兩種文法的樹不同本身當歧義證明。
即時檢查:G1 的兩種改寫次序能否證明 G1 有歧義?
不能。歧義要求同一終結字有兩棵不同有序剖析樹,等價於兩個不同最左推導。同樹的兩個展開次序不足夠;空字時兩個次序甚至相同。G0 見證結構真正不同,才證明歧義。
七個單一括號類型的固定短字,G1 首次回零樹及 G0 的構造見證族,顯示一至三層空包裝。無限性由任意延長構造證明,不是聲稱有限列表已完整。不實作任意文法剖析、LR 表、PDA 執行或 Catalan 字枚舉。
有限狀態為何不能記住所有深度
定理 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 的後續行為只依當前狀態,所以相同狀態再讀相同後綴,接受結果必須相同,不能同時識別正確。
快速檢查
(計算字串,不是有歧義的樹)
由 用遞推式求 ,並列出 的五個字串。為何這不是 的分析樹數?
解答 · 答案
。五個三對字串為 ((()))、(()())、(())()、()(())、()()()。它們是不同終結符字串; 對同一字串可有多樹,包括額外連接空字串的樹,因此樹數不等於這個字串數。