編譯原理總結(jié)7_語法4

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

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

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

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

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

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

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

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

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

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

11、2）若狀態(tài)）若狀態(tài)i i和和j j中的中的LR(0)LR(0)項目出自同一條產(chǎn)生式，只是圓項目出自同一條產(chǎn)生式，只是圓 點的位置相差一個符號，即：點的位置相差一個符號，即： 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連一條標記為連一條標記為X Xi i的箭弧，說明在狀態(tài)的箭弧，說明在狀態(tài) i i下，識別了符號下，識別了符號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為待約項目，即：為待約項目，即： i i為：為：AA B B 則也會有以非終結(jié)符則也會有以非終結(jié)符B B為左部的相關(guān)項目及其相應(yīng)狀為左部的相關(guān)項目及其相應(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連一條標記為連一條標記為 的箭弧。的箭弧。154.7 LR4.7 LR分析法分析法構(gòu)造活前綴的方法二：直接構(gòu)造構(gòu)造活前綴的方法二：直接構(gòu)造DFADFA 方法一：方法一：工作量大工作量大，不適用，

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

14、集閉包函數(shù)項目集閉包函數(shù)closureclosure B. B. 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)GOGO4.7 LR4.7 LR分析法分析法A. A. 項目集閉包函數(shù)項目集閉包函數(shù)closure(I)closure(I) （1 1）每一個）每一個I I中的項目都加進中的項目都加進closure(I)closure(I)； （2 2）若）若AABclosure(I) Bclosure(I) 且且 BB產(chǎn)生式，若產(chǎn)生式，若 BBclosure(I)closure(I)，則將，則將BB加進加進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是文法符號

16、是文法符號 GO(I,X)=closure(J)GO(I,X)=closure(J) J= J=形如形如AXAX的項目的項目|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(項目集項目集) )出發(fā)，經(jīng)過出發(fā)，經(jīng)過X X弧弧 所應(yīng)該到達的狀態(tài)所應(yīng)該到達的狀態(tài)( (項目集項目集) )。在在LRLR分析中，若分析中，若I I中有圓點位于中有圓點位于X X左邊的項目左邊的項目AAXX， 則當分析器從輸入符號串中識則當分析器從輸入符號串中識別出文法符號后，分析器要進入后續(xù)狀態(tài)。別出文法符號后，分析器要進入后續(xù)狀態(tài)。4.7 LR4.7

18、 LR分析法分析法204.7 LR4.7 LR分析法分析法直接構(gòu)造直接構(gòu)造DFA的思想的思想q 從從S SS S開始，得到開始，得到DFADFA的的初態(tài)項目集初態(tài)項目集q 然后通過狀態(tài)轉(zhuǎn)換函數(shù)然后通過狀態(tài)轉(zhuǎn)換函數(shù)GOGO求其所有的求其所有的后繼項目集后繼項目集算法算法C=closure(SC=closure(SS ); S ); do for(Cdo for(C中的每個項目集中的每個項目集I I和每個符號和每個符號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，則對任意終結(jié)符，則對任意終結(jié)符a a（包括（包括# #）置）置ACTIONk,a=rACTIONk,a=rj j （j j為產(chǎn)生式為產(chǎn)生式AA 的編號）；的編號）；（3 3）若項目）若項目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)容的單元置為“出錯標志出錯標志”（用空白表示）。（用空白表示）。 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）寫出文法）寫出文法G G的拓廣文法的拓廣文法G G；（2 2）寫出文法）寫出文法GG的基本的基本LR(0)LR(0)項目；項目；（3 3）利用函數(shù)）利用函數(shù)closureclosure和和GOG

22、O，求出相應(yīng)的項目集規(guī)范族，求出相應(yīng)的項目集規(guī)范族C C； （4 4）構(gòu)造識別文法）構(gòu)造識別文法GG所有活前綴的所有活前綴的DFADFA；（5 5）根據(jù)）根據(jù)DFADFA構(gòu)造構(gòu)造LR(0)LR(0)分析表。分析表。24或存在或存在歸約歸約歸約歸約沖突：沖突：A. BA. B. .一個項目集中存在一個項目集中存在移進移進- -歸約歸約沖突：沖突：A.a BA.a B . .LR(0)LR(0)分析表具有多重定義入口分析表具有多重定義入口, ,分析動作不唯一分析動作不唯一LR(0)LR(0)分析法存在的問題分析法存在的問題4.7 LR4.7 LR分析法分析法254.7 LR4.7 LR分析法分析法

23、SLR(1)SLR(1)分析法分析法 若若LR(0)LR(0)項目集規(guī)范族中有項目集項目集規(guī)范族中有項目集I Ik k含移進含移進- -歸約或歸約歸約或歸約- -歸約沖突歸約沖突 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)技術(shù)：技術(shù)：對于歸約項目向前查看一個符號對于歸約項目向前查看一個符號ACTIONACTIONk,b=k,b=移進移進對對a a FOLLOW(A)FOLLOW(A) 則則 ACTIONACTIONk,a=k,a=用用A A歸約歸約對對a a FOLLOW(BFOLLOW(B) ) 則則 ACTIONA