語法分析——自底向上分析技術

1、5.1 引言引言5.2 算符優(yōu)先分析技術算符優(yōu)先分析技術5.3 LR(k)分析技術分析技術本章小結本章小結5.1 引言引言 5.1.1 自底向上分析技術及識別算法自底向上分析技術及識別算法 5.1.2 討論的前提討論的前提 5.1.3 基本實現(xiàn)方法基本實現(xiàn)方法5.1 引言引言5.1.1 自底向上分析技術及識別算法自底向上分析技術及識別算法 基本思想基本思想是是: 從輸入符號串出發(fā)，在每一分析步對相從輸入符號串出發(fā)，在每一分析步對相應句型中的某個簡單短語進行歸約。如果最終能歸約到識應句型中的某個簡單短語進行歸約。如果最終能歸約到識別符號，則該輸入符號串是相應文法的句子，否則就不是。別符號，則該輸

2、入符號串是相應文法的句子，否則就不是。 當句型分析過程中每個分析步都對最左的簡單短語進當句型分析過程中每個分析步都對最左的簡單短語進行直接歸約時，自底向上分析技術的兩個基本問題可以更行直接歸約時，自底向上分析技術的兩個基本問題可以更確切地敘述為：確切地敘述為：如何找出句柄如何找出句柄及及把此句柄直接歸約為哪個把此句柄直接歸約為哪個非終結符號非終結符號。5.1 引言引言5.1.1 自底向上分析技術及識別算法自底向上分析技術及識別算法5.1.2 討論的前提討論的前提 識別過程是從左到右、自底向上地進行的，一般識別過程是從左到右、自底向上地進行的，一般都將采用規(guī)范歸約；除了特別指明的以外，每一步都將

3、采用規(guī)范歸約；除了特別指明的以外，每一步總是對句柄總是對句柄最左的簡單短語進行直接歸約最左的簡單短語進行直接歸約。5.1.3 基本實現(xiàn)方法基本實現(xiàn)方法 采用自底向上分析技術時，通常以移入采用自底向上分析技術時，通常以移入- -歸約歸約法為基礎。一般地，動作共有法為基礎。一般地，動作共有4 4類，即移入、歸約、類，即移入、歸約、接受與報錯。接受與報錯。v移入：移入：讀入下一個輸入符號并把它下推進棧；讀入下一個輸入符號并把它下推進棧；v歸約：歸約：當棧頂?shù)漠敆ｍ數(shù)? (部分部分) )符號串形成一個句柄時，對符號串形成一個句柄時，對此句柄進行直接歸約；此句柄進行直接歸約；v接受：接受：當識別程序發(fā)現(xiàn)

4、棧中除了棧底標志符號當識別程序發(fā)現(xiàn)棧中除了棧底標志符號# #外外僅有識別符號，而輸入也已到達右端僅有識別符號，而輸入也已到達右端# #，則接受；，則接受；v報錯：報錯：當識別程序察覺一個錯誤，因此輸入符號串當識別程序察覺一個錯誤，因此輸入符號串不是句子而無法繼續(xù)識別工作時，調用一個出錯處不是句子而無法繼續(xù)識別工作時，調用一個出錯處理子程序進行處理或停止。理子程序進行處理或停止。 步驟 棧 輸入 動作 規(guī)則 （1） （2） （3） （4） （5） （6） （7） （8） （9）（10）（11） # #i #E #E* #E*i #E*E #E #E+ #E+i #E+E #E i*i+i# *i

5、+i#*i+i# i+i#+i#+i#+i# i# 移入 歸約 移入 移入 歸約 歸約 移入 移入 歸約 歸約 接受 E=i E=i E=E*E E=i E=E+E例例5.1 5.1 設有文法設有文法GEGE：E=E+E|EE=E+E|E* *E|(E)|iE|(E)|i自底向上分析技術的步驟自底向上分析技術的步驟: : 1) 1) 找出句柄找出句柄u;u; 2) 2) 找出規(guī)則找出規(guī)則U=uU=u； 3) 把把u u直接歸約成直接歸約成U U。 分析技術不同分析技術不同, ,尋找句柄的方法也不同。尋找句柄的方法也不同。5.25.2 算符優(yōu)先分析技術算符優(yōu)先分析技術 一、一、算符優(yōu)先分析技術的

6、引進算符優(yōu)先分析技術的引進 二、二、算符文法算符文法 三、三、算符優(yōu)先關系與算符優(yōu)先文法算符優(yōu)先關系與算符優(yōu)先文法 四、四、算符優(yōu)先文法句型的識別算符優(yōu)先文法句型的識別 五、實際應用中的五、實際應用中的算符優(yōu)先分析技術算符優(yōu)先分析技術 一、算符優(yōu)先分析技術的引進一、算符優(yōu)先分析技術的引進 對算術表達式，運算符完全決定了運算對算術表達式，運算符完全決定了運算次序，運算次序，運算對象完全不起作用。對象完全不起作用。 因此，將文法中的因此，將文法中的終結符號終結符號看作看作運算符運算符； 非終結符號非終結符號看作看作運算對象運算對象。 算符優(yōu)先分析技術：只在終結符號之間算符優(yōu)先分析技術：只在終結符號

7、之間引進優(yōu)先關系，并利用優(yōu)先關系找出句柄引進優(yōu)先關系，并利用優(yōu)先關系找出句柄（最左質短語）。（最左質短語）。5.25.2算符優(yōu)先分析技術算符優(yōu)先分析技術一、算符優(yōu)先分析技術的引進一、算符優(yōu)先分析技術的引進二、算符文法二、算符文法 定義定義5.1 如果文法如果文法G中沒有形如中沒有形如 U =VW 的規(guī)則，其中的規(guī)則，其中U、V、WVN，則該文法，則該文法G稱為算稱為算符文法，縮寫為符文法，縮寫為OG。5.25.2算符優(yōu)先分析技術算符優(yōu)先分析技術 一、一、算符優(yōu)先分析技術的引進算符優(yōu)先分析技術的引進 二、二、算符文法算符文法 三、三、算符優(yōu)先關系與算符優(yōu)先文法算符優(yōu)先關系與算符優(yōu)先文法v算符優(yōu)先

8、關系算符優(yōu)先關系v算符優(yōu)先文法算符優(yōu)先文法5.2 簡單優(yōu)先分析技術5.2.1算符優(yōu)先分析技術的引進5.2.2算符文法v算符優(yōu)先關系算符優(yōu)先關系v算符優(yōu)先文法算符優(yōu)先文法定義定義5.25.2 設文法設文法G G是一個算符文法，是一個算符文法，T Tj j與與T Ti i是兩個任意的終結符號，而是兩個任意的終結符號，而U,V,WVU,V,WVN N，定義算符優(yōu)先關系如下：，定義算符優(yōu)先關系如下：T Tj j=T=Ti i 當且僅當文法當且僅當文法G G中存在形如中存在形如U=U=T Tj jT Ti i或或U=U=T Tj jVTVTi i的規(guī)則；的規(guī)則；T Tj jT Ti i 當且僅當文法當且

9、僅當文法G G中存在形如中存在形如U=U=T Tj jV V的規(guī)則，其中的規(guī)則，其中V=TV=Ti i或或V=WTV=WTi i；T Tj jT Ti i 當且僅當文法當且僅當文法G G中存在形如中存在形如U=U=VTVTi i的規(guī)則，其中的規(guī)則，其中V=V=T Tj j或或V=V=T Tj jW W。例例 設有文法設有文法GZ: Z=E E=T|E+T T=F|TGZ: Z=E E=T|E+T T=F|T* *F F=(E)|iF F=(E)|i+ i + i + * * ( ) ( )i i + + * * ( =( ) 5.25.2算符優(yōu)先分析技術算符優(yōu)先分析技術 一、一、算符優(yōu)先分析技

10、術的引進算符優(yōu)先分析技術的引進 二、二、算符文法算符文法 三、三、算符優(yōu)先關系與算符優(yōu)先文法算符優(yōu)先關系與算符優(yōu)先文法v算符優(yōu)先關系算符優(yōu)先關系v算符優(yōu)先文法算符優(yōu)先文法定義定義5.55.5 設有算符文法設有算符文法G G，如果在它的任意兩，如果在它的任意兩個終結符號之間，算符優(yōu)先關系個終結符號之間，算符優(yōu)先關系 =、與、與至多只有一種關系成立，則稱該文法至多只有一種關系成立，則稱該文法G G為算符為算符優(yōu)先文法，縮寫為優(yōu)先文法，縮寫為OPGOPG。例例1 1 文法文法GZ: Z=E E=T|E+T GZ: Z=E E=T|E+T T=F|T T=F|T* *F F=(E)|iF F=(E)|

11、i例例2 2 文法文法GEGE： E=E+E|EE=E+E|E* *E|(E)|iE|(E)|i5.2 簡單優(yōu)先分析技術5.2.1算符優(yōu)先分析技術的引進5.2.2算符文法四、四、算符優(yōu)先文法句型的識別算符優(yōu)先文法句型的識別v質短語質短語v算符優(yōu)先識別算法算符優(yōu)先識別算法定義定義5.65.6 設有算符文法設有算符文法GZGZ，( (句型的句型的) )質短語定義為這樣一個短語：質短語定義為這樣一個短語：它至少包含一個終結符號，且除它自身外不再包含其他質短語。它至少包含一個終結符號，且除它自身外不再包含其他質短語。例例1 1 文法文法GZ: Z=E E=T|E+T T=F|TGZ: Z=E E=T|

12、E+T T=F|T* *F F=(E)|iF F=(E)|i （考慮句型（考慮句型T+TT+T* *F+i)F+i)定理定理5.35.3 一個算符優(yōu)先文法句型一個算符優(yōu)先文法句型NN1 1TT1 1NN2 2 NNn nTTn nNNn+1 的最左質的最左質短語是滿足條件：短語是滿足條件：T Tj j1 1 T T Ti+1i+1的最左子符號串的最左子符號串 j jTTj jNNj+1j+1 NNi iTTi iNNi+1i+1 ，其中的，其中的N Nk k(k=1,2,(k=1,2,，n+1)n+1)可能有也可能無可能有也可能無。四、四、算符優(yōu)先文法句型的識別算符優(yōu)先文法句型的識別v質短語質

13、短語v算符優(yōu)先識別算法算符優(yōu)先識別算法例例 文法文法GZ:GZ: Z=E E=T|E+T Z=E E=T|E+T T=F|T T=F|T* *F F=(E)|iF F=(E)|i 設有輸入符號串設有輸入符號串i+(i+i)i+(i+i)* *i i， 試識別它是否是文法的句子。試識別它是否是文法的句子。五、實際應用中的五、實際應用中的算符優(yōu)先分析技術算符優(yōu)先分析技術 算符優(yōu)先分析技術由于它的簡單直觀、所需存儲容量小、算符優(yōu)先分析技術由于它的簡單直觀、所需存儲容量小、且速度快而被廣泛應用于識別各類表達式，把且速度快而被廣泛應用于識別各類表達式，把while、do與與if之類界限符也看作運算符之類

14、界限符也看作運算符 (稱作廣義運算符稱作廣義運算符)，給它們優(yōu)先，給它們優(yōu)先數(shù)，則算符優(yōu)先分析技術可擴充到整個語言的處理。對于數(shù)，則算符優(yōu)先分析技術可擴充到整個語言的處理。對于C等實際的程序設計語言，只需對文法稍加修改便可應用算符等實際的程序設計語言，只需對文法稍加修改便可應用算符優(yōu)先分析技術。算符優(yōu)先分析技術是一種行之有效、廣為應優(yōu)先分析技術。算符優(yōu)先分析技術是一種行之有效、廣為應用的分析技術。用的分析技術。五、實際應用中的五、實際應用中的算符優(yōu)先分析技術算符優(yōu)先分析技術 通常實際的編譯程序應用算符優(yōu)先分析通常實際的編譯程序應用算符優(yōu)先分析技術實現(xiàn)表達式的編譯時，使用的棧往往不技術實現(xiàn)表達式

15、的編譯時，使用的棧往往不是一個，而是兩個，即運算分量棧與運算符是一個，而是兩個，即運算分量棧與運算符棧，分別用來存放還不能生成目標棧，分別用來存放還不能生成目標(歸約歸約)的運的運算分量算分量(標識符或常量之類終結符號標識符或常量之類終結符號)與運算符與運算符(其他終結符號其他終結符號)。算法框圖如下：。算法框圖如下：5.2算符優(yōu)先分析技術5.35.3 LR(K)分析技術分析技術 5.3.1 LR(K)分析技術的邏輯結構和分析過程分析技術的邏輯結構和分析過程 5.3.2 LR(0)分析技術分析技術 5.3.3 SLR(1)分析技術分析技術 5.3.4 LR(1)分析技術分析技術5.3.1 LR

16、(K)分析技術的邏輯結分析技術的邏輯結構和分析過程構和分析過程一、活前綴與可歸前綴一、活前綴與可歸前綴二、二、 LR(K)分析技術的邏輯結構分析技術的邏輯結構三、三、LR(K)分析技術的分析過程分析技術的分析過程5.3.1 LR(K)分析技術的邏輯結構和分分析技術的邏輯結構和分析過程析過程一、活前綴與可歸前綴一、活前綴與可歸前綴 1、定義定義 對于文法對于文法GS,若若S= , VtVt* *, ,則稱則稱為為規(guī)范前綴規(guī)范前綴, ,又稱又稱活前綴活前綴。 若若是含句柄的是含句柄的活前綴，并且每個句柄是活前綴，并且每個句柄是的后綴，則的后綴，則為可歸規(guī)范前綴，或為可歸規(guī)范前綴，或可歸前綴可歸前綴

17、。 例例: (0)S:=S (4)B:=C: (0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (1)S:=CbBA (5)B:=Db (2)A:=Aab (6)C:=a (2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a (3)A:=ab (7)D:=a*rr5.3.1 LR(K)分析技術的邏輯結構和分分析技術的邏輯結構和分析過程析過程一、活前綴與可歸前綴一、活前綴與可歸前綴 1、定義定義 2 2、可歸前綴的求法、可歸前綴的求法 如某文法有可歸前綴如某文法有可歸前綴xAy ,AVn,xAy ,AVn, 若有規(guī)則：若有規(guī)則：A:=u,A:=u,則則xux

18、u也是文法的可歸前綴。也是文法的可歸前綴。 例例: :設有文法設有文法GS: (1) S:=aAcGS: (1) S:=aAc (2) A:=Abb (2) A:=Abb (3) A:=b (3) A:=br5.3.1 LR(K)分析技術的邏輯結構和分分析技術的邏輯結構和分析過程析過程二、二、 LR(K)分析技術的邏輯結構分析技術的邏輯結構 1、邏輯結構、邏輯結構 LR(K)分析器包括：總控程序和分析表分析器包括：總控程序和分析表 總控程序：根據(jù)不同的分析表決定下一步的總控程序：根據(jù)不同的分析表決定下一步的處理動作。對不同的文法，總控程序都一樣，只處理動作。對不同的文法，總控程序都一樣，只是分

19、析表不同。是分析表不同。 分析表：是分析表：是LR(K)分析技術的核心，是根據(jù)分析技術的核心，是根據(jù)具體文法按某種規(guī)則構造出來的。具體文法按某種規(guī)則構造出來的。圖8-3LR(K)分析方法的邏輯結構5.3.1 LR(K)分析技術的邏輯結構和分分析技術的邏輯結構和分析過程析過程二、二、 LR(K)分析技術的邏輯結構分析技術的邏輯結構 1、邏輯結構、邏輯結構 2、分析表的組成、分析表的組成 (1)分析動作表：分析動作表：ACTIONS,y指明當狀態(tài)指明當狀態(tài)S與與向前看符號串向前看符號串y相匹配時所應采取的動作。包括：相匹配時所應采取的動作。包括：移進、歸約、接受、出錯移進、歸約、接受、出錯 (2)

20、狀態(tài)轉換表狀態(tài)轉換表 ：GOTOS,U指明當狀態(tài)指明當狀態(tài)S與與非終結符號非終結符號U相匹配時所轉換到的下一狀態(tài)。相匹配時所轉換到的下一狀態(tài)。 (表8-3）LR(K)分析表5.3.1 LR(K)分析技術的邏輯結構和分分析技術的邏輯結構和分析過程析過程三、三、LR(K)分析技術的分析過程分析技術的分析過程 分析步驟分析步驟: (1)將初始狀態(tài)將初始狀態(tài)S0與與#壓進分析棧壓進分析棧. (2)根據(jù)棧頂狀態(tài)和當前輸入符號查動作表進行以下工作根據(jù)棧頂狀態(tài)和當前輸入符號查動作表進行以下工作: a.移進移進:當前輸入符號進符號棧當前輸入符號進符號棧,新的狀態(tài)進狀態(tài)棧新的狀態(tài)進狀態(tài)棧,繼續(xù)掃描繼續(xù)掃描. b

21、.歸約歸約:按某規(guī)則歸約按某規(guī)則歸約,若規(guī)則的右部長度若規(guī)則的右部長度n,則符號棧頂和狀態(tài)棧頂則符號棧頂和狀態(tài)棧頂n個元素同時退棧個元素同時退棧. 把歸約后的左部符號進符號棧把歸約后的左部符號進符號棧,查狀態(tài)轉換表查狀態(tài)轉換表,新的新的狀態(tài)進狀態(tài)棧狀態(tài)進狀態(tài)棧. c.接受接受: 分析成功分析成功,結束結束. d.出錯出錯: 報告出錯信息報告出錯信息. (3)重復重復(2),直到接受或出錯為止直到接受或出錯為止. 5.3.1 LR(K)分析技術的邏輯結構和分分析技術的邏輯結構和分析過程析過程三、三、LR(K)分析技術的分析過程分析技術的分析過程 分析步驟分析步驟: (1)將初始狀態(tài)將初始狀態(tài)S0

22、與與#壓進分析棧壓進分析棧. (2)根據(jù)棧頂狀態(tài)和當前輸入符號查動作表進行以下工作根據(jù)棧頂狀態(tài)和當前輸入符號查動作表進行以下工作: a.移進移進:當前輸入符號進符號棧當前輸入符號進符號棧,新的狀態(tài)進狀態(tài)棧新的狀態(tài)進狀態(tài)棧,繼續(xù)掃描繼續(xù)掃描. b.歸約歸約:按某規(guī)則歸約按某規(guī)則歸約,若規(guī)則的右部長度若規(guī)則的右部長度n,則符號棧頂和狀態(tài)棧頂則符號棧頂和狀態(tài)棧頂n個元素同時退棧個元素同時退棧. 把歸約后的左部符號進符號棧把歸約后的左部符號進符號棧,查狀態(tài)轉換表查狀態(tài)轉換表,新的新的狀態(tài)進狀態(tài)棧狀態(tài)進狀態(tài)棧. c.接受接受: 分析成功分析成功,結束結束. d.出錯出錯: 報告出錯信息報告出錯信息. (

23、3)重復重復(2),直到接受或出錯為止直到接受或出錯為止. 例例:設有文法設有文法GL: (1)L:=E,L (2)L:=E (3)E:=a (4)E:=b 分析輸入串分析輸入串#a,b,a#5.3.2 LR(0)分析技術分析技術 一、基本概念一、基本概念 二、項集規(guī)范族和特征有窮狀態(tài)機二、項集規(guī)范族和特征有窮狀態(tài)機 三、三、 LR(0)分析表的構造分析表的構造 四、應用舉例四、應用舉例5.3.2 LR(0)分析技術分析技術一、基本概念一、基本概念(1) LR(0)(1) LR(0)項項 定義定義5.145.14 如果如果=uv=uv是文法是文法G G的一個規(guī)則，的一個規(guī)則，其中其中u u或或

24、v v可為空串，則可為空串，則Uu.vUu.v稱為稱為G G的一個的一個LR(0)LR(0)項，簡稱項。項，簡稱項。 完備項：完備項：圓點在整個右部之后的圓點在整個右部之后的LR(0)LR(0)項稱為完備項。項稱為完備項。 接受項接受項：如果一個完備項呈如果一個完備項呈Zu.形，形，Z是識別符號。是識別符號。 歸約項歸約項：其余所有的完備項稱歸約項：其余所有的完備項稱歸約項 。 不完備項：不完備項：不是完備項的項不是完備項的項 。 移入項移入項 ：圓點之后是終結符號的不完備項。：圓點之后是終結符號的不完備項。 待約項待約項：圓點之后是非終結符號的不完備項：圓點之后是非終結符號的不完備項 。 5

25、.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念 (1) LR(0)項項 (2) 初始項初始項 定義定義5.15 文法文法GZ的的LR(0)項項Z.u稱為稱為G的初始的初始LR(0)項，簡稱初始項。項，簡稱初始項。 5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念 (1) LR(0)項項 (2) 初始項初始項 定義定義5.20 文法文法GZ的的LR(0)項項Z.u稱為稱為G的初始的初始LR(0)項，簡稱初始項。項，簡稱初始項。 (3) 后繼項后繼項 定義定義5.16 設設u.Av是文法是文法G的一個的一個LR(0)項，其中項，其中AVNVT，則，則LR(0)項項uA.

26、v稱為稱為它的后繼項。它的后繼項。 5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念 (4) 項集項集 定義定義5.17 由由LR(0)項組成的集合稱項組成的集合稱LR(0)項集，項集，簡稱項集。簡稱項集。 后繼項集后繼項集: 如果識別程序所處狀態(tài)所對應的如果識別程序所處狀態(tài)所對應的項集中有一個項，其中圓點后面是符號項集中有一個項，其中圓點后面是符號X，則識別，則識別程序在該符號程序在該符號X下將進入所處狀態(tài)的下將進入所處狀態(tài)的X_后繼狀態(tài)。后繼狀態(tài)。相應的項集稱相應的項集稱X_后繼項集。后繼項集。 每個項集每個項集Si的后繼項集的后繼項集S通常是基本項集的閉通常是基本項集的閉包

27、集合，基本項集可直接由項集包集合，基本項集可直接由項集Si生成，生成， 即即uA.v|u.AvSi 5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念 (5)項集的閉包項集的閉包 定義定義5.18 設設Si是文法是文法G的一個項集，項集的一個項集，項集Si 的閉包的閉包CLOSURE(Si )是按下列步驟構造而得的項是按下列步驟構造而得的項集。集。 步驟步驟1 Si中每個項在中每個項在CLOSURE(Si)中；中； 步驟步驟2 如果如果u.VvCLOSURE(Si )，且，且V =w是一個規(guī)則，則把是一個規(guī)則，則把V.w添入添入CLOSURE(Si )中；中； 步驟步驟3 重復步驟

28、重復步驟2，直到，直到CLOSURE(Si )不再擴不再擴大。這時所得的便是項集大。這時所得的便是項集Si的閉包的閉包CLOSURE(Si)。 5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念二、項集規(guī)范族和特征有窮狀態(tài)機二、項集規(guī)范族和特征有窮狀態(tài)機 一個文法一個文法GZ的的LR(0)項集規(guī)范族的構造步驟：項集規(guī)范族的構造步驟： 步驟步驟1 初始項集初始項集S0=CLOSURE(Z.Z)是是G 的的LR(0)項集，這里項集，這里Z是包含有規(guī)則是包含有規(guī)則 Z =Z的增廣文法之識別符號；的增廣文法之識別符號； 步驟步驟2 如果如果Si是是G的項集，則的項集，則Si的一切后繼項集的

29、一切后繼項集 均是均是G的項集；的項集； 步驟步驟3 重復步驟重復步驟2，直到再無新的項集可以添入。，直到再無新的項集可以添入。 5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念二、項集規(guī)范族和特征有窮狀態(tài)機二、項集規(guī)范族和特征有窮狀態(tài)機 一個文法一個文法GZ的的LR(0)項集規(guī)范族項集規(guī)范族的構造步驟：的構造步驟： 步驟步驟1 初始項集初始項集S0=CLOSURE(Z.Z)是是G的的LR(0)項集，這里項集，這里Z是是包含有規(guī)則包含有規(guī)則Z =Z的增廣文法之識別符號；的增廣文法之識別符號； 步驟步驟2 如果如果Si是是G的項集，則的項集，則Si的一切后繼項集均是的一切后繼項集均

30、是G的項集；的項集； 步驟步驟3 重復步驟重復步驟2，直到再無新的項集可以添入。，直到再無新的項集可以添入。 特別說明特別說明: 某一項集中某一項集中,不同的項不同的項,其后繼符號相同時其后繼符號相同時,后繼項集相同。后繼項集相同。 不同的不同的項集中項集中,若干個與前面對應相同的項若干個與前面對應相同的項,其后繼項集與其后繼項集與前面的相同。前面的相同。例：設有文法例：設有文法GS：(1)S:=A (4)A:=c (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念二、項集規(guī)范族和特征有窮狀態(tài)機二、項集規(guī)范族和特

31、征有窮狀態(tài)機 一個文法一個文法GZ的的LR(0)項集規(guī)范族項集規(guī)范族的構造步驟：的構造步驟： 步驟步驟1 初始項集初始項集S0=CLOSURE(Z.Z)是是G的的LR(0)項集，這里項集，這里Z是是包含有規(guī)則包含有規(guī)則Z =Z的增廣文法之識別符號；的增廣文法之識別符號； 步驟步驟2 如果如果Si是是G的項集，則的項集，則Si的一切后繼項集均是的一切后繼項集均是G的項集；的項集； 步驟步驟3 重復步驟重復步驟2，直到再無新的項集可以添入。，直到再無新的項集可以添入。 特別說明特別說明: 某一項集中某一項集中,不不 同的項同的項,其后繼符號相同時其后繼符號相同時,后繼項集相同。后繼項集相同。 不同

32、的不同的項集中項集中,若干個與前面對應相同的項若干個與前面對應相同的項,其后繼項集與其后繼項集與前面的相同。前面的相同。例：增廣文法例：增廣文法GS：(0)S=S(1)S:=A (4)A:=c (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d圖8-55.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念二、項集規(guī)范族和特征有窮狀態(tài)機二、項集規(guī)范族和特征有窮狀態(tài)機 文法的文法的LR(0)項集規(guī)范族可以被抽象成一個有窮狀態(tài)機項集規(guī)范族可以被抽象成一個有窮狀態(tài)機(FSM)，其步驟如下，其步驟如下:步驟步驟1 把各個項集定義為該把各個項集定義為該FSM的內部狀態(tài)，并用項集

33、的編的內部狀態(tài)，并用項集的編號來命名各個狀態(tài)，因此，每一個項集在號來命名各個狀態(tài)，因此，每一個項集在FSM中有一個對中有一個對應狀態(tài)；應狀態(tài)；步驟步驟2 讓該讓該FSM狀態(tài)之間的轉換對應于后繼關系。狀態(tài)之間的轉換對應于后繼關系。步驟步驟3 與初始項集對應的狀態(tài)作為該與初始項集對應的狀態(tài)作為該FSM的初始狀態(tài)，與的初始狀態(tài)，與#歸歸約約_后繼項集對應的狀態(tài)作為該后繼項集對應的狀態(tài)作為該FSM的終止狀態(tài)。的終止狀態(tài)。這種有窮狀態(tài)機這種有窮狀態(tài)機FSM稱為文法的稱為文法的特征有窮狀態(tài)機特征有窮狀態(tài)機 (CFSM)。 5.3.2 LR(0)分析技術分析技術一、一、基本概念基本概念二、項集規(guī)范族和特征有

34、窮狀態(tài)機二、項集規(guī)范族和特征有窮狀態(tài)機 如果項集中包含的全是完備項，則稱相應狀態(tài)如果項集中包含的全是完備項，則稱相應狀態(tài)為為歸約狀態(tài)歸約狀態(tài) ；如果項集中包含的全是不完備項，；如果項集中包含的全是不完備項，則稱相應的狀態(tài)為則稱相應的狀態(tài)為讀狀態(tài)讀狀態(tài)；如果項集中既有完備項，；如果項集中既有完備項，又有不完備項，則稱相應的狀態(tài)為又有不完備項，則稱相應的狀態(tài)為不適定狀態(tài)不適定狀態(tài)。 定義定義5.19 一個上下文無關文法一個上下文無關文法G是是LR(0)文文法法，當且僅當該文法，當且僅當該文法G的的CFSM中無不適定狀態(tài)。中無不適定狀態(tài)。5.3.2 LR(0)分析技術分析技術 三、三、 LR(0)分

35、析表的構造分析表的構造 (i)如果移入項如果移入項u.avSi,且且GO(Si,a)=Sj，其中，其中aVt，則置，則置ACTIONSi,a=把狀態(tài)把狀態(tài)j及符號及符號a移入移入(下推下推)進棧進棧，簡記作，簡記作Sj。 (ii)如果歸約項如果歸約項u.Si，且，且 =u是增廣文法是增廣文法G的第的第j個規(guī)個規(guī)則，則對任何輸入符號則，則對任何輸入符號a,aVt，置，置ACTIONSi,a=按第按第j個規(guī)個規(guī)則則 =u進行直接歸約進行直接歸約，簡記作，簡記作rj。 (iii)如果項如果項ZZ.Si，置，置ACTIONSi,#為為接受接受，簡記作，簡記作acc。 (iv)如果如果GO(Si,)=S

36、j,Vn，則置，則置GOTOSi,U=j。 (v)凡不能由上述凡不能由上述4個規(guī)則確定的分析表元素全置為報錯標志個規(guī)則確定的分析表元素全置為報錯標志(空空白白)。 表8-5例：增廣文法例：增廣文法GS：(0)S=S(1)S:=A (4)A:=c (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d5.3.2 LR(0)分析技術分析技術四、四、 應用舉例應用舉例例：設有文法例：設有文法GS: (1)S:=A (4)A:=c (0) S:=S (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d 構造項集規(guī)范族和構造項集規(guī)范族和 LR(0)分析表，并對輸入串分析

37、表，并對輸入串 #aacbb#進行分析。進行分析。 5.3.3 SLR(1)分析技術分析技術 一、問題的提出一、問題的提出 二、簡單向前看二、簡單向前看1集合集合 三、三、 SLR(1)文法文法 四、四、 SLR(1)分析表的構造分析表的構造 五、應用舉例五、應用舉例5.3.3 SLR(1)分析技術分析技術一、問題的提出一、問題的提出 例：設有文法例：設有文法GS：(0)S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i 5.3.3 SLR(1)分析技術分析技術 一、問題的提出一、問題的提出 例：設有文法例：設有文法GS：(0)

38、S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i S2：E T. 歸約項歸約項 T T.T.* *F F 移入項移入項 S9: E E+T. E+T. 歸約項歸約項 TT.TT.* *F F 移入項移入項 S2 和和S9均為不適定狀態(tài)均為不適定狀態(tài),文法文法GS不是不是LR(0)文法。文法。5.3.3 SLR(1)分析技術分析技術二、簡單向前看二、簡單向前看1集合集合 定義定義5.20 一個簡單向前看一個簡單向前看1集合是某些文法符號組成的集合是某些文法符號組成的集合，它和集合，它和CFSM中一個不適定狀態(tài)的各個轉換相聯(lián)系。不

39、中一個不適定狀態(tài)的各個轉換相聯(lián)系。不適定狀態(tài)的轉換有兩類適定狀態(tài)的轉換有兩類: 一類是文法符號一類是文法符號X下的轉換下的轉換(稱稱X_轉換轉換)，簡單向前看，簡單向前看1集合便是集合便是X， 另一類是另一類是# =u轉換轉換，簡單向前看，簡單向前看1集合是集合是FT1()： FT1()=FOLLOW() 例：文法例：文法GS的的CFSM的狀態(tài)的狀態(tài)S2是不適定狀態(tài)，對于它是不適定狀態(tài)，對于它的簡單向前看的簡單向前看1集合，存在兩類轉換：集合，存在兩類轉換： *_轉換轉換 簡單向前看簡單向前看1集合是集合是* #E =T轉換轉換 簡單向前看簡單向前看1集合是集合是 FT1(E) FT1(E)=

40、FOLLOW(E)=+,)，#5.3.3 SLR(1)分析技術分析技術 三、三、 SLR(1)文法文法 定義定義5.21 一個上下文無關文法一個上下文無關文法G是是SLR(1)文文法，當且僅當與其法，當且僅當與其CFSM每個不適定狀態(tài)的各個每個不適定狀態(tài)的各個T_轉換與轉換與# =u轉換相聯(lián)系的簡單向前看轉換相聯(lián)系的簡單向前看1集合集合互不相交?；ゲ幌嘟?。 5.3.3 SLR(1)分析技術分析技術 四、四、 SLR(1)分析表的構造分析表的構造 分析表中的分析表中的ACTION部分與部分與GOTO部分可按下述規(guī)則構造如下部分可按下述規(guī)則構造如下:(i)如果移入項如果移入項u.avSi,且且GO

41、(Si,a)=Sj，其中，其中aVt，則置，則置ACTIONSi,a=把狀態(tài)把狀態(tài)j及符號及符號a移入移入(下推下推)進棧進棧，簡記作，簡記作Sj。(ii)如果歸約項如果歸約項u.Si，且，且 =u是增廣文法是增廣文法G的第的第j個規(guī)則，個規(guī)則，則對任何輸入符號則對任何輸入符號a,aFT1()，置，置ACTIONSi,a=按第按第j個規(guī)則個規(guī)則 =u進行直接歸約進行直接歸約，簡記作，簡記作rj。(iii)如果項如果項ZZ.Si，置，置ACTIONSi,#為為接受接受，簡記作，簡記作acc。(iv)如果如果GO(Si,)=Sj,VN，則置，則置GOTOSi,=j。(v)凡不能由上述凡不能由上述4

42、個規(guī)則確定的分析表元素全置為報錯標志個規(guī)則確定的分析表元素全置為報錯標志(空白空白)。 5.3.3 SLR(1)分析技術分析技術五、應用舉例五、應用舉例 例：設有文法例：設有文法GS：(0)S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i 對輸入串對輸入串i+i*i#進行分析。進行分析。 *5.3.4 LR(1)分析技術分析技術 一、問題的提出一、問題的提出例例: : 設有文法設有文法S:S:(0)S:=S (4)B:=C(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db(1)S:=CbBA (5)B:=D

43、b (2)A:=Aab (6)C:=a(2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a(3)A:=ab (7)D:=a 其項集規(guī)范族如下圖所示其項集規(guī)范族如下圖所示: :5.3.4 LR(1)分析技術分析技術 一、問題的提出一、問題的提出 考察狀態(tài)考察狀態(tài) S8 : C a,D a S10: SCbBA,A A.ab 對對S10，F(xiàn)T1(S)=# 與與 a 不相交不相交, 對對S8, FT1(C)=Follow(C)=a,b , FT1(D)= Follow(D)=b 有交集有交集, 因此該文法不能使用因此該文法不能使用SLR(1)分析技術分析技術.例例:設有文法設有文法S

44、:(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a5.3.4 LR(1)分析技術分析技術 二、二、 幾個基本概念幾個基本概念 1、LR(1)項項 定義：在定義：在LR(0)項中放一個向前搜索符號項中放一個向前搜索符號a, 成為形式成為形式: A .,a, 其中其中a Follow(A),Follow(A),稱為稱為LR(1)項。項。 2 2、有效項、有效項 定義定義: :設有文法設有文法GS,LR(1)GS,LR(1)項項A A . ,a 對活前綴對活前綴= =有效有效, ,是指存在規(guī)范推導：是指存在規(guī)

45、范推導：S=S=Ay=Ay=y, y VtVt* *, ,且滿足下列條件且滿足下列條件: :當當y=y=, a=# , a=# 當當y y, a=First(y), a=First(y) 考慮規(guī)范句型考慮規(guī)范句型:Cbabab:Cbabab和和CbaababCbaabab*rr例例:設有文法設有文法S:(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a5.3.4 LR(1)分析技術分析技術 二、二、 幾個基本概念幾個基本概念 3 3、LR(1)LR(1)項集的閉包項集的閉包 定義定義 設設Si是文法是文法G的一個的一個LR(1)項集，項集項集，項集Si的閉包的閉包CLOSURE(Si )是按下列步驟構造而得的項集。是按下列步驟構造而得的項集。 步驟步驟1 Si 中每個項在中每個項在CLOSURE(Si )中；中； 步驟步驟2 如果如果u.Vv,aCLOSURE(Si )，且，且V =w是一個規(guī)則，則把是一個規(guī)則，則把V.w,b,添入添入CLOSURE(Si )中中,這里這里b=First(va)； 步驟步驟3 重復步驟重復步驟2，直到，直到CLOSURE(Si )不再擴大。這不再擴大。這時所