編譯原理第4章5

1、 LR分析法是一種自下而上進行規(guī)范歸約的語法分析方法。 這里L(fēng)是指從左到右掃描輸入符號串。R是指構(gòu)造最右推導(dǎo)的逆過程。 這種分析法比遞歸下降分析法、預(yù)測分析法和算符優(yōu)先分析法對文法的限制要少得多。 大多數(shù)用無二義性大多數(shù)用無二義性上下文無關(guān)文法描述的語言都可以用上下文無關(guān)文法描述的語言都可以用LR分析法進行有效的分析分析法進行有效的分析， 而且這種分析法分析速度快，并能準確及時地指出輸入串的語法錯誤和出錯的位置。 但是，這種分析法有一個主要缺點，那就是對于一個語言的文法，構(gòu)造LR分析器的工作量相當大，具體實現(xiàn)較困難。 也就是說， 對于 因此，目前對于真正實用的編譯程序，采用構(gòu)造 LR 分析器的

2、專用工具“ YACC ” （見附錄） 自動地構(gòu)造出 LALR(1) 語法分析器。 本 章主要介紹LR分析法的基本思想和LR(0)、SLR(1) 、LR(1) 、LALR(1)分析器的工作原理和構(gòu)造方法。 LR分析法的基本思想分析法的基本思想:LR分析法是一種規(guī)范歸約分析法。 規(guī)范歸約分析法的關(guān)鍵是在分析規(guī)范歸約分析法的關(guān)鍵是在分析過程中如何確定分析棧棧頂?shù)姆柎^程中如何確定分析棧棧頂?shù)姆柎欠裥纬删浔Ｊ欠裥纬删浔?LR分析法確定句柄的基本思想基本思想是在規(guī)范歸約分析過程中，根據(jù)分析棧中記錄的已移進和歸約出的整個符號串（即歷史）和根據(jù)使用的規(guī)則推測未來可能遇到的輸入符號（即展望）以及現(xiàn)實

3、讀到的輸入符號這三個方面的信息來確定分析棧棧頂?shù)姆柎欠駱?gòu)成句柄。 LR分析器的邏輯結(jié)構(gòu)分析器的邏輯結(jié)構(gòu)一個LR分析器的邏輯結(jié)構(gòu)示意圖如下圖所示。 它由分析棧、分析棧、 分析表分析表和總控程序總控程序3個部分組成。 總控程序LR分析表a1aiam$SmXm$S0X1S1分析棧輸出 分析棧用來存放分析過程中的歷史和展望信息。 LR分析法將歷史和展望信息抽象成狀態(tài)，并放在分析棧中，這就是說分析棧分析棧中的每個狀態(tài)概括了從分析開始到某一中的每個狀態(tài)概括了從分析開始到某一歸約階段的整個分析歷史和對未來進行歸約階段的整個分析歷史和對未來進行的展望。的展望。 1. 分析棧對此，下面用一個簡單例子來說明。

4、 例如，對文法GE: EE+T| TTT*F | FF(E) | id 狀態(tài)Sm不僅表征了從分析開始到現(xiàn)在已掃描過的輸入符號被歸約成$ET，而且由Sm可以預(yù)測，如果輸入串沒有語法錯誤，根據(jù)歸約時所用規(guī)則（非終結(jié)符T的規(guī)則）推測出未來可能遇到的輸入符號僅是中的任意一個符號。 FOLLOW(T)=+,*,),$SmTE$+S0S1分析棧示意圖 它們都是二維數(shù)組。 LR分析表是LR分析器的核心部分。 一張LR分析表由和 兩部分組成， 狀態(tài)轉(zhuǎn)換表元素GOTOSi , X規(guī)定了當狀態(tài)Si面臨文法符號X時，應(yīng)轉(zhuǎn)移到的下一個狀態(tài)。 2. LR分析表 分析動作分析動作(ACTION)表表狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換( G

5、OTO )表表見表 分析動作表元素ACTIONSi , a規(guī)定了當狀態(tài)Si面臨輸入符號a時應(yīng)執(zhí)行的動作。 分析動作表對應(yīng)四種可能動作： 移進移進：把狀態(tài)Sj=GOTOSi , a和輸入符號 a移入分析棧。歸約歸約：當棧頂符號串形成句柄，且文法中 有A的規(guī)則，其中|=，則歸約 動作是從分析棧棧頂去掉個文法符 號和個狀態(tài)，并把歸約符A和 GOTOSi- ，A=Sj移入分析棧中。 見表接受接受（acc): 表示分析成功。此時，分析棧 中只剩文法開始符號S和當前讀到的 輸入符號是$。即輸入符號串已經(jīng)結(jié) 束。 報錯報錯：表示輸入串含有錯誤，此時出現(xiàn)棧頂 的某一狀態(tài)遇到了不該遇到的輸入符 號。 見表總控程

6、序也稱為驅(qū)動程序。 總控程序從左至右掃描輸入符號串，并根據(jù)當前分析棧中棧頂狀態(tài)以及當前讀到的輸入符號按照LR分析表元素所指示的動作完成每一步的分析工作。 3. 總控程序 對所有的LR分析器其總控程序是相同的?？偪爻绦蛩惴偪爻绦蛩惴ǎ狠斎耄狠斎氪甒和LR分析表。 輸出：若W是句子，得到W的自下而上 分析成功，否則輸出錯誤信息。 ( LR分析器的工作過程的形式化描述 )算法：初始化時，初始狀態(tài)S0在分析棧 棧頂，輸入串W$的第1個符號讀 入a中。 ; ) ( error)a,( ERRORSACTIONifelse=)a,( rSACTIONifelsej=)a,( SSACTIONifi=)!

7、a,(accSACTIONwhile= a a i中；將下一個輸入符號讀入進棧；和輸入符號將狀態(tài) SA,SGOTOA S | Aj = 進棧；和，將當前棧頂狀態(tài)為個輸入符號退棧；個狀態(tài)和將歸約：條規(guī)則用第aaa狀態(tài)ACTION a b c d $GOTOS A B678910 S8 r6 r6 r6 r6 r6 S10 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5012345 S4 S5 S6 acc S4 S5 S6 r4 r4 r4 r4 r41 2 37 9 r2 r2 r2 r2 r2 r1 r1 r1 r1 r1返回返回返回 LR(0)分析就是在分析的每一步，只需根據(jù)當

8、前棧頂狀態(tài)而不必向前查看輸入符號就能確定應(yīng)采取的分析動作。 LR分析器的關(guān)鍵部分是分析表的構(gòu)造。 構(gòu)造LR分析表的基本思想是: 從給定的上下文無關(guān)文法直接構(gòu)造識從給定的上下文無關(guān)文法直接構(gòu)造識別文法所有規(guī)范句型活前綴的別文法所有規(guī)范句型活前綴的DFA，然后，然后再將再將DFA轉(zhuǎn)換成一張轉(zhuǎn)換成一張LR分析表分析表。 為了給出構(gòu)造LR分析表的算法，需要定義一些重要的概念和術(shù)語。 文法規(guī)范句型的活前綴 1. 字符串的前綴是指字符串的任意首部。 例如，字符串a(chǎn)bc的前綴有,a,ab,abc。 2. 規(guī)范句型活前綴是指規(guī)范句型的前綴，這種前綴不包含句柄右邊的任何符號。 注意，活前綴可以是一個或者是若干個

9、規(guī)范句型的前綴。 例 1 設(shè)文法G為： 0. SS1. SA2. SB3. AaAb4. Ac5. BaBb6. Bd句型aaAbb的前綴、規(guī)范句型活前綴 LR(0)項目項目 由活前綴定義可知，在一個規(guī)范句型的活前綴中，絕不含有句柄右邊的任何符號。因此，活前綴與句柄之間的關(guān)系有下述三種情況： 活前綴中已含有句柄的全部符號，表明此時某一規(guī)則A的右部符號串已出現(xiàn)在棧頂，其相應(yīng)的分析動作是用此規(guī)則進行歸約。 活前綴中只含有句柄的一部分符號，此時意味著形如 A12 規(guī)則的右部子串1已出現(xiàn)在棧頂，2正期待著從余留的輸入串中進行歸約得到。 活前綴中全然不含有句柄的任何符號，此時意味著期望從余留輸入串能看到

10、由某規(guī)則 A 的右部 所推出的符號串。 為了刻畫在分析過程中, 文法的一個規(guī)則右部符號串已有多大一部分被識別，我們可在文法中每個規(guī)則右部適當位置上加一個圓點來表示。針對上述三種情況，標有圓點的規(guī)則分別為： AA 1 2A 我們把文法G中右部標有圓點的規(guī)則稱為G的一個LR(0)項目。 值得注意的是對空規(guī)則 A，僅有LR(0)項目A 。 文法G的全部LR(0)項目是構(gòu)造識別文法所有規(guī)范句型活前綴的DFA的基礎(chǔ)。我們將會看到這種DFA的每一個狀態(tài)和有窮個LR(0) 項目的集合相關(guān)聯(lián)。 一個LR(0)項目指明了對文法規(guī)范句型活前綴的不同識別狀態(tài), 由于不同的LR(0)項目反映了在分析過程中棧頂?shù)牟煌?/p>

11、況，因此，我們可以根據(jù)圓點位置和圓點后是終結(jié)符還是非終結(jié)符，將一個文法的全部LR(0)項目進行分類。 直觀上說，LR(0)項目分類如下：歸約項目歸約項目 移進項目移進項目 待約項目待約項目 接受項目接受項目 歸約項目歸約項目，形如A，其中(VNVT)*，即圓點在最右端的項目，它表示一個規(guī)則的右部已分析完, 句柄已形成，應(yīng)該按此規(guī)則進行歸約。 移進項目移進項目，形如A a，其中， (VNVT)* ，即圓點后面為終結(jié)符的項目, 它表示期待從輸入串中移進一個符號，以待形成句柄。 待約項目待約項目，形如A B，其中， (VNVT) * , B VN*，即圓點后面為非終結(jié)符的項目，它表示期待從余留的輸入

12、串中進行歸約得到B，然后分析A的右部。 接受項目接受項目，形如SS ，其中S為文法的開始符號，即文法開始符號的歸約項目。 S為左部的規(guī)則僅只有一個，它是歸約項目的特殊情況，它表示整個句子已經(jīng)分析完畢，可以接受。 構(gòu)造識別文法所有規(guī)范句型活前綴構(gòu)造識別文法所有規(guī)范句型活前綴DFA的方法的方法 : 在這個項目集中，所有的LR(0)項目識別的活前綴是相同的，我們可以利用閉包函數(shù)（CLOSURE）來求DFA一個狀態(tài)的項目集。 對于構(gòu)成識別文法規(guī)范句型活前綴DFA的每一個狀態(tài)是由若干個LR(0)項目所組成的集合，稱為LR(0)項目集 ， 為了使“接受”項目唯一，我們總對文法G進行拓廣。假定文法G的開始符

13、號為S，在文法G中引入一個新的開始符號S，并加進一個新的規(guī)則S S，從而得到文法G的拓廣文法G。 (1) 定義閉包函數(shù)定義閉包函數(shù) 設(shè)I是拓廣文法G的一個LR(0)項目集，定義和構(gòu)造I的閉包CLOSURE(I)如下： I中的任何一個項目都屬于 CLOSURE(I)。 (b) 若A B屬于CLOSURE(I)， 則每一形如 B 的項目 也屬于CLOSURE(I)。 (c) 重復(fù)(b)直到CLOSURE(I)不再增 大為止。例如，對例1中的文法 令I(lǐng)=SS ，則即為初態(tài)的項目集I0 CLOSURE(I)SS， SA， SB， AaAbAc， BaBb， Bd0. SS1. SA2. SB3. Aa

14、Ab4. Ac5. BaBb6. Bd= 有了初態(tài)的項目集之后，如何求出對于文法符號X可能轉(zhuǎn)移到的下一個狀態(tài)的項目集？ (2) 定義狀態(tài)轉(zhuǎn)移函數(shù)定義狀態(tài)轉(zhuǎn)移函數(shù)GO 設(shè)I是拓展文法G的任一個項目集，X為一文法符號，定義狀態(tài)轉(zhuǎn)移函數(shù)GO(I,X)如下： GO( I , X )=CLOSURE( J )J=AaX | AaX I例如：初態(tài)的項目集GO(I0 , S )=CLOSURE(SS )= SS =I1GO(I0 , a )=CLOSURE(AaAb , BaBb)= AaAb , AaAb , Ac BaBb , BaBb , Bd =I4 SS , SA , SB, AaAb , Ac

15、，BaBb , Bd I0= 通過閉包函數(shù)（CLOSURE）和狀態(tài)轉(zhuǎn)移函數(shù)(GO)很容易構(gòu)造出文法 G 的識別文法規(guī)范句型活前綴的DFA。 (3) 構(gòu)造識別文法規(guī)范句型活前綴構(gòu)造識別文法規(guī)范句型活前綴DFA的方法的方法 : (a) 求CLOSURESS，得到初態(tài) 項目集。 (b) 對初態(tài)項目集或其它已構(gòu)造的項 目集，應(yīng)用狀態(tài)轉(zhuǎn)移函數(shù)GO(I,X) 求出新的項目集（后繼狀態(tài)）。 (d) 轉(zhuǎn)移函數(shù)GO建立狀態(tài)之間的連 結(jié)關(guān)系。 對前例中的文法，構(gòu)造識別文法所有規(guī)范句型活前綴的DFA如下圖所示：(c) 重復(fù)(b)直到不出現(xiàn)新的項目集 （新狀態(tài)）為止。 0. SS1. SA2. SB3. AaAb4.

16、 Ac5. BaBb6. BdSSSASBAaAbAcBaBbBdI0:I1: SSI2: SAI4:AaAbAcBaBb BdAaAbBaBbI5: AcI6: Bd識別文法G活前綴的DFASABacdcdaI3: SBI7: AaAbI8: AaAbI9: BaBb識別文法G活前綴的DFAI10: BaBbbbABaSSSASBAaAbAcBaBbBdI0:I1: SSI2: SAI4:AaAbAcBaBb BdAaAbBaBbI6: BdSABacdcdI3: SBI5: Ac 注意，DFA中的每一個狀態(tài)都是終態(tài)，當M到達它們時，識別出某規(guī)范句型的一個活前綴，對那些只含歸約項目的項目集，

17、如I2、I3、I5 、 I6、I8、I10，當M到達這些狀態(tài)時，表示已識別出一個句柄，這些狀態(tài)稱為句柄識別態(tài)句柄識別態(tài)。 當M處于狀態(tài)I1時，M識別的活前綴為S，表示輸入串已成功分析完畢，用SS進行最后一次歸約，稱狀態(tài)為接受狀態(tài)接受狀態(tài)。 構(gòu)成識別一個文法活前綴的DFA的狀態(tài)（項目集）的全體稱為這個文法的LR(0)項項目集規(guī)范族目集規(guī)范族。 (4) LR(0)分析表的構(gòu)造分析表的構(gòu)造 : 若一個文法G的拓廣文法G的LR(0)項目集規(guī)范族中的每個項目集不存在移進項目和歸約項目同時并存或多個歸約項目同時并存，則稱G為LR(0)文法。 I7: AaAbI8: AaAbI9: AaBb識別文法G活前綴

18、的DFAI10: BaBbbbABaSSSASBAaAbAcBaBbBdI0:I1: SSI2: SAI4:AaAbAcBaBb BdAaAbBaBbI6: BdSABacdcdI3: SBI5: Ac 對LR(0)文法，構(gòu)造LR(0)分析表的算法如下： 輸入：識別LR(0)文法G規(guī)范句型活 前綴的DFA 輸出：文法G的LR(0)分析表 方法：用整數(shù) 0, 1, 2, ，n 分別表示 狀態(tài) I0, I1, I2 , In, 令包含項目 SS 的集合 Ik 的下標為分析 器的初始狀態(tài)。 若項目Ax屬于 Ik, 且轉(zhuǎn)換函數(shù) GO(Ik , x)=Ii , 當 x 為終結(jié)符時，則置ACTIONk,

19、x=Si。2. 當 x 為非終結(jié)符時，則置 GOTOk, x=i。 見圖見圖見表見表3. 若項目A屬于Ik ，則對任何終 結(jié)符和結(jié)束符$（統(tǒng)一記為a）則置 ACTIONk, a=rj （假定A為文法的第j條規(guī)則） 見圖見表0. SS1. SA2. SB3. AaAb4. Ac5. BaBb6. Bd5. 分析表中凡不能用規(guī)則1至4填入信 息的元素均置為“出錯標志”，為了 分析表的清晰，僅用空白表示出錯 標志。 4. 若項目SS 屬于Ik，則置 ACTIONk, $=acc。 見圖見表見表 根據(jù)上述方法構(gòu)造的LR(0)分析表不含多重定義時，稱這樣的分析表為LR(0)分析表，能構(gòu)造LR(0)分析表

20、的文法稱為LR(0)文法。 例2 考慮文法GS: (1) 構(gòu)造識別文法規(guī)范句型活前綴的DFA(2) 判斷該文法是否LR(0)文法，若是， 請構(gòu)造LR(0)分析表，若不是，請說 明理由。S(S) | a分 析：首先將文法拓廣，并給出每條規(guī)則編號0. SS1. S (S)2. S a識別文法規(guī)范句型活前綴的DFA如下圖所示 ：I0:SSS (S)S aI2:S (S)S (S)S aI1: SSSaI3: S a(aI4: S (S)I5: S (S)S識別活前綴的DFA0. SS1. S (S)2. S a 因為它的6個LR(0)項目集中均不含有沖突項目，即不存在移進項目和歸約項目并存或多個歸約

21、項目并存的情況。該文法是LR(0)文法。 其LR(0)分析表如下： ACTIONa ( ) $SGOTO文法GS的LR(0)分析表0S3 S211acc2345S3 S2r2 r2 r2 r2S5r1 r1 r1 r14見圖0. SS1. S (S)2. S a 由上述構(gòu)造過程可以看出，LR(0)分析器的特點是不需要向前查看輸入符號就能歸約，即當棧頂形成句柄，不管不一個輸入符號是什么，都可以立即進行歸約而不會發(fā)生錯誤。 識別活前綴的DFA見表I0:SSS (S)S aI2:S (S)S (S)S aI1: SSSaI3: S a(aI4: S (S)I5: S (S)S0. SS1. S (S)2. S a識別文法G活前綴的DFA返回返回返回0. SS1. SA2. SB3. AaAb4. Ac5. BaBb6. BdI7: AaAbI8: AaAbI9: BaBbI10: BaBbbbABaSSSASBAaAbAcBaBbBdI0:I1: SSI2: SAI4:AaAbAcBaBb BdAaAbBaBbI6: BdSABacdcdI3: SBI5: Ac012345 S4