4.5.3SLR（1）分析法

這個條件比較苛刻，對于大多數程序設計語言來說，一般都不能滿足LR(0)文法的條件，即使是描述一個算述表達式的簡單文法也不是LR(0)文法。例考慮算術表達式的文法：

每一個LR(0)項目集中都不含有沖突的項目，由于LR(0)文法要求文法的E→E+T|TT→T*F|FF→(E)|id4.5.3SLR（1）分析法將文法拓廣并對規(guī)則進行編號直接構造出識別文法規(guī)范句型活前綴的DFA下如圖所示。0.E'→E1.E→E+T2.E→T3.T→T*F4.

T→F5.

F→(E)6.

F→idE→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)·)識別表達式文法活前綴的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+4.5.3SLR（1）分析法不難看出在I1，I2，I9中既含有移進項目，又含有歸約項目，因而這個表達式的文法不是LR(0)文法。根據構造LR(0)分析表的方法，構造出的LR(0)分析表中在2狀態(tài)和9狀態(tài)下面臨輸入符號‘*’時含多重定義元素，見下表。表達式文法的LR(0)分析表012345S5S4S6accS5S4r2r2S7r2

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

r1r1r1r3r3r3r3r3r3r5r5r5r5r5r51193104.5.3SLR（1）分析法

為了對語言句子進行確定性的分析，需要解決移進—歸約或歸約—歸約沖突。我們采用對含有沖突的項目集向前查看一個輸入符號的辦法來解決沖突，這種分析法稱為簡單的LR分析法，即SLR(1)分析法。4.5.3SLR（1）分析法仔細分析構造LR(0)分析表的方法，容易看出使分析表出現(xiàn)多重定義的原因在于其中的規(guī)則2，即對于每一個項目集Ik中的歸約項目A→α?，不管當前輸入符號是什么，都將ACTION表中第K行的各個元素均置為rj，其中j為規(guī)則A→α的編號。

4.5.3SLR（1）分析法因此，當一個LR(0)項目集規(guī)范族中存在一個含移進—歸約沖突和歸約—歸約沖突的項目集時則在分析表第K行中遇輸入符號b必然會出現(xiàn)多重定義元素。

IK={X→δ·bB,A→α·,B→r·}對含沖突的項目集，僅根據LR(0)項目本身的信息是無法解決沖突的。需要向前查看一個輸入符號以考察當前所處的環(huán)境。4.5.3SLR（1）分析法對歸約項目A→α?和B→γ?，只需要考察當將句柄α或γ歸約為A或B時，直接跟在A或B后的終結符的集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移進符號b，即滿足：IK={X→δ·bB,A→α·,B→r·}FOLLOW(A)∩FOLLOW(B)=Φ

FOLLOW(B)∩=ΦFOLLOW(A)∩=Φ4.5.3SLR（1）分析法那么，當狀態(tài)K面臨輸入符號a時，可按以下規(guī)則解決沖突：(1)若a=b則移進(2)若aFOLLOW(A)，則用規(guī)則A進行歸約。

(3)若aFOLLOW(B)，則用規(guī)則Br進行歸約。(4)此外報錯。4.5.3SLR（1）分析法 一般而言，若一個LR(0)項目集I中有m個移進項目和n個歸約項目時： 對所有移進項目向前看一符號集合{a1,a2,…,am}和FOLLOW(B1),FOLLOW(B2),…，F(xiàn)OLLOW(Bn)兩兩相交為Φ時，則項目集I中沖突仍可用下述規(guī)則解決沖突。I:{A1→α1·a1β1,A2→α2·a2β2,

…,Am→αm·amβm,B1→r1·,B2→r2·,…,Bn→rn·}4.5.3SLR（1）分析法設a為當前輸入符：(1)若a∈{a1,a2,…,am}則移進。(3)此外報錯。(2)若a∈FOLLOW(Bi),i=1,2,…,n,

則用Bi→ri進行歸約。

這種用來解決分析動作沖突的方法稱為SLR(1)方法。4.5.3SLR（1）分析法現(xiàn)在分別考察上例中的三個項目集I1,I2,I9中沖突能否用SLR(1)方法解決。由于FOLLOW(E')={$}∩{+}=Φ，且E'→E?是“接受”項目，所以I1中的接受—移進沖突可以用SLR(1)方法解決。如果對于一個文法的某些LR(0)項目集或LR(0)分析表中所含有的動作沖突都能用SLR(1)方法解決，則稱這個文法是SLR(1)文法。

I1={E'→E·,E→E·+T}4.5.3SLR（1）分析法由于FOLLOW(E)={+,),$}∩{*}=Φ,因此面臨輸入符為‘＋’,‘）’,‘$’時，用規(guī)則E→T進行歸約，當面臨輸入符‘*’時，則移進，I2中移進—歸約沖突可以用SLR(1)方法解決。與I2中情況類似，其項目集中移進—歸約沖突可用SLR(1)方法解決。因此該文法是SLR(1)文法。I2={E→T·,T→T·*F}I9={E→E+T·,T→T·*F}4.5.3SLR（1）分析法SLR(1)分析表的構造與LR(0)分析表的構造基本相同。僅對LR(0)分析表構造算法中的規(guī)則2進行如下修改：

若歸約項目A→α?屬于Ik，則對任何終結符

a∈FOLLOW(A)置ACTION[k,a]=rj，其中A→α為文法的第j條規(guī)則。

G[E]的SLR(1)分析表GOTO狀態(tài)ACTIONid+*()$ETF012345S5S4S6accS5S4r2S7r2r2r4r4r4r4123823r6r6r6r6678910S5S4S5S4S6S11r1S7r1r1r3r3r3r3r5r5r5r51193104.5.3SLR（1）分析法

若文法的SLR(1)分析表不含多重定義元素，則稱文法G為SLR(1)文法。

例1設有拓廣文法G[S′]0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a4.5.3SLR（1）分析法(1)構造識別文法規(guī)范句型活前綴的DFA。(2)判斷該文法是否SLR(1)文法，若是，構造SLR(1)分析表，若不是，請說明理由。該文法的LR(0)項目集規(guī)范族及轉換函數如下圖所示: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)項目集及轉換函數I9:A→aSb·S→Sb·

cb0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a4.5.3SLR（1）分析法0S2112345r1r1r1r2r2r2S5r4r1r1r146789S3accS9S8S6r5S2r37狀態(tài)GOTOACTIONabc$SAG[S]的SLR(1)分析表0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a4.5.3SLR（1）分析法SLR(1)分析法是一種簡單而實用的方法,其造表演算法簡單,狀態(tài)數目少,且大多數程序設計語言都可以用SLR(1)文法來定義。但是仍存在這樣一些文法，其項目集中的移進一歸約沖突或歸約—歸約沖突不能用SLR(1)方法解決。4.5.3SLR（1）分析法例2下列拓廣文法G′為我們首先用S'→?S作為初態(tài)集的項目，然后用閉包函數和轉換函數構造識別文法G'活前綴的DFA如下圖所示。0.S'→S1.S→L=R2.S→R3.L→*R4.L→i5.R→LI0: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)識別G’活前綴的DFA0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L4.5.3SLR（1）分析法1.SLR(1)方法為什么不能解決I2中的移進和歸約沖突?2.怎樣解決I2中的移進和歸約沖突?問題:4.5.3SLR（1）分析法

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

。

Ii:A→α?I0I1Ii$δαaa'a"…I0I1Ij$δAaa'a"…4.5.3SLR（1）分析法因為如果棧里的符號串為$δα，歸約后變?yōu)?δA，當前讀到的輸入符號是a，若文法中不存在以δAa為前綴的規(guī)范句型，那么，這種歸約無效。

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

I0:S→L=·RL→·*RL→·iR→·LS'→·SS→·L=RS→·RL→·*RL→·iR→·L