編譯原理第4章 語(yǔ)法分析 自下而上 LR分析法.ppt

1、4.3 LR分析法,圖 1,語(yǔ)法分析概述,LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語(yǔ)法分析方法, L指自左向右掃描輸入串, R指最右推導(dǎo)(規(guī)范歸約)。 LR分析法比遞歸下降分析法、LL(1)分析法對(duì)文法的限制要少得多, 大多數(shù)無(wú)二義性CFG語(yǔ)言都可用LR分析器識(shí)別, 且速度快, 并能準(zhǔn)確、指出輸入串的語(yǔ)法錯(cuò)誤及出錯(cuò)位置。 LR分析法的主要缺點(diǎn): 手工構(gòu)造工作量相當(dāng)大, 必須求助自動(dòng)產(chǎn)生工具。,LR分析程序(器)：自左向右掃描，識(shí)別句柄，自下而上歸約的語(yǔ)法分析程序。 LR分析程序生成器：自動(dòng)生成LR分析程序的程序。,LR分析器（分析表）的分類： LR(0)表構(gòu)造法。這種方法的局限性較大、但它是建立

2、其它較一般的LR分析法的基礎(chǔ)。 簡(jiǎn)單LR（簡(jiǎn)稱SLR）表構(gòu)造法。雖然一些文法不能構(gòu)造SLR分析表，但是，它是一種比較容易實(shí)現(xiàn)又很有使用價(jià)值的方法。 規(guī)范LR表構(gòu)造法。這種分析表能力最強(qiáng)，能夠適用一大類文法，但實(shí)現(xiàn)代價(jià)高，或者說(shuō)，分析表的體積非常大。 向前LR表構(gòu)造法（簡(jiǎn)稱LALR）。這種分析表的能力介于SIR和規(guī)范LR之間，可以高效地實(shí)現(xiàn)。,LR分析器的工作原理 規(guī)范歸約(最右推導(dǎo)逆過(guò)程)的關(guān)鍵是尋找句柄。 LR分析法的基本思想: 在規(guī)范歸約過(guò)程中,一方面記住已移進(jìn)和歸約出的符號(hào)串,即記住“歷史”(棧); 另一方面根據(jù)所用產(chǎn)生式推測(cè)未來(lái)可能遇到的輸入符,即對(duì)未來(lái)進(jìn)行“展望” 。 當(dāng)一串貌似句柄

3、的符號(hào)串呈現(xiàn)于分析棧棧頂時(shí),希望能根據(jù)所記載的“歷史”、“展望”及“現(xiàn)實(shí)”材料來(lái)確定棧頂符號(hào)是否構(gòu)成句柄。,分析表 產(chǎn)生器,文法,分析表,LR分析程序結(jié)構(gòu),一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧）的確定有限狀態(tài)自動(dòng)機(jī)。 我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)”（自動(dòng)機(jī)）。 分析棧（先進(jìn)后出存儲(chǔ)器）用來(lái)存放狀態(tài)。棧里的每個(gè)狀態(tài)概括了從分析開(kāi)始直到某一歸約階段的全部“歷史”和“展望”資料。 任何時(shí)候，棧頂?shù)臓顟B(tài)都代表了整個(gè)的歷史和已推測(cè)出的展望。因此，在任何時(shí)候都可從棧頂狀態(tài)得知所想了解的文法的一切信息，而沒(méi)有必要從底而上翻閱整個(gè)棧。 LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)

4、行輸入符號(hào)所唯一決定的。,4.3.1 LR分析過(guò)程,LR分析的核心分析表,分析表由ACTION表和GOTO表兩部分組成。 ACTION(s，a)：表示當(dāng)狀態(tài)s面臨輸入a時(shí)的動(dòng)作 GOTO(s，x)：規(guī)定了狀態(tài)s面對(duì)文法符號(hào)X(非終結(jié)符）時(shí)的下一狀態(tài), 文法G (1)EE+T (2) ET (3) TT *F (4) TF (5) F(E) (6) Fi, 分析表（圖 ）, 分析表中記號(hào)的含義 sj： 把下一狀態(tài) j 和現(xiàn)行輸入符號(hào) a 移進(jìn)棧； rj： 按第 j 個(gè)產(chǎn)生式進(jìn)行歸約； acc： 接受； 空白格：出錯(cuò)標(biāo)志，報(bào)錯(cuò),給出下述文法G的LR分析表,幻燈片 11,ACTIONk, a的動(dòng)作:

5、 (1)移進(jìn): 設(shè)表中ACTIONk，a= Sj，當(dāng)S棧頂狀態(tài)為k，現(xiàn)行輸入符號(hào)為a，總控程序根據(jù)“k”和“a”查L(zhǎng)R(0)分析表，得： ACTIONk，a= Sj 此時(shí)，Sj 表示j狀態(tài)進(jìn)S棧，a進(jìn)T棧（文法符號(hào)棧）。,(2)歸約:設(shè)LR(0)分析表中的ACTIONmn，a= rj，其中rj表示使用文法的第j個(gè)產(chǎn)生式Ax1x2xp歸約；mn表示LR分析表的一個(gè)狀態(tài)。 假設(shè)總控程序按S棧頂狀態(tài)mn和現(xiàn)行輸入符號(hào)a查L(zhǎng)R分析表，得 ACTIONmn，a= rj 此時(shí)，S棧的狀態(tài)為： m1,mn-p+1,mn 文法符號(hào)T棧的符號(hào)為： x1x2xp 按ACTIONmn，a= rj 的要求：, S棧應(yīng)

6、刪除棧頂p個(gè)狀態(tài)： mn-p+1,mn 刪除后，S棧成為： m1,mn-p T棧中x1x2xp歸約成A，即T棧棧頂刪除p個(gè)文法符號(hào)，非終極符A進(jìn)T棧； 若GOTOmn-p，A=j，則狀態(tài)j進(jìn)S棧。,(3)接受: 宣布分析成功,分析器停止工作。 當(dāng)S棧頂狀態(tài)為k，現(xiàn)行輸入符號(hào)為a，總控程序根據(jù)“k”和“a”查L(zhǎng)R分析表得： ACTIONk，a=acc acc說(shuō)明語(yǔ)法分析成功。 (4)報(bào)錯(cuò): 報(bào)告發(fā)現(xiàn)源程序有錯(cuò),調(diào)用出錯(cuò)處 理程序。 總控程序若按“k”和“a”查表得： ACTIONk，a=空白 說(shuō)明語(yǔ)法分析出錯(cuò)，所給輸入串不是本文法的句子。,LR分析器總 控 程 序 的工作十分簡(jiǎn)單,它的任一步只需

7、按分析棧棧頂狀態(tài)s和現(xiàn)行輸入符a執(zhí)行ACTIONs,a所規(guī)定的動(dòng)作。 LR分析器的工作過(guò) 程 可看成是棧中狀態(tài)序列、已歸約串和輸入串構(gòu)成的三元式的變化過(guò)程。,2. 句型分析過(guò)程,設(shè)所給輸入串為#i*i+i#，則總控程序分析此輸入串的過(guò)程，如表4-11所示，通過(guò)分析，說(shuō)明i*i+i是文法例4.4的句子。,例 利用上述分析表，假定輸入串為 i * i + i ，描述LR分析器的工作過(guò)程。,狀 態(tài),符 號(hào),輸入串,（1） 0#i * i + i # （2） 05#i * i + i # （3） 03#F * i + i # （4） 02#T * i + i # （5） 027#T* i + i #

8、（6） 0275#T*i + i # （7） 02710#T*F + i # （8） 02#T + i # （9） 01#E + i #,ACTION 0, i =s5 移進(jìn) 5 和 i,ACTION 5, * =r6 按第6個(gè)產(chǎn)生式進(jìn)行歸約，即： (6) Fi,GOTO0,F=3 移進(jìn)狀態(tài)3,ACTION 10, + =r3 按第3個(gè)產(chǎn)生式進(jìn)行歸約，即 (3) TT *F,GOTO0,T=2 移進(jìn)狀態(tài)2,例 利用上述分析表，假定輸入串為 i * i + i ，描述LR分析器的工作過(guò)程。(續(xù)),狀 態(tài),符 號(hào),輸入串,（10） 016#E+ i # （11） 0165#E+i # （12） 0

9、163#E+F # （13） 0169#E+T # （14） 01#E #,ACTION1,#=acc 接受輸入串！,LR文法, LR（k）文法：一個(gè)文法，如果能用一個(gè)每步頂多向前檢查k個(gè)輸入符號(hào)的LR分析器進(jìn)行分析，則這個(gè)文法就稱為L(zhǎng)R(k)文法。,定義：對(duì)于一個(gè)文法，如果能夠構(gòu)造一張分析表，使得它的每個(gè)入口均是唯一確定的，則我們把這個(gè)文法稱為L(zhǎng)R文法。,存在不是LR的上下文無(wú)關(guān)文法 若一個(gè)文法的任何“移進(jìn)-歸約”分析器都存在下 述情況: 盡管棧的內(nèi)容和下一輸入符都已了解, 但仍無(wú)法確定是“移進(jìn)”還是“歸約”, 或無(wú)法從幾種可能的歸約中確定其一, 則該文法為非LR文法。 注意: (1) LR

10、文法肯定是無(wú)二義的, 一個(gè)二義文法不會(huì)是LR文法。 (2) LR分析技術(shù)可適當(dāng)修改以適于一定的二義文法。,LR分析法的主要任務(wù)：構(gòu)造一張LR分析表 首先討論一種只概括“歷史”資料而不包含推 測(cè)性“展望”材料的“狀態(tài)”。 希望僅由這種簡(jiǎn)單狀態(tài)就能識(shí)別呈現(xiàn)在棧頂 的某些句柄。 LR(0)項(xiàng)目集就是這樣一種簡(jiǎn)單狀態(tài)。,4.3.2、 LR(0)項(xiàng)目集規(guī)范族和LR(0)分析表,兩種LR(0)分析表的構(gòu)造算法： 方法一：先構(gòu)造識(shí)別文法的活前綴非確定有限 自動(dòng)機(jī)，然后確定化，再構(gòu)造LR(0)分析表； 方法二：是直接構(gòu)造LR(0)項(xiàng)目集規(guī)范族，再 構(gòu)造LR(0) 分析表。,方法一：LR(0)分析表的構(gòu)造步驟

11、確定G的LR(0)項(xiàng)目 以LR(0)項(xiàng)目為狀態(tài),構(gòu)造一個(gè)能識(shí)別文法G的所有活前綴的NFA 利用子集法,將NFA確定化,成為以項(xiàng)目集合為狀態(tài)的DFA根據(jù) 上述DFA可直接構(gòu)造出LR分析表,定義：文法G每一個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)，稱為 G的一個(gè)LR(0)項(xiàng)目。設(shè)文法G的某一產(chǎn)生式為Ax1x2xn，則Ax1xi.xi+1xn稱為文法G的LR(0)項(xiàng)目。 如：AXY對(duì)應(yīng)三個(gè)項(xiàng)目： AXY AXY AXY 而: A的項(xiàng)目 A,B、句型的活前綴及文法的LR(0)分析表,項(xiàng)目的意義：指明在分析過(guò)程的某時(shí)刻，我們看到產(chǎn)生式多大一部分 項(xiàng)目在計(jì)算機(jī)中的表示：（m，n） int m，n m：代表產(chǎn)生式編號(hào) n

12、：指出圓點(diǎn)的位置,如：abc前綴：，a，ab，abc 活前綴：規(guī)范句型的一個(gè)前綴，該前綴是不含句柄之后 的任何符號(hào)。,C、字的前綴：指該字的任意首部,例4.5 文法為： （1） SE （2） EaA （3） AcA （4） Ad 其句型 “acd”， d是句柄，活前綴為：；a；ac；acd 同理，在句型“acA”中，句柄是“cA”活前綴為： ；a；ac；acA,稱為活前綴原因：在右邊增添一些終結(jié)符號(hào)就可以使它成為一個(gè)規(guī)范句型。 在LR分析工作過(guò)程中的任何時(shí)候，棧里的文法符號(hào)（自棧底而上）X1X2.Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型（如果整個(gè)輸入串確實(shí)構(gòu)成一個(gè)句子）。

13、 因此，只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過(guò)的部分沒(méi)有錯(cuò)誤。,D、對(duì)文法G，構(gòu)造能識(shí)別G的所有活前綴的NFA,識(shí)別文法句型活前綴的非確定有限自動(dòng)機(jī)(NFA M)包括：狀態(tài)、狀態(tài)轉(zhuǎn)換、初態(tài)、終態(tài) NFA的狀態(tài)：是一個(gè)LR(0)項(xiàng)目,一個(gè)項(xiàng)目指明了在分析過(guò)程的某時(shí)刻看到產(chǎn)生式多大一部分 構(gòu)造方法： a.文法開(kāi)始符號(hào)的形如SS的項(xiàng)目為NFA的唯一初態(tài)；文法的所有LR(0)項(xiàng)目構(gòu)成的狀態(tài)都是識(shí)別文法的規(guī)范句型的活前綴的終態(tài)?；钋熬Y識(shí)別態(tài),b.若狀態(tài)i和j出自同一個(gè)產(chǎn)生式，而且j的圓點(diǎn)只落后于i的圓點(diǎn)一個(gè)位置，就從i畫一條標(biāo)志為Xi的弧到j(luò)。 （即，i：XX1Xi-1XiXn

14、 j：XX1 Xi-1XiXn） c.若狀態(tài)i的圓點(diǎn)之后的符號(hào)為非終結(jié)符，如i為 XA，其中A屬于VN，就從狀態(tài)i畫弧到所有A狀態(tài)。,例.構(gòu)造以下文法的NFA,文法G的所有LR(0)項(xiàng)目,文法 G S E E aA|bB A cA|d B cB|d,1.S E 2. S E 3. E aA 4. E a A 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d 11. E bB 12. E b B 13. E bB 14. B cB 15. B c B 16. B cB 17. B d 18. B d ,利用上述規(guī)則a，b，c構(gòu)造NFA，如圖所示：,E

15、,E、使用子集方法，將NFA確定化，使之成為一個(gè) 以項(xiàng)目集合為狀態(tài)的DFA。 （1） SE（2） EaA （3） AcA （4） Ad,可將文法的LR(0)項(xiàng)目分成如下四類： A 歸約項(xiàng)目 S 接收項(xiàng)目，其中，S是開(kāi)始符號(hào) Aa 移進(jìn)項(xiàng)目，其中，aVT AB 待歸約項(xiàng)目，其中，BVN 識(shí)別例4.5的文法的句型“acd”的過(guò)程,先構(gòu)造識(shí)別句型的活前綴NFA M，然后確定化太繁瑣，下面給出一種直接構(gòu)造DFA M的方法,3. LR(0)項(xiàng)目集規(guī)范族（方法二） 相關(guān)定義： 定義 4.12 若I是一個(gè)LR(0)項(xiàng)目集，則項(xiàng)目集 Closure(I)的定義如下： （a）Closure(I)=I； （b）若

16、項(xiàng)目ABClosure(I)，BVN，則Closure(I)= Closure(I)B； （c）重復(fù)(b)，直至Closure(I)不再擴(kuò)大為止。,定義 4.13 設(shè)I為L(zhǎng)R(0)項(xiàng)目集，X是一文法符號(hào)，LR(0)狀態(tài)轉(zhuǎn)換函數(shù)GO(I，X)的定義如下： GO(I，X)=Closure(J) 其中： J=任何形如AX的項(xiàng)目|AXI,文法（1） SE （2） EaA （3） AcA （4） Ad 若S EI，則Closure(I)= S E，E aA， 令I(lǐng)0= SE，EaA，則 GO(I0，E)= SE=I1 GO(I0，a)= EaA，AcA，Ad=I2 從項(xiàng)目集I0開(kāi)始，將I0定義成一個(gè)狀態(tài)

17、，按照狀態(tài)轉(zhuǎn)換函數(shù)GO(I，X)的定義可以找出所有的項(xiàng)目集（狀態(tài)），由GO(I，X)所產(chǎn)生的項(xiàng)目集（狀態(tài)）全體稱為L(zhǎng)R(0)項(xiàng)目集規(guī)范族。,構(gòu)造一個(gè)G，它包含了整個(gè)G，但它引進(jìn)了一個(gè)不出現(xiàn)在G中的非終結(jié)符S，并加進(jìn)一個(gè)新產(chǎn)生式SS，而這個(gè)S是G的開(kāi)始符號(hào)。稱G是G的拓廣文法。 把文法G進(jìn)行拓廣為了使“接受”狀態(tài)易于識(shí)別，有一個(gè)僅含項(xiàng)目SS的狀態(tài)，這就是唯一的“接受”態(tài)。,拓廣文法,步驟一:令NFA的初態(tài)為I,求其CLOSURE(I),得到初態(tài)項(xiàng)目集。即: 求CLOSURE（SS) 步驟二:對(duì)所得項(xiàng)目集I和文法G的每個(gè)文法符號(hào)X(包括VT和VN) 計(jì)算GO（I，X） =CLOSURE（J），得到

18、新的項(xiàng)目集。 其中J=任何形如A X 的項(xiàng)目| A X 屬于I 步驟三:重復(fù)步驟二，直至沒(méi)有新的項(xiàng)目集出現(xiàn)。 經(jīng)過(guò)以上步驟構(gòu)造出的項(xiàng)目集的全體即為L(zhǎng)R(0)項(xiàng)目集規(guī)范族。,利用LR(0)項(xiàng)目集規(guī)范族和GO函數(shù)畫出DFA,構(gòu)造項(xiàng)目集規(guī)范族方法,構(gòu)造LR(0)項(xiàng)目集規(guī)范族的,例如，文法G為： SaBCBbCc 拓廣文法G為： （1）SS （2）SaBC （3）Bb （4）Cc 句子“abc”的規(guī)范歸約過(guò)程如下： abc，aBc，aBC，S，S 運(yùn)用圖識(shí)別輸入串“abc”的過(guò)程,有效項(xiàng)目（課本P86類似）,項(xiàng)目A 1.2對(duì)活前綴1是有效的，存在規(guī)范推導(dǎo),在任何時(shí)候，分析棧中的活前綴 X1X2 Xm的

19、有效項(xiàng)目集正是狀態(tài)棧頂Sm所代表的那個(gè)集合。也正是從識(shí)別活前綴的DFA的初態(tài)出發(fā)，讀出X1X2 Xm后到達(dá)的那個(gè)項(xiàng)目集(狀態(tài))。(LR分析的基本定理，陳火旺P108),*,文法G(S) SE EaA|bB AcA|d BcB|d 考慮： 項(xiàng)目：B c.BB . cB B . d 活前綴：bc S E bB bc.B (項(xiàng)目B c.B) S E bB bcB bccB (項(xiàng)目B . cB) S E bB bcB bcd (項(xiàng)目B . d),項(xiàng)目A 1.2對(duì)活前綴1 是有效的，其條件是 存在規(guī)范推導(dǎo):, 相關(guān)定義： LR(0)文法：不存在以下兩種沖突的文法 移進(jìn)歸約沖突 歸約歸約沖突 LR(0)表

20、：由LR(0)文法得到的分析表 LR(0)分析器：使用LR(0)表的分析器,LR（0）分析表的構(gòu)造,給定文法G，設(shè)文法G拓廣為文法G，假若文法G的項(xiàng)目集規(guī)范族（識(shí)別句型的活前綴確定有限自動(dòng)機(jī)）已經(jīng)給出; 其狀態(tài)（項(xiàng)目集）為I0，I1In，則分析表的構(gòu)造算法如下（算法中，Ii狀態(tài)用右下角標(biāo)i表示，Sj、rk的意義同前）：,分析表的構(gòu)造方法 如下： （1）設(shè)GO(Ii，X)=Ij，若XVT，則置Action(i，X)=Sj，表示將狀態(tài)j和終結(jié)符X移進(jìn)棧；若XVN，則置GOTO(i，X)=j，表示將狀態(tài)轉(zhuǎn)換為j進(jìn)棧。 （2）設(shè)項(xiàng)目AIi，若A不是文法的開(kāi)始符號(hào)，則置Action(i，a)=rk，rk

21、表示用文法的第k個(gè)產(chǎn)生式進(jìn)行歸約，“a”表示集合VT#的所有符號(hào)，若A是文法的開(kāi)始符號(hào)，則置Action(i，#)=“acc”，符號(hào)“#”表示句子右界符。 （3）分析表中的空白表示出錯(cuò)。,（1）SS （2）SaBC （3）Bb （4）Cc,練習(xí)：假定文法的各個(gè)產(chǎn)生式的編號(hào)如下，構(gòu)造其LR(0)項(xiàng)目集規(guī)范族 和LR(0)分析表： 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,DFA構(gòu)造：（部分）,CLOSURE ( S-E ) = S-E, E-aA, E-bB 此即為DFA的狀態(tài)0,令I(lǐng) = S-E, E-aA, E-bB GO( I, a ) =

22、 CLOSURE( E-aA ) /即I中所有圓點(diǎn)之后緊跟a的 = E-aA, A-cA, A-d GO( I, b ) = CLOSURE( E-bB ) = E-bB, B-cB, B-d GO( I, E ) = CLOSURE( S-E ) = S-E ,同上步驟，依次對(duì)各項(xiàng)目集進(jìn)行計(jì)算（略） LR(0)分析表構(gòu)造,（DFA部分圖，全圖見(jiàn)下頁(yè)）,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,E,a,b,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,E,該文法的LR(0)分析表

23、？,該文法的LR(0)分析表如下所示：,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,試對(duì)acccd進(jìn)行分析？,例: 按上表對(duì)acccd進(jìn)行分析 步驟 狀態(tài)棧 符號(hào)棧輸入串 10#acccd# 202#acccd# 3024#acccd# 40244#acccd# 502444#acccd# 60244410#acccd# 7024448#acccA# 802448#accA# 90248#acA# 10026#aA# 1101#E#,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,L

24、R(0)分析法的局限性-語(yǔ)法動(dòng)作沖突,LR(0)分析法的關(guān)鍵: 由項(xiàng)目集規(guī)范族構(gòu)造LR(0)分析表 任給一狀態(tài)（項(xiàng)目集）和任一符號(hào)“a”（aVT#），使得Action(i，a)的值是唯一的（無(wú)沖突）。 若Action(i，a)值不唯一，我們稱為語(yǔ)法動(dòng)作沖突。 分情況討論：,（1）無(wú)沖突：若一個(gè)項(xiàng)目集Ii中僅含移進(jìn)項(xiàng)目或僅含一個(gè)規(guī)約項(xiàng)目，則Action(i，a)的值是唯一的，其中，aVT。,（2）移進(jìn)歸約沖突：若一個(gè)項(xiàng)目集Ii中，既含有移進(jìn)項(xiàng)目，又含有歸約項(xiàng)目，此時(shí)，Action(i，a)值不唯一，其中，aVT，i表示狀態(tài)Ii。,（3）歸約歸約沖突：若一個(gè)項(xiàng)目集Ii中，存在兩個(gè)或兩個(gè)以上的歸約項(xiàng)

25、目，則Action(i，a)的值不唯一 上述（2）、（3）兩種情況中的動(dòng)作沖突，有一部分可以使用FOLLOW集 解決 ,即SLR(1)分析法。,例4.6 設(shè)文法為： （0）SS （1）SabdD （2）SaBc （3）Bb （4）Dd LR(0)項(xiàng)目集規(guī)范族 應(yīng)按如下規(guī)則填寫，cFOLLOW(B) ： Action(3，c)=r3 Action(3, d)=S4， d不屬于FOLLOW(B) 所以： Action(3,d)r3,4.3.3、SLR（1）表的構(gòu)造方法,SLR是LR(0)的一種改進(jìn)，它在歸約時(shí)除了考慮歷史情況之外還考慮了現(xiàn)實(shí)輸入。,（0）SS （1）SabdD （2）SaBc （3

26、）Bb （4）Dd,對(duì)于I3 SLR(1)填寫規(guī)則： cFOLLOW(B) ： Action(3，c)=r3 Action(3, d)=S4，,為什么當(dāng)xFOLLOW(B)時(shí)，SLR(1)分析表填A(yù)ction(3，x)=r3,而Action(3，d)=s4呢 ？ 因?yàn)?SaBdD不成立，而S SabdD成立，也就是說(shuō)，“aBdD”不是句型，B后面只能出現(xiàn)“x”，不能出現(xiàn)“d”，,（0）SS （1）SabdD （2）SaBc （3）Bb （4）Dd,歸約歸約沖突 例 若I=Xb， A， B 若當(dāng)前輸入符號(hào)為b，則含有移進(jìn)歸約沖突； 而A和B，又含有歸約歸約沖突。,則當(dāng) I 面臨任何輸入符號(hào)a時(shí)，

27、可做出如下 “移進(jìn)歸約 ” 決策： 若a=b，移進(jìn)； 若a屬于FOLLOW（A），則用A歸約； 若a屬于FOLLOW（B），則用B歸約； 此外，報(bào)錯(cuò)。,I=Xb， A， B,2、SLR（1）表的構(gòu)造方法 若項(xiàng)目Aa屬于Ik且GO(Ik,a) Ij，a為終結(jié)符，且置 ACTIONk，a為“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡(jiǎn)記為“sj”； 若項(xiàng)目A屬于Ik，那么，對(duì)任何輸入符號(hào)a， aFOLLOW(A)，置ACTIONk，a為“用產(chǎn)生式A進(jìn) 行歸約”，簡(jiǎn)記為“rj”；其中，假定A為文法G的第j個(gè) 產(chǎn)生式； 若項(xiàng)目SS屬于Ik，則置ACTIONk，為“接受”，簡(jiǎn) 為“acc”； 若GO(Ik，A)=Ij，

28、A為非終結(jié)符，則置GOTOk，A= j； 分析表中凡不能使用規(guī)則1至4填入信息的空白格均置上“出 錯(cuò)標(biāo)志”。,只在歸約時(shí) 展望,即已到產(chǎn)生式末尾,則去判斷FOLLOW(A),SLR(1)分析表 項(xiàng)目集,（0）SS （1）SabdD （2）SaBc （3）Bb （4）Dd,文法 G：(0) SE (1) EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,練習(xí)：對(duì)如下文法構(gòu)造其SLR（1）分析表。, FOLLOW集如下：FOLLOW(S)= # FOLLOW(E）= +，），# FOLLOW(T)= +, * , ) , # FOLLOW(F)= +, * ,

29、 ) , # ,該文法的LR(0)項(xiàng)目集規(guī)范族 由這些項(xiàng)目集的轉(zhuǎn)換函數(shù)GO表示成的DFA 文法G的非終結(jié)符的FOLLOW集如下： FOLLOW(S)= # FOLLOW(E）= +，），# FOLLOW(T)= +, * , ) , # FOLLOW(F)= +, * , ) , # SLR分析表,I0：S E E E+T E T T T*F T F F (E) F i,I2：E T T T*F,I1：S E E E+T,I4：F(E) E E+T E T T T*F T F F (E) F i,I7：T T*F F (E) F i,I10：T T*F ,I6： E E+T T T*F T F

30、 F (E) F i,I8：F (E) E E+T,I11：F (E),I9：E E+T TT * F,I5：F i,I3：T F,T,E,(,i,i,F,F,*,+,(,(,E,T,I2,),T,F,i,I3,I5,F,(,*,I4,i,I5,FOLLOW(S)= # FOLLOW(E）= +，），# FOLLOW(T)= +, * , ) , # FOLLOW(F)= +, * , ) , # ,文法 G 的SLR分析表如下所示：,FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +, * , ) , # FOLLOW(F)= +, * , ) , # ,任

31、一文法，可按上述算法構(gòu)造一張表，若表無(wú)多重定義入口，則此表稱為SLR(1)分析表。具有SLR(1)分析表的文法，稱為SLR(1)文法。 具有SLR(1)分析表的分析器（SLR(1)分析表+總控程序）稱為SLR(1)分析器；,1. 非SLR(1)文法舉例 例4.7 文法： （0）SS （1）SaCaCb （2）SaDb （3）Ca （4）Da,4.3.4、LR（1）分析表的構(gòu)造,I3有歸約沖突，用C、D的后繼符號(hào)： FOLLOW(C)=a，b FOLLOW(D)=b 解決不了沖突，因?yàn)椋篎OLLOW(C)FOLLOW(D)=b 完整 LR(0)項(xiàng)目集規(guī)范族見(jiàn)課本,（0）SS （1）SaCaCb

32、（2）SaDb （3）Ca （4）Da,問(wèn)題：有些無(wú)二義文法會(huì)產(chǎn)生“移進(jìn)/歸約”沖突 或“歸約/歸約”沖突 產(chǎn)生原因：SLR(1)分析法未包含足夠多的“展望”信息 解決辦法：讓每個(gè)狀態(tài)含有更多的“展望”信息 方法：重新定義項(xiàng)目，使得每個(gè)項(xiàng)目都附帶有k個(gè)終結(jié)符；即每個(gè)項(xiàng)目的形式為： A- , a1a2ak,LR（1）分析表的構(gòu)造,LR(0)項(xiàng)目A加上k個(gè)搜索符a1a2ak，就構(gòu)成一個(gè)LR(k)項(xiàng)目： A，a1a2ak 其中，aiVT（i=1，2，k），此項(xiàng)目要求存在規(guī)范推導(dǎo) SA a1a2aka1a2ak 這里僅考慮LR(1)項(xiàng)目A，a，LR(0)項(xiàng)目與LR(1)項(xiàng)目之間的區(qū)別是后者多了一個(gè)搜索

33、符。,2. LR(k)項(xiàng)目與LR(1)有效項(xiàng)目,向前搜索符a僅對(duì)歸約項(xiàng)目A-, a有意義； 歸約項(xiàng)目A-, a意味著：當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的輸入符號(hào)為a時(shí)，才可以把棧頂上的歸約為A 只研究k1的情形,說(shuō)明：,定義4.15 我們稱一個(gè)LR(1)項(xiàng)目A，a對(duì)活前綴是有效的，如果存在規(guī)范推導(dǎo) SAWW 其中，=，aFIRST(W)， 若W=，則a=“#”。,SAWW 其中，=，aFIRST(W) 例4.8 （0）SS （1）SBB （2）BaB （3）Bb LR(1)項(xiàng)目BaB，a對(duì)活前綴=aaa是有效的， 這里，=aa，=a，=B。 對(duì)于活前綴=aaa，下面給出規(guī)范推導(dǎo)證明：SSBBBa

34、baBabaaBabaaaBab 即：SaaBabaaaBab “aaaBab”中，“aaa”是規(guī)范句型的前綴，而且不含句柄（aB）之后的符號(hào)，所以是活前綴。,3. LR(1)項(xiàng)目集規(guī)范族的構(gòu)造算法,算法與構(gòu)造LR(0)項(xiàng)目集規(guī)范族類似。 對(duì)任意LR(1)項(xiàng)目集I,需定義 Closure(I)和GO(I，X)，其中，X(VNVT) 定義4.16 (a)若I是一個(gè)LR(1)項(xiàng)目集，則置Closure(I):=I； (b)若項(xiàng)目AB，aClosure(I)，且B是一產(chǎn)生式，則對(duì)于bFIRST(a)的每個(gè)符號(hào)，做： Closure(I) :=Closure(I)B，b (c)重復(fù)(b),直至Clos

35、ure(I)不再擴(kuò)大為止。 （對(duì)于A有：SAWBW，同理對(duì)于B也符合定義）,例如，文法 SAB Aa Bb 假設(shè)I= SAB，#，則Closure(I)= SAB，#，Aa，b ,定義4.17: 令I(lǐng)是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(shù)GO (I，X)定義為： GO(I，X)CLOSURE(J) 其中 J形如AX, a的項(xiàng)目 | AX, a I 注意 ：搜索符號(hào)a不改變。 例如項(xiàng)目集I0= SAB，#，Aa，b，則 GO(I0，A)= SAB，#，Bb，#,LR(1)項(xiàng)目集規(guī)范族算法 設(shè)所給文法G,定義拓廣文法G S ： void intemsetsb(G) C=closureSS，# ; d

36、o for(C中的每個(gè)項(xiàng)目集I和G中的每個(gè)文法 符號(hào)X） if (GO(I, X)非空且不屬于G) 將GO(I, X)加入G; while(!(G不擴(kuò)大為止) ,例4.7（0）SS（1）SaCaCb （2）SaDb（3）Ca（4）Da,練習(xí)： 例4.8 （0）SS （1）SBB （2）BaB（3）Bb 構(gòu)造 LR(1)項(xiàng)目集規(guī)范族,（0）SS （1）SBB （2）BaB （3）Bb,4、構(gòu)造LR（1）分析表的步驟：,確定LR(1)項(xiàng)目； 利用函數(shù)CLOSURE和GO求DFA （即：構(gòu)造 LR(1)項(xiàng)目集規(guī)范族）; 根據(jù)DFA，構(gòu)造LR (1)分析表。,根據(jù)DFA,構(gòu)造LR(1)分析表,設(shè)文法G

37、的LR(1)項(xiàng)目集為：I0，I1，In 。在分析表 中，用狀態(tài)i表示第i個(gè)項(xiàng)目集Ii，分析表的構(gòu)造算法如下： （1）若LR(1)項(xiàng)目AX，aIi，且 GO(Ii，X)=Ij，則當(dāng)XVT時(shí)，置ACTION(i，X)=Sj； 當(dāng)XVN時(shí)，置GOTO(Ii，X)=j。 （2）若A，aIi，且A是文法的第k個(gè)產(chǎn)生 式，則當(dāng)AVn-S時(shí)，置ACTION(i，a)=rk，rk 表示使用 第k個(gè)產(chǎn)生式的歸約； 當(dāng)A=Sa=“#”時(shí)，置ACTION(i，#)=“acc”。 （3）空白表示出錯(cuò)。,例4.8拓廣文法的規(guī)范LR分析表,(0)S-S(2) B-aB (1) S-BB(3) B-b,LR(1)分析法小結(jié)

38、,LR(1) 分析表的構(gòu)造,狀態(tài)集的計(jì)算方法和 LR(0) 基本相同,分析表的構(gòu)造方法和 LR(0) 基本相同,構(gòu)造方法的不同點(diǎn)：歸約動(dòng)作的選擇,SLR(1) 分析參考 FOLLOW 集歸約,LR(1) 分析僅考慮 LR(1)項(xiàng)目中的后繼符,LR(1)方法的優(yōu)缺點(diǎn)： 解決了SLR(1)分析所難以解決的“移進(jìn)-歸約”或“歸約-歸約”沖突。 LR(1)分析表狀態(tài)多，規(guī)模大。 算法適用范圍廣。,4.3.5 LALR(1)方法,LALR(lookahead-LR)技術(shù)。這種方法在實(shí)際中是經(jīng)常使用的。 LALR(1)和SLR( LR(0) )的分析表有同樣多的狀態(tài)，而規(guī)范LR分析表要大得多。 LALR(

39、1)的能力介于SLR(1)和規(guī)范LR(1)之間。,LALR(1)分析表的構(gòu)造,問(wèn)題：對(duì)于一般的語(yǔ)言，規(guī)范LR分析表要用幾千個(gè)狀態(tài)，實(shí)際應(yīng)用很困難 分析：由例4.8中可以看到，有些狀態(tài)集除了搜索符不同外是兩兩相同的 解決辦法：合并同心集，構(gòu)造LALR(1)分析表,我們稱兩個(gè)LR(1)項(xiàng)目集具有相同的心，如果除去搜索符之后，這兩個(gè)集合是相同的(LR(0)項(xiàng)目相同)。,將所有同心的LR(1)項(xiàng)目集合并后，得到一個(gè)心就是一個(gè)LR(0)項(xiàng)目集。,說(shuō)明：,I3: B a B, a/b B aB, a/b B b, a/b,I6: B a B, # B aB, # B b, #,I36: B a B, a/

40、b/# B aB, a/b/# B b, a/b/#,合并為,合并項(xiàng)目集時(shí)要修改轉(zhuǎn)換函數(shù)，即GO(I,X)；動(dòng)作ACTION應(yīng)進(jìn)行修改，使得能夠反映各被合并的集合的既定動(dòng)作。,LR(1)項(xiàng)目集導(dǎo)入同心集I i0，Ii1，Iik的弧， 現(xiàn)導(dǎo)入合并后的項(xiàng)目集JP，弧上標(biāo)記不變； 由同心集I i0，Ii1，Iik導(dǎo)出的弧，改由JP 導(dǎo)出，弧上標(biāo)記不變。,根據(jù)圖413 I3和I6 ， I4和I7 ， I8和I9分別為同心集,I3: B a B, a/b B aB, a/b B b, a/b,I6: B a B, # B aB, # B b, #,I4: B b , a/b,I7: B b , #,I8

41、: B a B , a/b,I9: B a B , #,I36: B a B, a/b/# B aB, a/b/# B b, a/b/#,I47: B b , a/b/#,I89: B a B , a/b/#,合并為,合并為,合并為,合并同心集不會(huì)產(chǎn)生新的移進(jìn)-歸約沖突，但有可能產(chǎn)生新的“歸約-歸約”沖突。, 若同心集合并前，任一同心集無(wú)移進(jìn)、歸約沖突，則合并后，不可能引起歸約、移進(jìn)沖突。 若 a1，amX1，Xn 則 有語(yǔ)法分析動(dòng)作沖突 ；反之無(wú)沖突。, 合并同心集，可能引起歸約與歸約沖突。 例：下面文法是LR(1)的，但不是LALR(1)的。 S S S aAd bBd aBe bAe A

42、 c B c,S S，# S aAd, # S bBd, # S aBe, # S bAe, #,S S ，#,S a Ad, # S a Be, # A c, d B c, e,a,S,S b Bd, # S b Ae, # A c, e B c, d,b,A,S a A d, #,B,S a B e, #,c,A c , d B c , e,A c , e B c , d,c,引起歸約與歸約沖突。,I3和I5合并得：,對(duì)于同一個(gè)文法，LALR分析表和SLR分析表具有相同數(shù)目的狀態(tài)，卻能處理一些SLR所不能分析的文法。 思考：文法： S-L=R (2) S-R ( 3) L-*R (4) L

43、-i (5) R-L (0)S-S 判斷該文法是否是LR(0)、SLR(1)、LR(1)、LALR(1)文法？,文法： S-L=R (2) S-R ( 3) L-*R (4) L-i (5) R-L (0)S-S,S-L=R R-L,LR(0)項(xiàng)目,S-L=R, # R-L , #,LALR(1)項(xiàng)目,A、構(gòu)造LALR分析表的第一個(gè)算法,步驟： 構(gòu)造文法G的LR(1)項(xiàng)目集族C=I0,I1,In 把所有的同心集合并在一起，記C=J0,J1,Jm為合并后的新族。那個(gè)含有項(xiàng)目S-S,#的Jk為分析表的初態(tài) 從C構(gòu)造ACTION表 構(gòu)造GOTO表 分析表空白格均填上“出錯(cuò)標(biāo)志”,a、若項(xiàng)目Aa,b屬

44、于Jk且GO(Jk,a) Jj，a為終結(jié)符，則置ACTIONk，a為 “sj”； b、若項(xiàng)目A,a屬于Jk，則置ACTIONk，a為“用產(chǎn)生式A歸約”，簡(jiǎn)記為“rj”；其中，假定A為文法G的第j個(gè)產(chǎn)生式； c、若項(xiàng)目SS,#屬于Jk，則置ACTIONk，為“接受”，簡(jiǎn)記為“acc”；,從C構(gòu)造ACTION表,根據(jù)圖413 I3和I6 ， I4和I7 ， I8和I9分別為同心集,I3: B a B, a/b B aB, a/b B b, a/b,I6: B a B, # B aB, # B b, #,I4: B b , a/b,I7: B b , #,I8: B a B , a/b,I9: B

45、a B , #,I36: B a B, a/b/# B aB, a/b/# B b, a/b/#,I47: B b , a/b/#,I89: B a B , a/b/#,合并為,合并為,合并為,由合并后的集族所構(gòu)成的LALR分析表,結(jié)論： LALR(1)分析法比LR(1)分析法對(duì)某些錯(cuò)誤發(fā)現(xiàn)的時(shí)間推遲-合并同心集后多做了規(guī)約.,一個(gè)文法是LALR(1)文法，也是LR(1)文法，但不一定是SLR(1)，LR(0)文法。,一個(gè)文法是LR(1)文法，不一定是LALR(1)文法。,LR(1)分析方法和LL(1)分析方法的比較,LR分析方法和LL(1)分析方法的比較,LR(1)分析方法和LL(1)分析方

46、法的比較,4.3.6 二義文法的應(yīng)用,任何二義文法不是一個(gè)LR文法,因而也不是SLR(1)或LALR(1)文法。 但二義文法的問(wèn)題是因其沒(méi)有定義算符優(yōu)先級(jí)和結(jié)合規(guī)則而產(chǎn)生了二義性。 因此,下面討論使用LR分析法的基本思想,憑借一些其它條件分析二義文法 。,二義文法G1：E E + E | E * E | (E) | i 非二義的文法G2： E E + T | T T T * F | F F (E) | i 對(duì)比可以發(fā)現(xiàn)G1有兩個(gè)優(yōu)點(diǎn)： 1)、若需要改變算符的優(yōu)先級(jí)或結(jié)合規(guī)則，不需要改變文法G1本身； 2)、文法G1的分析表所包含的狀態(tài)肯定比G2的狀態(tài)要少得多。因?yàn)?，在文法G2中含有單個(gè)非終結(jié)符的產(chǎn)生式，這些產(chǎn)生式是用來(lái)定義算符的優(yōu)先級(jí)和結(jié)合規(guī)則的，它們要占用不少狀態(tài)和消耗不少時(shí)間