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

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

3、”； 如果GO(Ik，A)Ij和a是非終結(jié)符號(hào)，則GOTOk和A=j。 5 .在分析表中不能按規(guī)則1至4填寫(xiě)信息的空白單元格全部標(biāo)記“錯(cuò)誤標(biāo)志”。 上述構(gòu)筑的ACTION和GOTO表如果不包含多條目，則將該語(yǔ)法稱為SLR(1)語(yǔ)法。 使用SLR表的分析器稱為SLR分析器。 每個(gè)SLR(1)語(yǔ)法不是二義的。 然而，許多無(wú)二義語(yǔ)法并非SLR(1)，我們考慮了示例5.11次擴(kuò)展語(yǔ)法： (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。 可以對(duì)從FOLLOW集合得到的先行碼集合進(jìn)行修正，該語(yǔ)法的LR(0)項(xiàng)集規(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方法中，在項(xiàng)目集Ii中包含項(xiàng)目a .接著輸入符號(hào)aFOL

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

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

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

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

9、I )； 重復(fù)步驟2直到Closure(I )不增大，如果AB，a對(duì)活動(dòng)前綴有效的話，對(duì)于b那樣的每個(gè)形狀的生成式，對(duì)于任何bFIRST(a )，b，b都有效。證明：如果項(xiàng)目a、b、a有效，則有規(guī)范的推導(dǎo)，其中I是項(xiàng)目集合，x是語(yǔ)法符號(hào)，并且在函數(shù)GO(I，x )是GO(I，X)CLOSURE(J )中，j的形式類似于AX的重復(fù)c的每個(gè)項(xiàng)目集合I和g的每個(gè)符號(hào)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)動(dòng)作ACTION和狀態(tài)轉(zhuǎn)移GOTO的結(jié)構(gòu)如果1 .項(xiàng)目Aa、b屬于Ik，并且GO(Ik，a)Ij、a是終止符號(hào)，則設(shè)為ACTIONk、a是“sj”。 2 .如果項(xiàng)目a和a屬于Ik，則操作a為“rj”； 在此，假設(shè)a是語(yǔ)法g的第j個(gè)生成式。 3 .在項(xiàng)目SS、#屬于Ik的情況下，將ACTIONk、#設(shè)為“acc”。 如果是GO(Ik，A)Ij，則設(shè)GOTOk、A=j。 5 .在分析表中，在規(guī)則14中不能填寫(xiě)信息的空白欄中填寫(xiě)“錯(cuò)誤標(biāo)志”。 用上述算法構(gòu)筑的分析表，如果不存在多重定義的入口(即動(dòng)作沖突)，則稱為語(yǔ)法g的一張規(guī)范的LR(1)分析表。 使用此分析表的分析器稱為規(guī)格的LR分析器。 有

11、規(guī)范的LR(1)分析表的語(yǔ)法稱為L(zhǎng)R(1)語(yǔ)法。 LR(1)的狀態(tài)比SLR多，LR(0)SLR LR(1)沒(méi)有二義語(yǔ)法，例如5.13 (5.10 )的擴(kuò)展語(yǔ)法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。 按照上述表對(duì)例：aabab進(jìn)行分析的步驟狀態(tài)符號(hào)輸入串00 # aabab # 103 # aabab # 2033 # aabab # 30334 # aabab # 4

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