1、自下而上語法分析對于產生語言來講，自上而下分析的方法是自然的。對于分析語言來講，自下而上分析的方法更自然，因為語法分析處理的對象一開始都是終結符組成的輸入序列，而不是文法的開始符號。同時，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要強，從而使得LR分析成為最為實用的語法分析方法。3.5.1 自下而上分析的基本方法思路：從句子開始，從左到右掃描，反復用產生式的左部替換產生式的右部、謀求對的匹配，最終得到文法的開始符號，或者發現一個錯誤。3.5.1.1 規范歸約與“剪句柄”定義3.13設是文法G的一個句型，若存在S =*>A，A =+>，則稱是句型相對于A的短語

2、，特別的，若有A，則稱是句型相對于產生式A的直接短語。一個句型的最左直接短語被稱為句柄。 # 直觀上，句型是一個完整結構，短語是句型中的某部分。S是一個句型，而不是一個短語。 短語形成的兩個要素：1從S可以推導出A，即S=*>A；2從A至少一次推導出，即A=+>。特征： 短語：以非終結符為根的子樹中所有從左到右排列的葉子； 直接短語：只有父子關系的樹中所有從左到右排列的葉子（樹高為2）； 句柄：最左邊父子關系樹中所有從左到右排列的葉子（句柄是唯一的）。問題：id1+id2是句型id1+id2*id3的一個短語嗎？答案：不是。因為： 沒有一個E的子樹，它的全部葉子是id1+id2；或

3、者 找不到某個E，使得E=>* E*id3，E=>+ id1+id2定義3.14 若是文法G的句子且滿足下述條件，則稱序列n，n-1，.，0是的一個最左歸約。 1. n= 2. 0=S（S是G 的開始符號）3. 對任何i(0<i<=n)，i-1是從i把句柄替換為相應產生式左部非終結符得到的。 #注意：最左歸約的逆過程是一個最右推導，分別稱最右推導和最左歸約為規范推導和規范歸約。 需要解決的問題： 確定右句型中將要歸約的子串（確定句柄）； 確定如何選擇正確的產生式進行歸約。3.5.1.2 移進-歸約分析器工作模式 解決方法：移進-歸約分析用一個?！坝涀　睂⒁獨w約句柄的前綴

4、，句柄未形成前移進，形成后歸約。移進-歸約分析器的工作模式：（不同的分析表決定了不同的分析方法）工作方法：放幻燈，每個幻燈片是一個格局。格局：（#棧，當前剩余輸入#，改變格局的動作）改變格局的動作： 移進（shift）：輸入序列中的終結符進棧。（匹配終結符） 歸約（reduce）：將棧頂句柄替換為對應的非終結符。（歸約產生式） 接受（accept）：宣告分析成功。 報錯（error）：發現語法錯誤，調用錯誤恢復例程。從移進-歸約分析過程中可以看出： 句柄總是在棧頂形成。這是因為在分析的過程中一旦形成某產生式的右部就立即進行歸約，而從左到右掃描輸入，最早形成的自然是最左的直接短語； 棧中保留的總

5、是一個右句型的前綴（加上若干終結符形成句型），稱為活前綴； 如果將每次歸約邏輯上認為是構造對應產生式的樹，則分析的全過程邏輯上就是從下到上構造一棵分析樹；反之，如果將每次歸約邏輯上認為是剪去假想分析樹上對應產生式的孩子，則分析的全過程邏輯上就是從下到上為分析樹剪句柄。需要解決的問題： （由分析表確定） 如何保證棧中總是活前綴 (正確移進) ； 如何確定棧頂已經形成句柄并選擇正確的產生式進行歸約(正確歸約)。3.5.2 LR分析LR分析的特點： 采用最一般的無回溯移進-歸約方法； 可分析的文法是LL文法的真超集； 能夠及時發現錯誤，快到從左到右掃描輸入序列的最大可能； 分析表較復雜，難以手工構造

6、。3.5.2.1 LR分析與LR文法<1> 移進-歸約分析表LR分析器的核心是LR分析表和驅動器。文法：EE-T | T TT*F | F F-F | id id-*#ETF0 s4 s51231 s6 acc2 r2 s7 r23 r4 r4 r44 r6 r6 r65 s4 s586 s4 s5937 s4 s5 108 r5 r5 r59 r1 s7 r110 r3 r3 r3actiongoto動作表（action）與轉移表（goto）：兩者都是二維數組，且行下標由稱之為狀態的整型數統一表示。動作表以終結符作為列下標，轉移表以非終結符作為列下標。action根據輸入確定改變

7、格局的動作，而goto僅指示非終結符的狀態轉移。故僅有動作表與輸入有關。<2> 格局與改變格局的動作開始格局：（#0，#，第一個動作）結束格局：（#0S，#，接受）出錯格局：（#，'#，報錯）改變格局的四個動作： actions, a= si：終結符進棧并轉向狀態i（移進） = rj：用第j個產生式的左部替換棧中的句柄（與共同完成歸約） = acc：接收 = blank：報錯 gotos, A = s'：在s狀態下遇到A轉移到狀態s'。事實上，和共同完成歸約。算法3.8 LR分析輸入 輸入序列和文法G的LR分析表action與goto輸出 若屬于L(G)，得

8、到的規范歸約，否則指出一個錯誤方法 初始格局為：（#0，#， 驅動器的第一個動作），其中0是初始狀態令ip指向#中的第一個終結符，top指向棧頂初始狀態；loop s := top; a := ip; case actions，a is shift s': push(a); push(s'); next(ip); - 移進，a與s'進棧且掃描下一輸入 reduce by A: pop(2*|); - 彈出棧頂的|個狀態和產生式右部的|個文法符號 s' := top; - 暴露出當前棧頂狀態s' push(A); - 產生式左部符號進棧 push(goto

9、(s'，A); - 新棧頂狀態進棧 write(A); - 完成歸約，跟蹤分析軌跡 accept: return; - 成功返回 others: error; - 出錯處理 end case;end loop; #習慣上在實際的算法中僅存放狀態，而在分析的格局中，僅顯示文法符號。定義3.15若為文法G構造的移進-歸約分析表中不含多重定義的條目，則稱G為LR(k)文法，分析器被稱為是LR(k)分析器，它所識別的語言被稱為LR(k)語言。L表示從左到右掃描輸入序列，R表示逆序的最右推導，k表示為確定下一動作向前看的終結符個數，一般情況下k<=1。當k=1時，簡稱LR。 #LR分析器是

10、一類分析器，根據分析表構造的不同，可以有LR(0)、SLR(1)、LALR(1)和LR(1)分析器。它們功能的強弱和構造的難度依次遞增。當k>1后，分析器的構造趨于復雜，一般情況下并不構造k>1的LR(k)分析器。3.5.2.2 構造SLR(1)分析器基本思路：首先構造一個可以識別文法G中所有活前綴的DFA，然后根據DFA和簡單的向前看信息構造SLR分析表。<1> 活前綴與LR（0）項目集族定義3.16 出現在移進-歸約分析器棧中的右句型的前綴，被稱為文法G的活前綴（viable prefix）。 #活前綴的兩個要素：1右句型的前綴；2已在分析棧中即：活前綴若干剩余輸入

11、（不在棧中）>右句型。意味著：在移進-歸約分析中，只要保證已掃描過的輸入序列可以歸約為一個活前綴，則分析到目前為止沒有錯誤。SLR分析器的關鍵：為文法G構造一個識別它的所有活前綴的DFA。構造步驟：NFADFA問題：識別活前綴的NFA是什么樣的？例：首先回顧產生式的狀態轉換圖。有EE+T和TT*F，則：1這些狀態轉換圖是NFA，因為從狀態1經+既到達狀態2也到達狀態4（為什么？）；2如何表示這些NFA的狀態？3在產生式的右部加入一個點“.”，用它在右部的位置來表示一個NFA的狀態。 例：產生式右部若有n個文法符號，則有n+1個LR(0)項目。G3.13的全部LR(0)項目： E.E-T

12、EE.-T EE-.T EE-T. E.T ET. T.T*F TT.*F TT*.F TT*F. T.F TF. F.-F F-.F F-F. F.id Fid.項目顯示了分析過程中看到了（移進了）產生式的多大部分：A.。不為空的項目稱為可移進項目，為空的項目稱為可歸約項目。項目如何識別活前綴：若T.T*F是識別活前綴的狀態，則TT.*F是識別活前綴T的狀態。產生式TT*F是識別活前綴T*F的NFA。即：每個產生式是一個識別活前綴的NFA，則每個項目是NFA的一個狀態；于是：所有產生式構成識別活前綴的NFA集合，將它們確定化，則得到識別活前綴的DFA。<2> 拓廣文法與識別活前綴

13、的DFAa拓廣文法G'：G' = GS'S其中：S'.S是識別S的初態，S'S.是識別S的終態。目的是使得最終構造的DFA狀態集中具有唯一初態和唯一終態。例：上例的拓廣文法增加的兩個項目分別為E'.E（初態）和E'E.（終態）。bNFA（項目）DFA（項目集）回顧詞法分析中“子集法”構造的兩個主要過程： _閉包(I)： I狀態集下不經任何字符a所能到達狀態的全體； smove（I，a）：I中所有經字符a狀態轉移所能直接到達的狀態全體。類似的兩個過程： closure(I)： I項目集下不經任何文法符號所能到達狀態的全體； goto（I，x

14、）：I中所有經文法符號x狀態轉移所能直接到達的項目的全體。定義3.18 項目集I的閉包closure(I)是這樣一個項目集1. I中的所有項目屬于closure(I)；2. 若A.B屬于closure(I)，則所有形如B.的項目屬于closure(I)；3. 其它任何項目不屬于closure(I)。 closure(I)的計算function closure（I） isbegin J := I； for 狀態J中每個項目A.B和文法G中每個產生式B loop if 項目B.不在J中 then 加入B.到J; end if； exit when 再沒有項目可以被加入到J中； end loop；

15、return（J）；end closure； 定義3.19 對所有屬于項目集I、且形如A.X的項目，令XNT，則goto（I，X）是所有形如AX.的項目。 #由定義可知，goto（I，X）集合中的項目有一個共同特點：項目中的“.”都不在產生式右部的最左邊，即A.中不為空，因為至少有一個X。設J=goto(I，X)，K=closure(J)，考察K-J中的項目A.，它們具有特點： "."在產生式右部最左邊（=）； 可由某個J計算而來（K-J=closure(J)-J）。定義3.20 項目S'.S和所有“.”不在產生式右部最左邊的項目稱為核心項目（kernel item

16、s），其它所有“.”在產生式右部最左邊的項目（不包括S'.S）稱為非核心項目（nonkernel items）。 #核心項目：J=goto(I，X)加S'.S非核心項目：K-J=closure(J)-J（特點是：可由某個J計算而得）識別活前綴的DFA的一個狀態，是NFA的一個狀態集合，稱為LR(0)項目集，DFA的所有狀態被稱為LR(0)項目集族。有了以上基礎，下邊給出計算識別G活前綴DFA的算法。算法3.9 計算文法G的、基于LR(0)項目的、識別活前綴的DFA輸入：拓廣文法G'輸出：DFA=(C, Dtran) - C是狀態集，Dtran是狀態轉移方法：I := c

17、losure(S' .S); 加入I到C中,且未標記;- 初態 while C中還有未標記狀態I- 對所有未標記狀態 loop 標記I; for I狀態下的每個文法符號x- 對當前狀態下所有x loop if J := closure(goto(I,x)非空- 有下一狀態轉移 then DtranI,x:= J; - 記錄狀態轉移 if J不在C中 - J是一個新狀態 then 加入J到C中，且未標記；- 加入新狀態到狀態集中 end if; end if; end loop; end loop; # 用算法3.9為文法G3.13'造識別活前綴的DFA，過程如下。計算DFA的初

18、態，I0=closure(E'.E)（略） 計算初態下的每個可能的狀態轉移，即考察I0中每個項目'.'后邊文法符號X，計算經X所能到達的下一狀態全體(closure(goto(I0,x)。 對所有還有下一狀態轉移的狀態Ii，反復計算closure(goto(Ii,X)，直到再沒有新狀態集加入。最終得到的DFA如圖3.19所示。其中：E'.E在I0中，I0是DFA的初態E'.E在I1中，I1是DFA的終態<3> 如何識別活前綴定義3.21 若存在最右推導S'=*>A=>12，則稱項目A1.2被稱為對活前綴1有效。 #一個活前

19、綴1對項目A1.2有效，具有兩層含意： 從文法開始符號，經1可到達該項目（項目所在狀態）； 在當前活前綴的情況下，該項目可指導下一步分析動作（A=>12）。活前綴與項目的關系： 一個項目可能對若干個活前綴有效考察圖3.19的項目集I5: F -.F F .-F F .id其中的項目F -.F對活前綴“T*-”、“E-”和“-”都有效。因為，存在最右推導: E'=>E=>T=>T*F=>T*-F （T*-.F） E'=>E=>E-T=>E-F=>E-F （E-.F） E'=>E=>T=>F=>-

20、F （-.F）直觀上：對項目集I中項目A1.2有效的所有活前綴，就是從初態出發所有可以到達I的路徑上的標記，即一條路徑標記，就是一個活前綴。若從初態到達I的路徑上有環，則I項目集中的項目對無窮多的活前綴有效。例如項目集I5中有環，所以I5中項目F -.F對無窮多個活前綴T*-，T*-，.，E-，E-，.，-，-,.均有效。 若干個項目可能對同一個活前綴有效 再考察I5：由于F-.F對T*-有效，因此，F .-F和F .id對T*-也有效： E'=>E=>T=>T*F=>T*-F （T*-.F） E'=>E=>T=>T*F=>T*-

21、F=>T*-F （T*-.-F） E'=>E=>T=>T*F=>T*-F=>T*-id （T*-.id）即項目集中的所有項目對同一活前綴有效。綜合，可以得出這樣一個結論，在同一項目集中的所有項目，對此項目集對應的所有活前綴均有效。也就是說，項目集中的每個項目均有同等權利指導下一步動作。 有效項目的意義* 到目前為止分析是正確的；* 指導下一步的分析：A1.2：移進2中第一個終結符，B.：按產生式B歸約。 項目集中的沖突和解決沖突的簡單方法：SLR(1)當一個項目集中同時存在：(a) A1.2和B.：下一步既可以移進又可以歸約，引起移進/歸約沖突。(b

22、) A.和B.：均可以指導下一步分析，引起歸約/歸約沖突。解決方法：簡單向前看一個終結符a(a) 對于移進/歸約沖突：若FIRST(2)FOLLOW(B)=，沖突可以解決。(b) 對于歸約/歸約沖突：若FOLLOW(A) FOLLOW(B)=，沖突可以解決。若沖突可以解決，則稱其為SLR(1)文法和SLR(1)分析表。否則需要尋求能力更強文法，即尋求新的項目集（LR(1)項目集）。<4> SLR分析表的構造算法3.10 構造SLR分析表輸入 基于G的LR(0)項目集的、識別活前綴的DFA=(C, Dtran)輸出 若G是SLR(1)文法，得到分析表action和goto，否則指出一個錯誤方法 按下述步驟構造分析表1.if DFA中有SLR(1)方法不能解決的移進/歸約和歸約/歸約沖突then error;elsefor 每個狀態轉移Dtrani, x=jloop if xT then actioni,x:= Sj; else