編譯原理課件-7

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

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

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

假定uAv=>uxv

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

LR分析器的邏輯結(jié)構(gòu)

一個(gè)輸入、一個(gè)輸出、一個(gè)棧、一個(gè)驅(qū)動(dòng)程序和一張分析表。id+id*id$SmXmSm-1Xm-1…S0LR驅(qū)動(dòng)程序動(dòng)作轉(zhuǎn)移actiongoto輸出分析動(dòng)作表（ACTION）：

移進(jìn)ai

和s=goto[sm,ai]進(jìn)棧action[sm,ai]=歸約rj

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

接收s=goto[sm-r

,A]

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

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

,ai]=si

則把a(bǔ)i,si=action[sm,ai]推進(jìn)棧。格局：（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,則分析結(jié)束。4.若action[sm,ai]=error,則轉(zhuǎn)出錯(cuò)處理程序。狀態(tài)ACTIONGOTOid+*()＄ETF0S5S41231S6acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R51E::=E+T2E::=T3T::=T*F4T::=F5F::=(E)6F::=id7.2LR(0)分析表的構(gòu)造

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

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

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

；2.活前綴含有句柄的部分符號(hào)，1

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

用圓點(diǎn)“”表示識(shí)別一個(gè)產(chǎn)生式右部符號(hào)到達(dá)的位子，若有規(guī)則AXYZ,則有下面四個(gè)項(xiàng)目：

AXYZ

AXYZ

AXYZ

AXYZ

另：A,A

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

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

closure(I)是從I出發(fā)用下面三個(gè)規(guī)則構(gòu)造的項(xiàng)目集:

1．I中每一個(gè)項(xiàng)目都屬于closure(I)。

2．若項(xiàng)目A→α·Bβ

closure(I)且B→γP

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

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

{VT∪VN}

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

其中,

J={A→αX·β|當(dāng)A→α·Xβ

I時(shí)}

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

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

∪VN}

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

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

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

S=>uAv=>uxyv其中，xy是規(guī)范句型uxyv的句柄，v是一個(gè)終結(jié)符號(hào)串。*項(xiàng)目A→x.y對(duì)活前綴ux有效的情況可用于判斷：當(dāng)發(fā)現(xiàn)ux已呈現(xiàn)于棧頂時(shí)，是應(yīng)該進(jìn)行歸約還是進(jìn)行移進(jìn)。一個(gè)活前綴w的有效項(xiàng)目集正是從項(xiàng)目集規(guī)范族對(duì)應(yīng)的DFA初態(tài)出發(fā)，經(jīng)由標(biāo)記為w的路徑所到達(dá)的那個(gè)項(xiàng)目集。E→E+TT→T*FT→FF→(E)F→id對(duì)于活前綴w＝E+T*，從初態(tài)I0出發(fā)，經(jīng)過E+T*路徑到達(dá)狀態(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識(shí)別活前綴的DFALR(0)文法如果文法G’的項(xiàng)目集規(guī)范族的每個(gè)項(xiàng)目集中不存在下述任何沖突項(xiàng)目：①移進(jìn)項(xiàng)目和歸約項(xiàng)目并存；②多個(gè)歸約項(xiàng)目并存；則稱文法G’為L(zhǎng)R(0)文法。當(dāng)且僅當(dāng)一個(gè)文法是LR(0)文法時(shí)，才能構(gòu)造出它的不含沖突動(dòng)作的LR(0)分析表。構(gòu)造LR(0)分析表的算法設(shè)一文法G‘的項(xiàng)目集規(guī)范族C＝{I0,I1,…,In},令其中每個(gè)項(xiàng)目集Ii的下標(biāo)作為分析器的狀態(tài)，令包含項(xiàng)目S’→.S的項(xiàng)目集Ik的下標(biāo)k為分析器的初態(tài)，則構(gòu)造LR(0)分析表的步驟為：若項(xiàng)目A→α.xβ∈Ii且goto(Ii,x)=Ij,x∈∑,則置ACTION[i,x]=Si，即“將狀態(tài)j、符號(hào)x移進(jìn)?！?；但若x∈VN，則僅置GOTO[i,x]=j。若項(xiàng)目A→α.∈Ii，對(duì)于任何輸入符號(hào)a∈(∑∪{$})，則置ACTION[i,a]=rj，即“用第j條產(chǎn)生式A→α進(jìn)行歸約”。若項(xiàng)目S’→S.∈Ik，則置ACTION[k,$]=“接收”。分析表中凡不能用規(guī)則①～③填入信息的元素均置上ERROR（用空白表示）。構(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)分析表。7.3SLR分析表的構(gòu)造LR(0)文法所構(gòu)造出來的識(shí)別活前綴的DFA中每個(gè)狀態(tài)（每個(gè)項(xiàng)目集）不能包含沖突項(xiàng)目。許多沖突動(dòng)作都可以通過考察有關(guān)非終結(jié)符的FOLLOW集而得到解決，即通過向前查看一個(gè)輸入符號(hào)來協(xié)助解決沖突。例如：沖突項(xiàng)目集合Ii：

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

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

和j個(gè)歸約項(xiàng)目

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

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

[A→α.β,a]

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

LALR（向