動機
文法說明哪些字存在以及它們有甚麼結構;語法分析器則必須從輸入中恢復這種結構,自左向右讀入,並在每一點決定下一步做甚麼。自底向上分析保存一個已讀符號的堆疊,並反覆在兩類動作之間選擇:移進把下一個輸入符號移到堆疊上,歸約把構成某條規則右部的符號替換為它的左部變元。困難在於判斷何時可以歸約。LR 分析用一個以規則的部分識別狀態為狀態集、以文法符號為字母表的有限自動機來回答這個問題。
本節對小型文法展開 LR(0) 機制,定義 LR(k),並用一個最小的例子說明前瞻為甚麼會改變可分析的範圍。本節不為任意 LR(k) 文法構造分析表,也不涉及 LALR。
定義
定義 3.1.1
(增廣文法與結束標記)
給定上下文無關文法 ,其增廣文法加入新變元 與規則 ,並以 為新的起始變元。符號 是結束標記,置於每個輸入字之後。由於 不出現在任何右部,規則 在每個推導中恰好使用一次,即第一步。
定義 3.1.2
(LR(0) 項目、閉包與 goto)
LR(0) 項目是在右部中標出一個位置的規則,對規則 寫作 。對項目集 , 是滿足如下條件的最小集合 :只要 且 是規則,就有 。對文法符號 ,
規範族是包含 、且對所有符號 的 封閉(捨去空結果)的最小項目集族 。
定義 3.1.3
(分析表與移進-歸約分析器)
給規則編號,並以 為狀態索引。ACTION 表對每個狀態 設一行,對每個終結符及 設一列;GOTO 表對每個變元設一列。表項定義如下:
- 若 ,,且 ,則 含移進 ;
- 若 且 ,則對每個 , 含歸約 ;
- 若 ,則 含接受;
- 對變元 ,。
含兩個或更多動作的表項稱為衝突:含一個移進和一個歸約的是移進/歸約衝突,含兩個歸約的是歸約/歸約衝突(含接受時類似)。若沒有表項含有多於一個動作,則稱該文法按表為 LR(0)。
分析器的格局由堆疊 (狀態與符號交替)和剩餘輸入組成。設 為下一個輸入符號(或 )。若 為移進 ,則壓入 與 並前進。若為歸約 ,則彈出 項,設此時堆疊頂狀態為 ,壓入 與 ,輸入不前進。若為接受,則成功停止。空白表項表示錯誤。
概念視角結構
堆疊作為有限自動機中的一條路徑
把規範族看作以文法符號為字母表的確定型自動機:狀態是項目集,轉移是 goto。分析器的堆疊記錄了從 出發走過的路徑,而按 歸約就是把這條路徑倒退 步,然後從所到達的狀態取 轉移。因此堆疊始終是有限圖中的一條路徑,分析器唯一的無限資源是這條路徑的長度。
為使下文的可靠性證明獨立完整,本節採用帶檢查的歸約:按 歸約之前,驗證堆疊頂恰有足夠的符號與狀態對、最上面的 個文法符號正好拼成 ,且歸約後的 GOTO 表項有定義;否則報告錯誤。通常的可行前綴定理可在完整 LR 實現中證明無需重複此檢查,但本節的初等逆推導證明明確使用它。
定義 3.1.4
(LR(k) 文法)
設 是增廣文法,。對終結符串 ,記 為 的前 個符號。若下述條件成立,則稱該文法是 LR(k)。只要 且 ,其中 為終結符串, 且 ,就有 , 且 。這裏 表示替換最右邊變元的一步。
通俗地說:在看到堆疊內容 之後,接下來的 個輸入符號決定歸約哪條規則以及在哪裏歸約。 的情形在這一決定中不允許任何前瞻。
定理
定理 3.1.5
(閉包、goto 與規範族是良定義且有限的)
對有限文法的任一有限項目集 , 存在且有限,並滿足 。規範族存在且有限,至多有 個成員,其中 為該文法的項目數。
證明
(閉包步驟的最小不動點)
令 ,令 為 加上所有由 中點號位於 之前的項目所要求的項目 。這一序列遞增,且每個 都在文法的有限項目集之內,所以它穩定於某個集合 。這個 是封閉的且包含 。任何封閉的 對 歸納可知包含每個 ,所以 是這類集合中最小的。由於 本身已經封閉且包含自身, 的最小封閉超集就是 ,這證明了冪等性。於是每個 是有限項目集。規範族通過反覆添加尚未出現的 goto 得到;每個成員都是有限項目集的子集,所以至多有 種可能,過程必然終止。
定理 3.1.6
(分析器所做的歸約構成一個最右推導)
設 是增廣文法,假設移進-歸約分析器在用上述規則構造的任一分析表下接受 。則 ,且所做的歸約按相反次序恰是某個最右推導的各步。特別地,。
證明
(把歸約倒過來讀)
固定對 的一次接受運行。在每個時刻 ,令 為堆疊上的符號, 為剩餘輸入(終結符串),並令 。起初堆疊上沒有符號,所以 。移進把一個終結符從輸入移到堆疊頂,不改變 。按 歸約把 變成 ;由於 是終結符串, 是 的最右變元,所以 是最右的一步。把這些步驟連起來,得到從最終的 到 的最右推導。餘下要證最終的 就是 。接受發生在含 的狀態。因為 不出現在任何右部,含 的集合只有 ,產生項目 的轉移只有 。此外, 永遠不是某個 goto 的目標,因為每個 goto 目標都含有點號位於至少一個符號之後的項目,而 的每個項目點號都在開頭。所以狀態 只出現在堆疊底部,接受時的堆疊恰是 ,且剩餘輸入為空。因此最終的 就是 。
證明透視
為甚麼可靠性證明不需要完整的自動機理論
所用的假設只是:歸約恰好彈出它所指明的規則的右部,而被移進的只有終結符。表項是否正確(點號項目是否真的刻畫了可行前綴)並未被使用,所以該定理是一個安全性陳述:分析器接受的一切都是可推導的。它沒有說語言中的每個字都被接受,也沒有說分析器是確定的。完備性需要有效項目的理論,本節不予展開;確定性則需要沒有衝突。
證明思路
定理 3.1.7
( 的分析器)
增廣後為 ,規則編號為 ,。規範族恰有五個狀態:,,,,,且 ,,,,,。該表沒有衝突,且分析器接受 當且僅當 。
證明
(小文法的項目、goto 與運行軌跡)
所列的項目集與 goto 直接來自定義: 的閉包加入 的兩條規則;讓點號越過 、、 分別得到 、內核為 的集合(其閉包加入 與 )以及 ;從 出發,符號 得到 ,而 與 分別回到 與 。再無其他 goto,所以該族封閉。狀態 各含一個完整項目且沒有點號後為終結符的項目,所以它們的行各只有一個動作; 與 不含完整項目,所以只有移進。因此沒有衝突。關於接受性,我們跟蹤運行。字 的處理為:從 或 作 次移進到 ,移進 到 ,按 歸約,落在 (從 來)或 (若 ,從 來);然後,若 ,作 次按 的歸約,每次彈出兩對並在下方狀態之上壓入 ,最終在 之上到達 ,並在 上接受。反之,不屬於 的輸入要麼在 或 中耗盡輸入而 無表項,要麼在 之後還讀到符號,要麼帶著終結符到達 ,每種情形都遇到空白表項。 中的歸約對所有前瞻符號都執行,所以這樣的錯誤可能比出錯的輸入符號晚一次歸約才被發現;這是 LR(0) 的特點。
定理 3.1.8
(前瞻區分 LR(0) 與 LR(1))
文法 不是 LR(0) 的,而是 LR(1) 的。其 LR(0) 自動機的表在讀入 後到達的狀態中有移進/歸約衝突。
證明
(讀入 a 之後的衝突與 LR(1) 檢驗)
對 ,增廣文法有 ,且 。第一個項目對所有終結符(包括 )給出歸約,第二個項目對 給出移進,所以 列的表項含兩個動作。取 ,其中 ,,,;再取 ,其中 ,,。則 ,。對 ,前瞻條件是空的,但 ,所以該文法不是 LR(0)。對 ,,所以這一對不受約束。為驗證 LR(1) 條件,列出所有歸約情形。共有三種,都有 :步驟 ,此時 ;步驟 ,此時 ;步驟 ,此時 。一對情形要滿足 ,只有當第二個串 以第一個情形的 為前綴才可能。串 既不是 或 的前綴,也不以它們為前綴,而 不是 的前綴。相同的情形平凡地滿足結論。唯一餘下的一對就是上面處理過的那一對,其前瞻假設不成立。所以 LR(1) 條件成立。
反例模式
無歧義不等於 LR(0)
斷言(錯誤):每個字恰有一棵分析樹的文法可以不用前瞻來分析。文法 是無歧義的,因為兩個字的樹形狀不同,且每個字只有一棵樹。但它的 LR(0) 自動機有一個狀態,同時含完整項目 與項目 ,所以讀入 之後分析器無法在歸約與移進 之間決定。有一個符號的前瞻就能強制決定:在 上歸約,在 上移進。修正:允許前瞻,如 LR(1) 的定義。LR(k) 文法都是無歧義的,這是一個標準事實,此處不予證明;這個例子表明對 僅有無歧義是不夠的。
例題
例題 3.1.9
( 的完整分析表)
規則:,。空白表項表示錯誤。
| 狀態 | ||||
|---|---|---|---|---|
| 0 | 移進 2 | 移進 3 | 1 | |
| 1 | 接受 | |||
| 2 | 移進 2 | 移進 3 | 4 | |
| 3 | 歸約 2 | 歸約 2 | 歸約 2 | |
| 4 | 歸約 1 | 歸約 1 | 歸約 1 |
歸約狀態的各行體現了 LR(0) 的特徵:完整項目在每一列上都歸約。沒有一行含兩個動作,所以該文法按表為 LR(0)。
例題 3.1.10
(分析 aab)
初始堆疊為 ,輸入為 。移進 :堆疊 ,輸入 。移進 :,輸入 。移進 :,輸入 。按規則 ()歸約:彈出一對,堆疊頂狀態為 ,壓入 與 :。按規則 ()歸約:彈出兩對,堆疊頂狀態為 ,壓入 :。再按規則 歸約:彈出兩對,堆疊頂為 ,壓入 與 :。在 上,狀態 的表項是接受。歸約按相反次序給出 ,正是一個最右推導,與可靠性定理的預言一致。對只含 的字,分析更短:移進 到狀態 ,按規則 歸約並取 ,然後接受。
例題 3.1.11
(前瞻能解決的衝突,與不能解決的衝突)
對 ,讀入 之後的狀態是 ,LR(0) 表中 列的表項是移進/歸約衝突。若有前瞻集, 只在下一個符號可以跟在 之後時才可歸約,這裏只有 ,於是衝突消失。再看 。在 之後,狀態含 與 。可以跟在 之後的符號是 與 ,所以在 上歸約是允許的,移進 也是允許的。即使有一個符號的前瞻,衝突依然存在,因為該文法有歧義,兩個動作對應兩棵不同的分析樹。
常見錯誤
另有一點屬於記帳層面。不要混淆符號堆疊與狀態堆疊:符號拼出可行前綴,而狀態記錄自動機的位置;歸約按右部符號的個數彈出。
常見錯誤
(零前瞻不等於不看輸入)
不要把「LR(0)」理解為「分析器從不查看輸入」。移進依賴於下一個終結符;零前瞻指的是歸約的決定,它必須僅由狀態決定。
常見錯誤
(計算 goto 時漏掉閉包)
計算 時漏掉閉包這一步,會丟掉緊跟在點號之後的變元所對應的項目。對 ,移動後的集合 在 與 上都不給出移進。
常見錯誤
(更長的前瞻不能消除歧義)
不要相信增加前瞻就能讓每個文法都可分析:歧義與前瞻的長度無關。上面的 就是例子:它的衝突對每個 都存在。
總結
LR 分析運行一個由項目集自動機引導的基於堆疊的移進-歸約循環。閉包與 goto 是良定義的,規範族有限。這樣的分析器接受的一切都是可推導的,所做的歸約按相反次序構成最右推導。對 ,表有五個狀態且無衝突;字 被明確地分析了一遍。文法 表明,一個符號的前瞻可以解決零前瞻無法解決的衝突。
練習
快速檢查
(構造增廣文法 的規範族與分析表。)
先閉包,再 goto。
解答 · 答案
規則編號為 ,。狀態:;;;;;;此外 ,。表:第 0 行: 上移進 2, 上移進 3,GOTO 為 1;第 1 行: 上接受;第 2 行: 上移進 2, 上移進 3,GOTO 為 4;第 3 行:在 上歸約 2;第 4 行: 上移進 5;第 5 行:在 上歸約 1。沒有衝突。
快速檢查
(對該文法,給出分析 時每一步的堆疊與輸入。)
同時記錄狀態與符號。
解答 · 答案
堆疊與剩餘輸入: 配 ;移進: 配 ;移進: 配 ;移進 : 配 ;歸約 2:;移進 : 配 ;歸約 1 彈出三對,剩下 ,壓入 與 GOTO:;移進 : 配 ;歸約 1 彈出三對,剩下 ,壓入 :;接受。
快速檢查
(證明 ,, 的 LR(0) 表中有歸約/歸約衝突,並把它與文法聯繫起來。)
檢查讀入 、再讀入 之後的狀態。
解答 · 答案
讀入 之後的狀態是 ,且 ,它在每一列上都有兩個歸約:這是歸約/歸約衝突。它反映了歧義: 有兩棵分析樹,一棵經過 ,一棵經過 。
快速檢查
(證明對有限項目集 有 ,並舉例說明 不一定等於上面所定義的 。)
用閉包的最小性。
解答 · 答案
集合 包含 且封閉,因為若某個點號位於 之前的項目屬於其中一部分,則所要求的項目 屬於同一部分。由最小性,。反之, 是 的封閉超集,故包含 ,同理包含 ;所以 。舉例:在文法 中取 ,按定義 ,因為 中沒有點號位於 之前的項目,而 。這就是定義要把 goto 作用於封閉項目集(例如規範族的成員)的原因。