編譯原理課件-7

第7章自下而上的LR(k)分析方法

LR(k)分析器是這樣一種分析程序：它總是按從左至右方式掃描輸入串，并按自下而上方式進行規(guī)范歸約。在這種分析過程中，它至多只向前查看k個輸入符號就能確定當前的動作是移進還是歸約；若動作為歸約，則它還能唯一地選中一個產(chǎn)生式去歸約當前已識別出的句柄（這里稱為活前綴）。若該輸入串是給定文法的一個句子，則它總可以把這個輸入串歸約到文法的開始符號；否則報錯，指明它不是該文法的一個句子。7.1LR(k)文法和LR(k)分析方法7.2LR(0)分析表的構造7.3SLR分析表的構造7.4規(guī)范LR(1)分析表的構造7.5LALR分析表的構造7.6無二義性規(guī)則的使用7.7小結7.1LR(k)文法和LR(k)分析器給定文法G，S是其開始符號。考慮該文法中一個終結符號串w的一個規(guī)范推導

S=>w1=>w2=>…=>w

假定uAv=>uxv

是上述推導中的一個推導步。A::=x是用于該推導步的產(chǎn)生式。對于每一個這樣的推導和推導步，僅通過掃描ux和查看v中開始的k個符號就能唯一確定選用產(chǎn)生式A::=x，我們就稱G為LR(k)文法。

LR分析器的邏輯結構

一個輸入、一個輸出、一個棧、一個驅動程序和一張分析表。id+id*id$SmXmSm-1Xm-1…S0LR驅動程序動作轉移actiongoto輸出分析動作表（ACTION）：

移進ai

和s=goto[sm,ai]進棧action[sm,ai]=歸約rj

:A::=Xm-r+1Xm-r+2…Xm

接收s=goto[sm-r

,A]

錯誤處理LR分析器的分析表：分析動作表和goto函數(shù)表GOTO函數(shù)表：GOTO[si,xj]規(guī)定了當狀態(tài)si面臨文法符號xj時所應到達的下一狀態(tài)。格局（構形）：（棧中符號序列，剩余輸入符號串）開始：（s0,a1a2……an$)

中間：（s0x1s1x2s2…xmsm,aiai+1…an$)LR分析器的工作過程1.若action[sm

,ai]=si

則把ai,si=action[sm,ai]推進棧。格局：（s0x1s1x2s2…xmsm

aisi,ai+1…an$)2.若action[sm

,ai]=r

(A::=xm-r+1xm-r+2…xm),則格局：（s0x1s1x2s2…xm-rsm-rAs,aiai+1…an$)其中，s=goto[sm-r,A]3.若action[sm

，$]=accept,則分析結束。4.若action[sm,ai]=error,則轉出錯處理程序。狀態(tài)ACTIONGOTOid+*()＄ETF0S5S41231S6acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R51E::=E+T2E::=T3T::=T*F4T::=F5F::=(E)6F::=id7.2LR(0)分析表的構造

LR分析方法的基本原理是：把每個句柄（某個產(chǎn)生式的右部）的識別過程劃分為若干狀態(tài)，每個狀態(tài)從左至右識別句柄中的一個符號，若干個狀態(tài)就可識別句柄左端的一部分符號。識別了句柄的這一部分就相當于識別了當前規(guī)范句型的左起部分——規(guī)范句型的活前綴。因而，對句柄的識別就變成了對規(guī)范句型活前綴的識別。

LR(0)分析程序，即在分析的每一步，僅根據(jù)當前的棧頂狀態(tài)就能確定應執(zhí)行何種分析動作，而無須向前查看任何輸入符號。規(guī)范句型的活前綴

活前綴（ViablePrefix）是指規(guī)范句型的一個前綴，它不包含該句型的句柄右邊的任何符號?；钋熬Y和句柄的關系：1.活前綴不含有句柄的任何符號，

；2.活前綴含有句柄的部分符號，1

；3.活前綴已含有句柄的全部符號，。LR(0)項目

用圓點“”表示識別一個產(chǎn)生式右部符號到達的位子，若有規(guī)則AXYZ,則有下面四個項目：

AXYZ

AXYZ

AXYZ

AXYZ

另：A,A

以上項目稱作LR(0)項目。項目指明在分析過程的某一時刻，已經(jīng)看到一個產(chǎn)生式的多少。文法G的拓廣文法給定文法G，S是其開始符號，我們構造一個與S相關的文法G’：它包含整個G，而且外加一個新產(chǎn)生式S’::=S。其中，S’是G’的開始符號，稱G’為G的拓廣文法。AaaVT

移進項目ABBVN待歸約項目A歸約項目S′S接收項目CLOSURE(I)函數(shù)設I是文法G的一個LR(0)項目集合

closure(I)是從I出發(fā)用下面三個規(guī)則構造的項目集:

1．I中每一個項目都屬于closure(I)。

2．若項目A→α·Bβ

closure(I)且B→γP

則將B→·γ加進closure(I)中。

3．重復執(zhí)行(2)直到closure(I)不再增大為止。goto(I,X)函數(shù)若I是G的一個LR(0)項目集,X

{VT∪VN}

則goto(I,X)=closure(J)

其中,

J={A→αX·β|當A→α·Xβ

I時}

goto(I,X)稱為轉移函數(shù)。項目A→αX·β稱為A→α·Xβ的后繼。I:A→α·XβJ:A→αX·βXLR(0)項目集規(guī)范族LR(0)項目集規(guī)范族的構造

PROCEDUREITEMS(G);BEGINC:={closure(S→S)};REPEATFORIC和X{VT

∪VN}

把goto(I,X)加入到C中

UNTILC不再增大END;最后得到的C就是拓廣文法G’的LR(0)項目集規(guī)范族。DFAm=(VT∪VN∪{S},Q{項目集規(guī)范族}，

q0=closure{S→S},Q,=go(I,X))它識別文法G的所有活前綴。有效項目一個項目[A→x.y]稱為對某個活前綴ux是有效的，當且僅當存在某個規(guī)范推導

S=>uAv=>uxyv其中，xy是規(guī)范句型uxyv的句柄，v是一個終結符號串。*項目A→x.y對活前綴ux有效的情況可用于判斷：當發(fā)現(xiàn)ux已呈現(xiàn)于棧頂時，是應該進行歸約還是進行移進。一個活前綴w的有效項目集正是從項目集規(guī)范族對應的DFA初態(tài)出發(fā)，經(jīng)由標記為w的路徑所到達的那個項目集。E→E+TT→T*FT→FF→(E)F→id對于活前綴w＝E+T*，從初態(tài)I0出發(fā)，經(jīng)過E+T*路徑到達狀態(tài)集I7I7：

T→T*.FF→.(E)

F→.id①E’=>E=>E+T=>E+T*F=>E+T*id=>E+T*F*id②E’=>E=>E+T=>E+T*F=>E+T*(E)③E’=>E=>E+T=>E+T*F=>E+T*idI0:S’→.SS→.A

A→.aAb

A→.cS→.B

B→.aBb

B→.dI1:S’→S.I2:S→A.I3:S→B.I5:A→c.I6:B→d.I7:A→aA.bI8:A→aAb.I9:B→aB.bI10:B→aBb.I4:

A→a.Ab

A→.aAb

A→.cB→a.Bb

B→.aBb

B→.dSABacdcdabABb文法G(S)：S→A|BA→aAb|cB→aBb|d拓廣文G’(S)：0S’→S1S→A2S→B3A→aAb4A→c5B→aBb6B→d識別活前綴的DFALR(0)文法如果文法G’的項目集規(guī)范族的每個項目集中不存在下述任何沖突項目：①移進項目和歸約項目并存；②多個歸約項目并存；則稱文法G’為LR(0)文法。當且僅當一個文法是LR(0)文法時，才能構造出它的不含沖突動作的LR(0)分析表。構造LR(0)分析表的算法設一文法G‘的項目集規(guī)范族C＝{I0,I1,…,In},令其中每個項目集Ii的下標作為分析器的狀態(tài)，令包含項目S’→.S的項目集Ik的下標k為分析器的初態(tài)，則構造LR(0)分析表的步驟為：若項目A→α.xβ∈Ii且goto(Ii,x)=Ij,x∈∑,則置ACTION[i,x]=Si，即“將狀態(tài)j、符號x移進?！保坏魓∈VN，則僅置GOTO[i,x]=j。若項目A→α.∈Ii，對于任何輸入符號a∈(∑∪{$})，則置ACTION[i,a]=rj，即“用第j條產(chǎn)生式A→α進行歸約”。若項目S’→S.∈Ik，則置ACTION[k,$]=“接收”。分析表中凡不能用規(guī)則①～③填入信息的元素均置上ERROR（用空白表示）。構造LR(0)分析表的步驟小結①寫出給定文法G的拓廣文法G’；②寫出文法G’的基本LR(0)項目——G’的LR(0)項目集；③利用CLOSURE和GOTO函數(shù)，求出相應的LR(0)項目集規(guī)范族C；④構造識別該文法全部活前綴的DFA；⑤根據(jù)算法構造LR(0)分析表。7.3SLR分析表的構造LR(0)文法所構造出來的識別活前綴的DFA中每個狀態(tài)（每個項目集）不能包含沖突項目。許多沖突動作都可以通過考察有關非終結符的FOLLOW集而得到解決，即通過向前查看一個輸入符號來協(xié)助解決沖突。例如：沖突項目集合Ii：

{A→α.bβ,B→γ.,C→γ.}一般，設LR(0)項目集規(guī)范族的某個項目集I中含有i個移進項目

A1→α1.a1β1A2→α1.a2β2…Ai→αi.aiβi

和j個歸約項目

B1→γ1.B2→γ2.…Bj→γj.

若已知集合{a1,a2,…,ai}，F(xiàn)OLLOW(B1)，…，F(xiàn)OLLOW(Bj)兩輛不相交，且沒有兩個FOLLOW集含有$，則I中的沖突動作可通過查看當前輸入符號a屬于上述j+1個集合中的哪一個集合而獲得解決，即若a∈{a1,a2,…,ai}，則移進a；若A∈FOLLOW(Bk），k=1,2,…,j，則用產(chǎn)生式Bk進行歸約；其它則報錯。這種解決沖突動作的方法成為SLR(1)解決方法。構造SLR(1)分析表的算法設一文法G‘的項目集規(guī)范族C＝{I0,I1,…,In},令其中每個項目集Ii的下標作為分析器的狀態(tài)，令包含項目S’→.S的項目集Ik的下標k為分析器的初態(tài)，則構造SLR(1)分析表的步驟為：若項目A→α.xβ∈Ii且goto(Ii,x)=Ij,x∈∑,則置ACTION[i,x]=Si，即“將狀態(tài)j、符號x移進?！?；但若x∈VN，則僅置GOTO[i,x]=j。若項目A→α.∈Ii，對于任何輸入符號a∈FOLLOW(A)，則置ACTION[i,a]=rj，即“用第j條產(chǎn)生式A→α進行歸約”。若項目S’→S.∈Ik，則置ACTION[k,$]=“接收”。分析表中凡不能用規(guī)則①～③填入信息的元素均置上ERROR（用空白表示）。能夠構造出SLR分析表的文法G稱為SLR(1)文法7.4規(guī)范LR(1)分析表的構造（略）重新定義項目，使得每個項目包含兩個部分，第一部分就是原來的項目本身，第二部分是由一個終結符號（可能為$）組成。重新定義后的項目稱為LR(1)項目，其一般形式為

[A→α.β,a]

項目中第二部分稱為向前看符號。對于β＝ε的項目[A→α.,a]，其作用在于：當相應的狀態(tài)呈現(xiàn)于棧頂且下一個輸入符號為a時，才可選用產(chǎn)生式A→α，將棧頂?shù)摩烈?guī)約到A。構造規(guī)范LR(1)分析表的算法設一文法G‘的LR(1)項目集族C＝{I0,I1,…,In},令其中每個項目集Ii的下標作為分析器的狀態(tài)，令包含項目[S’→.S,$]的項目集Ik的下標k為分析器的初態(tài)，則構造規(guī)范LR(1)分析表的步驟為：若項目[A→α.xβ,b]∈Ii且goto(Ii,x)=Ij,x∈∑,則置ACTION[i,x]=Si，即“將狀態(tài)j、符號x移進?！?；但若x∈VN，則僅置GOTO[i,x]=j。若項目[A→α.,a]∈Ii，則置ACTION[i,a]=rj，即“用第j條產(chǎn)生式A→α進行歸約”。若項目[S’→S.,$]∈Ik，則置ACTION[k,$]=“接收”。分析表中凡不能用規(guī)則①～③填入信息的元素均置上ERROR（用空白表示）。能夠構造出規(guī)范LR分析表的文法G稱為規(guī)范LR(1)文法7.5LALR分析表的構造（略）

LALR（向