編譯原理課件Chapt5-3.ppt

1、編譯原理，第五章語法分析自下而上分析，SLR分析，LR(0)方法對語法要求嚴(yán)格，現(xiàn)實中很難保證語法的適應(yīng)LR(0)能夠通過非終結(jié)符跟蹤符號的展望來解決部分LR(0)分析沖突，假定一個LR(0)的follow (0) 在aFOLLOW(A )的情況下，用發(fā)生式a歸約。 如果是aFOLLOW(B )，則以發(fā)生式b歸約。 4 .還要報告錯誤。 如果LR(0)規(guī)范系列的項目集I=A1a11，A2a22，Amamm，B1，B2， Bn是一組a1，am，跟隨(B1)，跟隨(Bi )，I=1，2， n，則3 .還要報告錯誤。 沖突性操作的這樣的解決方案被稱為SLR(1)解決方案。 SLR分析的特點是，SLR

2、的DFA和LR(0)完全相同！ 制作分析表的方法與LR(0)沖突的狀態(tài)不同，SLR可以通過修正Follow集判斷是繼續(xù)還是使用哪個發(fā)生式規(guī)則，SLR(1)和LR(0)、LR(0)只看分析堆棧的內(nèi)容，不考慮當(dāng)前的輸入的分析能力強(qiáng)，制作SLR(1)的分析表的方法：首先將g擴(kuò)展到g，對于g結(jié)構(gòu)LR(0)的項目收集規(guī)范族c和活前綴，識別自動機(jī)的狀態(tài)變換函數(shù)GO .然后使用g和GO，按照下面的算法，分析表的ACTION和GOTO 2 .在項目a屬于Ik的情況下，對于任意的終止符號a、aFOLLOW(A )，將ACTIONk、a設(shè)為“rj”。 3 .如果項目SS屬于Ik，則設(shè)置ACTIONk，#是“acc

3、”； 如果GO(Ik，A)Ij和a是非終結(jié)符號，則GOTOk和A=j。 5 .在分析表中不能按規(guī)則1至4填寫信息的空白單元格全部標(biāo)記“錯誤標(biāo)志”。 上述構(gòu)筑的ACTION和GOTO表如果不包含多條目，則將該語法稱為SLR(1)語法。 使用SLR表的分析器稱為SLR分析器。 每個SLR(1)語法不是二義的。 然而，許多無二義語法并非SLR(1)，我們考慮了示例5.11次擴(kuò)展語法： (0) se (1) eet (2) et (3) TT * f (4) TF (5) I 03360 se ee t et * f TT * f TF (e ) fi，I 133330 I :托架、I 43360托架

4、、I 43360托架、I 43360托架、I 1000托架我們考慮了非SLR句法的例子： (0) ss (1) sl=r (2) Sr (3) l * r (4) Li (5) rl。 可以對從FOLLOW集合得到的先行碼集合進(jìn)行修正，該語法的LR(0)項集規(guī)范族為：I0:SS SL=R SR S*R Li RL、I1:SS、I2:SL=R RL、I3:SR、i4:l FOLLOW(R)#、=、I2: sl=。 在不以sl=r(2)sr(3)l*r、“R=”為前綴的規(guī)范句型中，有以“*R=”為前綴的規(guī)范句型，在I2:SL=R RL，SLR方法中，在項目集Ii中包含項目a .接著輸入符號aFOL

5、LOW(A )時然而，在一些情形中，當(dāng)狀態(tài)I出現(xiàn)在棧頂部時，棧中的活躍前綴不一定允許返回a。 原因是，“Aa”這樣的規(guī)范句型可能不存在。 因此，在這種情況下，以“a”簽約未必合適。 FOLLOW收藏提供的信息太多了！ LR(k )分析法、Donald E. Knuth LR(k )分析器(第6章)和屬性語法(第14章)的發(fā)明者最強(qiáng)的無跟蹤自下而上分析器、LR(1)分析法、LR(0 SLR(1)的方法可以簡單地將非終結(jié)符的Follow集作為歸約的依據(jù)另外，判斷SLR(1)語法的界限是否能夠用A-將#a歸結(jié)為約#Aa的前提條件不僅要求a Follow(A )，還要求Aa是某規(guī)范句型的前綴。 LR(

6、1)的項目，在現(xiàn)有的方法LR(0)和SLR(1)中，如果在某個狀態(tài)中包含歸約項目a，則當(dāng)列出現(xiàn)在堆棧上時，我們可以用a進(jìn)行歸約，現(xiàn)在，希望在各狀態(tài)中包含很多的“展望”信息，這有助于克服動作項目中的a1a2ak被稱為其前向檢索字符串(或展望字符串)。 向前檢索字符串只對歸約項目a、a1a2ak有意義。 移動或者預(yù)約項目a，a1a-2 AK，檢索字符串a(chǎn)1a-2 AK中沒有任何作用。歸約項目a、a1a-2 AK意味著只有當(dāng)它所屬的狀態(tài)出現(xiàn)在堆棧的頂部，后續(xù)的k個輸入符號為a1a-2 AK時，堆棧頂部的歸約才可以為a。 我們只對k1的狀況感興趣，只需積極地檢索(展望)一個符號，就能決定是“前進(jìn)”還是

7、“回去”。 LR(1)項在原始的每個LR(0)項a中放置前向搜索符號a: A，并且被稱為LR(1)項。 每個LR(1)項要求對應(yīng)的活動前綴有效，并且確保在每個步驟的分析中得到規(guī)范句型的活動前綴。 LR(1)項和一個LR(1)項被定義為a、a、a VT，稱為前進(jìn)搜索器。 此時，a表示對分析的進(jìn)行沒有幫助的=時，a表示項目A-，a表示堆疊狀態(tài)的項目時，僅在當(dāng)前的輸入端子為a時進(jìn)行歸約。 回顧一下SLR(1)中遇到的問題。 S V=E S E V E V id E V、i0:sssv=esevidev、I2 : S V=E E V、v，第一項為動作2。 為了以ev簽約，所屬于=e的Follow集，=

8、是e的接班人：回顧在S V=E E=E，SLR(1)中遇到的問題，用ev規(guī)定的話， 我們得到的句型是E=，但語法中不存在以E=開頭的右句型，是有效項目，LR(1)項目a，a對活前綴有效：存在導(dǎo)出s*時a是w的最初符號，或者w是a是#，有效項目，例子S BBB bB | a是從最右開始s * bbbba BBB 因為我們根據(jù)有效項目的規(guī)約會得到規(guī)范句型的前綴。LR(1)項目的閉包運(yùn)算，I定義為LR(1)項目集，Closure(I )定義為： I的任意項目Closure(I )。 項目AB，a Closure(I )，b如果是生成式的話，任意的終端符號bFirst(a )，b，b Closure(

9、I )； 重復(fù)步驟2直到Closure(I )不增大，如果AB，a對活動前綴有效的話，對于b那樣的每個形狀的生成式，對于任何bFIRST(a )，b，b都有效。證明：如果項目a、b、a有效，則有規(guī)范的推導(dǎo)，其中I是項目集合，x是語法符號，并且在函數(shù)GO(I，x )是GO(I，X)CLOSURE(J )中，j的形式類似于AX的重復(fù)c的每個項目集合I和g的每個符號XDO IF GO(I，x ) x )加上c，UNTILC就不再增大END，例如S BB B bB | a，s，# I0 S BB，# B bB，b/a，s，# I1，sbb，# B bB，# B a，# I2將各Ik的下標(biāo)k設(shè)為分析表的

10、狀態(tài)動作ACTION和狀態(tài)轉(zhuǎn)移GOTO的結(jié)構(gòu)如果1 .項目Aa、b屬于Ik，并且GO(Ik，a)Ij、a是終止符號，則設(shè)為ACTIONk、a是“sj”。 2 .如果項目a和a屬于Ik，則操作a為“rj”； 在此，假設(shè)a是語法g的第j個生成式。 3 .在項目SS、#屬于Ik的情況下，將ACTIONk、#設(shè)為“acc”。 如果是GO(Ik，A)Ij，則設(shè)GOTOk、A=j。 5 .在分析表中，在規(guī)則14中不能填寫信息的空白欄中填寫“錯誤標(biāo)志”。 用上述算法構(gòu)筑的分析表，如果不存在多重定義的入口(即動作沖突)，則稱為語法g的一張規(guī)范的LR(1)分析表。 使用此分析表的分析器稱為規(guī)格的LR分析器。 有

11、規(guī)范的LR(1)分析表的語法稱為LR(1)語法。 LR(1)的狀態(tài)比SLR多，LR(0)SLR LR(1)沒有二義語法，例如5.13 (5.10 )的擴(kuò)展語法g(s)(0)ss(1)sbb() I1: SS，#，i23360sb，# BaB，# b，i:bab， I4: B b i73360b，#，I 83360 b ab，a/b，I 93360 b ab，#，I0: SS，# SBB，# BaB，a BaB，bb，ab。 按照上述表對例：aabab進(jìn)行分析的步驟狀態(tài)符號輸入串00 # aabab # 103 # aabab # 2033 # aabab # 30334 # aabab # 4

12、0338 # aabab # 5038 # abab bb # 1101 # s # ACC，例336 根據(jù)上表進(jìn)行分析的步驟狀態(tài)符號輸入串00 # abab # 103 # abab # 2034 # abab # 3038 # abab # 402 #的LALR(1)分析法大多數(shù)編程語言語法分析都使用lld來模仿可以使用LR(1)的# S V=E、# S E、# V E、=/# V id、=/# E V、#、I2 : S V=E、# E V、#、v、上一個示例。 一個是，先行搜索符號沒有用于移動到項目，搜索符號集不起作用。對于歸約項目，掃描不同的符號時，以不同的生成方式進(jìn)行歸約，LR(1)分析的缺點，通常是由于具有不同的前進(jìn)搜索符，所