自下而上的LRk分析方法.ppt

《自下而上的LRk分析方法.ppt》由會員分享，可在線閱讀，更多相關(guān)《自下而上的LRk分析方法.ppt（177頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、、SLR(1) 、LR(1) 、LALR(1)分析器的工作原理和構(gòu)造方法。,LR分析法,,LR分析法的基本思想:,LR分析法是一種規(guī)范歸約分析法。,規(guī)范歸約分析法的關(guān)鍵是在分析過程中如何確定分析棧棧頂?shù)姆柎欠裥纬删浔?LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR分析法確定句柄的基本思想是在規(guī)范歸約分析過程中，根據(jù)分析棧中記錄的已移進和歸約出的整個符號串（即歷史）和根據(jù)使用的規(guī)則推測未來可能遇到的輸入符號（即展望）以及現(xiàn)實讀到的輸入符號這三個方面的信息來確定分析棧棧頂?shù)姆柎欠駱?gòu)成句柄。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR分析器的邏輯結(jié)構(gòu),一個LR分析器的邏輯結(jié)構(gòu)示意圖如下圖所示。,它由分

3、析棧、,分析表和,總控程序3個部分組成。,分析棧,,,,輸出,LR分析器的邏輯結(jié)構(gòu)和工作過程,,分析棧用來存放分析過程中的歷史和展望信息。,LR分析法將歷史和展望信息抽象成狀態(tài)，并放在分析棧中，這就是說分析棧中的每個狀態(tài)概括了從分析開始到某一歸約階段的整個分析歷史和對未來進行的展望。,1. 分析棧,對此，下面用一個簡單例子來說明。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,例如，對文法GE:,EE+T| T,TT*F | F,F(E) | id,狀態(tài)Sm不僅表征了從分析開始到現(xiàn)在已掃描過的輸入符號被歸約成$ET，而且由Sm可以預(yù)測，如果輸入串沒有語法錯誤，根據(jù)歸約時所用規(guī)則（非終結(jié)符T的規(guī)則）推測出未

4、來可能遇到的輸入符號僅是,中的任意一個符號。,FOLLOW(T)=+,*,),$,分 析 棧 示 意 圖,LR分析器的邏輯結(jié)構(gòu)和工作過程,,若當前讀到的輸入符號是* ，根據(jù)文法可知*的優(yōu)先級高于，棧頂尚未形成句柄，則應(yīng)將*移入棧中；,若當前讀到的輸入符號是或）或$時，根據(jù)文法可知棧頂已形成句柄，則應(yīng)將符號串ET歸約為E；,若當前讀到的輸入符號不是上述四種符號之一，則表示輸入串有語法錯誤。,由此可知，LR分析器的每一步分析工作，都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一確定的。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,它們都是二維數(shù)組。,LR分析表是LR分析器的核心部分。,一張LR分析表由,和

5、 兩部分組成，,狀態(tài)轉(zhuǎn)換表元素GOTOSi , X規(guī)定了當狀態(tài)Si面臨文法符號X時，應(yīng)轉(zhuǎn)移到的下一個狀態(tài)。,2. LR分析表,分析動作(ACTION)表,狀態(tài)轉(zhuǎn)換( GOTO )表,LR分析器的邏輯結(jié)構(gòu)和工作過程,,分析動作表元素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移

6、入分析棧中。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR分析器的邏輯結(jié)構(gòu)和工作過程,,接受（acc): 表示分析成功。此時，分析棧 中只剩文法開始符號S和當前讀到的 輸入符號是$。即輸入符號串已經(jīng)結(jié) 束。,報錯：表示輸入串含有錯誤，此時出現(xiàn)棧頂 的某一狀態(tài)遇到了不該遇到的輸入符 號。,總控程序也稱為驅(qū)動程序。,總控程序從左至右掃描輸入符號串，并根據(jù)當前分析棧中棧頂狀態(tài)以及當前讀到的輸入符號按照LR分析表元素所指示的動作完成每一步的分析工作。,3. 總控程序,對所有的LR分析器其總控程序是相同的。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,總控程序算法：,輸入：輸入串W

7、和LR分析表。,輸出：若W是句子，得到W的自下而上 分析成功，否則輸出錯誤信息。,( LR分析器的工作過程的形式化描述 ),算法：初始化時，初始狀態(tài)S0在分析棧 棧頂，輸入串W$的第1個符號讀 入a中。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,,,,,,,LR分析器的邏輯結(jié)構(gòu)和工作過程,,例 1 設(shè)文法G為：,相應(yīng)于文法的LR分析表如下表所示。,0. SS,1. SA,2. SB,3. AaAb,4. Ac,5. BaBb,6. Bd,LR分析器的邏輯結(jié)構(gòu)和工作過程,,對文法句子aacbb$的LR分析過程如下:,初始化時，初始狀態(tài) 0 和句子的左界符 $在分析棧棧頂，讀入輸入串 a

8、acbb$ 的第1個符號a 。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR（0）分析法,,LR(0)分析就是在分析的每一步，只需根據(jù)當前棧頂狀態(tài)而不必向前查看輸入符號就能確定應(yīng)采取的分析動作。,LR分析器的關(guān)鍵部分是分析表的構(gòu)造。,構(gòu)造LR分析表的基本思想是:,從給定的上下文無關(guān)文法直接構(gòu)造識別文法所有規(guī)范句型活前綴的DFA，然后再將DFA轉(zhuǎn)換成一張LR分析表。,LR（0）分析法,,為了給出構(gòu)造LR分析表的算法，需要定義一些重要的概念和術(shù)語。,文法規(guī)范句型的活前綴,1. 字符串的前綴是指字符串的任意首部。,例如，字符串a(chǎn)bc的前綴有,a,ab,abc。,2. 規(guī)范

9、句型活前綴是指規(guī)范句型的前綴， 這種前綴不包含句柄右邊的任何符號。,注意，活前綴可以是一個或者是若干個規(guī)范句型的前綴。,LR（0）分析法,,LR（0）分析法,,由前例，對輸入串a(chǎn)acbb的歸約過程，可以看出，當所分析的輸入串沒有語法錯誤時，則在分析的每一步，分析棧中已移進一歸約的全部文法符號與余留的輸入符號串合起來，就是所給文法的一個規(guī)范句型。,LR（0）分析法,,這也就是說，在LR分析過程中的任何時刻，棧中的文法符號應(yīng)是某一規(guī)范句型的活前綴，這是因為一旦句型句柄在棧的頂部形成，就會立即被歸約，因此，只要輸入串已掃描過的部分保持可歸約成一個活前綴，那就意味著所掃描過的部分是正確的。,LR（0

10、）分析法,,例如，對前例，文法GS的規(guī)范句型aaAbb的句柄是aAb，棧中符號串為aaAb，此句型的活前綴為,a,aa,aaA,aaAb，它們均不含句柄右邊符號b。,這樣一來，我們對句柄的識別就變成對規(guī)范句型活前綴的識別。,LR（0）分析法,,那么，如何識別文法規(guī)范句型的活前綴呢？由于在分析的每一步分析棧中的全部文法符號是當前規(guī)范句型的活前綴，且與當前棧頂狀態(tài)相關(guān)聯(lián)，因而可以利用有窮自動機去識別所給文法的所有規(guī)范句型的活前綴。,LR分析器的工作過程可看成是一個逐步識別所給文法規(guī)范句型活前綴的過程。,LR（0）分析法,,由此可知，,LR（0）分析法,,LR(0)項目,由活前綴定義可知，在一個規(guī)范

11、句型的活前綴中，絕不含有句柄右邊的任何符號。因此，活前綴與句柄之間的關(guān)系有下述三種情況：, 活前綴中已含有句柄的全部符號，表明此時某一規(guī)則A的右部符號串已出現(xiàn)在棧頂，其相應(yīng)的分析動作是用此規(guī)則進行歸約。,LR（0）分析法,, 活前綴中只含有句柄的一部分符號，此時意味著形如 A12 規(guī)則的右部子串 1已出現(xiàn)在棧頂，2正期待著從余留的輸入串中進行歸約得到。, 活前綴中全然不含有句柄的任何符號，此時意味著期望從余留輸入串能看到由某規(guī)則 A 的右部 所推出的符號串。,LR（0）分析法,,為了刻畫在分析過程中, 文法的一個規(guī)則右部符號串已有多大一部分被識別，我們可在文法中每個規(guī)則右部適當位置上加一個圓點

12、來表示。針對上述三種情況，標有圓點的規(guī)則分別為：,A,A 1 2,A,我們把文法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ù)牟煌闆r，因此，我們可以根據(jù)圓點位置和圓點后是終結(jié)符還是非終結(jié)符，將一個文法的全部LR(0)項目進行分類。,LR（0）分析法,,直觀上說，,LR（0）分析法,

13、,LR(0)項目分類如下：,歸約項目,移進項目,待約項目,接受項目,LR（0）分析法,, 歸約項目，形如A，其中(VNVT)*，即圓點在最右端的項目，它表示一個規(guī)則的右部已分析完, 句柄已形成，應(yīng)該按此規(guī)則進行歸約。, 移進項目，形如A a，其中， (VNVT)* ，即圓點后面為終結(jié)符的項目, 它表示期待從輸入串中移進一個符號，以待形成句柄。,LR（0）分析法,, 待約項目，形如A B，其中， (VNVT) * , B VN*，即圓點后面為非終結(jié)符的項目，它表示期待從余留的輸入串中進行歸約得到B，然后分析A的右部。, 接受項目，形如SS ，其中S為文法的開始符號，即文法開始符號的歸約項目。 S

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

15、設(shè)I是拓廣文法G的一個LR(0)項目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：,LR（0）分析法,,I中的任何一個項目都屬于 CLOSURE(I)。,(b) 若A B屬于CLOSURE(I)， 則每一形如 B 的項目 也屬于CLOSURE(I)。,(c) 重復(fù)(b)直到CLOSURE(I)不再增 大為止。,LR（0）分析法,,例如，對例1中的文法,令I(lǐng)=SS ，則,即為初態(tài)的項目集I0,CLOSURE(I),,SS，,SA，,SB，,AaAb,Ac，,BaBb，,Bd,,=,有了初態(tài)的項目集之后，如何求出對于文法符號X可能轉(zhuǎn)移到的下一個狀態(tài)的項目集？,LR（0）分析法,,(2)

16、 定義狀態(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,LR（0）分析法,,例如：初態(tài)的項目集,GO(I0 , S ),=,CLOSURE(SS ),=, SS ,=,I1,GO(I0 , a ),=,CLOSURE(AaAb , BaBb),=, AaAb , AaAb , Ac BaBb , BaBb , Bd ,=,I4, SS , SA , SB, AaAb , Ac ，BaBb , Bd ,I0=,LR（0）分析法,,通過閉包函數(shù)（CLOSURE

17、）和狀態(tài)轉(zhuǎn)移函數(shù)(GO)很容易構(gòu)造出文法 G 的識別文法規(guī)范句型活前綴的DFA。,LR（0）分析法,,(3) 構(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)）。,LR（0）分析法,,(d) 轉(zhuǎn)移函數(shù)GO建立狀態(tài)之間的連 結(jié)關(guān)系。,對前例中的文法，構(gòu)造識別文法所有規(guī)范句型活前綴的DFA如下圖所示：,(c) 重復(fù)(b)直到不出現(xiàn)新的項目集 （新狀態(tài)）為止。,LR（0）分析法,,I0:,,,I1: SS,,,I2: SA,,,I4:,,,I5:

18、 Ac,,,I6: Bd,,識別文法G 活前綴的DFA,S,A,B,a,c,d,c,d,a,,I3: SB,,,LR（0）分析法,,,I7: AaAb,,,I8: AaAb,,I9: AaBb,,,識別文法G 活前綴的DFA,I10: BaBb,b,b,,,A,B,LR（0）分析法,,注意，DFA中的每一個狀態(tài)都是終態(tài)，當M到達它們時，識別出某規(guī)范句型的一個活前綴，對那些只含歸約項目的項目集，如I2、I3、I5 、 I6、I8、I10，當M到達這些狀態(tài)時，表示已識別出一個句柄，這些狀態(tài)稱為句柄識別態(tài)。,當M處于狀態(tài)I1時，M識別的活前綴為S，表示輸入串已成功分析完畢，用SS進行最后一次歸約，稱

19、狀態(tài)為接受狀態(tài)。,LR（0）分析法,,構(gòu)成識別一個文法活前綴的DFA的狀態(tài)（項目集）的全體稱為這個文法的LR(0)項目集規(guī)范族。,(4) LR(0)分析表的構(gòu)造 :,若一個文法G的拓廣文法G的LR(0)項目集規(guī)范族中的每個項目集不存在移進項目和歸約項目同時并存或多個歸約項目同時并存，則稱G為LR(0)文法。,LR（0）分析法,LR（0）分析法,,對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, 令包含項目

20、 SS 的集合 Ik 的下標為分析 器的初始狀態(tài)。,LR（0）分析法,,若項目Ax屬于 Ik, 且轉(zhuǎn)換函數(shù) GO(Ik , x)=Ii , 當 x 為終結(jié)符時，則置ACTIONk, x=Si。,2. 若GO(Ik , A)=Ij , A為非終符，則 置GOTOk, A=j。,LR（0）分析法,,3. 若項目A屬于Ik ，則對任何終 結(jié)符和結(jié)束符$（統(tǒng)一記為a）則置 ACTIONk, x=rj （假定A為文法的第j條規(guī)則）,LR（0）分析法,,5. 分析表中凡不能用規(guī)則1至4填入信 息的元素均置為“出錯標志”，為了 分析表的清晰，僅用空白表示出錯 標志。,4. 若項目SS 屬于

21、Ik，則置 ACTIONk, $=acc。,LR（0）分析法,,根據(jù)上述方法構(gòu)造的LR(0)分析表不含多重定義時，稱這樣的分析表為LR(0)分析表，能構(gòu)造LR(0)分析表的文法稱為LR(0)文法。,LR（0）分析法,,例2 考慮文法GS:,(1)構(gòu)造識別文法規(guī)范句型活前綴的DFA,(2) 判斷該文法是否LR(0)文法，若是， 請構(gòu)造LR(0)分析表，若不是，請說 明理由。,S(S) | a,LR（0）分析法,,分 析：,首先將文法拓廣，并給出每條規(guī)則編號,0. SS,1. S (S),2. S a,識別文法規(guī)范句型活前綴的DFA如下圖所示 ：,LR（0）分析法,,,I0:,,I2:,,

22、,I1: SS,S,,a,I3: S a,,,(,(,,a,,,I4: S (S),,),,I5: S (S),S,識別活前綴的DFA,LR（0）分析法,,因為它的6個LR(0)項目集中均不含有沖突項目，即不存在移進項目和歸約項目并存或多個歸約項目并存的情況。該文法是LR(0)文法。,其LR(0)分析表如下：,LR（0）分析法,,文法GS的LR(0)分析表,0,S3 S2,1,1,acc,2,3,4,5,S3 S2,r2 r2 r2 r2,S5,r1 r1 r1 r1,4,LR（0）分析法,,由上述構(gòu)造過程可以看出，LR(0)分析器的特點是不需要向前查看輸入符號就能歸約，即當棧頂形成句柄，不管

23、不一個輸入符號是什么，都可以立即進行歸約而不會發(fā)生錯誤。,LR（0）分析法,識別活前綴的DFA,,識別文法G活前綴的DFA,0. SS,1. SA,2. SB,3. AaAb,4. Ac,5. BaBb,6. Bd,,I7: AaAb,,,I8: AaAb,,I9: AaBb,,I10: BaBb,b,b,,,A,B,a,,0,1,2,3,4,5,S4 S5 S6,acc,S4 S5 S6,r1 r1 r1 r1 r1,r2 r2 r2 r2 r2,r4 r4 r4 r4 r4,1 2 3,7 9,文法GS的LR(0)分析表,6,7,8,9,10,S8,

24、r6 r6 r6 r6 r6,S10,r3 r3 r3 r3 r3,r5 r5 r5 r5 r5,,SLR（1）分析法,這個條件比較苛刻，對于大多數(shù)程序設(shè)計語言來說，一般都不能滿足LR(0)文法的條件，即使是描述一個算述表達式的簡單文法也不是LR(0)文法。,例 考慮算術(shù)表達式 的文法 ：,每一個LR(0)項目集中都不含有沖突的項目，,由于LR(0)文法要求文法的,EE+T | T,TT*F | F,F(E) | id,,SLR（1）分析法,將文法拓廣并對規(guī)則進行編號,直接構(gòu)造出識別文法規(guī)范句型活前綴的DFA下如圖所示。,0. EE,1. EE+T,2. ET,3.

25、 TT * F,4. TF,5. F(E),6. Fid,,I0:,,E,,I1:EE,EE+T,,,I2: ET,TT*F,T,,,I3:TF,F,,I4:,,(,(,,F,T,,,I5: Fid,id,,,I6:,,+,F,,(,id,,I7:,,(,,,id,id,*,,,I8:F (E),EE+T,E,,+,,,I6:,,,id,,,I8:F (E),EE+T,E,,+,,T,I9:EE+T,TT*T,,*,,,F,I10:TT*F,,,I11:F(E) ,),識別表達式文法活前綴的DFA,,I0:,,E,,I1:EE,EE+T,,,I2: ET,TT*F,T,,,I3:TF,F,,I

26、4:,,(,(,,F,T,,,I5: Fid,id,+,F,(,id,,I7:,,(,,,id,id,*,,E,,+,,SLR（1）分析法,不難看出在I1，I2，I9中既含有移進項目，又含有歸約項目，因而這個表達式的文法不是LR(0)文法。,根據(jù)構(gòu)造LR(0)分析表的方法，構(gòu)造出的LR(0)分析表中在2狀態(tài)和9狀態(tài)下面臨輸入符號*時含多重定義元素，見下表。,表達式文法的LR(0)分析表,,SLR（1）分析法,為了對語言句子進行確定性的分析，需要解決,移進歸約或歸約歸約沖突。,我們采用對含有沖突的項目集向前查看一個輸入符號的辦法來解決沖突，,這種分析法稱為簡單的LR分析法，即SLR(1)分析法。

27、,,SLR（1）分析法,仔細分析構(gòu)造LR(0)分析表的方法，容易看出使分析表出現(xiàn)多重定義的原因在于其中的規(guī)則2，即對于每一個項目集Ik中的歸約項目A ，不管當前輸入符號是什么，都將ACTION表中第K行的各個元素均置為rj，其中j為規(guī)則A的編號。,,SLR（1）分析法,因此，當一個LR(0)項目集規(guī)范族中存在一個含移進歸約沖突和歸約歸約沖突的項目集時,則在分析表第K行中遇輸入符號b必然會出現(xiàn)多重定義元素。,IK= XbB, A, Br ,對含沖突的項目集，僅根據(jù)LR(0)項目本身的信息是無法解決沖突的。需要向前查看一個輸入符號以考察當前所處的環(huán)境。,,SLR（1）分析法,對歸約項目A和B ，只

28、需要考察當將句柄或歸約為A或B時，直接跟在A或B后的終結(jié)符的集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移進符號b，即滿足：,IK= XbB, A, Br ,FOLLOW(A)FOLLOW(B)=,FOLLOW(B)b=,FOLLOW(A)b=,,SLR（1）分析法,那么，當狀態(tài)K面臨輸入符號a時，可按以下規(guī)則解決沖突：,(1) 若a=b則移進,(2) 若aFOLLOW(A)，則用規(guī)則 A進行歸約。,(3) 若aFOLLOW(B)，則用規(guī)則 Br進行歸約。,(4) 此外報錯。,,SLR（1）分析法,一般而言，若一個LR(0)項目集I中有m個移進項目和n個歸約項目時：,對所有

29、移進項目向前看一符號集合a1,a2,,am和 FOLLOW(B1), FOLLOW(B2), ，F(xiàn)OLLOW(Bn)兩兩相交為時，則項目集 I 中沖突仍可用下述規(guī)則解決沖突。,I : A11a11 ,A22a22 , , Ammamm ,,B1r1, B2 r2, , Bn rn ,,SLR（1）分析法,設(shè)a為當前輸入符：,(1) 若aa1,a2,,am則移進。,(3) 此外報錯。,(2) 若aFOLLOW(Bi) ,i=1,2, ,n, 則用Biri進行歸約。,這種用來解決分析動作沖突的方法稱為SLR(1)方法。,,SLR（1）分析法,現(xiàn)在分別考察上例中的三個項目集I1,I2,I9

30、中沖突能否用SLR(1)方法解決。,由于FOLLOW(E)=$+= ，且EE是“接受”項目，所以I1中的接受移進沖突可以用SLR(1)方法解決。,如果對于一個文法的某些LR(0)項目集或LR(0)分析表中所含有的動作沖突都能用SLR(1)方法解決，則稱這個文法是SLR(1)文法。,I1= EE, EE+T ,,SLR（1）分析法,由于FOLLOW(E)=+,),$*=, 因此面臨輸入符為,）,$時，用規(guī)則ET進行歸約，當面臨輸入符*時，則移進，I2中移進歸約沖突可以用SLR(1)方法解決。,與I2中情況類似，其項目集中移進歸約沖突可用SLR(1)方法解決。因此該文法是SLR(1)文法。,I2=

31、 ET, TT*F ,I9= EE+T, TT*F ,,SLR（1）分析法,SLR(1)分析表的構(gòu)造與LR(0)分析表的構(gòu)造基本相同。僅對LR(0)分析表構(gòu)造算法中的規(guī)則2進行如下修改：,若歸約項目A屬于Ik，則對任何終結(jié)符 a FOLLOW(A) 置 ACTIONk, a=rj，其中A為文法的第j條規(guī)則。,,SLR（1）分析法,按上述方法對前例中的算術(shù)表達式文法構(gòu)造出SLR(1)分析表如表所示：,FOLLOW(E)=$,FOLLOW(E)=+, ), $,FOLLOW(T)=+, ), $, *,,SLR（1）分析法,若文法的SLR(1)分析表不含多重定義元素，則稱文法G為SLR(1)文法。

32、,例1 設(shè)有拓廣文法GS,0. SS,1. S Sb,2. S bAa,3. A aSc,4. A aSb,5. A a,,SLR（1）分析法,(1) 構(gòu)造識別文法規(guī)范句型活前綴的DFA。,(2) 判斷該文法是否SLR(1)文法，若是， 構(gòu)造SLR(1)分析表，若不是，請說明 理由。,該文法的LR(0)項目集規(guī)范族及轉(zhuǎn)換函數(shù)如下圖所示:,,I0:,,S,,I1: SS,S Sb,,b,,I2:,,I3: S Sb,,b,,I4: S bAa,,,,I5:,a,,b,A,,a,,I6:S bAa,,,I7:,S,,I8: A aSc,文法GSLR(0)項目集及轉(zhuǎn)換函數(shù),,I9: A aSb,

33、S Sb,,,c,b,,SLR（1）分析法,分析所有這些項目集，可知在項目集I1，I5中存在移進歸約沖突，I9中存在歸約歸約沖突，因此該文法不是LR(0)文法。,考慮含沖突的項目集能否用SLR(1)方法解決。,FOLLOW(A) =a,FOLLOW(S) =b,c,$,FOLLOW(S) =$,,SLR（1）分析法,由于有FOLLOW(S)b =$b=，I1中的移進歸約沖突可以用SLR(1)方法解決。,由于有FOLLOW(A)b =ab=，I5中的移進歸約沖突可以用SLR(1)方法解決。,I1= SS, S Sb ,I5= A a, S bAa ,,SLR（1）分析法,由于有 FOLLOW(A

34、) FOLLOW(S) =ab, c, $=, I9中的歸約歸約沖突也可用SLR(1)方法解決。,所以該文法是SLR(1)文法。相應(yīng)的SLR(1)分析表如下表:,I9= A aSb, S Sb ,SLR（1）分析法,,I0:,,S,,I1: SS,S Sb,,b,,I2:,,I3: S Sb,,b,,I4: S bAa,,,,I5:,a,,b,A,,a,,I6:S bAa,,,I7:,S,,I8: A aSc,文法GSLR(0)項目集及轉(zhuǎn)換函數(shù),,I9: A aSb,S Sb,,,c,b,,SLR（1）分析法,SLR(1)分析法是一種簡單而實用的方法,其造表演算法簡單,狀態(tài)數(shù)目少,且大多數(shù)程序

35、設(shè)計語言都可以用SLR(1)文法來定義。,但是仍存在這樣一些文法，其項目集中的移進一歸約沖突或歸約歸約沖突不能用SLR(1)方法解決。,,SLR（1）分析法,例2 下列拓廣文法G為,我們首先用SS作為初態(tài)集的項目，然后用閉包函數(shù)和轉(zhuǎn)換函數(shù)構(gòu)造識別文法G活前綴的DFA如下圖所示。,0. SS,1. S L=R,2. S R,3. L *R,4. L i,5. R L,,SLR（1）分析法,可以發(fā)現(xiàn)項目集 I2中存在移進和歸約沖突：,因此，I2中移進和歸約沖突不能用SLR(1) 方法解決。,SL=R *R=R,S R,I2 =,,S L=R,R L,,由于 FOLLOW(R)==,$=,,SLR（

36、1）分析法,1. SLR(1)方法為什么不能解決 I2中 的移進和歸約沖突?,2. 怎樣解決 I2中的移進和歸約沖突?,問題:,,SLR（1）分析法,由于用SLR(1)方法解決動作沖突時，它僅孤立地考察對于歸約項目A ，只要當前面臨輸入符號aFollow(A)時，就確定使用規(guī)則A進行歸約，而沒有考察符號串所在規(guī)范句型的環(huán)境 。,Ii : A,I0 I1 Ii,$ ,aaa,I0 I1 Ij,$A,aaa,,SLR（1）分析法,因為如果棧里的符號串為$ ，歸約后變?yōu)?A，當前讀到的輸入符號是a，若文法中不存在以Aa為前綴的規(guī)范句型，那么，這種歸約無效。,例如，我們考查規(guī)范句型ii的SLR(1)

37、 分析過程：,,I0:,,S,,I1:SS,,,I2: S L=R,R L,L,,,I3: S R,R,,I4:,,*,*,,,i,,i,I5: L i,,,I6:,=,,*,,,I7: L *R,R,i,,,L,I8: R L,L,,R,,I9: S L=R,LR(0)識別G活前綴的DFA,,SLR（1）分析法,不難看出當狀態(tài)2呈現(xiàn)于棧頂且面臨的輸入符號是時，由于這個文法不含有以R為前綴的規(guī)范句型，因此用RL進行的歸約是無效歸約。,,SLR（1）分析法, SL=R*R=R,也就是說，并不是FOLLOW(R)中的每個元素在含R的所有句型中在R的后面都會出現(xiàn)。解決這一問題的方法是采用LR(1)分

38、析法。,,LR（1）分析法,在分析過程中，當試圖用某一規(guī)則A歸約棧頂?shù)姆柎畷r不僅應(yīng)該察看棧中符號串，還應(yīng)向前掃視一個輸入符號a，只有當Aa的確構(gòu)成文法某一規(guī)范句型的前綴時，才能用此規(guī)則進行歸約。,LR(1)分析法的思想:,,LR（1）分析法,為此，我們可以考慮在原來LR(0)項目集中;增加更多的展望信息，這些展望信息有助于克服動作沖突和排除無效歸約。也就是需要重新定義項目，稱之為LR(1)項目。,一個LR(1)項目是一個二元組,A，a,,LR（1）分析法,當時，搜索符a明確指出當A，a是棧頂狀態(tài)的一個LR(1)項目時，僅在輸入符號是a時才能用A歸約，而不是對FOLLOW(A)中的所有符號都用

39、A歸約。,當時，搜索符是無意義的。,其中A是一個LR(0)項目，每個a是終結(jié)符，稱為展望符或搜索符。,,LR（1）分析法,構(gòu)造LR(1)項目集族的方法和構(gòu)造LR(0)項目集規(guī)范族的方法基本相同。具體構(gòu)造方法如下：,(1) 構(gòu)造LR(1)項目集 I 的閉包函數(shù),(a) I的任何LR(1)項目都屬于CLOSURE(I)。,(b) 若項目 AB, a 屬于CLOSURE(I), Br 是文法中的一條規(guī)則, bFIRST(a),則Br, b也屬于CLOSURE(I)。,(c) 重復(fù)(b),直到CLOSURE(I)不再增大為止。,,LR（1）分析法,對例2中的文法G, 令 I=SS，$為初態(tài)集的初始項目

40、集，對其求閉包：,= CLOSURE(SS，$),CLOSURE(I),= SS，$ SL=R，$ SR，$,L*R，=/$ Li，=/$,RL，$ ,= I0,FIRST(a)=FIRST($)=$,FIRST(a)=FIRST(=R$)==,FIRST(a)=FIRST($)=$,FIRST(a)=FIRST($)=$,,LR（1）分析法,(2) 構(gòu)造轉(zhuǎn)換函數(shù),令I(lǐng)是一個LR(1)項目集，X是一個文法符號，函數(shù),GO(I，X)=CLOSURE(J)。,J=AX,a | AX,aI,,LR（1）分析法,GO( I0 ,S) = SS，$ = I1,GO( I0 ,*) = L*R，=/$ R

41、L，=/$,L*R，=/$ Li，=/$ ,= I4,,I0:,,S,,I1: SS,$,,L,,I2:SL=R,$,RL,$,,,I3: SR,$,,,R,I4:,*,,,I5: Li,=/$,i,,i,*,,I6:,I9:SL=R,$,,,,I11:,I10:RL,$,,I12: Li,$,I7: L*R,=/$,,I13:L*R,$,,I8: RL,=/$,,*,LR(1)項目集族及轉(zhuǎn)換函數(shù),,=,,,R,L,,R,,L,,,*,L,,,i,R,,i,,LR（1）分析法,分析所有這些項目集,可以發(fā)現(xiàn)每個項目集中都不含移進歸約沖突,或歸約歸約沖突。,在項目集 I2中，由于歸約項目RL,$的

42、搜索符集合$與移進項目SL=R,$的待移進符號號不相交，所以在I2中，當面臨輸入符為$時用規(guī)則RL歸約，為時則移進，I2中的移進一歸約沖突在LR(1)分析法中得到了解決。,,LR（1）分析法,構(gòu)造LR(1)分析表的方法與構(gòu)造LR(0)分析表的方法基本相同，僅對歸約項目作如下修改：,若歸約項目A,a屬于Ik，則對搜索符a置ACTIONK，arj。其中A為文法的第j條規(guī)則。,按上述方法我們對例2中文法的LR(1)項目集族構(gòu)造相應(yīng)的LR(1)分析表如下表所示：,GS的LR(1) 分析表,,LR（1）分析法,由上表可以看出，對LR(1)的歸約項目不存在任何無效歸約。但在多數(shù)情況下同一個文法的LR(1)

43、項目集的個數(shù)比LR(0)項目集的個數(shù)要多。,這是因為對同一個LR(0)項目集，由于搜索符不同而對應(yīng)著多個LR(1)項目集。,,LR（1）分析法,例2中的文法是一個LR(1)文法，卻不是SLR(1)文法。然而，當一個文法是LR(0)文法，則一定也是一個SLR(1)文法，也是LR(1)文法。反之則不一定成立。,如果一個文法的LR(1)分析表不含多重入口時，或者任何一個LR(1)項目集中沒有移進一歸約沖突或歸約一歸約沖突， 則稱該文法為LR(1)文法。,,LR（1）分析法,例3 考慮拓廣文法:,試構(gòu)造它的LR(1)項目集合的DFA和LR(1)分析表。,0. SS,1. S (S),2. S a,,L

44、R（1）分析法,,I0:,,,S,I1: SS, $,,,I3: Sa, $,a,,,I2:,,S,,I4: S(S), $,,,I6: Sa, ),,I5:,,a,(,(,,a,(,,),,I7: S(S),$,,S,,I8: S(S), ),,,I9: S(S),),),文法GS項目集合的DFA,,LR（1）分析法,由該文法的10個LR(1)項目集中可以看出，均不存在移進一歸約或歸約一歸約沖突，因此該文法為LR(1)文法。,實際上，該文法是一個LR(0)文法，因此該文法也是SLR(1)文法，也是LR(1)文法。該文法相應(yīng)的LR(1)分析表如表所示。,,LR（1）分析法,LR（1）分析法,本

45、節(jié)完,,LALR（1）分析法,LR(1)分析法雖然可以解決SLR(1)方法所難以解決的移進歸約或歸約歸約沖突，但是對同一個文法而言，當搜索符不同時，使得同一個項目集被分裂成多個項目集從而引起狀態(tài)數(shù)的劇烈增長，導(dǎo)致時間和內(nèi)存空間的急劇上升，使其應(yīng)用受到一定的限制，為了克服LR(1)分析法的這種缺點，我們可以采用LALR(1)分析法。,,LALR（1）分析法,LALR(1)分析法是界于SLR(1)分析法和LR(1)分析法之間的一種語法分析方法，這種分析法能解決SLR(1)分析法所不能解決的沖突動作，并且其分析表的狀態(tài)個數(shù)與SLR(1)分析表的狀態(tài)個數(shù)一樣多。,LALR(1)分析法的基本思想是對LR

46、(1)項目集規(guī)范族中將所有同心的項目集合并為一，以減少項目集個數(shù)。,,LALR（1）分析法,所謂同心的LR(1)項目集是指在兩個LR(1)項目集中，除搜索符不同之外，核心部分是相同的。,例如，分析前例文法的LR(1)項目集族，可以發(fā)現(xiàn)同心集如下：,0. SS 3. L *R 1. S L=R 4. L i 2. S R 5. R L,,I4與I11，I5與I12，I7與I13，I8與I10它們倆 倆之間除了搜索符不同之外, “心”是相同 的。將同心集合并為：,,LALR（1）分析法,,,LALR（1）分析法,我們看到合并同心集后的項目集其核心部分不變，僅搜索符合并。對合并同心集后

47、的項目集的轉(zhuǎn)換函數(shù)為GO(I,X)自身的合并，這是因為相同的心之轉(zhuǎn)換函數(shù)仍屬同心集。,例如,GO(I4,11, i)=GO(I4, i)GO(I11, i)= I5,12,GO(I4,11, R)=GO(I4, R)GO(I11, R)= I7,13,GO(I4,11, *)=GO(I4, *)GO(I11, *)= I4,11,,LALR（1）分析法,合并同心集需著重指出的是若文法是LR(1)文法, 即它的LR(1)項目集中不存在動作沖突, 合并同心集后若有沖突也只可能是歸約歸約沖突而不可能是移進歸約沖突。,假定LR(1)文法的項目集Ik與Ij為同心集，其中,Ik= A, a1 Ba, b1

48、 ,Ij= A, a2 Ba, b2 ,合并同心集后的項目集,Ikj= A, a1/a2 Ba, b1/b2 ,,LALR（1）分析法,因為假設(shè)文法是LR(1)的, 在Ik中a1a=, 在Ij中a2a=, 顯然在Ik j中,(a1a2)a=,這也就是說合并同心集以后，不可能有移進歸約沖突。,但可能有歸約歸約沖突。例如,可設(shè)想有兩個同心的LR(1)項目集:,,LALR（1）分析法,現(xiàn)在我們可以根據(jù)合并同心集后的項目集族構(gòu)造文法的LALR(1)分析表，其構(gòu)造方法如下：,Ik= A, a B, b ,Ij= A, b B, a ,合并同心集后的項目集,Ikj= A, a/b B, a/b ,合并后產(chǎn)

49、生了歸約歸約沖突。,,LALR（1）分析法,2. 若LR(1)項目集族中不存在含沖突的項目集，則合并所有同心集，構(gòu)造出文法的LALR(1)項目集族。,1. 構(gòu)造拓廣文法G的LR(1)項目集族。,例如，對前例中文法G的LR(1)項目集族合并同心集后構(gòu)造出的LALR(1)項目集族如下圖所示。,,LALR （1）分析法,4LALR(1)項目集族構(gòu)造該文法的LALR(1)分析表的方法與LR(1)分析表的構(gòu)造方法相同。由圖構(gòu)造文法的LALR(1)分析表如下表所示。,3. 若LALR(1)項目集族中不存在歸約一歸約沖突，則該文法是LALR(1)文法。對例中的文法，由于合并同心集后不存在歸約歸約沖突，所以該

50、文法是LALR(1)文法。,,LALR（1）分析法,對一給定的文法G而言，其LALR(1)分析表比LR(1)分析表狀態(tài)數(shù)要少(例中LALR(1)的狀態(tài)數(shù)比LR(1)狀態(tài)數(shù)減少了4個)，但在分析文法GS的某一個含有錯誤的符號串時，LALR(1)分析速度比LR(1)分析速度要慢，這是因為合并同心集后多做不必要的歸約，從而推遲發(fā)現(xiàn)錯誤。,,對二義性文法的應(yīng)用,與其相應(yīng)的LR分析表一定含有多重定義的元素。但是對某些二義性文法，在含多重定義的LR分析表中加進足夠的無二義性規(guī)則，從而可以構(gòu)造出比相應(yīng)非二義性文法更優(yōu)越的LR分析器。,任何一個二義性文法決不是LR類文法，,我們知道,,對二義性文法的應(yīng)用,EE

51、+E | E*E | (E) | id,相應(yīng)的非二義性文法為：,EE+T | T,TT*F | F,F(E) | id,例如，考慮算術(shù)表達式的二義性文法,,對二義性文法的應(yīng)用,2. 二義性文法的LR分析表所含狀態(tài)數(shù)肯定比非二義性文法少，因為非二義性文法含有右部僅只一個非終結(jié)符號的規(guī)則 ET 和TF，它們要占用狀態(tài)和降低分析器的分析效率。,兩者相比，二義性文法的優(yōu)點在于:,1. 若需改變運算符的優(yōu)先級或結(jié)合性，無需改變文法自身。,,對二義性文法的應(yīng)用,現(xiàn)在我們構(gòu)造算術(shù)表達式二義性文法的LR(0)項目集規(guī)范族如下圖所示：,,對二義性文法的應(yīng)用,從圖中可以看出狀態(tài)I1,I7和I8中存在移進歸約沖突,

52、I1中沖突可用SLR(1)方法解決。,對I7和I8而言：,因為FOLLOW(E)+,*=，即遇到輸入符號為$時則接受，遇到或*時則移進。,FOLLOW(E)+,*=$,+,*,)+,*,由于有,,對二義性文法的應(yīng)用,因而I7和I8中沖突不能用SLR(1)方法解決，也不能用其它LR(K)方法解決，但是我們用+，*的優(yōu)先級和結(jié)合性可以解決這類沖突。,,對二義性文法的應(yīng)用,那么在 I7中, 由于*優(yōu)先級高于, 所以狀態(tài)7面臨*移進，又因服從左結(jié)合，所以狀態(tài)7面臨則用 EEE歸約。,若我們規(guī)定*的優(yōu)先級高于的優(yōu)先級，且它們都服從左結(jié)合,,對二義性文法的應(yīng)用,在 I8中, 由于*優(yōu)先于且*服從左結(jié)合，因

53、此狀態(tài)8面臨或*都應(yīng)用EE*E歸約。,由此構(gòu)造的該二義性文法的LR分析表如下表所示：,,對二義性文法的應(yīng)用,二義性文法的LR分析表,,對二義性文法的應(yīng)用,其它的二義性文法也可用類似方法進行處理，可以構(gòu)造出無多重定義的LR分析表。,本章小結(jié),,本章主要介紹了LR分析法,大多數(shù)用上下文無關(guān)文法描述的語言都可以用相應(yīng)的LR分析器予以識別。,1. LR分析法是一種規(guī)范歸約分析法，,本章小結(jié),,2. 從給定的上下文無關(guān)文法構(gòu)造LR分析表的方法是：,對LR(1)或 LALR(1)分析表，構(gòu)造 LR(1)項目集規(guī)范族。,(1)對LR(0)或 SLR(1)分析表，構(gòu)造 LR(0)項目集規(guī)范族;,本章小結(jié),

54、,(2)構(gòu)造識別文法規(guī)范句型活前綴的DFA。,(3)將DFA轉(zhuǎn)換成相應(yīng)的LR分析表。,注意文法一定要拓廣。,四種分析表的構(gòu)造基本相同，僅對含歸約項目的項目集構(gòu)造分析表元素不同。,3. 四種LR文法的判別方法,(1)任何的二義性文法都不是LR類文法。,本章小結(jié),, SLR(1)文法是LR(0)項目集中所有含沖突的項目集都能用SLR規(guī)則解決沖突。 (或SLR(1)分析表中不含多重定義),(2)根據(jù)項目集中是否含沖突項目或相應(yīng)分析表中是否含多重定義元素進行判斷：, LR(0)文法是所有的LR(0)項目集中沒有移進一歸約沖突或歸約一歸約沖突。(或LR(0)分析表中不含多重定義),本章小結(jié),,SLR規(guī)則

55、：,I: A .b B 1 1. B2 2. ,b FOLLOW(B1)=,FOLLOW(B1)FOLLOW(B2)=,b FOLLOW(B2)=,a b 移進,a FOLLOW(B1) 用B 1 1 歸約,a FOLLOW(B2) 用B2 2 歸約,本章小結(jié),, LR(1)項目集中無移進一歸約沖突或歸約一歸約沖突。（或LR(1)分析表中不含多重定義）,LALR(1)項目集中無歸約一歸約沖突。(或LALR(1) 分析表中不含多重定義）,4.四種LR類文法之間的關(guān)系,注意搜索符只對歸約項目起作用。,本章小結(jié),,一個文法是LR(0)文法一定也是SLR(1)文法，也是LR(1)、LALR(1)文法，

56、反之則不一定成立。即,LR(0),,SLR(1),LALR(1),LR(1),,,例1 考慮文法,SAS | b,ASA | a,(1) 構(gòu)造識別文法活前綴的DFA。,本章小結(jié),,(3) 該文法是SLR(1)的嗎？若是，構(gòu)造它 的SLR(1)分析表。,(2) 該文法是LR(0)文法嗎？請說明理由。,(4) 該文法是LR(1)或LALR(1)文法嗎？請 說明理由。,解：首先將文法拓廣，并對規(guī)則進行編號,0. S S,1. S AS,2. S b,3. A SA,4. A a,(1) 識別文法活前綴的DFA如下圖所示。,,I0:,I1:,,,I2:,,I5:,I3: S b,I4: A a

57、,I6:,,,,,S,,A,b,b,b,,a,,a,,a,,A,,A,a,b,,S,,,S,A,b,,a,A,識別文法GS活前綴DFA,(1) 識別文法活前綴的DFA如下圖所示。,,I0:,I1:,,,I2:,,I7:,,I5:,I3: S b,I4: A a,I6:,,,,,S,,A,b,b,b,,a,,a,,a,,A,,A,a,b,,S,,,S,A,b,,a,A,,S,S,,b,A,,S,a,識別文法GS活前綴DFA,本章小結(jié),,(2) 由上圖不難看出，項目集I1, I5, I6 中存在著移進歸約沖突，所以該文法不是LR(0)文法。,(3) 由于對該文法句子abab對應(yīng)下面兩棵不同的語法樹

58、：(見下圖),本章小結(jié),,S,S,A,a,S,A,S,A,b,a,b,,,,,,,,,,,S,S,A,a,S,A,S,A,b,a,b,,,,,,,,,,所以該文法為二義性文法，任何二義性文法絕不是SLR(1)文法，也不是LALR(1)或LR(1)文法。,,本章小結(jié),,例2 設(shè)有文法GS:,S (S) |,試判斷該文法是否SLR(1)文法，若不是，請說明理由；若是，請構(gòu)造SLR(1)分析表。,解：首先將文法拓廣，并給出每條規(guī)則編號,0. SS,1. S (S),2. S ,本章小結(jié),,I0:,I3: S (S),,構(gòu)造該文法的LR(0)項目集族和轉(zhuǎn)換函數(shù)如下圖所示。,該文法不是LR(0)文法。因

59、為I0，I2中含有移進歸約的沖突。,,I1: SS.,,I2:,,,I4: S (S),,S,,(,,S,(,),,見表,本章小結(jié),,但是I0，I2中的移進歸約的沖突可以用SLR(1)方法解決：,FOLLOW(S)=), $(=,所以該文法是SLR(1)文法。,其SLR(1)分析表如下表：,本章小結(jié),,O,1,2,3,4,S2 r2 r2,acc,1,S2 r2 r2,3,S4,r1 r1,文法GS的SLR(1)分析表,見圖,本章小結(jié),,例3 設(shè)有文法GS:,試證明該文法是SLR(1)文法，但不是LR(0)文法。,解：首先將文法拓廣，并對規(guī)則進行編號,直接構(gòu)造LR(0)項目集如下：,

60、S aSb | aSd |,0. S S,1. S aSb,2. S aSd,3. S ,本章小結(jié),,I0:,S S,S aSb,S aSd,S ,I1:,SS,I2:,S aSb,S aSd,S aSb,S aSd,S ,I3:,S aSb,S aSd,I4:,S aSb,I5:,S aSd,0. S S 2. S aSb 1. S aSd 3. S ,本章小結(jié),,檢查每個項目集可知，項目集I0和I2中有移進一歸約沖突，因此該文法不是LR(0)文法。,又因為,所以項目集I0和I2中移進一歸約沖突可以用SLR(1)方法解決。因此該文法是SLR(1)文法，但不是LR(0)文法。,FOLLOW(S

61、)=b,d,$a= ,本章小結(jié),,例4 設(shè)有文法GS:,2.試判斷該文法是否SLR(1)文法, 若不是, 請說明理由；若是，請構(gòu)造出SLR(1)分析表, 并給出符號串(( ))$的分析過程。,1.構(gòu)造識別文法規(guī)范句型活前綴的DFA( LR(0)項目集族和GO函數(shù) )。,S S(S) |,本章小結(jié),,3. 試判斷該文法是否LR(1)文法，若不是，請說明理由；若是，請構(gòu)造LR(1)分析表。,4. 試判斷該文法是否LALR(1)文法，請說明理由。,本章小結(jié),,分析 首先將文法拓廣，并對規(guī)則編號:,0. SS S S(S) S ,構(gòu)造LR(0)項目集規(guī)范族和轉(zhuǎn)換函數(shù)如下圖所示:,本章小結(jié),S S(S.

62、),S S.(S),I0:,,,I1: SS.,,I2:,,,I4: S S(S),,S,,(,S,(,),,0. SS S S(S) S ,S S.(S),S S(S),S ,S S(.S),,I3:,,,本章小結(jié),,I1中的移進歸約的沖突可以用SLR(1)方法解決：,FOLLOW(S)=$(=,所以該文法是SLR(1)文法。,本章小結(jié),FOLLOW(S) = $, (, ) ,符號串(( ))$的分析過程如下：,本章小結(jié),,0. SS S S(S) S ,構(gòu)造LR(1)項目集規(guī)范族和轉(zhuǎn)換函數(shù)如下圖所示:,本章小結(jié),,I0:,SS, $,SS(S), $/(,S , $/(,,,I1: SS , $,,I2:,,,,S,(,S,(,),,0. SS S S(S) S ,SS.(S), $/(,SS(S), )/(,S , )/(,SS(S), $/(,,I3:,SS(S.), $/(,S S.(S), )/(,,,I5:,,SS(S), )/(,S , )/(,SS(S), )/(,,I6:,SS(S), )/(,S S(S), )/(,S,,,I7:SS(S), )/(,),I4:SS(S),$/(,,本章小結(jié),所有的LR(1)項目集中沒有移進歸約的沖突,所以該文法為LR(1)文法,,或該文法為SLR(1)文法, 任何SLR(1)文法都是LR(1)或LALR(1)文法,