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

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

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

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

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

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

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

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

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

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

9、0.S A 1.AaBcDe 2.Bb 3.BBb 4.Dd,該文法的LR(0)項(xiàng)目: 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)項(xiàng)目集,SS 初始項(xiàng)目 SS 接收項(xiàng)目 Ux.歸約項(xiàng)目； Ux.Vy(VVN)待約項(xiàng)目。 Ux.ay(x，y為符號(hào)串，aVT)移進(jìn)項(xiàng)目； Uxa.y(x，y為符號(hào)串，aVT)是Ux.ay

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

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

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 因此從初始項(xiàng)目出發(fā)S .A出發(fā)，利用CLOSURE和GO函數(shù)，可以構(gòu)造出不識(shí)別文法G的所有活前綴的DFA,構(gòu)造的方法：,(1)求CLOSURE(SS),得到I0; (2)對(duì)初始項(xiàng)目集或其它已構(gòu)造的項(xiàng)目集，應(yīng)用狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)求出新的后繼項(xiàng)目集； (3)重復(fù)(2)直到不再出現(xiàn)新的狀態(tài)為止； (4)利用GO函數(shù)建立狀態(tài)間的聯(lián)系,構(gòu)造識(shí)別文法活前綴的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的項(xiàng)目集規(guī)范族的每個(gè)項(xiàng)目集中不存在下述任何沖突項(xiàng)目： 移進(jìn)項(xiàng)目和歸約項(xiàng)目并存， 多個(gè)歸約項(xiàng)目并存， 則稱文法G為LR(0)文法。,7.2 LR(0)分析表的構(gòu)造,構(gòu)造LR(0)分析表的算法 若項(xiàng)目AxIi且goto(Ii, x)=Ij，xVT，則置ACTIONi, x=Sj，即“將狀態(tài)j、符號(hào)x移進(jìn)?！保坏魓VN，則僅置GOTOi, x=j。 若項(xiàng)目AIi，對(duì)于任何輸入符號(hào)a(VT$)，則置ACTIONi,a=rj，即“用第j條產(chǎn)生式A進(jìn)行歸約”（這里假定A是G中的第j條產(chǎn)生式）。 若項(xiàng)目SSIk，則置ACTIONk, $=“接收”。 分析表中凡不能用規(guī)則填入信息的元素均置上ERROR（用空白表示）。,7.2 LR(0)分析表的構(gòu)造,7.2.11 構(gòu)造LR(0)分析表的步驟小結(jié) 寫出給定文法G的拓廣文法G； 寫出文法G的基本LR(0)項(xiàng)目G的LR(0)項(xiàng)目集； 利用CLOSURE和goto函數(shù)，求出相應(yīng)的LR(0)項(xiàng)目集規(guī)范族C； 構(gòu)造識(shí)別該文法全部活前綴的DFA； 根據(jù)算法構(gòu)造LR(0)分析表。,The end.,,