編譯原理SLR分析法

會(huì)計(jì)學(xué)1編譯原理SLR分析法4.5.3SLR（1）分析法將文法拓廣并對規(guī)則進(jìn)行編號(hào)

直接構(gòu)造出識(shí)別文法規(guī)范句型活前綴的DFA下如圖所示。0.E'→E1.E→E+T2.E→T3.T→T*F4.

T→F5.

F→(E)6.

F→id第1頁/共57頁E'→·EE→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI0:EI1:E'→E·E→E·+TI2:E→T·T→T·*FTI3:T→F·FF→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI4:((FTI5:F→id·idE→E+·TT→·T*FT→·FF→·(E)F→·idI6:+F(idI7:T→T*·FF→·(E)F→·id(idid*I8:F→

(E·)E→E·+TE+0E'→E1E→E+T2E→T3T→T*F4

T→F5

F→(E)6

F→id第2頁/共57頁E→E+·TT→·T*FT→·FF→·(E)F→·idI6:idI8:F→

(E·)E→E·+TE+TI9:E→E+T·T→T·*T*FI10:T→T*F·I11:F→(E)·)識(shí)別表達(dá)式文法活前綴的DFAE'→·EE→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI0:EI1:E'→E·E→E·+TI2:E→T·T→T·*FTI3:T→F·FF→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI4:((FTI5:F→id·id+F(idI7:T→T*·FF→·(E)F→·id(idid*E+第3頁/共57頁4.5.3SLR（1）分析法

不難看出在I1，I2，I9中既含有移進(jìn)項(xiàng)目，又含有歸約項(xiàng)目，因而這個(gè)表達(dá)式的文法不是LR(0)文法。

根據(jù)構(gòu)造LR(0)分析表的方法，構(gòu)造出的LR(0)分析表中在2狀態(tài)和9狀態(tài)下面臨輸入符號(hào)‘*’時(shí)含多重定義元素，見下表。第4頁/共57頁表達(dá)式文法的LR(0)分析表012345S5S4S6accS5S4r2r2S7r2

r2r2r2r4r4r4r4r4r4123823r6r6r6r6r6r6GOTO狀態(tài)ACTIONid+*()$ETF678910S5S4S5S4S6S11r1r1S7r1

r1r1r1r3r3r3r3r3r3r5r5r5r5r5r5119310第5頁/共57頁4.5.3SLR（1）分析法

為了對語言句子進(jìn)行確定性的分析，需要解決移進(jìn)—?dú)w約或歸約—?dú)w約沖突。我們采用對含有沖突的項(xiàng)目集向前查看一個(gè)輸入符號(hào)的辦法來解決沖突，

這種分析法稱為簡單的LR分析法，即SLR(1)分析法。第6頁/共57頁4.5.3SLR（1）分析法

仔細(xì)分析構(gòu)造LR(0)分析表的方法，容易看出使分析表出現(xiàn)多重定義的原因在于其中的規(guī)則2，即對于每一個(gè)項(xiàng)目集Ik中的歸約項(xiàng)目A→α?，不管當(dāng)前輸入符號(hào)是什么，都將ACTION表中第K行的各個(gè)元素均置為rj，其中j為規(guī)則A→α的編號(hào)。

第7頁/共57頁4.5.3SLR（1）分析法

因此，當(dāng)一個(gè)LR(0)項(xiàng)目集規(guī)范族中存在一個(gè)含移進(jìn)—?dú)w約沖突和歸約—?dú)w約沖突的項(xiàng)目集時(shí)

則在分析表第K行中遇輸入符號(hào)b必然會(huì)出現(xiàn)多重定義元素。

IK={X→δ·bB,A→α·,B→r·}

對含沖突的項(xiàng)目集，僅根據(jù)LR(0)項(xiàng)目本身的信息是無法解決沖突的。需要向前查看一個(gè)輸入符號(hào)以考察當(dāng)前所處的環(huán)境。第8頁/共57頁4.5.3SLR（1）分析法

對歸約項(xiàng)目A→α?和B→γ?

，只需要考察當(dāng)將句柄α或γ歸約為A或B時(shí)，直接跟在A或B后的終結(jié)符的集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移進(jìn)符號(hào)b，即滿足：IK={X→δ·bB,A→α·,B→r·}FOLLOW(A)∩FOLLOW(B)=Φ

FOLLOW(B)∩=ΦFOLLOW(A)∩=Φ第9頁/共57頁4.5.3SLR（1）分析法

那么，當(dāng)狀態(tài)K面臨輸入符號(hào)a時(shí)，可按以下規(guī)則解決沖突：(1)若a=b則移進(jìn)(2)若aFOLLOW(A)，則用規(guī)則

A進(jìn)行歸約。

(3)若aFOLLOW(B)，則用規(guī)則

Br進(jìn)行歸約。(4)此外報(bào)錯(cuò)。第10頁/共57頁4.5.3SLR（1）分析法

一般而言，若一個(gè)LR(0)項(xiàng)目集I中有m個(gè)移進(jìn)項(xiàng)目和n個(gè)歸約項(xiàng)目時(shí)：

對所有移進(jìn)項(xiàng)目向前看一符號(hào)集合{a1,a2,…,am}和FOLLOW(B1),FOLLOW(B2),…，F(xiàn)OLLOW(Bn)兩兩相交為Φ時(shí)，則項(xiàng)目集I中沖突仍可用下述規(guī)則解決沖突。I:{A1→α1·a1β1,A2→α2·a2β2,

…,Am→αm·amβm,B1→r1·,B2→r2·,…,Bn→rn·}第11頁/共57頁4.5.3SLR（1）分析法設(shè)a為當(dāng)前輸入符：(1)若a∈{a1,a2,…,am}則移進(jìn)。(3)此外報(bào)錯(cuò)。(2)若a∈FOLLOW(Bi),i=1,2,…,n,

則用Bi→ri進(jìn)行歸約。

這種用來解決分析動(dòng)作沖突的方法稱為SLR(1)方法。第12頁/共57頁4.5.3SLR（1）分析法

現(xiàn)在分別考察上例中的三個(gè)項(xiàng)目集I1,I2,I9中沖突能否用SLR(1)方法解決。

由于FOLLOW(E')={$}∩{+}=Φ

，且E'→E?是“接受”項(xiàng)目，所以I1中的接受—移進(jìn)沖突可以用SLR(1)方法解決。

如果對于一個(gè)文法的某些LR(0)項(xiàng)目集或LR(0)分析表中所含有的動(dòng)作沖突都能用SLR(1)方法解決，則稱這個(gè)文法是SLR(1)文法。

I1={E'→E·,E→E·+T}第13頁/共57頁4.5.3SLR（1）分析法

由于FOLLOW(E)={+,),$}∩{*}=Φ,因此面臨輸入符為‘＋’,‘）’,‘$’時(shí)，用規(guī)則E→T進(jìn)行歸約，當(dāng)面臨輸入符‘*’時(shí)，則移進(jìn)，I2中移進(jìn)—?dú)w約沖突可以用SLR(1)方法解決。

與I2中情況類似，其項(xiàng)目集中移進(jìn)—?dú)w約沖突可用SLR(1)方法解決。因此該文法是SLR(1)文法。I2={E→T·,T→T·*F}I9={E→E+T·,T→T·*F}第14頁/共57頁4.5.3SLR（1）分析法SLR(1)分析表的構(gòu)造與LR(0)分析表的構(gòu)造基本相同。僅對LR(0)分析表構(gòu)造算法中的規(guī)則2進(jìn)行如下修改：

若歸約項(xiàng)目A→α?屬于Ik，則對任何終結(jié)符a∈FOLLOW(A)置ACTION[k,a]=rj，其中A→α為文法的第j條規(guī)則。第15頁/共57頁4.5.3SLR（1）分析法

按上述方法對前例中的算術(shù)表達(dá)式文法構(gòu)造出SLR(1)分析表如表所示：FOLLOW(E')={$}FOLLOW(E)={+,),$}0E'→E1E→E+T2E→T3T→T*F4

T→F5

F→(E)6

F→idFOLLOW(T)={+,),$,*}第16頁/共57頁E→E+·TT→·T*FT→·FF→·(E)F→·idI6:idI8:F→

(E·)E→E·+TE+TI9:E→E+T·T→T·*T*FI10:T→T*F·I11:F→(E)·)識(shí)別表達(dá)式文法活前綴的DFAE'→·EE→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI0:EI1:E'→E·E→E·+TI2:E→T·T→T·*FTI3:T→F·FF→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI4:((FTI5:F→id·id+F(idI7:T→T*·FF→·(E)F→·id(idid*E+第17頁/共57頁G[E]的SLR(1)分析表GOTO狀態(tài)ACTIONid+*()$ETF012345S5S4S6accS5S4r2S7r2r2r4r4r4r4123823r6r6r6r6678910S5S4S5S4S6S11r1S7r1r1r3r3r3r3r5r5r5r5119310第18頁/共57頁4.5.3SLR（1）分析法

若文法的SLR(1)分析表不含多重定義元素，則稱文法G為SLR(1)文法。例1設(shè)有拓廣文法G[S′]0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a第19頁/共57頁4.5.3SLR（1）分析法(1)構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA。(2)判斷該文法是否SLR(1)文法，若是，構(gòu)造SLR(1)分析表，若不是，請說明理由。

該文法的LR(0)項(xiàng)目集規(guī)范族及轉(zhuǎn)換函數(shù)如下圖所示:第20頁/共57頁I0:S'→·SS→·SbS→·bAaSI1:S'→S·S→S·bbI2:S→b·AaA→·aScA→·aSbA→·aI3:S→Sb·bI4:S→bA·aS→·SbS→·bAaA→a·ScA→a·SbA→a·I5:abAaI6:S→bAa·I7:S→S·bA→aS·cA→aS·bSI8:A→aSc·文法G[S']LR(0)項(xiàng)目集及轉(zhuǎn)換函數(shù)I9:A→aSb·S→Sb·cb0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a第21頁/共57頁4.5.3SLR（1）分析法

分析所有這些項(xiàng)目集，可知在項(xiàng)目集I1，I5中存在移進(jìn)—?dú)w約沖突，I9中存在歸約—?dú)w約沖突，因此該文法不是LR(0)文法。

考慮含沖突的項(xiàng)目集能否用SLR(1)方法解決。0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→aFOLLOW(A)={a}FOLLOW(S)={b,c,$}FOLLOW(S')={$}第22頁/共57頁4.5.3SLR（1）分析法

由于有FOLLOW(S')∩={$}∩=Φ，I1中的移進(jìn)—?dú)w約沖突可以用SLR(1)方法解決。

由于有FOLLOW(A)∩={a}∩=Φ，I5中的移進(jìn)—?dú)w約沖突可以用SLR(1)方法解決。I1={S'→S·,S→S·b}I5={A→a·,S→·bAa}第23頁/共57頁4.5.3SLR（1）分析法

由于有FOLLOW(A)∩FOLLOW(S)={a}∩{b,c,$}=Φ,I9中的歸約—?dú)w約沖突也可用SLR(1)方法解決。

所以該文法是SLR(1)文法。相應(yīng)的SLR(1)分析表如下表:I9={A→aSb·,S→Sb·}第24頁/共57頁4.5.3SLR（1）分析法0S2112345r1r1r1r2r2r2S5r4r1r1r146789S3accS9S8S6r5S2r37狀態(tài)GOTOACTIONabc$SAG[S]的SLR(1)分析表0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a第25頁/共57頁I0:S′→·SS→·SbS→·bAaSI1:S′→S·S→S·bbI2:S→b·AaA→·aScA→·aSbA→·aI3:S→Sb·bI4:S→bA·aS→·SbS→·bAaA→a·ScA→a·SbA→a·I5:abAaI6:S→bAa·I7:S→S·bA→aS·cA→aS·bSI8:A→aSc·文法G[S’]LR(0)項(xiàng)目集及轉(zhuǎn)換函數(shù)I9:A→aSb·S→Sb·cb0.S′→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a第26頁/共57頁4.5.3SLR（1）分析法SLR(1)分析法是一種簡單而實(shí)用的方法,其造表演算法簡單,狀態(tài)數(shù)目少,且大多數(shù)程序設(shè)計(jì)語言都可以用SLR(1)文法來定義。

但是仍存在這樣一些文法，其項(xiàng)目集中的移進(jìn)一歸約沖突或歸約—?dú)w約沖突不能用SLR(1)方法解決。第27頁/共57頁4.5.3SLR（1）分析法例2下列拓廣文法G′為

我們首先用S'→?S作為初態(tài)集的項(xiàng)目，然后用閉包函數(shù)和轉(zhuǎn)換函數(shù)構(gòu)造識(shí)別文法G'活前綴的DFA如下圖所示。0.S'→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L第28頁/共57頁I0:S→L=·RL→·*RL→·iR→·LS'→·SS→·L=RS→·RL→·*RL→·iR→·LSI1:S'→S·I2:S→L·=RR→L·LI3:S→R·RL→*·RL→·iR→·LL→·*RI4:**iiI5:L→i·I6:=*I7:L→*R·RiLI8:R→L·LRI9:S→L=R·LR(0)識(shí)別G'活前綴的DFA0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L第29頁/共57頁4.5.3SLR（1）分析法可以發(fā)現(xiàn)項(xiàng)目集I2中存在移進(jìn)和歸約沖突：

因此，I2中移進(jìn)和歸約沖突不能用SLR(1)方法解決。SL=R

*R=RSRI2={S→L·=RR→L·}由于FOLLOW(R)∩{=}＝{=,$}∩{=}≠Ф0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L第30頁/共57頁4.5.3SLR（1）分析法1.SLR(1)方法為什么不能解決I2中的移進(jìn)和歸約沖突?2.怎樣解決I2中的移進(jìn)和歸約沖突?問題:第31頁/共57頁4.5.3SLR（1）分析法

由于用SLR(1)方法解決動(dòng)作沖突時(shí)，它僅孤立地考察對于歸約項(xiàng)目A→α?，只要當(dāng)前面臨輸入符號(hào)a∈Follow(A)時(shí)，就確定使用規(guī)則A→α進(jìn)行歸約，而沒有考察符號(hào)串α所在規(guī)范句型的環(huán)境。

Ii:A→α?I0I1Ii$δαaa'a"…I0I1Ij$δAaa'a"…第32頁/共57頁4.5.3SLR（1）分析法

因?yàn)槿绻麠＠锏姆?hào)串為$δα，歸約后變?yōu)?δA，當(dāng)前讀到的輸入符號(hào)是a，若文法中不存在以δAa為前綴的規(guī)范句型，那么，這種歸約無效。

例如，我們考查規(guī)范句型i＝i的SLR(1)分析過程：

第33頁/共57頁I0:S→L=·RL→·*RL→·iR→·LS'→·SS→·L=RS→·RL→·*RL→·iR→·LSI1:S′→S·I2:S→L·=RR→L·LI3:S→R·RL→*·RL→·iR→·LL→·*RI4:**iiI5:L→i·I6:=*I7:L→*R·RiLI8:R→L·LRI9:S→L=R·LR(0)識(shí)別G’活前綴的DFA0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L第34頁/共57頁4.5.3SLR（1）分析法狀態(tài)棧符號(hào)棧輸入串0$i=i$05$i=i$02$L=i$03$R=i$

不難看出當(dāng)狀態(tài)2呈現(xiàn)于棧頂且面臨的輸入符號(hào)是＝時(shí)，由于這個(gè)文法不含有以R＝為前綴的規(guī)范句型，因此用R→L進(jìn)行的歸約是無效歸約。第35頁/共57頁4.5.3SLR（1）分析法∵SL=R*R=R

也就是說，并不是FOLLOW(R)中的每個(gè)元素在含R的所有句型中在R的后面都會(huì)出現(xiàn)。解決這一問題的方法是采用LR(1)分析法。

第36頁/共57頁4.5.4LR（1）分析法

在分析過程中，當(dāng)試圖用某一規(guī)則A→α歸約棧頂?shù)姆?hào)串α?xí)r不僅應(yīng)該察看棧中符號(hào)串δα，還應(yīng)向前掃視一個(gè)輸入符號(hào)a，只有當(dāng)δAa的確構(gòu)成文法某一規(guī)范句型的前綴時(shí)，才能用此規(guī)則進(jìn)行歸約。LR(1)分析法的思想:第37頁/共57頁4.5.4LR（1）分析法

為此，我們可以考慮在原來LR(0)項(xiàng)目集中;增加更多的展望信息，這些展望信息有助于克服動(dòng)作沖突和排除無效歸約。也就是需要重新定義項(xiàng)目，稱之為LR(1)項(xiàng)目。

一個(gè)LR(1)項(xiàng)目是一個(gè)二元組[A→α?β，a]第38頁/共57頁4.5.4LR（1）分析法

當(dāng)β＝ε時(shí)，搜索符a明確指出當(dāng)[A→α?β，a]是棧頂狀態(tài)的一個(gè)LR(1)項(xiàng)目時(shí)，僅在輸入符號(hào)是a時(shí)才能用A→α歸約，而不是對FOLLOW(A)中的所有符號(hào)都用A→α歸約。

當(dāng)β≠ε時(shí)，搜索符是無意義的。

其中A→α?β是一個(gè)LR(0)項(xiàng)目，每個(gè)a是終結(jié)符，稱為展望符或搜索符。第39頁/共57頁4.5.4LR（1）分析法

構(gòu)造LR(1)項(xiàng)目集族的方法和構(gòu)造LR(0)項(xiàng)目集規(guī)范族的方法基本相同。具體構(gòu)造方法如下：(1)構(gòu)造LR(1)項(xiàng)目集I的閉包函數(shù)(a)I的任何LR(1)項(xiàng)目都屬于CLOSURE(I)。

(b)若項(xiàng)目[A·B,a]屬于CLOSURE(I),Br是文法中的一條規(guī)則,bFIRST(a),則[B·r,b]也屬于CLOSURE(I)。

(c)重復(fù)(b),直到CLOSURE(I)不再增大為止。第40頁/共57頁4.5.4LR（1）分析法

對例2中的文法G',令I(lǐng)=[S'→?S，$]為初態(tài)集的初始項(xiàng)目集，對其求閉包：=CLOSURE({[S'→?S，$]})CLOSURE(I)={[S'→?S，$][S→?L=R，$][S→?R，$][L→?*R，=/$][L→?i，=/$][R→?L，$]}=I00.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→LFIRST(βa)=FIRST($)={$}FIRST(βa)=FIRST(=R$)={=}FIRST(βa)=FIRST($)={$}FIRST(βa)=FIRST($)={$}第41頁/共57頁4.5.4LR（1）分析法(2)構(gòu)造轉(zhuǎn)換函數(shù)

令I(lǐng)是一個(gè)LR(1)項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(shù)GO(I，X)=CLOSURE(J)。J={[A→αX·β,a]|[A→α·Xβ,a]∈I}第42頁/共57頁4.5.4LR（1）分析法GO(I0,S)={[S'→S·，$]}=I1GO(I0,*)={[L→*·R，=/$][R→·L，=/$][L→·*R，=/$][L→·i，=/$]}=I4I0={[S'→?S，$][S→?L=R，$][S→?R，$][L→?*R，=/$][L→?i，=/$][R→?L，$]}第43頁/共57頁I0:SI1:S'→S?,$LI2:S→L?=R,$R→L?,$I3:S→R?,$RI4:L→*?R,=/$R→?L,=/$L→?*R,=/$L→?i,=/$*I5:L→i?,=/$iiS'→?S,$S→?L=R,$S→?R,$L→?*R,=/$L→?i,=/$R→?L,$*I6:S→L=?R,$L→?*R,$L→?i,$R→?L,$I9:S→L=R?,$I11:L→*?R,$R→?L,$L→?*R,$L→?i,$I10:R→L?,$I12:L→i?,$I7:L→*R?,=/$I13:L→*R?,$I8:R→L?,=/$*LR(1)項(xiàng)目集族及轉(zhuǎn)換函數(shù)=RLRL*LiR0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→Li第44頁/共57頁4.5.4LR（1）分析法

分析所有這些項(xiàng)目集,可以發(fā)現(xiàn)每個(gè)項(xiàng)目集中都不含移進(jìn)—?dú)w約沖突,或歸約—?dú)w約沖突。

在項(xiàng)目集I2中，由于歸約項(xiàng)目[RL·,$]的搜索符集合{$}與移進(jìn)項(xiàng)目[SL·=R,$]的待移進(jìn)符號(hào)‘＝’號(hào)不相交，所以在I2中，當(dāng)面臨輸入符為‘$’時(shí)用規(guī)則R→L歸約，為‘＝’時(shí)則移進(jìn)，I2中的移進(jìn)一歸約沖突在LR(1)分析法中得到了解決。第45頁/共57頁4.5.4LR（1）分析法

構(gòu)造LR(1)分析表的方法與構(gòu)造LR(0)分析表的方法基本相同，僅對歸約項(xiàng)目作如下修改：

若歸約項(xiàng)目[A·,a]屬于Ik，則對搜索符a置ACTION[K，a]＝rj。其中A→α為文法的第j條規(guī)則。

按上述方法我們對例2中文法的LR(1)項(xiàng)目集族構(gòu)造相應(yīng)的LR(1)分析表如下表所示：第46頁/共57頁012345678910111213ACTIONGOTOi*=$SLRS5

S4123accS6

r5r2S5

S4r4

r4S12S11r3

r3r5

r5r187109r5S12S111013r4r3G[S]的LR(1)分析表0.S'→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L第47頁/共57頁I0:SI1:S'→S?,$LI2:S→L?=R,$R→L?,$I3:S→R?,$RI4:L→*?R,=/$R→?L,=/$L→?*R,=/$L→?i,=/$*I5:L→i?,=/$iiS'→?S,$S→?L=R,$S→?R,$L→?*R,=/$L→?i,=/$R→?L,$*I6:S→L=?R,$L→?*R,$L→?i,$R→?L,$I9:S→L=R?,$I11:L→*?R,$R→?L,$L→?*R,$L→?i,$I10:R→L?,$I12:L→i?,$I7:L→*R?,=/$I13:L→*R?,$I8:R→L?,=/$*LR(1)項(xiàng)目集族及轉(zhuǎn)換函數(shù)=RLRL*LiR0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→Li第48頁/共57頁4.5.4LR（1）分析法

由上表可以看出，對LR(1)的歸約項(xiàng)目不存在任何無效歸約。但在多數(shù)情況下同一個(gè)文法的LR(1)項(xiàng)目集的個(gè)數(shù)比LR(0)項(xiàng)目集的個(gè)數(shù)要多。

這是因?yàn)閷ν粋€(gè)LR(0)項(xiàng)目集，由于搜索符不同而對應(yīng)著多個(gè)LR(1)