編譯原理第4章5

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

2、專用工具“ YACC ” （見附錄） 自動(dòng)地構(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ìn)和歸約出的整個(gè)符號串（即歷史）和根據(jù)使用的規(guī)則推測未來可能遇到的輸入符號（即展望）以及現(xiàn)實(shí)

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

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

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

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

7、)!a,(accSACTIONwhile= a a i中；將下一個(gè)輸入符號讀入進(jìn)棧；和輸入符號將狀態(tài) SA,SGOTOA S | Aj = 進(jìn)棧；和，將當(dāng)前棧頂狀態(tài)為個(gè)輸入符號退棧；個(gè)狀態(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)分析就是在分析的每一步，只需根

8、據(jù)當(dāng)前棧頂狀態(tài)而不必向前查看輸入符號就能確定應(yīng)采取的分析動(dò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ī)范句型的前綴，這種前綴不包含句柄右邊的任何符號。 注意，活前綴可以是一個(gè)或者是若

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

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

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

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

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

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

15、c ，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) 項(xiàng)目集。 (b) 對初態(tài)項(xiàng)目集或其它已構(gòu)造的項(xiàng) 目集，應(yīng)用狀態(tài)轉(zhuǎn)移函數(shù)GO(I,X) 求出新的項(xiàng)目集（后繼狀態(tài)）。 (d) 轉(zhuǎn)移函數(shù)GO建立狀態(tài)之間的連 結(jié)關(guān)系。 對前例中的文法，構(gòu)造識別文法所有規(guī)范句型活前綴的DFA如下圖所示：(c) 重復(fù)(b)直到不出現(xiàn)新的項(xiàng)目集 （新狀態(tài)）為止。 0. SS1. SA2. SB3. AaAb

16、4. 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中的每一個(gè)狀態(tài)都是終態(tài)，當(dāng)M到達(dá)它們時(shí)，識別出某規(guī)范句型的一個(gè)活前綴，對那些只含歸約項(xiàng)目的項(xiàng)目

17、集，如I2、I3、I5 、 I6、I8、I10，當(dāng)M到達(dá)這些狀態(tài)時(shí)，表示已識別出一個(gè)句柄，這些狀態(tài)稱為句柄識別態(tài)句柄識別態(tài)。 當(dāng)M處于狀態(tài)I1時(shí)，M識別的活前綴為S，表示輸入串已成功分析完畢，用SS進(jìn)行最后一次歸約，稱狀態(tài)為接受狀態(tài)接受狀態(tài)。 構(gòu)成識別一個(gè)文法活前綴的DFA的狀態(tài)（項(xiàng)目集）的全體稱為這個(gè)文法的LR(0)項(xiàng)項(xiàng)目集規(guī)范族目集規(guī)范族。 (4) LR(0)分析表的構(gòu)造分析表的構(gòu)造 : 若一個(gè)文法G的拓廣文法G的LR(0)項(xiàng)目集規(guī)范族中的每個(gè)項(xiàng)目集不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目同時(shí)并存或多個(gè)歸約項(xiàng)目同時(shí)并存，則稱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, 令包含項(xiàng)目 SS 的集合 Ik 的下標(biāo)為分析 器的初始狀態(tài)。 若項(xiàng)目Ax屬于 Ik, 且轉(zhuǎn)換函數(shù) GO(Ik , x)=Ii , 當(dāng) x 為終結(jié)符時(shí)，則置ACTIONk

19、, x=Si。2. 當(dāng) x 為非終結(jié)符時(shí)，則置 GOTOk, x=i。 見圖見圖見表見表3. 若項(xiàng)目A屬于Ik ，則對任何終 結(jié)符和結(jié)束符$（統(tǒng)一記為a）則置 ACTIONk, a=rj （假定A為文法的第j條規(guī)則） 見圖見表0. SS1. SA2. SB3. AaAb4. Ac5. BaBb6. Bd5. 分析表中凡不能用規(guī)則1至4填入信 息的元素均置為“出錯(cuò)標(biāo)志”，為了 分析表的清晰，僅用空白表示出錯(cuò) 標(biāo)志。 4. 若項(xiàng)目SS 屬于Ik，則置 ACTIONk, $=acc。 見圖見表見表 根據(jù)上述方法構(gòu)造的LR(0)分析表不含多重定義時(shí)，稱這樣的分析表為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 因?yàn)樗?個(gè)LR(0)項(xiàng)目集中均不含有沖突項(xiàng)目，即不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目并存或多個(gè)

21、歸約項(xiàng)目并存的情況。該文法是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)分析器的特點(diǎn)是不需要向前查看輸入符號就能歸約，即當(dāng)棧頂形成句柄，不管不一個(gè)輸入符號是什么，都可以立即進(jìn)行歸約而不會(huì)發(fā)生錯(cuò)誤。 識別活前綴的DFA見表I0:SSS (S)S aI2:S (S)S (S)S aI1: SSSaI3: S a(aI4: S (S)I5: S (S)S0. SS1. S

22、(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 S5 S6 acc S4 S5 S6 r1 r1 r1 r1 r1 r2 r2 r2 r2 r2 r4 r4 r4 r4 r41 2 37 9文法GS的LR(0)分析表狀態(tài) ACTION a b c d $GOTOS A B0. SS1. SA2. SB3. AaAb4. Ac5. BaBb6.