1、1什么是什么是LR(k)LR(k)分析分析: : L L：從左到右掃描：從左到右掃描 R R：最右推導(dǎo)的逆過(guò)程（最左歸約）：最右推導(dǎo)的逆過(guò)程（最左歸約） k k：為作出分析決定而向前看的輸入符號(hào)的個(gè)數(shù)：為作出分析決定而向前看的輸入符號(hào)的個(gè)數(shù) 是一種規(guī)范歸約過(guò)程是一種規(guī)范歸約過(guò)程 LR(k) LR(k)分析技術(shù)分析技術(shù)KnuthKnuth于于19651965年首先提出年首先提出4.7 LR4.7 LR分析法分析法2q 適用范圍廣適用范圍廣，適用于多數(shù)無(wú)二義性，適用于多數(shù)無(wú)二義性2 2型文法型文法q 分析分析效率高效率高，報(bào)錯(cuò)及時(shí)報(bào)錯(cuò)及時(shí)q 可以可以自動(dòng)生成自動(dòng)生成q 手工實(shí)現(xiàn)手工實(shí)現(xiàn)工作量大工作

2、量大LRLR分析法的優(yōu)缺點(diǎn)分析法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)4.7 LR4.7 LR分析法分析法3LRLR分析器的邏輯結(jié)構(gòu)：分析器的邏輯結(jié)構(gòu)：分析棧、分析表、總控程序分析棧、分析表、總控程序LRLR分析器的邏輯結(jié)構(gòu)和工作過(guò)程分析器的邏輯結(jié)構(gòu)和工作過(guò)程棧棧# #S S0 0X X1 1S S1 1X Xm mS S1 1文法符號(hào)文法符號(hào)狀態(tài)狀態(tài)輸入輸入#總控程序總控程序ACTION GOTOLRLR分析表分析表產(chǎn)生式表產(chǎn)生式表輸出輸出4.7 LR4.7 LR分析法分析法4分析表的種類：四類分析表的種類：四類SLR(1)SLR(1)分析表分析表( (簡(jiǎn)單簡(jiǎn)單LRLR分析表分析表) ) LR(0)LR(

3、0)分析表分析表構(gòu)造簡(jiǎn)單構(gòu)造簡(jiǎn)單, ,最易實(shí)現(xiàn)最易實(shí)現(xiàn), ,大多數(shù)上下文無(wú)關(guān)文法都可以大多數(shù)上下文無(wú)關(guān)文法都可以構(gòu)造出構(gòu)造出SLRSLR分析表，所以具有較高的實(shí)用價(jià)值。使分析表，所以具有較高的實(shí)用價(jià)值。使用用SLRSLR分析表進(jìn)行語(yǔ)法分析的分析器叫分析表進(jìn)行語(yǔ)法分析的分析器叫SLRSLR分析器。分析器。對(duì)文法的限制較大，無(wú)實(shí)用價(jià)值，對(duì)文法的限制較大，無(wú)實(shí)用價(jià)值，是構(gòu)造其它是構(gòu)造其它LRLR分析表的基礎(chǔ)。分析表的基礎(chǔ)。（重點(diǎn)掌握）（重點(diǎn)掌握）4.7 LR4.7 LR分析法分析法5LR(1)LR(1)分析表分析表( (規(guī)范規(guī)范LRLR分析表分析表) )適用文法類最大適用文法類最大, ,幾乎所有上下

4、文無(wú)關(guān)文法幾乎所有上下文無(wú)關(guān)文法都能構(gòu)造出都能構(gòu)造出LR(1)LR(1)分析表，但其分析表體積分析表，但其分析表體積太大，實(shí)用價(jià)值不大。太大，實(shí)用價(jià)值不大。LALR分析表分析表(超前超前LR分析表分析表) 這種表適用的文法類及其實(shí)現(xiàn)上難易在這種表適用的文法類及其實(shí)現(xiàn)上難易在LR(1)LR(1)和和SLR(1)SLR(1)兩種之間，比較實(shí)用。使用兩種之間，比較實(shí)用。使用LALRLALR分分析表進(jìn)行語(yǔ)法分析的分析器叫析表進(jìn)行語(yǔ)法分析的分析器叫LALRLALR分析器。分析器。說(shuō)明：四種分析表對(duì)應(yīng)四類文法說(shuō)明：四種分析表對(duì)應(yīng)四類文法4.7 LR4.7 LR分析法分析法6LR(0)LR(0)分析法分析法

5、l LR(k)LR(k)分析法通過(guò)分析法通過(guò)活前綴活前綴來(lái)幫助確定句柄來(lái)幫助確定句柄活前綴：活前綴：規(guī)范句型中不含句柄右邊任何符號(hào)的前綴規(guī)范句型中不含句柄右邊任何符號(hào)的前綴規(guī)范句型規(guī)范句型：通過(guò)規(guī)范推導(dǎo)（規(guī)約）得到的句型：通過(guò)規(guī)范推導(dǎo)（規(guī)約）得到的句型前綴前綴：句型的任意首部：句型的任意首部 如如 abc abc 的前綴有的前綴有, a, b, ab, abc, a, b, ab, abc4.7 LR4.7 LR分析法分析法7LR分析器的工作過(guò)程分析器的工作過(guò)程逐步產(chǎn)生文法的規(guī)范句型逐步產(chǎn)生文法的規(guī)范句型活前綴活前綴的過(guò)程的過(guò)程當(dāng)棧頂形成當(dāng)棧頂形成句柄句柄時(shí)，立即進(jìn)行歸約時(shí)，立即進(jìn)行歸約4.7

6、 LR4.7 LR分析法分析法8活前綴與句柄的關(guān)系活前綴與句柄的關(guān)系為刻劃產(chǎn)生式右部符號(hào)已有多大一部分為刻劃產(chǎn)生式右部符號(hào)已有多大一部分被識(shí)別，用項(xiàng)目來(lái)指示位置被識(shí)別，用項(xiàng)目來(lái)指示位置項(xiàng)目項(xiàng)目: :產(chǎn)生式的右部添加一個(gè)圓點(diǎn)產(chǎn)生式的右部添加一個(gè)圓點(diǎn) 活前綴已含有句柄的活前綴已含有句柄的全部全部符號(hào)符號(hào)AA 的右部的右部 已出現(xiàn)在棧頂，可以已出現(xiàn)在棧頂，可以歸約歸約 AA 活前綴只含有句柄的活前綴只含有句柄的部分部分符號(hào)符號(hào)AA 1 1 2 2的右部子串的右部子串 1 1已出現(xiàn)在棧頂，正期待已出現(xiàn)在棧頂，正期待從剩余輸入串中能看到由從剩余輸入串中能看到由 2 2推出的符號(hào)串推出的符號(hào)串 AA 1

7、1 2 2 活前綴活前綴不含有不含有句柄的任何符號(hào)句柄的任何符號(hào)期望從剩余輸入串中能看到由某產(chǎn)生式期望從剩余輸入串中能看到由某產(chǎn)生式AA 的右部的右部 所推出的符號(hào)串所推出的符號(hào)串 AA 4.7 LR4.7 LR分析法分析法9項(xiàng)目的直觀意義項(xiàng)目的直觀意義: :在分過(guò)程中的某一時(shí)刻已經(jīng)規(guī)約的在分過(guò)程中的某一時(shí)刻已經(jīng)規(guī)約的 部分和等待規(guī)約部分部分和等待規(guī)約部分【例例】文法文法GSGS：SaS|bSaS|b 寫(xiě)出其所有的寫(xiě)出其所有的LR(0)LR(0)項(xiàng)目。項(xiàng)目。 SSaSaS，SaSaS S，SaSSaS，SSb b，SbSb一個(gè)產(chǎn)生式對(duì)應(yīng)的項(xiàng)目個(gè)數(shù)是右部符號(hào)長(zhǎng)度加一個(gè)產(chǎn)生式對(duì)應(yīng)的項(xiàng)目個(gè)數(shù)是右部符

8、號(hào)長(zhǎng)度加1 1產(chǎn)生式產(chǎn)生式AA 的項(xiàng)目個(gè)數(shù)只有一個(gè)，即的項(xiàng)目個(gè)數(shù)只有一個(gè)，即AA 4.7 LR4.7 LR分析法分析法10項(xiàng)目分為四類項(xiàng)目分為四類圓點(diǎn)后面是終結(jié)符，表示棧內(nèi)是句柄的一部分，圓點(diǎn)后面是終結(jié)符，表示棧內(nèi)是句柄的一部分，期待從輸入串中移進(jìn)一個(gè)符號(hào)，以形成句柄。期待從輸入串中移進(jìn)一個(gè)符號(hào)，以形成句柄。 移進(jìn)項(xiàng)目：移進(jìn)項(xiàng)目：AAaa 待約項(xiàng)目：待約項(xiàng)目：AABB圓點(diǎn)后面是非終結(jié)符的項(xiàng)目，表示棧內(nèi)是句柄的一部分，圓點(diǎn)后面是非終結(jié)符的項(xiàng)目，表示棧內(nèi)是句柄的一部分，為了形成句柄，期待從剩余的輸入串中進(jìn)行歸約而得到為了形成句柄，期待從剩余的輸入串中進(jìn)行歸約而得到，然后才能繼續(xù)分析，然后才能繼續(xù)分

9、析A A的右部。的右部。4.7 LR4.7 LR分析法分析法11項(xiàng)目分為四類項(xiàng)目分為四類 歸約項(xiàng)目：歸約項(xiàng)目：AA 圓點(diǎn)在最后，表示棧頂?shù)牟糠謨?nèi)容已構(gòu)成所期望的句柄，圓點(diǎn)在最后，表示棧頂?shù)牟糠謨?nèi)容已構(gòu)成所期望的句柄，應(yīng)使用產(chǎn)生式應(yīng)使用產(chǎn)生式AA進(jìn)行歸約。進(jìn)行歸約。 接受項(xiàng)目：接受項(xiàng)目：SS特殊的歸約項(xiàng)目，使用產(chǎn)生式特殊的歸約項(xiàng)目，使用產(chǎn)生式SS進(jìn)行歸約，進(jìn)行歸約，表示整個(gè)句子已經(jīng)分析完畢，分析成功，也即輸表示整個(gè)句子已經(jīng)分析完畢，分析成功，也即輸入串為該文法的句子。入串為該文法的句子。4.7 LR4.7 LR分析法分析法12構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的DFA（1 1）求出文法的所有項(xiàng)目，按

10、一定規(guī)則構(gòu)造）求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造NFANFA， 再確定化為再確定化為DFADFA（2 2）直接構(gòu)造）直接構(gòu)造DFADFA（重點(diǎn)掌握）（重點(diǎn)掌握） 有兩種方法有兩種方法4.7 LR4.7 LR分析法分析法13構(gòu)造活前綴的方法一：構(gòu)造活前綴的方法一：NFANFADFA DFA （1 1）設(shè)所有）設(shè)所有LR(0)LR(0)項(xiàng)目分別對(duì)應(yīng)項(xiàng)目分別對(duì)應(yīng)NFANFA的一個(gè)狀態(tài)，其中含有文的一個(gè)狀態(tài)，其中含有文 法開(kāi)始符號(hào)的產(chǎn)生式法開(kāi)始符號(hào)的產(chǎn)生式S SSS的第一個(gè)項(xiàng)目（的第一個(gè)項(xiàng)目（S SS S）作為）作為 NFANFA的唯一初態(tài)，歸約項(xiàng)目對(duì)應(yīng)為終態(tài)。的唯一初態(tài)，歸約項(xiàng)目對(duì)應(yīng)為終態(tài)。 （2

11、2）若狀態(tài)）若狀態(tài)i i和和j j中的中的LR(0)LR(0)項(xiàng)目出自同一條產(chǎn)生式，只是圓項(xiàng)目出自同一條產(chǎn)生式，只是圓 點(diǎn)的位置相差一個(gè)符號(hào)，即：點(diǎn)的位置相差一個(gè)符號(hào)，即： i i為：為：XXXX1 1X X2 2X Xi-1i-1X Xi iX Xn n j j為：為：XXXX1 1X X2 2X Xi-1i-1X Xi iX Xi+1i+1X Xn n 則從狀態(tài)則從狀態(tài)i i到狀態(tài)到狀態(tài)j j連一條標(biāo)記為連一條標(biāo)記為X Xi i的箭弧，說(shuō)明在狀態(tài)的箭弧，說(shuō)明在狀態(tài) i i下，識(shí)別了符號(hào)下，識(shí)別了符號(hào)X Xi i后，后，NFANFA從狀態(tài)從狀態(tài)i i轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換為狀態(tài)j j。4.7 LR4

12、.7 LR分析法分析法14構(gòu)造活前綴的方法一：構(gòu)造活前綴的方法一：NFANFADFA DFA 4.7 LR4.7 LR分析法分析法（3 3）若狀態(tài)）若狀態(tài)i i為待約項(xiàng)目，即：為待約項(xiàng)目，即： i i為：為：AA B B 則也會(huì)有以非終結(jié)符則也會(huì)有以非終結(jié)符B B為左部的相關(guān)項(xiàng)目及其相應(yīng)狀為左部的相關(guān)項(xiàng)目及其相應(yīng)狀 態(tài)，如狀態(tài)態(tài)，如狀態(tài)k k，k k為：為：BB 則從狀態(tài)則從狀態(tài)i i到狀態(tài)到狀態(tài)k k連一條標(biāo)記為連一條標(biāo)記為 的箭弧。的箭弧。154.7 LR4.7 LR分析法分析法構(gòu)造活前綴的方法二：直接構(gòu)造構(gòu)造活前綴的方法二：直接構(gòu)造DFADFA 方法一：方法一：工作量大工作量大，不適用，

13、不適用 方法二：分析方法二：分析DFADFA狀態(tài)的項(xiàng)目集之間、項(xiàng)目集內(nèi)的項(xiàng)目之間狀態(tài)的項(xiàng)目集之間、項(xiàng)目集內(nèi)的項(xiàng)目之間 的的規(guī)律規(guī)律性，性，直接構(gòu)造直接構(gòu)造出出DFADFAq 若項(xiàng)目集中有若項(xiàng)目集中有YY X X ，另一項(xiàng)目集中有，另一項(xiàng)目集中有YY X X ，則這，則這 兩個(gè)項(xiàng)目集之間必有一條兩個(gè)項(xiàng)目集之間必有一條X X弧。如，弧。如，I I0 0 和和I I1 1、I I2 2、I I3 3等。等。q 若項(xiàng)目集中有若項(xiàng)目集中有AA B B ，則必有，則必有BB，其中，其中BB是產(chǎn)是產(chǎn) 生式。如，生式。如，I I0 0 和和 I I2 2。16先給出兩個(gè)定義：先給出兩個(gè)定義： A. A. 項(xiàng)目

14、集閉包函數(shù)項(xiàng)目集閉包函數(shù)closureclosure B. B. 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)GOGO4.7 LR4.7 LR分析法分析法A. A. 項(xiàng)目集閉包函數(shù)項(xiàng)目集閉包函數(shù)closure(I)closure(I) （1 1）每一個(gè)）每一個(gè)I I中的項(xiàng)目都加進(jìn)中的項(xiàng)目都加進(jìn)closure(I)closure(I)； （2 2）若）若AABclosure(I) Bclosure(I) 且且 BB產(chǎn)生式，若產(chǎn)生式，若 BBclosure(I)closure(I)，則將，則將BB加進(jìn)加進(jìn)closure(I)closure(I)； （3 3）重復(fù)執(zhí)行（）重復(fù)執(zhí)行（2 2）直到）直到closure(I)

15、closure(I)不再增大為止。不再增大為止。17【例例】（0 0）SSS S （1 1）SSSS （2 2）SSaS aS （3 3）SaSaS S （4 4）SaSSaS （5 5）SSb b （6 6）SbSb4.7 LR4.7 LR分析法分析法I= SI= SS S closure(I)=closure(I)=？ S SS , SS , SaS , SaS , Sb b 練習(xí)：練習(xí)：I= SaI= SaSS closure(I)= closure(I)=？ Sa SaS , SS , SaS , SaS , Sb b 18B. B. 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)GOGO，X X是文法符號(hào)

16、是文法符號(hào) GO(I,X)=closure(J)GO(I,X)=closure(J) J= J=形如形如AXAX的項(xiàng)目的項(xiàng)目|A|AXIXI求求GO (I , b )=?GO (I , b )=?GO(I,b)=closure(SbGO(I,b)=closure(Sb)=Sb)=Sb 【例例】（0 0）SSS S （1 1）SSS S （2 2）S SaS aS （3 3）S Sa aS S （4 4）S SaSaS （5 5）S Sb b （6 6）S Sb b求求GO (I , a )=?GO (I , a )=?GO(I,a)=closure(SaGO(I,a)=closure(SaS)

17、=SaS)=SaS,SS,SaS,SaS,Sbb例：例：I= SI= SS , SS , SaS , SaS , Sb b 4.7 LR4.7 LR分析法分析法19GO(I,X) GO(I,X) 的直觀意義是的直觀意義是: :從狀態(tài)從狀態(tài)I(I(項(xiàng)目集項(xiàng)目集) )出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)X X弧弧 所應(yīng)該到達(dá)的狀態(tài)所應(yīng)該到達(dá)的狀態(tài)( (項(xiàng)目集項(xiàng)目集) )。在在LRLR分析中，若分析中，若I I中有圓點(diǎn)位于中有圓點(diǎn)位于X X左邊的項(xiàng)目左邊的項(xiàng)目AAXX， 則當(dāng)分析器從輸入符號(hào)串中識(shí)則當(dāng)分析器從輸入符號(hào)串中識(shí)別出文法符號(hào)后，分析器要進(jìn)入后續(xù)狀態(tài)。別出文法符號(hào)后，分析器要進(jìn)入后續(xù)狀態(tài)。4.7 LR4.7

18、 LR分析法分析法204.7 LR4.7 LR分析法分析法直接構(gòu)造直接構(gòu)造DFA的思想的思想q 從從S SS S開(kāi)始，得到開(kāi)始，得到DFADFA的的初態(tài)項(xiàng)目集初態(tài)項(xiàng)目集q 然后通過(guò)狀態(tài)轉(zhuǎn)換函數(shù)然后通過(guò)狀態(tài)轉(zhuǎn)換函數(shù)GOGO求其所有的求其所有的后繼項(xiàng)目集后繼項(xiàng)目集算法算法C=closure(SC=closure(SS ); S ); do for(Cdo for(C中的每個(gè)項(xiàng)目集中的每個(gè)項(xiàng)目集I I和每個(gè)符號(hào)和每個(gè)符號(hào)X X if(GO(I,X) if(GO(I,X)非空非空, ,且不在且不在C C中中) ) 把把GO(I,X)GO(I,X)加入加入C C中中; ; while( C while(

19、 C增大增大) ) return C;return C;214.7 LR4.7 LR分析法分析法LR(0)LR(0)分析表的構(gòu)造分析表的構(gòu)造（1 1）若）若AA a a IIk k，且，且GO(IGO(Ik k,a)=I,a)=Ij j(aV(aVT T) )，則置，則置ACTIONk,a=sACTIONk,a=sj j；（2 2）若）若AA IIk k，則對(duì)任意終結(jié)符，則對(duì)任意終結(jié)符a a（包括（包括# #）置）置ACTIONk,a=rACTIONk,a=rj j （j j為產(chǎn)生式為產(chǎn)生式AA 的編號(hào)）；的編號(hào)）；（3 3）若項(xiàng)目）若項(xiàng)目SSSSIIk k，則置，則置ACTIONk,#=ac

20、cACTIONk,#=acc；（4 4）若）若GO(IGO(Ik k,A)=I,A)=Ij j(AV(AVN N) )，則置，則置GOTOk,A=jGOTOk,A=j；（5 5）不能用上述方法填入內(nèi)容的單元置為）不能用上述方法填入內(nèi)容的單元置為“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”（用空白表示）。（用空白表示）。 22狀狀態(tài)態(tài)ACTIONACTION表表GOTOGOTO表表a ab b# #S S0 0S2S2S3S31 11 1accacc2 2S2S2S3S34 43 3r2r2r2r2R2R24 4r1r1r1r1r1r14.7 LR4.7 LR分析法分析法LR(0)LR(0)分析表的構(gòu)造分析表的構(gòu)造I

21、I0 0:S:SS S S SaSaS S Sb bI I1 1:S:SSSI I3 3:S:SaaS SI I2 2:S:SaaS S SSaSaS S Sb bI I4 4:S:SaSaSS Sb ba aS Sb ba a234.7 LR4.7 LR分析法分析法【例例】文法文法GSGS ： （1 1）S SSS （2 2）SaS|bSaS|b 構(gòu)造構(gòu)造LR(0)LR(0)分析表。分析表。（1 1）寫(xiě)出文法）寫(xiě)出文法G G的拓廣文法的拓廣文法G G；（2 2）寫(xiě)出文法）寫(xiě)出文法GG的基本的基本LR(0)LR(0)項(xiàng)目；項(xiàng)目；（3 3）利用函數(shù)）利用函數(shù)closureclosure和和GOG

22、O，求出相應(yīng)的項(xiàng)目集規(guī)范族，求出相應(yīng)的項(xiàng)目集規(guī)范族C C； （4 4）構(gòu)造識(shí)別文法）構(gòu)造識(shí)別文法GG所有活前綴的所有活前綴的DFADFA；（5 5）根據(jù)）根據(jù)DFADFA構(gòu)造構(gòu)造LR(0)LR(0)分析表。分析表。24或存在或存在歸約歸約歸約歸約沖突：沖突：A. BA. B. .一個(gè)項(xiàng)目集中存在一個(gè)項(xiàng)目集中存在移進(jìn)移進(jìn)- -歸約歸約沖突：沖突：A.a BA.a B . .LR(0)LR(0)分析表具有多重定義入口分析表具有多重定義入口, ,分析動(dòng)作不唯一分析動(dòng)作不唯一LR(0)LR(0)分析法存在的問(wèn)題分析法存在的問(wèn)題4.7 LR4.7 LR分析法分析法254.7 LR4.7 LR分析法分析法SLR(1)SLR(1)分析法分析法 若若LR(0)LR(0)項(xiàng)目集規(guī)范族中有項(xiàng)目集項(xiàng)目集規(guī)范族中有項(xiàng)目集I Ik k含移進(jìn)含移進(jìn)- -歸約或歸約歸約或歸約- -歸約沖突歸約沖突 I Ik k=X.b=X.b，A A. .，B B. 若若FOLLOW(A)FOLLOW(B)=FOLLOW(A)FOLLOW(B)= ，F(xiàn)OLLOW(A)b=FOLLOW(A)b= ，F(xiàn)OLLOW(B)b=FOLLOW(B)b= 則解決沖突的則解決沖突的SLR(1)SLR(1)技