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

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

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

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

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

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

5、 兩部分組成，,狀態(tài)轉(zhuǎn)換表元素GOTOSi , X規(guī)定了當(dāng)狀態(tài)Si面臨文法符號(hào)X時(shí)，應(yīng)轉(zhuǎn)移到的下一個(gè)狀態(tài)。,2. LR分析表,分析動(dòng)作(ACTION)表,狀態(tài)轉(zhuǎn)換( GOTO )表,LR分析器的邏輯結(jié)構(gòu)和工作過程,,分析動(dòng)作表元素ACTIONSi , a規(guī)定了當(dāng)狀態(tài)Si面臨輸入符號(hào)a時(shí)應(yīng)執(zhí)行的動(dòng)作。,分析動(dòng)作表對(duì)應(yīng)四種可能動(dòng)作：,移進(jìn)：把狀態(tài)Sj=GOTOSi , a和輸入符號(hào) a移入分析棧。,歸約：當(dāng)棧頂符號(hào)串形成句柄，且文法中 有A的規(guī)則，其中||=，則歸約 動(dòng)作是從分析棧棧頂去掉個(gè)文法符 號(hào)和個(gè)狀態(tài)，并把歸約符A和 GOTOSi- ，A=Sj移

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

7、和LR分析表。,輸出：若W是句子，得到W的自下而上 分析成功，否則輸出錯(cuò)誤信息。,( LR分析器的工作過程的形式化描述 ),算法：初始化時(shí)，初始狀態(tài)S0在分析棧 棧頂，輸入串W$的第1個(gè)符號(hào)讀 入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)和工作過程,,對(duì)文法句子aacbb$的LR分析過程如下:,初始化時(shí)，初始狀態(tài) 0 和句子的左界符 $在分析棧棧頂，讀入輸入串 a

8、acbb$ 的第1個(gè)符號(hào)a 。,LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR分析器的邏輯結(jié)構(gòu)和工作過程,,LR（0）分析法,,LR(0)分析就是在分析的每一步，只需根據(jù)當(dāng)前棧頂狀態(tài)而不必向前查看輸入符號(hào)就能確定應(yīng)采取的分析動(dòng)作。,LR分析器的關(guān)鍵部分是分析表的構(gòu)造。,構(gòu)造LR分析表的基本思想是:,從給定的上下文無關(guān)文法直接構(gòu)造識(shí)別文法所有規(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ī)范句型的前綴， 這種前綴不包含句柄右邊的任何符號(hào)。,注意，活前綴可以是一個(gè)或者是若干個(gè)規(guī)范句型的前綴。,LR（0）分析法,,LR（0）分析法,,由前例，對(duì)輸入串a(chǎn)acbb的歸約過程，可以看出，當(dāng)所分析的輸入串沒有語法錯(cuò)誤時(shí)，則在分析的每一步，分析棧中已移進(jìn)一歸約的全部文法符號(hào)與余留的輸入符號(hào)串合起來，就是所給文法的一個(gè)規(guī)范句型。,LR（0）分析法,,這也就是說，在LR分析過程中的任何時(shí)刻，棧中的文法符號(hào)應(yīng)是某一規(guī)范句型的活前綴，這是因?yàn)橐坏┚湫途浔跅５捻敳啃纬?，就?huì)立即被歸約，因此，只要輸入串已掃描過的部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過的部分是正確的。,LR（0

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

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

12、來表示。針對(duì)上述三種情況，標(biāo)有圓點(diǎn)的規(guī)則分別為：,A,A 1 2,A,我們把文法G中右部標(biāo)有圓點(diǎn)的規(guī)則稱為G的一個(gè)LR(0)項(xiàng)目。,值得注意的是對(duì)空規(guī)則 A，僅有LR(0)項(xiàng)目A 。,文法G的全部LR(0)項(xiàng)目是構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA的基礎(chǔ)。我們將會(huì)看到這種DFA的每一個(gè)狀態(tài)和有窮個(gè)LR(0) 項(xiàng)目的集合相關(guān)聯(lián)。,一個(gè)LR(0)項(xiàng)目指明了對(duì)文法規(guī)范句型活前綴的不同識(shí)別狀態(tài),,由于不同的LR(0)項(xiàng)目反映了在分析過程中棧頂?shù)牟煌闆r，因此，我們可以根據(jù)圓點(diǎn)位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符，將一個(gè)文法的全部LR(0)項(xiàng)目進(jìn)行分類。,LR（0）分析法,,直觀上說，,LR（0）分析法,

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

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

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

16、 定義狀態(tài)轉(zhuǎn)移函數(shù)GO,設(shè)I是拓展文法G的任一個(gè)項(xiàng)目集，X為一文法符號(hào)，定義狀態(tài)轉(zhuǎn)移函數(shù)GO(I,X)如下：,GO( I , X ),=,CLOSURE( J ),J,=,AaX | AaX I,LR（0）分析法,,例如：初態(tài)的項(xiàng)目集,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 的識(shí)別文法規(guī)范句型活前綴的DFA。,LR（0）分析法,,(3) 構(gòu)造識(shí)別文法規(guī)范句型活前綴DFA的方法 :,(a) 求CLOSURESS，得到初態(tài) 項(xiàng)目集。,(b) 對(duì)初態(tài)項(xiàng)目集或其它已構(gòu)造的項(xiàng) 目集，應(yīng)用狀態(tài)轉(zhuǎn)移函數(shù)GO(I,X) 求出新的項(xiàng)目集（后繼狀態(tài)）。,LR（0）分析法,,(d) 轉(zhuǎn)移函數(shù)GO建立狀態(tài)之間的連 結(jié)關(guān)系。,對(duì)前例中的文法，構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA如下圖所示：,(c) 重復(fù)(b)直到不出現(xiàn)新的項(xiàng)目集 （新狀態(tài)）為止。,LR（0）分析法,,I0:,,,I1: SS,,,I2: SA,,,I4:,,,I5:

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

19、狀態(tài)為接受狀態(tài)。,LR（0）分析法,,構(gòu)成識(shí)別一個(gè)文法活前綴的DFA的狀態(tài)（項(xiàng)目集）的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。,(4) LR(0)分析表的構(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為L(zhǎng)R(0)文法。,LR（0）分析法,LR（0）分析法,,對(duì)LR(0)文法，構(gòu)造LR(0)分析表的算法如下：,輸入：識(shí)別LR(0)文法G規(guī)范句型活 前綴的DFA,輸出：文法G的LR(0)分析表,方法：用整數(shù) 0, 1, 2, ，n 分別表示 狀態(tài) I0, I1, I2 , In, 令包含項(xiàng)目

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

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

22、,I1: SS,S,,a,I3: S a,,,(,(,,a,,,I4: S (S),,),,I5: S (S),S,識(shí)別活前綴的DFA,LR（0）分析法,,因?yàn)樗?個(gè)LR(0)項(xiàng)目集中均不含有沖突項(xiàng)目，即不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目并存或多個(gè)歸約項(xiàng)目并存的情況。該文法是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)分析器的特點(diǎn)是不需要向前查看輸入符號(hào)就能歸約，即當(dāng)棧頂形成句柄，不管

23、不一個(gè)輸入符號(hào)是什么，都可以立即進(jìn)行歸約而不會(huì)發(fā)生錯(cuò)誤。,LR（0）分析法,識(shí)別活前綴的DFA,,識(shí)別文法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）分析法,這個(gè)條件比較苛刻，對(duì)于大多數(shù)程序設(shè)計(jì)語言來說，一般都不能滿足LR(0)文法的條件，即使是描述一個(gè)算述表達(dá)式的簡(jiǎn)單文法也不是LR(0)文法。,例 考慮算術(shù)表達(dá)式 的文法 ：,每一個(gè)LR(0)項(xiàng)目集中都不含有沖突的項(xiàng)目，,由于LR(0)文法要求文法的,EE+T | T,TT*F | F,F(E) | id,,SLR（1）分析法,將文法拓廣并對(duì)規(guī)則進(jìn)行編號(hào),直接構(gòu)造出識(shí)別文法規(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) ,),識(shí)別表達(dá)式文法活前綴的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中既含有移進(jìn)項(xiàng)目，又含有歸約項(xiàng)目，因而這個(gè)表達(dá)式的文法不是LR(0)文法。,根據(jù)構(gòu)造LR(0)分析表的方法，構(gòu)造出的LR(0)分析表中在2狀態(tài)和9狀態(tài)下面臨輸入符號(hào)*時(shí)含多重定義元素，見下表。,表達(dá)式文法的LR(0)分析表,,SLR（1）分析法,為了對(duì)語言句子進(jìn)行確定性的分析，需要解決,移進(jìn)歸約或歸約歸約沖突。,我們采用對(duì)含有沖突的項(xiàng)目集向前查看一個(gè)輸入符號(hào)的辦法來解決沖突，,這種分析法稱為簡(jiǎn)單的LR分析法，即SLR(1)分析法。

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

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

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

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

31、 ET, TT*F ,I9= EE+T, TT*F ,,SLR（1）分析法,SLR(1)分析表的構(gòu)造與LR(0)分析表的構(gòu)造基本相同。僅對(duì)LR(0)分析表構(gòu)造算法中的規(guī)則2進(jìn)行如下修改：,若歸約項(xiàng)目A屬于Ik，則對(duì)任何終結(jié)符 a FOLLOW(A) 置 ACTIONk, a=rj，其中A為文法的第j條規(guī)則。,,SLR（1）分析法,按上述方法對(duì)前例中的算術(shù)表達(dá)式文法構(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)造識(shí)別文法規(guī)范句型活前綴的DFA。,(2) 判斷該文法是否SLR(1)文法，若是， 構(gòu)造SLR(1)分析表，若不是，請(qǐng)說明 理由。,該文法的LR(0)項(xiàng)目集規(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)項(xiàng)目集及轉(zhuǎn)換函數(shù),,I9: A aSb,

33、S Sb,,,c,b,,SLR（1）分析法,分析所有這些項(xiàng)目集，可知在項(xiàng)目集I1，I5中存在移進(jìn)歸約沖突，I9中存在歸約歸約沖突，因此該文法不是LR(0)文法。,考慮含沖突的項(xiàng)目集能否用SLR(1)方法解決。,FOLLOW(A) =a,FOLLOW(S) =b,c,$,FOLLOW(S) =$,,SLR（1）分析法,由于有FOLLOW(S)b =$b=，I1中的移進(jìn)歸約沖突可以用SLR(1)方法解決。,由于有FOLLOW(A)b =ab=，I5中的移進(jìn)歸約沖突可以用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)項(xiàng)目集及轉(zhuǎn)換函數(shù),,I9: A aSb,S Sb,,,c,b,,SLR（1）分析法,SLR(1)分析法是一種簡(jiǎn)單而實(shí)用的方法,其造表演算法簡(jiǎn)單,狀態(tài)數(shù)目少,且大多數(shù)程序

35、設(shè)計(jì)語言都可以用SLR(1)文法來定義。,但是仍存在這樣一些文法，其項(xiàng)目集中的移進(jìn)一歸約沖突或歸約歸約沖突不能用SLR(1)方法解決。,,SLR（1）分析法,例2 下列拓廣文法G為,我們首先用SS作為初態(tài)集的項(xiàng)目，然后用閉包函數(shù)和轉(zhuǎn)換函數(shù)構(gòu)造識(shí)別文法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)項(xiàng)目集 I2中存在移進(jìn)和歸約沖突：,因此，I2中移進(jìn)和歸約沖突不能用SLR(1) 方法解決。,SL=R *R=R,S R,I2 =,,S L=R,R L,,由于 FOLLOW(R)==,$=,,SLR（

36、1）分析法,1. SLR(1)方法為什么不能解決 I2中 的移進(jìn)和歸約沖突?,2. 怎樣解決 I2中的移進(jìn)和歸約沖突?,問題:,,SLR（1）分析法,由于用SLR(1)方法解決動(dòng)作沖突時(shí)，它僅孤立地考察對(duì)于歸約項(xiàng)目A ，只要當(dāng)前面臨輸入符號(hào)aFollow(A)時(shí)，就確定使用規(guī)則A進(jìn)行歸約，而沒有考察符號(hào)串所在規(guī)范句型的環(huán)境 。,Ii : A,I0 I1 Ii,$ ,aaa,I0 I1 Ij,$A,aaa,,SLR（1）分析法,因?yàn)槿绻麠＠锏姆?hào)串為$ ，歸約后變?yōu)?A，當(dāng)前讀到的輸入符號(hào)是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)識(shí)別G活前綴的DFA,,SLR（1）分析法,不難看出當(dāng)狀態(tài)2呈現(xiàn)于棧頂且面臨的輸入符號(hào)是時(shí)，由于這個(gè)文法不含有以R為前綴的規(guī)范句型，因此用RL進(jìn)行的歸約是無效歸約。,,SLR（1）分析法, SL=R*R=R,也就是說，并不是FOLLOW(R)中的每個(gè)元素在含R的所有句型中在R的后面都會(huì)出現(xiàn)。解決這一問題的方法是采用LR(1)分

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

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

40、集，對(duì)其求閉包：,= 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)是一個(gè)LR(1)項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(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)項(xiàng)目集族及轉(zhuǎn)換函數(shù),,=,,,R,L,,R,,L,,,*,L,,,i,R,,i,,LR（1）分析法,分析所有這些項(xiàng)目集,可以發(fā)現(xiàn)每個(gè)項(xiàng)目集中都不含移進(jìn)歸約沖突,或歸約歸約沖突。,在項(xiàng)目集 I2中，由于歸約項(xiàng)目RL,$的

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

43、項(xiàng)目集的個(gè)數(shù)比LR(0)項(xiàng)目集的個(gè)數(shù)要多。,這是因?yàn)閷?duì)同一個(gè)LR(0)項(xiàng)目集，由于搜索符不同而對(duì)應(yīng)著多個(gè)LR(1)項(xiàng)目集。,,LR（1）分析法,例2中的文法是一個(gè)LR(1)文法，卻不是SLR(1)文法。然而，當(dāng)一個(gè)文法是LR(0)文法，則一定也是一個(gè)SLR(1)文法，也是LR(1)文法。反之則不一定成立。,如果一個(gè)文法的LR(1)分析表不含多重入口時(shí)，或者任何一個(gè)LR(1)項(xiàng)目集中沒有移進(jìn)一歸約沖突或歸約一歸約沖突， 則稱該文法為L(zhǎng)R(1)文法。,,LR（1）分析法,例3 考慮拓廣文法:,試構(gòu)造它的LR(1)項(xiàng)目集合的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項(xiàng)目集合的DFA,,LR（1）分析法,由該文法的10個(gè)LR(1)項(xiàng)目集中可以看出，均不存在移進(jìn)一歸約或歸約一歸約沖突，因此該文法為L(zhǎng)R(1)文法。,實(shí)際上，該文法是一個(gè)LR(0)文法，因此該文法也是SLR(1)文法，也是LR(1)文法。該文法相應(yīng)的LR(1)分析表如表所示。,,LR（1）分析法,LR（1）分析法,本

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

46、(1)項(xiàng)目集規(guī)范族中將所有同心的項(xiàng)目集合并為一，以減少項(xiàng)目集個(gè)數(shù)。,,LALR（1）分析法,所謂同心的LR(1)項(xiàng)目集是指在兩個(gè)LR(1)項(xiàng)目集中，除搜索符不同之外，核心部分是相同的。,例如，分析前例文法的LR(1)項(xiàng)目集族，可以發(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）分析法,我們看到合并同心集后的項(xiàng)目集其核心部分不變，僅搜索符合并。對(duì)合并同心集后

47、的項(xiàng)目集的轉(zhuǎn)換函數(shù)為GO(I,X)自身的合并，這是因?yàn)橄嗤男闹D(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)項(xiàng)目集中不存在動(dòng)作沖突, 合并同心集后若有沖突也只可能是歸約歸約沖突而不可能是移進(jìn)歸約沖突。,假定LR(1)文法的項(xiàng)目集Ik與Ij為同心集，其中,Ik= A, a1 Ba, b1

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

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

50、文法是LALR(1)文法。,,LALR（1）分析法,對(duì)一給定的文法G而言，其LALR(1)分析表比LR(1)分析表狀態(tài)數(shù)要少(例中LALR(1)的狀態(tài)數(shù)比LR(1)狀態(tài)數(shù)減少了4個(gè))，但在分析文法GS的某一個(gè)含有錯(cuò)誤的符號(hào)串時(shí)，LALR(1)分析速度比LR(1)分析速度要慢，這是因?yàn)楹喜⑼募蠖嘧霾槐匾臍w約，從而推遲發(fā)現(xiàn)錯(cuò)誤。,,對(duì)二義性文法的應(yīng)用,與其相應(yīng)的LR分析表一定含有多重定義的元素。但是對(duì)某些二義性文法，在含多重定義的LR分析表中加進(jìn)足夠的無二義性規(guī)則，從而可以構(gòu)造出比相應(yīng)非二義性文法更優(yōu)越的LR分析器。,任何一個(gè)二義性文法決不是LR類文法，,我們知道,,對(duì)二義性文法的應(yīng)用,EE

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

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

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

54、,(2)構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA。,(3)將DFA轉(zhuǎn)換成相應(yīng)的LR分析表。,注意文法一定要拓廣。,四種分析表的構(gòu)造基本相同，僅對(duì)含歸約項(xiàng)目的項(xiàng)目集構(gòu)造分析表元素不同。,3. 四種LR文法的判別方法,(1)任何的二義性文法都不是LR類文法。,本章小結(jié),, SLR(1)文法是LR(0)項(xiàng)目集中所有含沖突的項(xiàng)目集都能用SLR規(guī)則解決沖突。 (或SLR(1)分析表中不含多重定義),(2)根據(jù)項(xiàng)目集中是否含沖突項(xiàng)目或相應(yīng)分析表中是否含多重定義元素進(jìn)行判斷：, LR(0)文法是所有的LR(0)項(xiàng)目集中沒有移進(jìn)一歸約沖突或歸約一歸約沖突。(或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 移進(jìn),a FOLLOW(B1) 用B 1 1 歸約,a FOLLOW(B2) 用B2 2 歸約,本章小結(jié),, LR(1)項(xiàng)目集中無移進(jìn)一歸約沖突或歸約一歸約沖突。（或LR(1)分析表中不含多重定義）,LALR(1)項(xiàng)目集中無歸約一歸約沖突。(或LALR(1) 分析表中不含多重定義）,4.四種LR類文法之間的關(guān)系,注意搜索符只對(duì)歸約項(xiàng)目起作用。,本章小結(jié),,一個(gè)文法是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)造識(shí)別文法活前綴的DFA。,本章小結(jié),,(3) 該文法是SLR(1)的嗎？若是，構(gòu)造它 的SLR(1)分析表。,(2) 該文法是LR(0)文法嗎？請(qǐng)說明理由。,(4) 該文法是LR(1)或LALR(1)文法嗎？請(qǐng) 說明理由。,解：首先將文法拓廣，并對(duì)規(guī)則進(jìn)行編號(hào),0. S S,1. S AS,2. S b,3. A SA,4. A a,(1) 識(shí)別文法活前綴的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,識(shí)別文法GS活前綴DFA,(1) 識(shí)別文法活前綴的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,識(shí)別文法GS活前綴DFA,本章小結(jié),,(2) 由上圖不難看出，項(xiàng)目集I1, I5, I6 中存在著移進(jìn)歸約沖突，所以該文法不是LR(0)文法。,(3) 由于對(duì)該文法句子abab對(duì)應(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)文法，若不是，請(qǐng)說明理由；若是，請(qǐng)構(gòu)造SLR(1)分析表。,解：首先將文法拓廣，并給出每條規(guī)則編號(hào),0. SS,1. S (S),2. S ,本章小結(jié),,I0:,I3: S (S),,構(gòu)造該文法的LR(0)項(xiàng)目集族和轉(zhuǎn)換函數(shù)如下圖所示。,該文法不是LR(0)文法。因

59、為I0，I2中含有移進(jìn)歸約的沖突。,,I1: SS.,,I2:,,,I4: S (S),,S,,(,,S,(,),,見表,本章小結(jié),,但是I0，I2中的移進(jìn)歸約的沖突可以用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)文法。,解：首先將文法拓廣，并對(duì)規(guī)則進(jìn)行編號(hào),直接構(gòu)造LR(0)項(xiàng)目集如下：,

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é),,檢查每個(gè)項(xiàng)目集可知，項(xiàng)目集I0和I2中有移進(jìn)一歸約沖突，因此該文法不是LR(0)文法。,又因?yàn)?所以項(xiàng)目集I0和I2中移進(jìn)一歸約沖突可以用SLR(1)方法解決。因此該文法是SLR(1)文法，但不是LR(0)文法。,FOLLOW(S

61、)=b,d,$a= ,本章小結(jié),,例4 設(shè)有文法GS:,2.試判斷該文法是否SLR(1)文法, 若不是, 請(qǐng)說明理由；若是，請(qǐng)構(gòu)造出SLR(1)分析表, 并給出符號(hào)串(( ))$的分析過程。,1.構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA( LR(0)項(xiàng)目集族和GO函數(shù) )。,S S(S) |,本章小結(jié),,3. 試判斷該文法是否LR(1)文法，若不是，請(qǐng)說明理由；若是，請(qǐng)構(gòu)造LR(1)分析表。,4. 試判斷該文法是否LALR(1)文法，請(qǐng)說明理由。,本章小結(jié),,分析 首先將文法拓廣，并對(duì)規(guī)則編號(hào):,0. SS S S(S) S ,構(gòu)造LR(0)項(xiàng)目集規(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中的移進(jìn)歸約的沖突可以用SLR(1)方法解決：,FOLLOW(S)=$(=,所以該文法是SLR(1)文法。,本章小結(jié),FOLLOW(S) = $, (, ) ,符號(hào)串(( ))$的分析過程如下：,本章小結(jié),,0. SS S S(S) S ,構(gòu)造LR(1)項(xiàng)目集規(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)項(xiàng)目集中沒有移進(jìn)歸約的沖突,所以該文法為L(zhǎng)R(1)文法,,或該文法為SLR(1)文法, 任何SLR(1)文法都是LR(1)或LALR(1)文法,