自下而上的LR(k)分析方法.ppt

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

1、第七章 自下而上的LR(k)分析方法,LR(K)的含義,L:自左向右掃描輸入串;R:采用最右推導(dǎo)的逆過程分析句子,K:在分析的過程中至多查看K個符號 給定文法G，S是其開始符號。考慮該文法中一個終結(jié)符串w的一個規(guī)范推導(dǎo)Sw1w2 w 假定uAvuxv是上述推導(dǎo)中的一個推導(dǎo)步。Ax是用于該推導(dǎo)步的產(chǎn)生式；u和v(VNVT)。 對上述這樣的一步推導(dǎo)，僅通過掃描ux和（至多）查看v中開始的k個符號就能唯一確定選用產(chǎn)生式Ax去進(jìn)行推導(dǎo),我們就稱G為LR(k)文法。,LR(k)分析器是按從左至右方式掃描輸入串，并按自下而上方式進(jìn)行規(guī)范歸約的分析程序。 一個LR(k)分析器主要由兩部分組成：一個總控程序和

2、一個分析表。一般說來，所有LR分析器的總控程序基本上是大同小異的，只是分析表各不相同。 本章主要介紹LR(0) 分析表的構(gòu)造算法及相關(guān)知識。,7.1 LR分析器的工作原理和過程,1. LR 分析法概述 LR分析是一種規(guī)范歸約。規(guī)范歸約的關(guān)鍵是分析過程中如何確定分析棧的棧頂?shù)姆柎欠裥纬删浔?LR分析確定句柄的基本思想是在規(guī)范歸約分析過程中,根據(jù)分析棧中記錄的已移進(jìn)和歸約出的整個符號串(即歷史)和根據(jù)使用的規(guī)則推測未來可能遇到的輸入符號(即展望),以及現(xiàn)實讀到的輸入符號這三個方面的信息來確定分析棧的棧頂符號串是否形成句柄.,2. LR(k)分析器的邏輯結(jié)構(gòu),LR分析器是一個確定的下推自動機,

3、,LR(k)分析方法的主要思想： 1.嚴(yán)格地進(jìn)行最左歸約（識別句柄并歸約它）。 2.將識別句柄的過程劃分為由若干狀態(tài)控制，每個狀態(tài)控制識別出句柄的一個符號。 3.分析棧：存放已識別的文法符號和狀態(tài),描述的是分析過程中的歷史和展望信息; 4.由一個總控程序來控制整個識別過程。,LR分析器的工作過程,總控程序在分析的每一步，都是按照棧頂狀態(tài)q和當(dāng)前輸入符號a，查閱LR分析表，并執(zhí)行其中ACTIONq，a和GOTO部分規(guī)定的操作。,LR分析器的分析表由分析動作表（ACTION表）和 狀態(tài)轉(zhuǎn)換表(goto函數(shù)表)兩部分組成，它們都是用二維數(shù)組表示的。 ACTION表指明了分析程序采取的動作 移進(jìn)(S

4、i)：句柄尚未形成，需要繼續(xù)把符號移進(jìn)棧以形成句柄 歸約( rj)：句柄已經(jīng)形成，用對應(yīng)的產(chǎn)生式進(jìn)行歸約。 接收(acc)：表示整個分析工作完畢，輸入串合法。 報錯(空白)：出錯處理。,ACTION Si,am 動作表,S1,S2Sn為分析器的各個狀態(tài); a1,a2am為文法的全部符號 ACTIONSi,a:規(guī)定了當(dāng)前狀態(tài)為Si,面臨輸入符號a時應(yīng)執(zhí)行的動作(移進(jìn)、歸約、接受、報錯）,GOTOSm,xi狀態(tài)轉(zhuǎn)換表,X1,X2Xn為文法字匯表中的全部文法符號 GOTOSi,X規(guī)定了當(dāng)前狀態(tài)為Si,棧頂為文法符號X時,轉(zhuǎn)移到的下一個狀態(tài).,LR分析器的工作過程,LR分析器的一個構(gòu)形由兩部分構(gòu)成:棧

5、中符號串和尚待掃描的輸入串 (S0X1S1X2S2XmSm,aiai+1an$) 分析器的工作過程就是從一種構(gòu)形到另一種構(gòu)形的轉(zhuǎn)換過程. (S0，a1a2an$)為初始構(gòu)形 (S0AZ,$),其中A是文法開始號,ACTIONZ,$= 接收 分析器的下一次移動是由棧頂狀態(tài)Sm和當(dāng)前輸入符號ai去查看ACTION表并執(zhí)行ACTIONSm,ai規(guī)定的動作并根據(jù)GOTOSm,ai表去確定棧頂狀態(tài),(1)若ACTIONSm,ai=移進(jìn)S,則分析器執(zhí)行一個移進(jìn)動作,進(jìn)入構(gòu)形 (S0X1S1X2S2XmSmaiS,ai+1an$),此時ai進(jìn)棧,棧頂狀態(tài)S=GOTOSm,ai (2)若ACTIONSm,a

6、i=歸約A,則分析器執(zhí)行一個歸約動作(按產(chǎn)生式A進(jìn)行歸約),進(jìn)入構(gòu)形 (S0X1S1X2S2Xm-rSm-rAS,aiai+1an$),其中 S=GOTOSm-r,A,r是產(chǎn)生式A的長度,棧頂符號串Xm-r+1Xm和A的右部匹配,即為當(dāng)前句型的句柄。 （3）若ACTIONSm,ai= 接收， 分析成功 （4）若ACTIONSm,ai=ERROR，輸入串有語法錯誤，分析器停止工作，進(jìn)行錯誤處理。,例: GA 1 AaBcDe 2 Bb 3 BBb 4 Dd,輸入串a(chǎn)bbcde$的分析過程,輸入串a(chǎn)bbcde$的分析過程,7.2 LR(0)分析表的構(gòu)造,LR分析法的基本原理 例如，對文法GA：

7、 AaBcDe Bb BBb Dd 分析符號串a(chǎn)bbcde。,句柄的識別是一個符號一個符號得到的，若將從左到右每識別得到句柄的一個符號就對應(yīng)著一個狀態(tài)，則可將n個符號的句柄的識別分成n+1個狀態(tài)。,用LR(0)項目來表示一個句柄的所有識別狀態(tài)。 文法G的LR(0)項目定義為：文法G的每個產(chǎn)生式右部的某個位置添加一個“”。,7.2 LR(0)分析表的構(gòu)造,規(guī)范句型的活前綴 一個符號串的前綴是指該串的任意首部，包括。 活前綴（Viable Prefix）是指規(guī)范句型的一個前綴，它不包含該句型的句柄右邊的任何符號。,,在得到一個規(guī)范句型的完整句柄之前所識別的符號串稱為規(guī)范句型

8、的活前綴。,7.2 LR(0)分析表的構(gòu)造,GS：AaBcDe Bb BBb Dd,7.2 LR(0)分析表的構(gòu)造,活前綴與句柄的關(guān)系 (1)AAB 句柄的符號還沒有開始識別, 希望看到從輸入串中與AB對應(yīng)的符號串。 (2)AAB 已識別句柄的一部分,希望看到能規(guī)約為B的符號串 (3)AAB 當(dāng)前句柄已經(jīng)形成，可以進(jìn)行規(guī)約。,7.2 LR(0)分析表的構(gòu)造,文法G的拓廣文法 給定文法G，S是其開始符號，G的拓廣文法是G，其開始符號為S，區(qū)別在于后者僅增加一個產(chǎn)生式SS。,例如，對文法GA： 1.AaBcDe 2.Bb 3.BBb 4.Dd 拓廣后文法為 GS:

9、0.S A 1.AaBcDe 2.Bb 3.BBb 4.Dd,該文法的LR(0)項目: 0.S .A 1.S A. 2.A.aBcDe 3.A a.BcDe 4.A aB.cDe 5.A aBc.De 6.A aBcD.e 7.A aBcDe. 8.B.b 9. Bb. 10.B.Bb 11.BB.b 12. BBb. 13. D.d 14.Dd.,7.2 LR(0)分析表的構(gòu)造,,LR(0)項目集,SS 初始項目 SS 接收項目 Ux.歸約項目； Ux.Vy(VVN)待約項目。 Ux.ay(x，y為符號串，aVT)移進(jìn)項目； Uxa.y(x，y為符號串，aVT)是Ux.ay

10、的后繼項目 S .A A.aBcDe 等價項目 A a.BcDe B.Bb B.b 等價項目,7.2 LR(0)分析表的構(gòu)造,文法共有個LR(0) 項目，表示在對這個文法的句子進(jìn)行分析的時候可能出現(xiàn)的種狀態(tài)，但是其中一些狀態(tài)是等價的。 等價項目識別的活前綴是相同的，可以由他們組成的項目集作為將要構(gòu)造的的一個狀態(tài)。,7.2 LR(0)分析表的構(gòu)造,CLOSURE(I)函數(shù)求與I相關(guān)的所有LR(0)項目的等價項目 I中的每一項目都屬于它 若AB屬于CLOSURE(I)且B是文法中的一個產(chǎn)生式，則關(guān)于產(chǎn)生式B的任何形如B的項目也屬于它 重復(fù)上述步驟，直到它不再增大為止 利用閉包算法可以把（）項目分

11、為幾個等價類,令 I= S .A 則CLOSURE(I)= = S .A,A.aBcDe它是DFA的初態(tài)，用I0來表示，它識別的活前綴是，那么在I0狀態(tài)下，移進(jìn)或歸約為某一個文法符號之后可能轉(zhuǎn)移的下一個狀態(tài)是什么？ 一般說來，對于狀態(tài)中的任意項目 A.，是任意文法符號（終結(jié)符或非終結(jié)符），在移進(jìn)或歸約出之后，應(yīng)該轉(zhuǎn)到其后繼項目A.（可能有多個）所在的狀態(tài),狀態(tài)轉(zhuǎn)換函數(shù),goto(I, X)函數(shù) goto(I, X)=CLOSURE (所有形如AX的項目 AXI) 先找出形如 AXI的項目 然后將其變成AX 再求CLOSURE (AX),例如： I0 S .A，A.aBcDe I0的后繼項目所

12、在的狀態(tài)為： GO(I0,A)=CLOSURE(S A.)= S A.=I1 GO(I0,a)= CLOSURE(Aa.BcDe)=Aa.BcDe, B.Bb,B.b=I2 GO(I2,B)= CLOSURE(AaB.cDe,BB.b)=AaB.cDe, BB.b =I3 GO(I2,b)= CLOSURE(Bb.)=Bb. =I4 GO(I3,c)= CLOSURE(AaBc.De)= AaBc.De. D.d=I5 GO(I3,b)= CLOSURE(BBb.)=BBb.=I6,GO(I5,D)= CLOSURE(AaBcD.e)= AaBcD.e= I7 GO(I5,d)= CLOSUR

13、E(Dd.)= Dd.= I8 GO(I7,e)= CLOSURE(AaBcDe.)= AaBcDe.=I9 因此從初始項目出發(fā)S .A出發(fā)，利用CLOSURE和GO函數(shù)，可以構(gòu)造出不識別文法G的所有活前綴的DFA,構(gòu)造的方法：,(1)求CLOSURE(SS),得到I0; (2)對初始項目集或其它已構(gòu)造的項目集，應(yīng)用狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)求出新的后繼項目集； (3)重復(fù)(2)直到不再出現(xiàn)新的狀態(tài)為止； (4)利用GO函數(shù)建立狀態(tài)間的聯(lián)系,構(gòu)造識別文法活前綴的DFA,,I0:S.A A.aBcDe,I1:SA.,I2: Aa.BcDe B.Bb B.b,,,I5: AaBc.De D.d,,

14、,I7: AaBcD.e,,I9: AaBcDe.,,I8:Dd.,,A,a,b,B,D,d,e,c,b,I6:BBb.,I4:Bb.,,,,I3: AaB.cDe BB.b,7.2 LR(0)分析表的構(gòu)造,LR(0)文法的概念 如果文法G的項目集規(guī)范族的每個項目集中不存在下述任何沖突項目： 移進(jìn)項目和歸約項目并存， 多個歸約項目并存， 則稱文法G為LR(0)文法。,7.2 LR(0)分析表的構(gòu)造,構(gòu)造LR(0)分析表的算法 若項目AxIi且goto(Ii, x)=Ij，xVT，則置ACTIONi, x=Sj，即“將狀態(tài)j、符號x移進(jìn)棧”；但若xVN，則僅置GOTOi, x=j。 若項目AIi，對于任何輸入符號a(VT$)，則置ACTIONi,a=rj，即“用第j條產(chǎn)生式A進(jìn)行歸約”（這里假定A是G中的第j條產(chǎn)生式）。 若項目SSIk，則置ACTIONk, $=“接收”。 分析表中凡不能用規(guī)則填入信息的元素均置上ERROR（用空白表示）。,7.2 LR(0)分析表的構(gòu)造,7.2.11 構(gòu)造LR(0)分析表的步驟小結(jié) 寫出給定文法G的拓廣文法G； 寫出文法G的基本LR(0)項目G的LR(0)項目集； 利用CLOSURE和goto函數(shù)，求出相應(yīng)的LR(0)項目集規(guī)范族C； 構(gòu)造識別該文法全部活前綴的DFA； 根據(jù)算法構(gòu)造LR(0)分析表。,The end.,,