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

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

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

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

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

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

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

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

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

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

11、2）若狀態）若狀態i i和和j j中的中的LR(0)LR(0)項目出自同一條產生式，只是圓項目出自同一條產生式，只是圓 點的位置相差一個符號，即：點的位置相差一個符號，即： 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 則從狀態則從狀態i i到狀態到狀態j j連一條標記為連一條標記為X Xi i的箭弧，說明在狀態的箭弧，說明在狀態 i i下，識別了符號下，識別了符號X Xi i后，后，NFANFA從狀態從狀態i i轉換為狀態轉換為狀態j j。4.7 LR4

12、.7 LR分析法分析法14構造活前綴的方法一：構造活前綴的方法一：NFANFADFA DFA 4.7 LR4.7 LR分析法分析法（3 3）若狀態）若狀態i i為待約項目，即：為待約項目，即： i i為：為：AA B B 則也會有以非終結符則也會有以非終結符B B為左部的相關項目及其相應狀為左部的相關項目及其相應狀 態，如狀態態，如狀態k k，k k為：為：BB 則從狀態則從狀態i i到狀態到狀態k k連一條標記為連一條標記為 的箭弧。的箭弧。154.7 LR4.7 LR分析法分析法構造活前綴的方法二：直接構造構造活前綴的方法二：直接構造DFADFA 方法一：方法一：工作量大工作量大，不適用，

13、不適用 方法二：分析方法二：分析DFADFA狀態的項目集之間、項目集內的項目之間狀態的項目集之間、項目集內的項目之間 的的規律規律性，性，直接構造直接構造出出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是產是產 生式。如，生式。如，I I0 0 和和 I I2 2。16先給出兩個定義：先給出兩個定義： A. A. 項目

14、集閉包函數項目集閉包函數closureclosure B. B. 狀態轉移函數狀態轉移函數GOGO4.7 LR4.7 LR分析法分析法A. A. 項目集閉包函數項目集閉包函數closure(I)closure(I) （1 1）每一個）每一個I I中的項目都加進中的項目都加進closure(I)closure(I)； （2 2）若）若AABclosure(I) Bclosure(I) 且且 BB產生式，若產生式，若 BBclosure(I)closure(I)，則將，則將BB加進加進closure(I)closure(I)； （3 3）重復執行（）重復執行（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 練習：練習：I= SaI= SaSS closure(I)= closure(I)=？ Sa SaS , SS , SaS , SaS , Sb b 18B. B. 狀態轉移函數狀態轉移函數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) 的直觀意義是的直觀意義是: :從狀態從狀態I(I(項目集項目集) )出發，經過出發，經過X X弧弧 所應該到達的狀態所應該到達的狀態( (項目集項目集) )。在在LRLR分析中，若分析中，若I I中有圓點位于中有圓點位于X X左邊的項目左邊的項目AAXX， 則當分析器從輸入符號串中識則當分析器從輸入符號串中識別出文法符號后，分析器要進入后續狀態。別出文法符號后，分析器要進入后續狀態。4.7 LR4.7

18、 LR分析法分析法204.7 LR4.7 LR分析法分析法直接構造直接構造DFA的思想的思想q 從從S SS S開始，得到開始，得到DFADFA的的初態項目集初態項目集q 然后通過狀態轉換函數然后通過狀態轉換函數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)分析表的構造分析表的構造（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，則對任意終結符，則對任意終結符a a（包括（包括# #）置）置ACTIONk,a=rACTIONk,a=rj j （j j為產生式為產生式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）不能用上述方法填入內容的單元置為）不能用上述方法填入內容的單元置為“出錯標志出錯標志”（用空白表示）。（用空白表示）。 22狀狀態態ACTIONACTION表表GOTOGOTO表表a ab b# #S S0 0S2S2S3S31 11 1accacc2 2S2S2S3S34 43 3r2r2r2r2R2R24 4r1r1r1r1r1r14.7 LR4.7 LR分析法分析法LR(0)LR(0)分析表的構造分析表的構造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 構造構造LR(0)LR(0)分析表。分析表。（1 1）寫出文法）寫出文法G G的拓廣文法的拓廣文法G G；（2 2）寫出文法）寫出文法GG的基本的基本LR(0)LR(0)項目；項目；（3 3）利用函數）利用函數closureclosure和和GOG

22、O，求出相應的項目集規范族，求出相應的項目集規范族C C； （4 4）構造識別文法）構造識別文法GG所有活前綴的所有活前綴的DFADFA；（5 5）根據）根據DFADFA構造構造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分析法分析法SLR(1)SLR(1)分析法分析法 若若LR(0)LR(0)項目集規范族中有項目集項目集規范族中有項目集I Ik k含移進含移進- -歸約或歸約歸約或歸約- -歸約沖突歸約沖突 I Ik k=X.b=X.b，A A. .，B B. 若若FOLLOW(A)FOLLOW(B)=FOLLOW(A)FOLLOW(B)= ，FOLLOW(A)b=FOLLOW(A)b= ，FOLLOW(B)b=FOLLOW(B)b= 則解決沖突的則解決沖突的SLR(1)SLR(1)技