語法分析——自底向上分析技術(shù)

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

2、入符號(hào)串是相應(yīng)文法的句子，否則就不是。 當(dāng)句型分析過程中每個(gè)分析步都對(duì)最左的簡單短語進(jìn)當(dāng)句型分析過程中每個(gè)分析步都對(duì)最左的簡單短語進(jìn)行直接歸約時(shí)，自底向上分析技術(shù)的兩個(gè)基本問題可以更行直接歸約時(shí)，自底向上分析技術(shù)的兩個(gè)基本問題可以更確切地?cái)⑹鰹椋捍_切地?cái)⑹鰹椋喝绾握页鼍浔绾握页鼍浔凹鞍汛司浔苯託w約為哪個(gè)把此句柄直接歸約為哪個(gè)非終結(jié)符號(hào)非終結(jié)符號(hào)。5.1 引言引言5.1.1 自底向上分析技術(shù)及識(shí)別算法自底向上分析技術(shù)及識(shí)別算法5.1.2 討論的前提討論的前提 識(shí)別過程是從左到右、自底向上地進(jìn)行的，一般識(shí)別過程是從左到右、自底向上地進(jìn)行的，一般都將采用規(guī)范歸約；除了特別指明的以外，每一步都將

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

4、棧中除了棧底標(biāo)志符號(hào)當(dāng)識(shí)別程序發(fā)現(xiàn)棧中除了棧底標(biāo)志符號(hào)# #外外僅有識(shí)別符號(hào)，而輸入也已到達(dá)右端僅有識(shí)別符號(hào)，而輸入也已到達(dá)右端# #，則接受；，則接受；v報(bào)錯(cuò)：報(bào)錯(cuò)：當(dāng)識(shí)別程序察覺一個(gè)錯(cuò)誤，因此輸入符號(hào)串當(dāng)識(shí)別程序察覺一個(gè)錯(cuò)誤，因此輸入符號(hào)串不是句子而無法繼續(xù)識(shí)別工作時(shí)，調(diào)用一個(gè)出錯(cuò)處不是句子而無法繼續(xù)識(shí)別工作時(shí)，調(diào)用一個(gè)出錯(cuò)處理子程序進(jìn)行處理或停止。理子程序進(jìn)行處理或停止。 步驟 棧 輸入 動(dòng)作 規(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 設(shè)有文法設(shè)有文法GEGE：E=E+E|EE=E+E|E* *E|(E)|iE|(E)|i自底向上分析技術(shù)的步驟自底向上分析技術(shù)的步驟: : 1) 1) 找出句柄找出句柄u;u; 2) 2) 找出規(guī)則找出規(guī)則U=uU=u； 3) 把把u u直接歸約成直接歸約成U U。 分析技術(shù)不同分析技術(shù)不同, ,尋找句柄的方法也不同。尋找句柄的方法也不同。5.25.2 算符優(yōu)先分析技術(shù)算符優(yōu)先分析技術(shù) 一、一、算符優(yōu)先分析技術(shù)的

6、引進(jìn)算符優(yōu)先分析技術(shù)的引進(jìn) 二、二、算符文法算符文法 三、三、算符優(yōu)先關(guān)系與算符優(yōu)先文法算符優(yōu)先關(guān)系與算符優(yōu)先文法 四、四、算符優(yōu)先文法句型的識(shí)別算符優(yōu)先文法句型的識(shí)別 五、實(shí)際應(yīng)用中的五、實(shí)際應(yīng)用中的算符優(yōu)先分析技術(shù)算符優(yōu)先分析技術(shù) 一、算符優(yōu)先分析技術(shù)的引進(jìn)一、算符優(yōu)先分析技術(shù)的引進(jìn) 對(duì)算術(shù)表達(dá)式，運(yùn)算符完全決定了運(yùn)算對(duì)算術(shù)表達(dá)式，運(yùn)算符完全決定了運(yùn)算次序，運(yùn)算次序，運(yùn)算對(duì)象完全不起作用。對(duì)象完全不起作用。 因此，將文法中的因此，將文法中的終結(jié)符號(hào)終結(jié)符號(hào)看作看作運(yùn)算符運(yùn)算符； 非終結(jié)符號(hào)非終結(jié)符號(hào)看作看作運(yùn)算對(duì)象運(yùn)算對(duì)象。 算符優(yōu)先分析技術(shù)：只在終結(jié)符號(hào)之間算符優(yōu)先分析技術(shù)：只在終結(jié)符號(hào)

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

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

9、僅當(dāng)文法G G中存在形如中存在形如U=U=T Tj jV V的規(guī)則，其中的規(guī)則，其中V=TV=Ti i或或V=WTV=WTi i；T Tj jT Ti i 當(dāng)且僅當(dāng)文法當(dāng)且僅當(dāng)文法G G中存在形如中存在形如U=U=VTVTi i的規(guī)則，其中的規(guī)則，其中V=V=T Tj j或或V=V=T Tj jW W。例例 設(shè)有文法設(shè)有文法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)先分析技術(shù)算符優(yōu)先分析技術(shù) 一、一、算符優(yōu)先分析技

10、術(shù)的引進(jìn)算符優(yōu)先分析技術(shù)的引進(jìn) 二、二、算符文法算符文法 三、三、算符優(yōu)先關(guān)系與算符優(yōu)先文法算符優(yōu)先關(guān)系與算符優(yōu)先文法v算符優(yōu)先關(guān)系算符優(yōu)先關(guān)系v算符優(yōu)先文法算符優(yōu)先文法定義定義5.55.5 設(shè)有算符文法設(shè)有算符文法G G，如果在它的任意兩，如果在它的任意兩個(gè)終結(jié)符號(hào)之間，算符優(yōu)先關(guān)系個(gè)終結(jié)符號(hào)之間，算符優(yōu)先關(guān)系 =、與、與至多只有一種關(guān)系成立，則稱該文法至多只有一種關(guān)系成立，則稱該文法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)先分析技術(shù)5.2.1算符優(yōu)先分析技術(shù)的引進(jìn)5.2.2算符文法四、四、算符優(yōu)先文法句型的識(shí)別算符優(yōu)先文法句型的識(shí)別v質(zhì)短語質(zhì)短語v算符優(yōu)先識(shí)別算法算符優(yōu)先識(shí)別算法定義定義5.65.6 設(shè)有算符文法設(shè)有算符文法GZGZ，( (句型的句型的) )質(zhì)短語定義為這樣一個(gè)短語：質(zhì)短語定義為這樣一個(gè)短語：它至少包含一個(gè)終結(jié)符號(hào)，且除它自身外不再包含其他質(zhì)短語。它至少包含一個(gè)終結(jié)符號(hào)，且除它自身外不再包含其他質(zhì)短語。例例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 一個(gè)算符優(yōu)先文法句型一個(gè)算符優(yōu)先文法句型NN1 1TT1 1NN2 2 NNn nTTn nNNn+1 的最左質(zhì)的最左質(zhì)短語是滿足條件：短語是滿足條件：T Tj j1 1 T T Ti+1i+1的最左子符號(hào)串的最左子符號(hào)串 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)先文法句型的識(shí)別算符優(yōu)先文法句型的識(shí)別v質(zhì)短語質(zhì)

13、短語v算符優(yōu)先識(shí)別算法算符優(yōu)先識(shí)別算法例例 文法文法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 設(shè)有輸入符號(hào)串設(shè)有輸入符號(hào)串i+(i+i)i+(i+i)* *i i， 試識(shí)別它是否是文法的句子。試識(shí)別它是否是文法的句子。五、實(shí)際應(yīng)用中的五、實(shí)際應(yīng)用中的算符優(yōu)先分析技術(shù)算符優(yōu)先分析技術(shù) 算符優(yōu)先分析技術(shù)由于它的簡單直觀、所需存儲(chǔ)容量小、算符優(yōu)先分析技術(shù)由于它的簡單直觀、所需存儲(chǔ)容量小、且速度快而被廣泛應(yīng)用于識(shí)別各類表達(dá)式，把且速度快而被廣泛應(yīng)用于識(shí)別各類表達(dá)式，把while、do與與if之類界限符也看作運(yùn)算符之類

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

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

16、(K)分析技術(shù)的邏輯結(jié)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程構(gòu)和分析過程一、活前綴與可歸前綴一、活前綴與可歸前綴二、二、 LR(K)分析技術(shù)的邏輯結(jié)構(gòu)分析技術(shù)的邏輯結(jié)構(gòu)三、三、LR(K)分析技術(shù)的分析過程分析技術(shù)的分析過程5.3.1 LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分分析技術(shù)的邏輯結(jié)構(gòu)和分析過程析過程一、活前綴與可歸前綴一、活前綴與可歸前綴 1、定義定義 對(duì)于文法對(duì)于文法GS,若若S= , VtVt* *, ,則稱則稱為為規(guī)范前綴規(guī)范前綴, ,又稱又稱活前綴活前綴。 若若是含句柄的是含句柄的活前綴，并且每個(gè)句柄是活前綴，并且每個(gè)句柄是的后綴，則的后綴，則為可歸規(guī)范前綴，或?yàn)榭蓺w規(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)分析技術(shù)的邏輯結(jié)構(gòu)和分分析技術(shù)的邏輯結(jié)構(gòu)和分析過程析過程一、活前綴與可歸前綴一、活前綴與可歸前綴 1、定義定義 2 2、可歸前綴的求法、可歸前綴的求法 如某文法有可歸前綴如某文法有可歸前綴xAy ,AVn,xAy ,AVn, 若有規(guī)則：若有規(guī)則：A:=u,A:=u,則則xux

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、的不同的項(xiàng)集中項(xiàng)集中,若干個(gè)與前面對(duì)應(yīng)相同的項(xiàng)若干個(gè)與前面對(duì)應(yīng)相同的項(xiàng),其后繼項(xiàng)集與其后繼項(xiàng)集與前面的相同。前面的相同。例：增廣文法例：增廣文法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)分析技術(shù)分析技術(shù)一、一、基本概念基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī) 文法的文法的LR(0)項(xiàng)集規(guī)范族可以被抽象成一個(gè)有窮狀態(tài)機(jī)項(xiàng)集規(guī)范族可以被抽象成一個(gè)有窮狀態(tài)機(jī)(FSM)，其步驟如下，其步驟如下:步驟步驟1 把各個(gè)項(xiàng)集定義為該把各個(gè)項(xiàng)集定義為該FSM的內(nèi)部狀態(tài)，并用項(xiàng)集

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

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

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

36、j,Vn，則置，則置GOTOSi,U=j。 (v)凡不能由上述凡不能由上述4個(gè)規(guī)則確定的分析表元素全置為報(bào)錯(cuò)標(biāo)志個(gè)規(guī)則確定的分析表元素全置為報(bào)錯(cuò)標(biāo)志(空空白白)。 表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)分析技術(shù)分析技術(shù)四、四、 應(yīng)用舉例應(yīng)用舉例例：設(shè)有文法例：設(shè)有文法GS: (1)S:=A (4)A:=c (0) S:=S (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d 構(gòu)造項(xiàng)集規(guī)范族和構(gòu)造項(xiàng)集規(guī)范族和 LR(0)分析表，并對(duì)輸入串分析

37、表，并對(duì)輸入串 #aacbb#進(jìn)行分析。進(jìn)行分析。 5.3.3 SLR(1)分析技術(shù)分析技術(shù) 一、問題的提出一、問題的提出 二、簡單向前看二、簡單向前看1集合集合 三、三、 SLR(1)文法文法 四、四、 SLR(1)分析表的構(gòu)造分析表的構(gòu)造 五、應(yīng)用舉例五、應(yīng)用舉例5.3.3 SLR(1)分析技術(shù)分析技術(shù)一、問題的提出一、問題的提出 例：設(shè)有文法例：設(shè)有文法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)分析技術(shù)分析技術(shù) 一、問題的提出一、問題的提出 例：設(shè)有文法例：設(shè)有文法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. 歸約項(xiàng)歸約項(xiàng) T T.T.* *F F 移入項(xiàng)移入項(xiàng) S9: E E+T. E+T. 歸約項(xiàng)歸約項(xiàng) TT.TT.* *F F 移入項(xiàng)移入項(xiàng) S2 和和S9均為不適定狀態(tài)均為不適定狀態(tài),文法文法GS不是不是LR(0)文法。文法。5.3.3 SLR(1)分析技術(shù)分析技術(shù)二、簡單向前看二、簡單向前看1集合集合 定義定義5.20 一個(gè)簡單向前看一個(gè)簡單向前看1集合是某些文法符號(hào)組成的集合是某些文法符號(hào)組成的集合，它和集合，它和CFSM中一個(gè)不適定狀態(tài)的各個(gè)轉(zhuǎn)換相聯(lián)系。不

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

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

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

42、個(gè)規(guī)則確定的分析表元素全置為報(bào)錯(cuò)標(biāo)志個(gè)規(guī)則確定的分析表元素全置為報(bào)錯(cuò)標(biāo)志(空白空白)。 5.3.3 SLR(1)分析技術(shù)分析技術(shù)五、應(yīng)用舉例五、應(yīng)用舉例 例：設(shè)有文法例：設(shè)有文法GS：(0)S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i 對(duì)輸入串對(duì)輸入串i+i*i#進(jìn)行分析。進(jìn)行分析。 *5.3.4 LR(1)分析技術(shù)分析技術(shù) 一、問題的提出一、問題的提出例例: : 設(shè)有文法設(shè)有文法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 其項(xiàng)集規(guī)范族如下圖所示其項(xiàng)集規(guī)范族如下圖所示: :5.3.4 LR(1)分析技術(shù)分析技術(shù) 一、問題的提出一、問題的提出 考察狀態(tài)考察狀態(tài) S8 : C a,D a S10: SCbBA,A A.ab 對(duì)對(duì)S10，F(xiàn)T1(S)=# 與與 a 不相交不相交, 對(duì)對(duì)S8, FT1(C)=Follow(C)=a,b , FT1(D)= Follow(D)=b 有交集有交集, 因此該文法不能使用因此該文法不能使用SLR(1)分析技術(shù)分析技術(shù).例例:設(shè)有文法設(shè)有文法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)分析技術(shù)分析技術(shù) 二、二、 幾個(gè)基本概念幾個(gè)基本概念 1、LR(1)項(xiàng)項(xiàng) 定義：在定義：在LR(0)項(xiàng)中放一個(gè)向前搜索符號(hào)項(xiàng)中放一個(gè)向前搜索符號(hào)a, 成為形式成為形式: A .,a, 其中其中a Follow(A),Follow(A),稱為稱為LR(1)項(xiàng)。項(xiàng)。 2 2、有效項(xiàng)、有效項(xiàng) 定義定義: :設(shè)有文法設(shè)有文法GS,LR(1)GS,LR(1)項(xiàng)項(xiàng)A A . ,a 對(duì)活前綴對(duì)活前綴= =有效有效, ,是指存在規(guī)范推導(dǎo)：是指存在規(guī)

45、范推導(dǎo)：S=S=Ay=Ay=y, y VtVt* *, ,且滿足下列條件且滿足下列條件: :當(dāng)當(dāng)y=y=, a=# , a=# 當(dāng)當(dāng)y y, a=First(y), a=First(y) 考慮規(guī)范句型考慮規(guī)范句型:Cbabab:Cbabab和和CbaababCbaabab*rr例例:設(shè)有文法設(shè)有文法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)分析技術(shù)分析技術(shù) 二、二、 幾個(gè)基本概念幾個(gè)基本概念 3 3、LR(1)LR(1)項(xiàng)集的閉包項(xiàng)集的閉包 定義定義 設(shè)設(shè)Si是文法是文法

46、G的一個(gè)的一個(gè)LR(1)項(xiàng)集，項(xiàng)集項(xiàng)集，項(xiàng)集Si的閉包的閉包CLOSURE(Si )是按下列步驟構(gòu)造而得的項(xiàng)集。是按下列步驟構(gòu)造而得的項(xiàng)集。 步驟步驟1 Si 中每個(gè)項(xiàng)在中每個(gè)項(xiàng)在CLOSURE(Si )中；中； 步驟步驟2 如果如果u.Vv,aCLOSURE(Si )，且，且V =w是一個(gè)規(guī)則，則把是一個(gè)規(guī)則，則把V.w,b,添入添入CLOSURE(Si )中中,這里這里b=First(va)； 步驟步驟3 重復(fù)步驟重復(fù)步驟2，直到，直到CLOSURE(Si )不再擴(kuò)大。這不再擴(kuò)大。這時(shí)所得的便是時(shí)所得的便是LR(1)項(xiàng)集項(xiàng)集Si的閉包的閉包CLOSURE(Si )。 特別說明特別說明:每一個(gè)每一個(gè)LR(1)項(xiàng)與其后繼項(xiàng)有相同的向前搜索符號(hào)項(xiàng)與其后繼項(xiàng)有相同的向前搜索符號(hào). 例例:設(shè)有文法設(shè)有文法S:(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (2)A: