語法分析-自下而上分析.ppt

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

1、第五章 語法分析-自下而上分析,5.1 自下而上分析的基本問題,Figure5.5LR演示自下而上分析 i+(i+i)*i 原理:自左向右掃描，自下而上分析 從輸入符號串入手，通過反復查找當前句型的可歸約串，并使用文法的產(chǎn)生式把它歸約成相應的非終結(jié)符來一步步地進行分析的。 最終把輸入串歸約成文法的開始符號，表明分析成功。,任何自下而上分析方法的關(guān)鍵就是要找出當前句型的可歸約串，然后根據(jù)產(chǎn)生式判別將它歸約成什么樣的非終結(jié)符。,規(guī)范歸約基本概念,如果A= ，則稱是句型 相對于非終結(jié)符A的直接短語。,G為文法，S為開始符號，假定是G的一個句型，如果 則稱是句型 相對于非終結(jié)符A的短語。,,表達式文

2、法的例子 i+i*i,找出所有短語，直接短語和句柄,最左直接短語稱為句柄。,從句子到開始符號的歸約序列，如果每一步都是把句柄替換為 相應產(chǎn)生式的左部符號而得到的，則稱為規(guī)范歸約。規(guī)范歸約 是最右推導（規(guī)范推導）的逆過程。,例：考慮文法G(E)：EE +T |T TT*F | F Fi| (E)并假定輸入串為（i+i)*i，考察自下而上的分析過程。,分析過程圖表：,步驟 分析棧 輸入串 動作 # (i+i)*i# 移進 #( i+i)*i# 移進 #(i +i)*i# 歸約 #(F +i)*i# 歸約 #(T +i)*i# 歸約 #(E +i)*i

3、# 移進 #(E+ i)*i# 移進 #(E+i )*i# 歸約 #(E+F )*i# 歸約,步驟 分析棧 輸入串 動作 10 #(E+T )*i# 歸約 11 #(E )*i# 移進 12 #(E) *i# 歸約 13 #F *i# 歸約 14 #T *i# 移進 15 #T* i# 移進 16 #T*i # 歸約 17 #T*F # 歸約 18 #T # 歸約 19 #E # 接受,棧上的候選式不一定是句柄。例如，在第14步對棧頂為T，它是E的一候選式，但它不是句柄，不能歸約成E。判定候選式是極為簡單的事情，但判定句柄就不那么容易。而不同的自

4、底向上方法給出不同的判定方法。,自下而上方法包括四個動作：,移進：把輸入流的頭符讀到分析棧中。,歸約：把分析棧頂?shù)木浔鷼w約為一非終極符。,接受：分析成功。,報錯：處理錯誤。,首先規(guī)定文法符號之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后再利用這種關(guān)系，通過比較兩個相鄰的符號之間的優(yōu)先順序來確定可歸約串。,算符文法：任何產(chǎn)生式的右部都不含兩個相繼的非終結(jié)符,5.2 算符優(yōu)先分析,例：考慮文法G(E)：EE +T |T TT*F | F Fi| (E)是否是算符文法？,優(yōu)先關(guān)系：,如果一個算符文法的任何終結(jié)符對至多只滿足三種關(guān)系之一，稱為算符優(yōu)先文法。,驗證終結(jié)符對之間的優(yōu)先關(guān)系

5、(p90優(yōu)先表),例：考慮文法G(E)：EE +T |T TT*F | F Fi| (E)是否是算符優(yōu)先文法？,如何從文法構(gòu)造優(yōu)先關(guān)系表？,,檢查文法產(chǎn)生式的每個候選，可找出所有滿足 的終結(jié)符對。,如何找出滿足 和 終結(jié)符對？,對每個非終結(jié)符P構(gòu)造兩個集合FIRSTVT(P)和LASTVT(P),FIRSTVT(P)=,LASTVT(P) =,檢查每個產(chǎn)生式候選，若形為...aP...,則對任何bFIRSTVT(P)， 我們有a b。,若形為...Pb...,則對任何aLASTVT(P)， 我們有a b。,對表達式文法的非終結(jié)符構(gòu)造FIRSTVT和LASTVT

6、并建立優(yōu)先關(guān)系表,算符優(yōu)先分析算法,素短語：這樣的一個短語，它至少含一個終結(jié)符，不含比自身更小的素短語。,最左素短語：句型最左邊的素短語。,演示SuanFuYouXian,優(yōu)先函數(shù),有的關(guān)系表不存在優(yōu)先函數(shù)！ 對于存在優(yōu)先函數(shù)的關(guān)系表，如何構(gòu)造優(yōu)先函數(shù)？ 請自學p9495優(yōu)先函數(shù)的構(gòu)造方法。,5.3 LR 分析法,1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技術(shù)。 LR(K)分析是指自左向右掃描和自下而上的語法分析，且 在分析的每一步，只須根據(jù)分析棧中當前已移進和歸約出的 全部文法符號，并至多再向前查看K個輸入符號，就能確定 相當于某一產(chǎn)生式右部符號的句柄是否已在分析棧

7、的頂部形 成。從而也就可以確定所應采取的分析動作（是移進輸入符號 還是按某產(chǎn)生式進行歸約）。,當前掃描到Xn+1,向前查看k個符號，來確定是把 Xn+1移進棧，還是把XiXn作為句柄進行歸約。,1） 要歸約時，則根據(jù)某產(chǎn)生式UXiXi+1Xn進行歸約： #X1X2Xi-1UXn+1Xn+2Xn+k#,LR(0) 表示在每一步分析時都不用向前輸入符號 LR(1) 表示在每一步分析時都向前看一個輸入符號來決定當 前的動作。 SLR(1) 表示簡單的LR(1)，即只在動作不唯一的地方向前看一 個符號，在動作唯一時則不向前看輸入符號。,5.3.1 LR分析概論,一 .LR分析器的邏輯結(jié)構(gòu)

8、及工作過程 從邏輯上來說，一個LR分析器如圖：,,所有LR分析器的總控程序大同小異,只有分析表各不相同。 三種不同的分析表,規(guī)范LR分析表構(gòu)造法。用此法構(gòu)造的分析表功能最強而且也適合于很多文法，但實現(xiàn)代價比較高。,簡單LR(即SLR)分析表構(gòu)造法。這是一種比較容易實現(xiàn)的方法。但SLR分析表的功能太弱，而且對某些文法可能根本就構(gòu)造不出相應的SLR分析表。,向前LR（即LALR）分析表構(gòu)造法。這種方法構(gòu)造的分析表功能介于規(guī)范LR分析表SLR分析表之間。這種表適用于絕大多數(shù)程序語言的文法。而且也可以設(shè)法有效的實現(xiàn)。,二、LR 分析器的分析過程如下：,1.首先將初始狀態(tài) S0及句子的左界限#分別壓入狀

9、態(tài)棧和符號棧中。,則用棧頂狀態(tài)Sm和當前掃描符 ai組成符號對（ Sm, ai)去查 分析動作表，根據(jù)ACTIONSm, ai的指示完成相應的分析動作。 表中每一表元素所規(guī)定的動作僅能是下列四種動作之一：,2.設(shè)在分析中的某一步，分析棧及余留的輸入串為如下格局： S0S1 Sm ai ai+1an #X1 Xm ,（1） ACTIONSm, ai= Sm+1 （移進） 表明句柄尚未在棧頂形成，此時正期待移進輸入符號以便形成 句柄。故將當前的輸入符號和表元素Sm+1分別壓入棧中，有,（2） ACTIONSm, ai= Rj (歸

10、約） 表明此時應按文法的第j個產(chǎn)生式A Xm-k+1Xm-k+2 Xm 進行歸約。即棧頂符號串Xm-k+1Xm-k+2 Xm已成為當前句型的句 柄。所謂按第j個產(chǎn)生式歸約，就是將分析棧中從頂向下的k個符 號退棧，然后將文法符號A壓入符號棧中。此時分析的格局為： S0S1 Sm-k ai ai+1an # # X1 Xm-k A ,然后以（ Sm-k,A)去查狀態(tài)轉(zhuǎn)移表，設(shè)GOTOSm-k,A= Sl ,則將此新狀態(tài)壓入狀態(tài)棧中，則有如下格局： S0S1 Sm-k Sl ai ai+1an #

11、 # X1 Xm-k A ,（3） ACTIONSm, ai=acc （接受）,表明當前的輸入串已被成功地分析完畢，應停止分析器的工作。,其中Z為文法開始符號 S為使ACTIONS ，#=acc的 唯一狀態(tài)（接受狀態(tài)）,（4） ACTIONSm, ai=ERROR（空白）。 表明當前的輸入串中含有錯誤，也應終止當前的分析工作。轉(zhuǎn)出錯處理。,3. 重復上述第2步的工作，直到分析棧頂出現(xiàn)“接受狀態(tài)”或“出錯狀態(tài)”為止。對接受狀態(tài)，分析棧的格局為： S0 S # # Z ,,5.3.2 LR(0) 分析表的構(gòu)造,為了給出構(gòu)造LR(0)分析表

12、的算法，給出一些術(shù)語： 1、規(guī)范句型的活前綴 前綴：一個符號串的前綴是指該串的任意首部（包括）。,例如 abc的前綴有： ,a,ab,abc abcd的前綴有：,a,ab,abc,abcd 由此可知，對于符號串 而言，其前綴的數(shù)量為+1。 例：有文法GS:SaAcBe1 Ab2 這里在每條產(chǎn)生式后加上了產(chǎn)生 AAb3 式的序號i當進行推導時把序號 Bd4 帶上，以便說明問題。 對輸入串a(chǎn)bbcde進行推導如下（最右推導）： S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 由此可知，abbcde是該

13、文法的句子。,最左歸約為： ab2b3cd4e1 用2式歸約, aAb3cd4e1 3, aAcd4e1 4, aAcBe1 1, S,其中表示歸約符,歸約時，歸約前和歸約后的被歸約部分與剩余部分合起來僅構(gòu)成文法的規(guī)范句型，而用哪個產(chǎn)生式歸約僅取決于當前句型的前面部分；X1X2Xnp 其中Xi為文法的符號，p為第p個產(chǎn)生式序號。 如上例中每次歸約前句型的前面部分為： ab2 aAb3 aAcd4 aAcBe1,我們把規(guī)范句型的這種前端部分的串稱為活前綴。實際上，它們恰好是符號棧棧頂形成句柄時符號棧中的內(nèi)容。,SaAcBe1 Ab2 AAb3 Bd4,這是

14、因為一旦句型的句柄在符號棧頂形成，將會立即被歸約 之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的 任何符號）的前綴稱之為活前綴。 對各規(guī)范句型有前綴：,ab2b3cd4e1 ,a,ab aAb3cd4e1 ,a,aA,aAb aAcd4e1 ,a,aA,aAc,aAcd aAcBe1 ,a,aA,aAc,aAcB,aAcBe,活前綴：是指規(guī)范句型的一個前綴，這種前綴不含句柄之 后的任何符號。,,,活前綴定義：,在規(guī)范歸約過程中的任何時候只要已分析過的部分即在符號棧中的符號串為規(guī)范句型的活前綴，表明輸入串的已被分析過的部

15、分是該文法某規(guī)范句型的一個正確部分。,2、LR（0）項目,活前綴與句柄間的關(guān)系：（1）活前綴中已含有句柄的全部符號（句柄的最后符號就是 活前綴的最后符號）。（2）活前綴中只含有句柄的前部分符號（句柄的最左子串 為活前綴的最右子串）。 （3）活前綴中全然不包含句柄的任何符號。,第一種情況表明：此時某一產(chǎn)生式A的右部已出現(xiàn)在符號 棧頂，因此此時相應的分析動作應當是用此產(chǎn)生式進行歸約。 第二種情況表明：形如A12的產(chǎn)生式的 右部子串已在符號棧棧頂，如1，正期待著從余留的輸入串中看到能由推出的 符號串，即期待2 進棧以便能進行歸約。故此時分析動作是“移進”當前輸入符號。 第三種情況則意味著：期

16、望從余留輸入串中能看到由某產(chǎn)生式 A的右部，即所代表的符號串(即句柄) 。所以此時分析的動作也是讀輸入符進符號棧。,,在產(chǎn)生式的右部相應位置上加一個圓點“.”，來指示識別位置，標明在“.”前的部分已被識別。 如上述三種情況，可分別標注為：A.； A1 .2 ; A. 。 右部某位置上標有圓點的產(chǎn)生式稱為LR(0)項目(item)。 不同的LR(0)項目，反映了分析過程中符號棧頂?shù)牟煌闆r。,例如：產(chǎn)生式SaAcBe對應有六個項目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,每個項目的含義與圓點的位置有關(guān)。 圓點

17、左邊的子串表示在分析過程的某一時刻用該產(chǎn)生式歸約時句柄中已識別過的部分，圓點右邊的子串表示待識別的部分。 文法的全部LR(0)項目將是構(gòu)造識別它的所有活前綴的有窮自動機的基礎(chǔ)。,3、LR(0)項目的分類：,例：考慮文法GS=(S,A,B, a,b,c,d,P,S),構(gòu)造其分析表： 其中P: (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d,求該文法的項目集規(guī)范族C： 在上述文法中引入一個新的開始符號S,且將S S作為第0個產(chǎn)生式添加到文法G中，得到G的拓廣文法G。顯然L(G)=L(G)，則對于文法G，其LR(0)項目為：,1)

18、S .S 2) S S. 3) S.A 4) SA . 5) S.B 6) SB. 7) A.aAb 8) Aa .Ab 9) AaA .b 10) AaAb . 11) A.c 12) Ac . 13) B.aBd 14) Ba .Bd 15) BaB .d 16) BaBd . 17)B.d 18) Bd .,G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d,LR(0)項目分類,A. 因為它表明右部符號串已出現(xiàn)在棧頂，此時相應的分析動作應當是按此產(chǎn)生式進行歸約，此種項目稱為

19、歸約項目。 S S. 稱為接受項目。 對于拓廣文法而言，接受項目是唯一的。 A. X 的項目（其中 可以是 ），當X為終結(jié)符時，相應的分析動作應將當前的輸入符號移入棧中，故我們將此種項目稱為移進項目。 當X為非終結(jié)符時，期待著從余留的輸入符中進行歸約后而得到X，此類項目稱為待約項目。,把終結(jié)符和非終結(jié)符都可看成一個有限自動機的輸入符號，每把一個符號進棧相當于已識別過該符號，而狀態(tài)進行轉(zhuǎn)換（到下一狀態(tài)），當識別到可歸前綴時相當于棧頂已形成了句柄，則認為到達了識別句柄的終態(tài)。,4、構(gòu)造識別活前綴的DFA DFA中的中每一個狀態(tài)由若干個LR(0)項目所組成的集合（稱為項目集）來表示。,舉例：構(gòu)造識別

20、前綴的DFA 用I0表示這個DFA的初態(tài)， 將項目S.S列入項目集I0。 將項目S.A和S.B加入I0中。 將A.aAb和A.c和B.aBb, B.d加入I0中。 項目集I0將由如下項目組成： I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d S.S稱為項目集I0的基本項目，從基本項目出發(fā)構(gòu)造項目集I0的過程，可用closure(S.S)表示。,closure(I)的定義：,Closure(I)=IA.AGK .Aclosure(I)V*V*,構(gòu)造closure(I)的算法： 1）I中的每一個項目都屬于closure(I); 2）若形如K.A的項目屬于I，且

21、A是文法的一個產(chǎn)生式，任何形如A.的項目也應加到closure(I)中 3）重復上述過程，直至不再有新的項目加入到closure(I)中為止。,如何確定從I0可能轉(zhuǎn)移到的下一狀態(tài)？ 若I0中有項目K .A，從輸入串識別出A后，進入下一狀態(tài)。設(shè)此狀態(tài)為Ii ，顯然Ii中必含有形如KA .的項目，稱為K .A的后繼項目。 后繼項目組成集合J，則J中的每個項目都是項目集Ii的基本項目，有： Ii =closure(J),定義狀態(tài)轉(zhuǎn)移函數(shù)：GO(I,A)=closure(J) 其中，I是當前狀態(tài)，A為文法符號，J是I中所有形如K.A 的項目之后繼項目KA.所組成的集合，而closure(J)就是項目

22、 集I（即狀態(tài)I)關(guān)于符號A的后繼項目集（即后繼狀態(tài)）。,GO(I,A)=closure(所有形如KA .的項目K .AI),對于上例，有： I1 =GO(I0,S)=closure(SS.) I1 : SS.; I2 =GO(I0,A)=closure(SA.) I2 :SA.; I3 =GO(I0,B)=closure(SB.) I3 : SB.; I4 =GO(I0,a)=closure(Aa.Ab,Ba.Bd),I4 : Aa.Ab Ba.Bd A.aAb B.aBd A.c B.d I5=GO(I0,c)=closure(Ac.) I5 : Ac.

23、 I6=GO(I0,d)=closure(Bd.) I6 :Bd. I1, I2,I3,I5,I6均無后繼項目集，僅I4有后繼項目集： I7 =GO(I4,A)=closure(AaA.b)=AaA.b I9 =GO(I4,B)=closure(BaB.d)=BaB.d 此外，還有： GO(I4,a)=closure(Aa.Ab, Ba.Bd)= I4 GO(I4,c)=closure(Ac.)= I5 GO(I4,d)=closure(Bd.)= I6 這些項目集均不產(chǎn)生新的項目集。另外還有:,I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,

24、b)=closure(BaBd.)=BaBd. I8 ， I10也后繼項目集。 GS的全部項目集即為I0 I10 。 將這些項目集的全體稱為文法GS的LR(0)項目集規(guī)范族，并記為C=(I0, I1,, I10) 識別文法GS的全部活前綴的DFA為 M=(C,V,GO, I0,Z) 其中CM的狀態(tài)集，即文法GS的LR(0)項目集規(guī)范族I0 I10 V M的字母表，即V=S,S,A,B,a,b,c,d； GOM的狀態(tài)轉(zhuǎn)換函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù)GO； I0M的唯一初態(tài)； ZM的終態(tài)集， ZC為規(guī)范族中所有含有歸約項目的 那些項目集。,DFA:,4、LR(0)分析

25、表的構(gòu)造,要求每一個項目集中的的諸項目不出現(xiàn)下列的情況： （1）移進項目和歸約項目并存，即存在移進歸約沖突； （2）多個歸約項目并存，即存在歸約歸約沖突。 如果一個文法G滿足上述條件，也就是它的每個LR(0)項目集中都不含有沖突的項目，則稱G為LR(0)文法。 只有當一個文法是LR(0)文法時，才能對它構(gòu)造不含沖突動作的LR(0)分析表。,構(gòu)造LR(0)分析表的算法為： (1)對于每一項目集Ii中形如A.X的項目，且有GO(Ii,X)=Ij, 若X為一終結(jié)符號 a 時，則置ACTIONi,a=Sj; 若X為一非終結(jié)符號時，則置GOTOi,X=j (2)若Ii中有歸約項目A. ,設(shè)A為文法

26、第j個產(chǎn)生式，則對文法的任何終結(jié)符和“#”（均記為a）置ACTIONi,a=Rj,(3)若接受項目SS .屬于Ii ,則置ACTIONi,#=acc。 (4)在分析表中,凡不能按上述規(guī)則填入信息的元素,均置為“出錯”。 如上例可構(gòu)造分析表為：,ACTION GOTO a b c d # S A B 0 S4 S5 S6 1 2 3 Acc R1 R1 R1 R1 R1 R2 R2 R2 R2 R2 S4 S5 S6

27、 7 9 R4 R4 R4 R4 R4 R6 R6 R6 R6 R6 S8 R3 R3 R3 R3 R3 S10 10 R5 R5 R5 R5 R5,5、LR(0)分析器的工作過程,根據(jù)輸入串當前符號a和分析棧棧頂狀態(tài)i查找分析表應采取的動作： 1）若ACTIONi,a=Sj, aVT,則把a移進符號棧，j移進狀態(tài)棧。 2）若ACTIONi,a=Rj，aVT或#，則用第j個產(chǎn)生式歸約。并將兩個棧的指針減去K(其中K為第j 個產(chǎn)生式右部的串長度），并把產(chǎn)生式的左部符號A壓入符號棧，同時用符號對（ Si-k,A)去查GOTO表（其中Si-k為狀態(tài)棧當前棧

28、頂元素，若GOTOSi-k,A=j,則j壓入狀態(tài)棧，使得兩個棧內(nèi)的元素一樣多。 3）若ACTIONi,a=Acc,（此時a應為“#”號），則表明分析成功，結(jié)束分析。 4）若ACTIONi,a=空白，轉(zhuǎn)出錯處理。,5.3.3 SLR分析表的構(gòu)造,大多數(shù)程序設(shè)計語言的文法不是LR(0)文法。 對LR(0)規(guī)范族中有沖突的項目集（狀態(tài)）用向前查 看一個（輸入）符號的辦法進行處理，以解決沖突。即為SLR(1)。 假定有一個LR(0)規(guī)范族中含有如下項目集(狀態(tài))I: I=X.b,A., B.其中,,,為符號串，bVT, I中含有移進歸約和歸約歸約沖突。 只要FOLLOW(A)和FOLLOW(B)互

29、不相交，且都不包含b,即：,當狀態(tài)I面臨某輸入符號a時，則動作為： 1）若a = b,則移進。 2）若a FOLLOW(A),則用產(chǎn)生式A歸約。 3）若a FOLLOW(B),則用產(chǎn)生式B歸約。 一般地，對于LR(0)規(guī)范族的一個項目集I可能含有多個移進項目和多個歸約項目，我們可假設(shè)項目集I中有m個移進項目： A11. b11, A2 2. b22, , Am m. bmm;同時含 有n個歸約項目：B11. , B2 2. ,, Bn n. ,只要集合 b1, b2,bm和FOLLOW(B1),FOLLOW(B2),,FOLLOW(Bn) 兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來解決沖突： 1

30、）若ab1, b2,,bm,則移進。 2）若aFOLLOW(Bi),i=1,,n,則用Bi i進行歸約。 3）此外，則報錯。,SLR分析表的構(gòu)造方法 (1)對于每一項目集Ii中形如A.X的項目，且有GO(Ii,X)=Ij, 若X為一終結(jié)符號a時，則置ACTIONI,a=S; 若X為一非終結(jié)符號時，則僅置GOTOi,X=j； (2)若歸約項目A.屬于Ii,設(shè)A為文法第j個行產(chǎn)生式，則 對任何屬于FOLLOW(A)的輸入符號a,置ACTIONi,a=Rj； (3)若接受項目S S.屬于Ii ,則置ACTIONi,#=acc。 (4) 在分析表,凡不能按上述規(guī)則填入信息的元素,均置為“出錯”。,

31、例： 表達式文法GE,構(gòu)造其LR(0)項目規(guī)范簇和SLR(1)分析表。GE: EE+TT TT*FF F(E) i,解：1、拓廣文法為GS : (0) SE EE+T ET TT*F TF F(E) Fi,2、再求識別G的全部活前綴的DFA：,I0: S.E E.E+T GO(I0,E)=I1 E.T T.T*F GO(I0,T)=I2 T.F GO(I0,F)=I3 F.(E) GO(I0,( )=I4,I1: SE. EE.+T GO(I1,+)=I6,I2: ET. TT.*F GO(I2,*)=I7,I3:

32、TF.,I4: F(.E) E.E+T GO(I4,E)=I8 E.T T.T*F GO(I4,F)=I2 T.F GO(I4,F)=I3 F.(E) GO(I4,( )=I4 F.i GO(I4,i)=I5,I5: Fi.,I6: EE+.T T.T*F GO(I6,T)=I9 T.F GO(I6,F)=I3 F.(E) GO(I6,( )=I4 F.i GO(I6,i)=I5,,I7: TT*.F GO(I7,F)=I10 F.(E) GO(I7,( )=I4 F.i GO(I7,i )=I5

33、,I8: F(E.) GO(I8,) )=I11 EE.+T GO(I8,+)=I6,I9: EE+T. TT.*F GO(I9,)=I7,I10: TT*F.,I11: F(E).,DFA,3、解決沖突,I1， I2， I9中有移進-歸約沖突。 FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 在I1中，由于FOLLOW(S)=#).而SE.是唯一的接受項目，所以當且僅當遇到句子的結(jié)束符“#”號時才被接受,又因#+=，故I1中的沖突可解決。 對于I2,因FOLLOW(E)

34、=+,),#*=,因此當面臨輸入符號為“+”，“ ）”或“#”號時，則用產(chǎn)生式ET歸約。當面臨輸入符為“*”時，則移進；其它情況則報錯。 對于I9, 當面臨輸入符號為“+”，“）”或“#”時，則用產(chǎn)生式EE+T歸約；當面臨輸入符號為“*”時，則移進，其余情況報錯。 演示Figure5.5LRDFA,4、構(gòu)造SLR(1)分析表,對于上述三個沖突項目等均可用SLR(1)方法解決沖突。因此該 文法是SLR(1)文法。我們可造成其相應的SLR(1)分析表為：,5.3.4 規(guī)范LR分析表的構(gòu)造,SLR(1)方法：若狀態(tài)k含有A. ，若aFOLLOW(A)，則用A歸約,演示Figure5.9LRDFA

35、i=*i 狀態(tài)2移進還是歸約？ 為什么=FOLLOW(R)，卻不能歸約？ S=L=R =*R=R 輸入符號為=時，若把L歸約為R,必須推導出 R=...，這是不可能的。 可見，SLR(1)方法：若狀態(tài)k含有A. ，若aFOLLOW(A)，則用A歸約，失于粗糙。,5.3.4 規(guī)范LR分析表的構(gòu)造,LR(1)項目 (A. ，x)表示： 在棧頂，輸入串頭部可由x導出。,LR(1)狀態(tài) LR(1)項目的集合。,Closure(I)= repeat for any item(A. X，z) in I for any production X for any wFIRST(z) IIX

36、 . , w until I does not change,GO (I,X)= J for any item(A. X，z) in I add (AX . ，z) to J return Closure(J),初態(tài) Closure((S.S，#) ),LR(1)項目集和GO函數(shù)的例子,a,(0)SS (1) BaB (2) SBB(3) Bb,5.3.5 LALR分析表的構(gòu)造,演示Figure5_10LR1DFA(aab#和aabab#)，觀察狀態(tài)4和狀態(tài)7的區(qū)別,同心項目集：除去搜索符之外都相同的LR(1)項目集,合并同心項目集不會產(chǎn)生新的移進-歸約沖突,合并同心項目集，如果沒有歸約-歸

37、約沖突，則為LALR(1)文法。,演示Table5.6LALRDFA(aab#和aabab#)，觀察LALR和LR(1)對正確的句子和有錯誤的輸入串的分析,5.3.6 二義文法的應用,演示ERYIWENFAdfa,I1的移進-歸約沖突SLR方法可以解決,I7的移進-歸約沖突用優(yōu)先級和結(jié)合性解決,5.3.7 LR分析中的錯誤處理,演示LRErrorHandling,缺少運算量的錯誤i+#,右括號不匹配的錯誤i*i)#,缺少運算符的錯誤（ii)#,缺少右括號的錯誤（i+i#,多個錯誤,,,LL(0),,,,,,,,,二義文法,非二義文法,LR(k),LL(k),LR(1),LL(1),LALR(1),SLR,LR(0),文法體系,作業(yè)：1，2，3，5，8,