第六章LR分析法

編譯原理第六章LR分析法LR分析法是自底向上的規(guī)范歸約的語法分析方法主要內(nèi)容：●LR(0)分析法●SLR(1)方法●LR(1)方法●LALR(1)方法(其中：SLR(1)是LR(0)方法的改進(jìn)方法;LALR(1)是LR(1)方法的改進(jìn)方法)§1LR方法的概述一、LR方法的優(yōu)點(diǎn)適用大多數(shù)無二義性上下文無關(guān)文法描述的語言的分析，對(duì)文法限制少。歸約過程是確定的，即每次歸約能唯一確定句型的句柄。3.分析效率高速度快，能準(zhǔn)確及時(shí)地指出出錯(cuò)位置。主要缺點(diǎn)：對(duì)使用的語言文法要求有一定限制，分析器構(gòu)造的工作量大，實(shí)現(xiàn)難度高。二、LR分析器的組成

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

一個(gè)LR分析器由3個(gè)部分組成：(1)總控程序(驅(qū)動(dòng)程序),對(duì)所有的LR分析器的總控程序都是相同的。 其主要功能：在分析的每一步，按照狀態(tài)棧頂狀態(tài)S和當(dāng)前輸入串中符號(hào)a，查閱分析表，并執(zhí)行其中ACTION[S,a]和GoTo部分規(guī)定的操作。操作分為：移進(jìn)、歸約、報(bào)錯(cuò)或接受。a1a2….an#總控程序

分析表

ACTIONGOTO文法產(chǎn)生式Sn...S1S0Xn..X1#輸出sp狀態(tài)棧符號(hào)棧輸入串(2)分析表：包括動(dòng)作表(ACTION)和狀態(tài)轉(zhuǎn)換表(GoTo)兩個(gè)部分。它們都可以用二維數(shù)組表示。動(dòng)作表(ACTION)：有4類動(dòng)作信息：移進(jìn)：Si表示；歸約：rj

表示；報(bào)錯(cuò)：空白表示；接受：acc不同的文法分析表內(nèi)容不同同一個(gè)文法采用的LR分析器不同時(shí)，分析表的內(nèi)容將也不同。LR分析器的關(guān)鍵部分是分析表的構(gòu)造。(3)分析棧：包括文法符號(hào)棧x和相應(yīng)的狀態(tài)棧S。它們均用一維數(shù)組表示。三、LR分析法及過程（1）LR分析總控程序的算法輸入：輸入串W和LR分析表輸出：若W是句子則有正確信息，否則報(bào)錯(cuò)算法：初始化時(shí)，初始狀態(tài)So在分析棧棧頂，輸入串W的第一個(gè)符號(hào)讀入a中。while(ACTION[s,a]!=acc){if(ACTION[s,a]==Si){將狀態(tài)i和輸入符號(hào)a進(jìn)棧；將下一個(gè)符號(hào)讀入a中；elseif(ACTION[s,a]==rj){用第j條規(guī)則A::=α歸約；將IαI個(gè)狀態(tài)和IαI個(gè)輸入符號(hào)退棧;

當(dāng)前狀態(tài)為S'，將A和GOTO[S',A]=S''進(jìn)棧；

}elseif(ACTION[s,a]==ERROR)error();}}(2)分析過程例：設(shè)文法G‘為：0.S'::=S1.S::=A2.S::=B3.A::=aAb4.A::=c5.B::=aBb6.B::=d輸入串a(chǎn)acbb＃的分析過程步驟棧中狀態(tài)棧中符號(hào)輸入串動(dòng)作10#aacbb#S4204#aacbb#S43044#aacbb#S540445#aacbb#用第4條產(chǎn)生式歸約50447#aaAbb#S8604478#aaAbb#用第3條產(chǎn)生式歸約7047#aAb#S880478#aAb#用第3條產(chǎn)生式歸約902#A#用第1條產(chǎn)生式歸約1001#S#accSi表示 當(dāng)前輸入符號(hào)a及下一狀態(tài)i移入分析棧中rj表示按第j條產(chǎn)生式歸約acc表示接受空白表示分析動(dòng)作調(diào)出出錯(cuò)處理程序相應(yīng)于文法的LR分析表狀態(tài)ACTIONabcd＃GOTOSAB0S4S5S61231acc2r1r1r1r1r13r2r2r2r2r24S4S5S6795r4r4r4r4r46r6r6r6r6r610r5r5r5r5r58r3r3r3r3r37S89S10§2.LR(0)分析法LR(0)分析法表示的含義：L：自左向右進(jìn)行分析；R：采用最右推導(dǎo)的逆過程－最左規(guī)約；（規(guī)范歸約）;0：向貌似句柄的符號(hào)串后面查看0個(gè)輸入符號(hào)。LR(0)分析法雖存在對(duì)文法限制的問題，但它是構(gòu)造其它LR類分析器的基礎(chǔ)。LR分析方法的重點(diǎn)：分析表的構(gòu)造。分析表的構(gòu)造過程：上下文無關(guān)文法＝＝>識(shí)別文法所有規(guī)范句型活前綴的DFA=＝>LR分析表●問題：（1）什么是文法所有規(guī)范句型的活前綴？（2）如何構(gòu)造識(shí)別活前綴的DFA？（3）如何構(gòu)造LR的分析表？轉(zhuǎn)換構(gòu)造一、可歸前綴和活前綴例：設(shè)有文法G[S]：(上下文無關(guān)文法) S∷=AS∷=BA∷=aAb A∷=c B∷=aBbB∷=d

如果將它們產(chǎn)生式的右部編上序號(hào)，并將序號(hào)人為的帶入句型分析中，即有：

S∷=A[1]S∷=B[2]A∷=aAb[3]A∷=c[4 ]B∷=aBb[5]B∷=d[6]設(shè)有句子aacbb的規(guī)范推導(dǎo)過程和其逆過程－規(guī)范歸約過程，為：S=>A[1]=>aAb[3][1]=>aaAb[3]b[3][1]=>aac[4]b[3]b[3][1]

歸約時(shí)，只參考當(dāng)前規(guī)范句型的前部分，它們依次為：

aac[4]aac是規(guī)范句型aacbb的可歸約前綴

aaAb[3]aaAb是規(guī)范句型aaAbb的可歸約前綴

aAb[3]aAb是規(guī)范句型aAb的可歸約前綴

A[1]A是規(guī)范句型A的可歸約前綴

注：它們正是上節(jié)分析過程表中，每次采用歸約動(dòng)作前，符號(hào)棧中的內(nèi)容，即4，6，8，9步驟內(nèi)棧中的符號(hào)串。稱規(guī)范句型的前部分串為可歸前綴。

aac[4]b[3]b[3][1]用產(chǎn)生式4歸約

<=aaAb[3]b[3][1]用產(chǎn)生式3歸約

<=aAb[3][1]用產(chǎn)生式3歸約

<=A[1]用產(chǎn)生式1歸約

<=S

●活前綴：規(guī)范句型的前綴，這種前綴不包含句柄右邊的任何符號(hào)。

例如：規(guī)范句型aaAbb的句柄是aAb，且aaAb是它的可歸前綴;則規(guī)范句型aaAbb的活前綴為ε,a,aa,aaA,aaAb,它們均不包含句柄右邊符號(hào)b。注:(1)可歸前綴也是規(guī)范句型的活前綴。

(2)活前綴可以是一個(gè)或多個(gè)規(guī)范句型的前綴。

(3)在分析棧中全部符號(hào)串均為當(dāng)前規(guī)范句型的活前綴。只要輸入串已掃描過的部分保持可歸約成一個(gè)活前綴，意味著所掃描的部分是正確的。這樣，對(duì)句柄的識(shí)別就變成了對(duì)規(guī)范句型活前綴的識(shí)別。

(4)可利用有窮自動(dòng)機(jī)去識(shí)別文法所有規(guī)范句型的活前綴。二、LR(0)項(xiàng)目

活前綴與句柄有以下三種情況：（1）活前綴中已含有句柄的全部符號(hào)，表明此時(shí)某一產(chǎn)生式A::=α的右邊已出現(xiàn)在棧頂，其相應(yīng)的分析動(dòng)作是用此產(chǎn)生式進(jìn)行歸約。（2）活前綴中已含有句柄的部分符號(hào)，此時(shí)意味著形如:A::=α1α2產(chǎn)生式的右邊子串α1已出現(xiàn)在棧頂，正期待著從剩余的輸入串中進(jìn)行移進(jìn)得到α2。（3）活前綴中不含有句柄的任何符號(hào)，此時(shí)意味著正期待從剩余的輸入串中能看到由某個(gè)產(chǎn)生式A::=α的右部α所推出的符號(hào)串。為了刻畫在分析過程中，文法的一個(gè)產(chǎn)生式右邊的符號(hào)串已有多大一部分被識(shí)別，可在文法產(chǎn)生式右邊的適當(dāng)?shù)奈恢蒙霞由弦粋€(gè)園點(diǎn)來表示。針對(duì)上述三種情況，標(biāo)有園點(diǎn)的產(chǎn)生式分別為：

A::=α

·A::=α1

·α2

A::=·α

文法G中右部標(biāo)有園點(diǎn)的產(chǎn)生式稱為G的一個(gè)LR(0)項(xiàng)目.

特別：對(duì)于空產(chǎn)生式A∷=ε,則僅有項(xiàng)目A∷=·

注

(1)文法G的全部LR(0)項(xiàng)目是構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA的基礎(chǔ)。

(2)每個(gè)項(xiàng)目的含義與圓點(diǎn)的位置有關(guān)，概括說：圓點(diǎn)左部表示分析過程的某時(shí)刻用該產(chǎn)生式歸約時(shí)句柄已識(shí)別過的部分。圓點(diǎn)右部表示待識(shí)別的部分。

(3)根據(jù)圓點(diǎn)位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符，將一個(gè)文法全部LR(0)項(xiàng)目分為4類：●移進(jìn)項(xiàng)目：形如U∷=x·ay(x，y為符號(hào)串，a∈VT)即圓點(diǎn)后為終結(jié)符的項(xiàng)目為移進(jìn)項(xiàng)目。表明期待從剩余的輸入串中移進(jìn)一個(gè)符號(hào)，以待形成句柄。

●待約項(xiàng)目：形如U∷=x·By(B∈VN)即圓點(diǎn)后為非終結(jié)符的項(xiàng)目為待約項(xiàng)目。表明期待從剩余的輸入串中進(jìn)行歸約得到B，然后才能繼續(xù)分析U的右部?！駳w約項(xiàng)目：形如U∷=x·(x∈VT)即圓點(diǎn)在最右端的項(xiàng)目，稱為規(guī)約項(xiàng)目。它表明一個(gè)產(chǎn)生式的右部已經(jīng)分析完，句柄已經(jīng)形成，可以按此產(chǎn)生式歸約。

●接受項(xiàng)目：對(duì)識(shí)別符號(hào)的歸約項(xiàng)目，形如：U∷=E·(E為識(shí)別符號(hào))稱接受項(xiàng)目。它是分析中的最后一次歸約，表明整個(gè)句子分析完畢，成功結(jié)束。注：可按照一定的規(guī)則，將這些項(xiàng)目組合成一些狀態(tài)，這些狀態(tài)實(shí)際上就是將要構(gòu)造的LR分析表的狀態(tài)。也可看作某個(gè)DFA的狀態(tài)集(每個(gè)項(xiàng)目作為一個(gè)狀態(tài))。DFA就能識(shí)別文法所有規(guī)范句型的活前綴。三.構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA

方法如下：1o

求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的NFA再確定化為DFA2o

通過項(xiàng)目集規(guī)范族的方法構(gòu)造識(shí)別活前綴的DFA下面重點(diǎn)介紹2o方法：1.LR(0)項(xiàng)目集規(guī)范族的構(gòu)造DFA方法步驟：1o

拓廣文法G為G’，方法：加入0.S’∷=S(S為G的識(shí)別符號(hào)，S’為G’的識(shí)別符號(hào))2o

列出所有G’的LR(0)項(xiàng)目3o

求DFA的初態(tài)I0=closure(I)1)I中每一個(gè)LR(0)項(xiàng)目屬于closure(I)；

2)若開始A∷=α·Bβ屬于closure(I)(B∈VN)

則文法中關(guān)于B的產(chǎn)生式B∷=·γ的項(xiàng)目也屬于closure(I)3)重復(fù)上述過程，直到closure(I)不再增大為止。4o再由I0求狀態(tài)轉(zhuǎn)換G0(I0,x)=closure(J)J={A∷=αX·β|A∷=α·Xβ∈I};從而得出I0后繼項(xiàng)目集。5o根據(jù)求出的項(xiàng)目集畫DFA.例：已知文法G[S]:S∷=AS∷=BA∷=aAbA∷=cB∷=aBbB∷=d求：識(shí)別活前綴的DFA。解：

⑴拓廣文法G：加入0.S’∷=S（使"接受"項(xiàng)目唯一）⑵列出文法所有的LR(0)項(xiàng)目S’∷=·SS’∷=S·S∷=·AS∷=A·S∷=·BS∷=B·A∷=·aAbA∷=a·AbA∷=aA·bA∷=aAb·A∷=·cA∷=c·B∷=·aBbB∷=a·BbB∷=aB·bB∷=aBb·B∷=·dB∷=d·⑶初態(tài)：令I(lǐng)={S’∷=·S}I0=Closure(I)=Closure({S’∷=·S}) ={S’∷=·S,S∷=·A,S∷=·B,A∷=·aAb,A∷=·C,B∷=·aBb,B∷=·d}⑷由I0求GO函數(shù)，得出I0后繼項(xiàng)目集。 通過考察I0中每個(gè)項(xiàng)目中’·’后的第一個(gè)符號(hào)x，可知：x={S,A,B,a,c,d}利用GO(I0,x)=Closure(J)，可以求I0后繼項(xiàng)目集。I1：GO(I0,S)=Closure({S’∷=S·})={S’∷=S·}I2：GO(I0,A)=Closure({S∷=A·})={S∷=A·}I3：GO(I0,B)=Closure({S∷=B·})={S∷=B·}I4：GO(I0,a)=Closure({A∷=a·Ab，B∷=a·Bb}）

={A∷=a·Ab,A∷=·aAb,A∷=·C,I5：GO(I0,C)=Closure({A∷=C·})={A∷=C·}I6：GO(I0,d)=Closure({B∷=d·})={B∷=d·}

至此求出了I0的全部后繼項(xiàng)目集I1,I2,…,I6。容易看出I1,I2,I3,I5,I6集中均無后繼項(xiàng)目。但I(xiàn)4有后繼項(xiàng)目,可通過G0(I4,x)繼續(xù)求出，這里x={A,B,a,c,d}。于是：B∷=a·Bb,B∷=·aBb,B∷=·d}I7：G0(I4,A)=Closure({A∷=aA·b})={A∷=aA·b}I9：G0(I4,B)=Closure({B∷=aB·b})={B∷=aB·b}而G0(I4,a)=I4,G0(I4,c)=I5,G0(I4,d)=I6最后求I7,I9的后繼項(xiàng)目：I8：G0(I7,b)=Closure({A∷=aAb·})={A∷=aAb·}I10：G0(I9,b)=Closure({B∷=aBb·})={B∷=aBb·}又因?yàn)镮8,I10無后繼項(xiàng)目，結(jié)束。⑸畫出DFA

構(gòu)成識(shí)別一個(gè)文法活前綴的項(xiàng)目集（狀態(tài)）的全體稱為該文法的LR(0)項(xiàng)目集規(guī)范族。

DFA圖中：歸約項(xiàng)目的項(xiàng)目集，如：I2,I3,I5,I6,I9,I10，表示DFA達(dá)到這些狀態(tài)時(shí)，已識(shí)別一個(gè)句柄，這些狀態(tài)稱為句柄識(shí)別態(tài)。接受項(xiàng)目的項(xiàng)目集，如：I1是DFA的接受狀態(tài)；表示成功完成輸入串的識(shí)別，用S’::=S.進(jìn)行最后一次歸約.。a

2.LR(0)文法定義：如果文法G’的項(xiàng)目集規(guī)范族中的每個(gè)項(xiàng)目集中，不存在下述沖突項(xiàng)目：①移進(jìn)項(xiàng)目和歸約項(xiàng)目同時(shí)存在：如：

A∷=b·aβ移進(jìn)項(xiàng)目和B∷=b·

歸約項(xiàng)目②多個(gè)歸約項(xiàng)目并存：如：

A∷=β· B∷=β·

則稱文法G’為LR(0)文法。注：①?zèng)_突會(huì)引起：移進(jìn)與歸約沖突，歸約與歸約沖突。如：對(duì)移進(jìn)與歸約沖突：若面臨輸入符號(hào)為a時(shí)，不能確定是移進(jìn)a還是把b歸約成B，因?yàn)長R(0)分析是不向前看符號(hào)的。

對(duì)歸約與歸約的沖突；面臨什么符號(hào)β輸入都不能確定歸約為A，或者為B。②僅文法為LR(0)時(shí)，才能構(gòu)造不會(huì)沖突的LR(0)分析表。四、構(gòu)造LR(0)分析表

算法：輸入：識(shí)別LR(0)文法所有規(guī)范句型活前綴的DFA

輸出：文法G的LR(0)分析表方法：用整數(shù)0,1,2…..n分別表示DFA中的I1,I2….In；令包含項(xiàng)目S’::=·S的項(xiàng)目集Ik的下標(biāo)k為分析器的初始狀態(tài)，則：

ACTION和GOTO表的構(gòu)造步驟：

1o若項(xiàng)目A∷=α·aβ∈IK,且轉(zhuǎn)換函數(shù)G0(IK,a)=Ij,當(dāng)a為終結(jié)符則置ACTION[K，a]為Sj,即把輸入符號(hào)a移入符號(hào)棧；狀態(tài)j移入狀態(tài)棧。－－移進(jìn)

2o

若項(xiàng)目A∷=α·∈IK,則對(duì)任何終結(jié)符號(hào)a和結(jié)束符號(hào)#，均置ACTION[K，a或#]=”rj“,表示按文法的第j個(gè)產(chǎn)生式A∷=α，把當(dāng)前文法符號(hào)棧頂?shù)姆?hào)串α歸約為A。(棧指針從棧頂向下移動(dòng))|α|長度，非終結(jié)符A變?yōu)楫?dāng)前面臨的符號(hào))

－－歸約

3o

若項(xiàng)目S’∷=S·∈IK，則置ACTION[K，#]=”acc“,表示接受。

4o

若G0(IK,A)=Ij,則置GOTO[K，A]=”j”,(A∈VN),表示當(dāng)前狀態(tài)為K，遇到文法符號(hào)A時(shí)狀態(tài)應(yīng)轉(zhuǎn)向j，因此A移入文法符號(hào)棧，j移入狀態(tài)棧。

5o

凡不能用上述1o---4o方法填入分析表中的元素，均置“報(bào)錯(cuò)標(biāo)志”(用空白或error)。

總之：

在一個(gè)狀態(tài)項(xiàng)目集中，若是移進(jìn)項(xiàng)目，在ACTOIN表中填Si；若是歸約項(xiàng)目，將在ACTOIN表中的對(duì)應(yīng)行上全部填ri。若是待約項(xiàng)目，就填GOTO表。例：依上例的DFA，構(gòu)造LR(0)分析表：ACTIONGOTO狀態(tài)abcd#SAB0S4S5S61231acc2r1r1r1r1r13r2r2r2r2r24S4S5S6795r4r4r4r4r46r6r6r6r6r67S88r3r3r3r3r39S1010r5r5r5r5r5

文法G[S]:1.S∷=A 2.S∷=B3.A∷=aAb 4.A∷=c5.B∷=aBb 6.B∷=da其中：表中行號(hào)0,1,2,…,n分別為DFA中的I0,I1,I2，…,In個(gè)狀態(tài)；

ACTION部分的列號(hào)為文法G[S]中的終結(jié)符號(hào)和#號(hào)；

GOTO部分的列號(hào)為文法G[S]中的非終結(jié)符號(hào)；空白元素為報(bào)錯(cuò)標(biāo)志。

rj表示要?dú)w約，Si表示要移進(jìn)。注：根據(jù)LR(0)分析表,算法唯一選擇產(chǎn)生式進(jìn)行歸約.不管產(chǎn)生式是否有相同的右部(如:A∷=d,B∷=d).下面將要介紹的SLR(1),LR(1)方法總控程序一樣，只是分析表的內(nèi)容不同。因此，重點(diǎn)介紹SLR(1),LR(1)方法要解決的問題及分析表的構(gòu)造。SLR(1)分析法是LR(0)的改進(jìn)方法。它針對(duì)LR(0)中有沖突的項(xiàng)目集，用向前查看一個(gè)符號(hào)的辦法進(jìn)行處理，以解決項(xiàng)目沖突。因此，本節(jié)主要介紹如何解決項(xiàng)目沖突的SLR(1)分析表構(gòu)造問題。一、項(xiàng)目沖突及解決的方法LR(0)分析表是根據(jù)LR(0)文法構(gòu)造的。但算術(shù)表達(dá)式文法就不是LR(0)文法。因此，LR(0)分析方法適用語法分析的范圍有限。要使它適用范圍擴(kuò)大就提出解決項(xiàng)目沖突問題。§3.SLR(1)分析法1.項(xiàng)目沖突項(xiàng)目沖突：指文法的一個(gè)項(xiàng)目集中既含有移進(jìn)項(xiàng)目又含有歸約項(xiàng)目，或含有不同的歸約項(xiàng)目。例如：假定LR(0)含有一個(gè)項(xiàng)目集：

Ii＝{A∷=α·bβ,B∷=α·,C∷=α·}其中：第一個(gè)項(xiàng)目為移進(jìn)項(xiàng)目，第二，三個(gè)項(xiàng)目為歸約項(xiàng)目。顯然，這三個(gè)項(xiàng)目告訴我們應(yīng)采取的動(dòng)作各不相同，相互沖突。第一個(gè)項(xiàng)目為移進(jìn)項(xiàng)目，指出應(yīng)把下一個(gè)輸入符號(hào)b移進(jìn)棧頂;

第二個(gè)項(xiàng)目為歸約項(xiàng)目，指出不管當(dāng)前輸入符號(hào)是什么（不向前查看一個(gè)符號(hào)）應(yīng)把棧頂頂部的α歸約到B;這就與第一項(xiàng)目的動(dòng)作發(fā)生了移進(jìn)和歸約沖突。第三個(gè)項(xiàng)目為歸約項(xiàng)目，指出不管當(dāng)前輸入符號(hào)是什么，應(yīng)把棧頂頂部的α歸約到c;這就與第二項(xiàng)目的動(dòng)作發(fā)生了歸約和歸約沖突。例：算術(shù)表達(dá)式文法G[E]:E::=E+TITT::=T*FIFF::=(E)Ii求:該文法的LR（0）分析表拓廣該文法并編號(hào)：

0.E’::=E1.E::=E+T2.E::=T3.T::=T*F4.T::=F5.F::=(E)6.F::=iI0：E'::=?EE::=?E+TE::=?T?T::=?T*FT::=?FF::=?(E)F::=iI1:E'::=E?E::=E?+TI3:T::=F?I4：F::=(?E)E::=?E+TE::=?T?T::=?T*FT::=?FF::=?(E)F::=iI8:F::=(E?)E::=E?+T)I11:F::=(E)?EF(TI2:E::=T?T::=T?*FI5:T::=i?iTi*I7:T::=T*?FF::=?（E）F::=?i(I6:E::=E+?TT::=?T*FT::=?FF::=?(E)F::=?i+FF(E+I9:E::=E+T?T::=T?*T*I10:T::=T*F?FTi狀態(tài)ACTIONi+*（）＃GOTOEFT0S5S41321S6acc

2r2r2S7r2r2r2r23r4r4r4r4r4r45r6r6r6r6r6r611r5r5r5r5r5r510r3r3r3r3r3r39r1r1S7r1r1r1r14S5S48236S5S4937S5S4108S6S11(在DFA中的I1,I2,I9,項(xiàng)目集中含有移進(jìn)和歸約項(xiàng)目，且在構(gòu)造的分析表內(nèi)的2和9狀態(tài)下，面臨輸入符號(hào)*時(shí)，含有多重定義元素（產(chǎn)生沖突）。因此，算術(shù)表達(dá)式文法不是LR(0)文法。原因在于：構(gòu)造LR(0)分析表的第2條規(guī)則，即對(duì)于每個(gè)項(xiàng)目集Ik中的歸約項(xiàng)目B::=α·，不管當(dāng)前輸入符號(hào)是什么，都要將ACTION表中第K行的各元素均置為rj(j為B::=α的編號(hào))。因此，當(dāng)LR(0)含有一個(gè)沖突項(xiàng)目集：

Ik＝{A∷=α·bβ,B∷=α·,C∷=α·}時(shí)，則在構(gòu)造的分析表內(nèi)必含有多重定義元素。對(duì)含有沖突的項(xiàng)目集，僅根據(jù)項(xiàng)目本身的信息是無法解決沖突的，需要向前查看一個(gè)輸入符號(hào)，以考察當(dāng)前所處的環(huán)境。對(duì)于B∷=α·和C∷=α·兩個(gè)歸約項(xiàng)目，需考察當(dāng)前是歸約到B或C，這就要求后繼終結(jié)符號(hào)集FOLLOW(B)和FOLLOW(C)互不相交，且不包含符號(hào)b。2.解決方法解決沖突的簡(jiǎn)單辦法：例如有沖突的狀態(tài)：

Ik＝{A∷=α·bβ,B∷=α·,C∷=α·}

考察所有含有B或C的句型中，直接跟在B或C后的終結(jié)符號(hào)集即FOLLOW(B)或FOLLOW(C)互不相交，且都不包含b，即滿足：判定SLR(1)文法（沖突可以解決）的判定式：

FOLLOW(B)∩FOLLOW(C)=Φ

歸約間的沖突

FOLLOW(B)∩=Φ歸約與移進(jìn)間的沖突

FOLLOW(C)∩=Φ在狀態(tài)Ik面臨任何輸入符號(hào)a時(shí)，動(dòng)作可由下列規(guī)定來解決沖突：

(1).若a=b，則移進(jìn)。(在分析表中：ACTION[k,a]=Sk)(2).若a∈FOLLOW(B),則用產(chǎn)生式B∷=α進(jìn)行歸約。(在分析表中：ACTION[k,a]=rj)(3).若a∈FOLLOW(C),則用產(chǎn)生式C∷=α進(jìn)行歸約。(在分析表中：ACTION[k,a]=ri)(4).其它則報(bào)錯(cuò)。說明：

1.若上述的判定式成立，沖突可以解決，說明該文法是SLR（1）文法。

2.SLR（1）分析表的構(gòu)造：僅是歸約項(xiàng)目(設(shè)：U∷=α·)，按FOLLOW(U)中終結(jié)符號(hào)填表。SLR(1)文法：如果對(duì)一個(gè)文法的LR(0)項(xiàng)目集或分析表中含有動(dòng)作沖突都能用上述方法解決，則稱該文法是SLR(1)文法。所構(gòu)造的分析表稱為SLR(1)分析表，使用SLR(1)分析表的分析器稱為SLR(1)分析器。例：設(shè)有表達(dá)式文法G[E]：E∷=E+T|TT∷=T*F|FF∷=(E)|i假定該文法的項(xiàng)目集I2:E∷=T·,T∷=T·*F有動(dòng)作沖突，則用SLR(1)方法解決?！吲c歸約項(xiàng)目左部相關(guān)的FOLLOW(E)={+,),#}而移進(jìn)項(xiàng)目的”

·”后僅為*又∵{*}∩FOLLOW(E)={*}∩{+,),#}=Φ∴當(dāng)狀態(tài)I2面臨輸入符號(hào)為+,),或#時(shí)，應(yīng)使用產(chǎn)生式E∷=T進(jìn)行歸約當(dāng)狀態(tài)I2面臨輸入符號(hào)為*時(shí)，應(yīng)移進(jìn)*當(dāng)狀態(tài)I2面臨其它輸入符號(hào)，應(yīng)報(bào)錯(cuò)二、構(gòu)造SLR(1)分析表對(duì)于SLR(1)文法，若要構(gòu)造該文法的SLR(1)分析表,只要將構(gòu)造LR(0)分析表的算法的第2條改為：若歸約項(xiàng)目A∷=α·∈IK，對(duì)任何輸入符號(hào)a(或#)∈FOLLOW(A),則置ACTION[K,a]=rj,即用第j條產(chǎn)生式A∷=α進(jìn)行歸約。(假定A∷=α為文法第j條產(chǎn)生式)其1o,3o,4o,5o條用LR(0)分析表構(gòu)造算法。現(xiàn)在考察上例的三個(gè)項(xiàng)目集I1,I2,I9,中的沖突能否用SLR(1)方法解決

I1={E'::=E?,E::E?+T}∵FOLLOW(E')={#},又∵FOLLOW（E'）∩{+}=Φ,可解決；∴當(dāng)I1面臨輸入符號(hào)為+時(shí)，移進(jìn)+；面臨輸入符號(hào)＃時(shí)，按E'::=E歸約。在I2中：{E::=T?,T::=T?*F}

∵FOLLOW(E)={+,),#}與{*}不相交，可解決；∴狀態(tài)I2面臨輸入符號(hào)為+，），#時(shí)，按E::=T歸約；面臨輸入符號(hào)*移進(jìn)。在I9中：{E::=E+T?,T::=T?*F}∵FOLLOW(E)∩{*}={+,),#}∩{*}=Φ,可解決；∴狀態(tài)I9面臨輸入符號(hào)為+，)，＃時(shí)，按E::=E+T歸約；面臨輸入符號(hào)*移進(jìn)。其文法的項(xiàng)目集中移進(jìn)一歸約沖突可用SLR（1）方法解決，因此該文法是SLR（1）文法。構(gòu)造文法的SLR(1)分析表：僅歸約項(xiàng)目(設(shè)：U∷=α·)，按FOLLOW(U)中終結(jié)符號(hào)填表。狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5SLR(1)分析表的特點(diǎn)：下標(biāo)相同的歸約符號(hào)在同一狀態(tài)行中，且不布滿此行。步驟狀態(tài)棧符號(hào)棧輸入串ACTIONGOTO10#i+i*i#S5205#i+i*i#r63303#F+i*i#r42402#T+i*i#r21501#E+i*i#S66016#E+i*i#S570165#E+i*i#r6380163#E+F*i#r4990169#E+T*i#S71001697#E+T*i#S511016975#E+T*i#r6101201697(10)#E+T*F#r39130169#E+T#r111401#E#acc

例：分析句子：i+i*i#的過程一、SLR(1)不能解決的項(xiàng)目沖突§4.LR(1)分析法例：有下列拓廣文法G’0S’∷=S1S∷=L=R2S∷=R3L∷=*R4L∷=I5R∷=LI0：S’∷=·SS∷=·L=RS∷=·RL∷=·*RL∷=·iR∷=·LI1：S’∷=S·I2：S∷=L·=RR∷=L·I3：S∷=R·I4：L∷=*·RR∷=·LL∷=·*RL∷=·iI6:S∷=L=·RR∷=·LL∷=·*RL∷=·iI7:L∷=*R·I8:R∷=L·I5:L∷=i·I9:S∷=L=R·SR*LLi=RLi*iR*其中I2是有沖突的項(xiàng)目(FOLLOW(R)∩{=}={=,#}∩{=}≠Φ)

因此，I2中移進(jìn)和歸約沖突不能用SLR(1)方法解決，需用LR(1)方法來解決。問題：若按R::=L歸約:狀態(tài)棧符號(hào)棧輸入符號(hào)

0#i=i#05#i=i#02#L=i#03#R=i#可見該文法G’不含“R=”為前綴的規(guī)范句型，因此，用R::=L進(jìn)行歸約是無效的歸約。這說明：(1)用SLR(1)方法解決移進(jìn)與歸約沖突時(shí)，對(duì)歸約項(xiàng)目A::=α·，只要當(dāng)前輸入符號(hào)為a∈FOLLOW(A)時(shí)，就可以確定采用產(chǎn)生式A::=α·進(jìn)行歸約，而不考察符號(hào)串α所在規(guī)范句型中的環(huán)境。即如果棧中符號(hào)為#δα，歸約后變成為#δA，當(dāng)前讀到的輸入符號(hào)是a,若#δAa不是文法的活前綴的規(guī)范句型，那么，這種歸約是無效歸約。

(2)LR(1)方法的基本思想：當(dāng)試圖用某一產(chǎn)生式A::=α歸約棧頂符號(hào)串α?xí)r，不僅要查看棧中符號(hào)串δα，還應(yīng)向前掃描一個(gè)輸入符號(hào)a，只有當(dāng)確實(shí)構(gòu)成文法規(guī)范句型的活前綴時(shí)，才能用A::=α歸約。為此，在原來LR（0）項(xiàng)目中增加展望信息a。這些展望信息有利于克服動(dòng)作沖突和排除無效歸約。即需要重新定義稱之為LR（1）項(xiàng)目。二.LR（1）項(xiàng)目集規(guī)范族的構(gòu)造1.LR(1)項(xiàng)目一個(gè)LR(1)項(xiàng)目是一個(gè)二元組[A∷=α·β,a],其中A∷=α·β是一個(gè)LR（0）項(xiàng)目，a為終結(jié)符，稱為展望符或搜索符。當(dāng)β≠ε時(shí)，a對(duì)[A∷=α·β,a]移進(jìn)項(xiàng)目是無意義的；當(dāng)β=ε，a對(duì)歸約項(xiàng)目[A∷=α·,a]有意義，他表示當(dāng)[A∷=α·,a]是棧頂狀態(tài)的一個(gè)LR(1)項(xiàng)目時(shí)，僅在輸入符號(hào)為a時(shí)，才用A∷=α歸約，而不是對(duì)FOLLOW（A）中的所有符號(hào)都用A∷=α歸約。2.LR(1)項(xiàng)目集規(guī)范族的構(gòu)造構(gòu)造LR(1)項(xiàng)目集族的方法與構(gòu)造LR(0)的項(xiàng)目集族相似。可利用閉包函數(shù)Closure和轉(zhuǎn)換函數(shù)GO求解。(1)構(gòu)造LR(1)項(xiàng)目集I的閉包函數(shù)①I的任何項(xiàng)目屬于Closure(I)；②若項(xiàng)目[A∷=α·Bβ,a]屬于Closure(I)，B∷=r是文法中的一條產(chǎn)生式，b∈FIRST(βa),則[B∷=·r,b]也屬于Closure(I)。所得的Closure(I)是LR(1)的一個(gè)項(xiàng)目集（派生項(xiàng)目的展望符b的求法）③重復(fù)①②直到Closure(I)不再增大為止。注：對(duì)于文法G的拓廣文法G’的LR(1)仍然以[S’∷=·S,#]為I0初態(tài)集的初始項(xiàng)目，然后對(duì)其求Closure和GO函數(shù)，直到項(xiàng)目集不再增大為止。

b可能是從β推出的第一個(gè)終結(jié)符號(hào)。若β推出ε，則b就是a;若β推出不是ε，則將β推出的第一個(gè)終結(jié)符號(hào)作為b。(2)構(gòu)造轉(zhuǎn)換函數(shù)GO(I,X)令I(lǐng)是LR(1)項(xiàng)目集，x是文法符號(hào)，函數(shù)

GO(I,x)=Closure(J)J={[A∷=αx·β,a]|[A∷=α·xβ,a]∈I}例：有下列拓廣文法G’產(chǎn)生式LR(0)項(xiàng)目集規(guī)范族0S’∷=SI0={S’∷=·S,S∷=·L=R,S∷=·R,L∷=·*R,L∷=·I,R∷=·L}I6={S∷=L=·R,R∷=·L,L∷=·*R,L∷=·i}1S∷=L=RI1={S’∷=S·}I7={L∷=*R·}2S∷=RI2={S∷=L·=R,R∷=L·}I8={R∷=L·}3L∷=*RI3={S∷=R·}I9={S∷=L=R·}4L∷=iI4={L∷=*·R,R∷=·L,L∷=·*R,L∷=·i}5R∷=LI5={L∷=i·}其中I2是有沖突的項(xiàng)目(FOLLOW(R)∩{#}≠Φ)求LR(1)項(xiàng)目集族解：首先由初始項(xiàng)目：[S’∷=·S,#]求初始項(xiàng)目集I0:依據(jù)構(gòu)造LR(1)項(xiàng)目集I的閉包Closure函數(shù)求I0集中的其余項(xiàng)目：①

已知[S’∷=·S,#]∈Closure(I0),用[S’∷=·S,#]去匹配算法中的[A∷=α·Bβ,a]，即令A(yù)=S',α=ε,B=S,β=ε,a=#。但Closure函數(shù)告訴我們，對(duì)于形如B::=γ

的產(chǎn)生式及終結(jié)符b∈FIRST(βa),應(yīng)將項(xiàng)目[B∷=·γ,b]加到Closure(I0)中。在該文法中：B::=γ應(yīng)是S::=L=R和S::=R(∵B=S),而且由于β=ε,a=#,所以，b就是a為#。因此,[s∷=·L=R,#]和[S∷=·R,#]都要加入到Closure(I0)中。

②已知[s∷=·L=R,#]∈Closure(I0),(匹配:A=S,α=ε,B=L,β==R,a=#)。

L::=*R和L::＝i是文法的產(chǎn)生式，又b∈FIRST(βa)＝FIRST(＝Ra)={=},即有[L∷=·*R,=/#]和[L∷=·i,=/#]都要加入到Closure(I0)中。

③

已知[s∷=·R,#]∈Closure(I0),(匹配:A=S,α=ε,B=R,β=ε)。

R::=L是文法的產(chǎn)生式，且由于β=ε,則有b=a=#,即有[R∷=·L,#]要加入到Closure(I0)中。至此，完成文法G’的I0項(xiàng)目集的構(gòu)造：I0:[S’∷=·

S,#] 派生 [s∷=·L=R,#][S∷=·R,#] [L∷=·*R,=/#][L∷=·i,=/#] [R∷=·L,#]根據(jù)LR(1)的GO函數(shù)定義求LR(1)其他項(xiàng)目集，需要針對(duì)I0中"."后的不同文法符號(hào)X，計(jì)算GO(I0,，X)。在此，X={S,L,R,*,i}。由GO(I0,S)可求得：

I1={[S’∷=S·,#

]}由GO(I0,L)可求得{[S∷=L·=R,#

],[R∷=L·,#]},再計(jì)算Closure：

I2=GO(I0,L)＝Closure({[S∷=L·=R,#

],[R∷=L·,#]})

＝{[S∷=L·=R,#

],[R∷=L·,#]}由GO(I0,R)可求得：

I3={[S∷=R·,#

]}由GO(I0,*)可求得：I4=GO(I0,*)＝Closure({[L∷=*·R,=/#

]})={[L∷=*·R,=/#

],[R∷=·L,=/#

],[L∷=·*R,=/#

],[L∷=·i,=/#

]}由GO(I0,i)可求得：I5={[L∷=i·,=/#

]}

至此，完成文法G’的I0項(xiàng)目集的GO計(jì)算。I1,I3，I5，不再產(chǎn)生新的項(xiàng)目集，I2和I4產(chǎn)生新的項(xiàng)目集如下：

由GO(I2,=)可求得：I6={[S∷=L=·R,#

],[R∷=·L,#

],[L∷=·*R,#

],[L∷=·i,#

]}由GO(I4,R)可求得：I7={[L∷=*R·,=/#

]}由GO(I4,L)可求得：I8={[R∷=L·,=/#

]}由GO(I6,R)可求得：I9={[S∷=L=R·,#

]}由GO(I6,L)可求得：I10={[R∷=L·,#

]}由GO(I6,*)可求得：

I11={[L∷=*·R,#

],[R∷=·L,#

],[L∷=·*R,#],[L∷=·i,#]}由GO(I6,i)可求得：I12={[L∷=i·,#

]}對(duì)于I11,計(jì)算GO（I11，X），此時(shí)I11中的X＝{R，L，*，i}由GO(I11,R)可求得：I13={[L∷=*R·,#

]}由GO(I11,L)可求得：{[R∷=L·,#

]}=I10由GO(I11,*)可求得：

{[L∷=*·R,#

],[R∷=·L,#

],[L∷=·*R,#],[L∷=·i,#]}=I11由GO(I11,i)可求得：{[L∷=i·,#

]}=I12注：①可將LR(1)項(xiàng)目看成兩個(gè)部分組成：一部分與LR(0)項(xiàng)目相同，我們稱為心。另一部分為向前搜索符集合。構(gòu)造LR(1)分析表與構(gòu)造LR(0)分析表大部分相同。僅歸約項(xiàng)目的歸約動(dòng)作取決于向前搜索字符集。若當(dāng)前輸入符號(hào)屬于該集合才歸約，否則出錯(cuò)。②LR(1)項(xiàng)目集族多于LR(0)項(xiàng)目集族(狀態(tài)數(shù)多)。(LR(0)是I0---I9共10個(gè)項(xiàng)目集族；LR(1)是I0---I13共14個(gè)項(xiàng)目集族)③

只要不是二義性文法，如果LR（1）方法還有沖突，則可采取LR（2），......，LR（K）方法總可以解決沖突。例：有下列拓廣文法G’0S’∷=S1S∷=L=R2S∷=R3L∷=*R4L∷=I5R∷=L識(shí)別G’文法LR(1)方法的DFAI0：S'::=?S,#S::=?L=R,#S::=?R,#L::=?*R,=/#L::=?i,=/#R::=?L,#I1:

S'::=S?,#I2:S::=L?=R,#R::=L?,#I12:

L::=i?,#I7:L::=*R?,=/#SLRiI5:

L::=i?,=/#i*I4:L::=*?R,=/#R::=?L,=/#L::=?*R,=/#L::=?i,=/#I6:

S::=L=?R,#R::=?L,#L::=?*R,#L::=?i,#=I8:R::=L?,=/#*RI3:S::=R?,#I11:

L::=*?R,#

R::=?L,#L::=?*R,#L::=?i,#I9:

S::=L=R?,#I10：

R::=L?,#I13:L::=*R?,#*RLiLR*i三、構(gòu)造LR(1)分析表構(gòu)造LR(1)分析表的過程：

已知已構(gòu)造某文法的LR(1)項(xiàng)目集族X,X={I0,I1,…,In}，IK的K為分析器的狀態(tài)。則：動(dòng)作表ACTION和狀態(tài)轉(zhuǎn)換表GO構(gòu)造如下：(1)若項(xiàng)目[A∷=α·aβ,b]∈IK,且GO(IK,a)=Ij,其中a∈VT,則置ACTION[K，a]為Sj,即把輸入符號(hào)a移入符號(hào)棧；狀態(tài)j移入狀態(tài)棧;(2)若項(xiàng)目[A∷=α·,a]∈IK,則置ACTION[K，a]=rj,其中a∈VT,rj動(dòng)作含義是把當(dāng)前棧頂?shù)姆?hào)串α歸約為A(用A∷=α歸約)，j為文法中產(chǎn)生式A∷=α的編號(hào)。(3)若項(xiàng)目[S’∷=S·]∈IK，則置ACTION[K，#]=”acc“,表示接受。(4)若GO(IK,A)=Ij,其中A∈VN,則置GO[K，A]=”j”,(A∈VN),表示轉(zhuǎn)入j狀態(tài)，置當(dāng)前文法符號(hào)棧頂為A，狀態(tài)棧頂為j。(5)凡不能用上述方法填入的分析表元素，均置“報(bào)錯(cuò)標(biāo)志”(用空白或error)。ACTIONGOTOi*=#S’SLR0S5S41231acc2S6r53r24S5S4875r4r46S12S111097r3r38r5r59r110r511S12S11101312r413r3根據(jù)上述(1)~(5)過程構(gòu)造上例的LR(1)分析表如左：.移進(jìn)項(xiàng)目：根據(jù)“·”后的終結(jié)符填表。

.規(guī)約項(xiàng)目：根據(jù)搜索符號(hào)填表。LR(1)分析表的特點(diǎn)：下標(biāo)相同的歸約符號(hào)分布在不同的行中注：①如果一個(gè)文法的LR(1)分析表中不含多重定義(無沖突)則稱該文法為LR(1)文法。②一個(gè)文法是LR(0)文法，則它也一定是SLR(1)文法，也是LR(1)文法(也一定是LALR(1)文法)，反之不一定成立。

③LR(1)的沖突項(xiàng)目[U∷=x·by,a]和[U∷=x·,b]即搜索符號(hào)與移進(jìn)符號(hào)相同。

④

LR(1)方法產(chǎn)生的狀態(tài)數(shù)很多。導(dǎo)致存儲(chǔ)容量增加，為此引入了LALR(1)分析方法(即合并同心集的方法)解決的主要問題：在LR(1)方法中，由于按搜索符將同一項(xiàng)目集分裂成多個(gè)項(xiàng)目集，從而引起狀態(tài)數(shù)得急劇增加，導(dǎo)致分析表占用的空間多和分析時(shí)間長的問題。LALR(1)分析法是介于SLR(1)和LR(1)之間的一種語法分析方法。即，它解決了SLR(1)分析法中所不能解決的沖突動(dòng)作，且其分析表的狀態(tài)個(gè)數(shù)與SLR(1)分析表中的狀態(tài)個(gè)數(shù)相同。LALR(1)分析法的基本思想：將LR(1)項(xiàng)目集規(guī)范族中所有同心的項(xiàng)目集合并為一個(gè)項(xiàng)目集，從而減少項(xiàng)目集的個(gè)數(shù)?！?.LALR(1)分析法一、同心的LR(1)項(xiàng)目集的合并所謂同心的LR(1)項(xiàng)目集是指兩個(gè)LR(1)項(xiàng)目集中，除了搜索符不同之外，核心部分是相同的。同心的LR(1)項(xiàng)目集的合并指將LR(1)項(xiàng)目集中核心部分相同的項(xiàng)目合并其搜索符，且核心部分不變。例：上節(jié)的例子中，I4與I11，I5與I12，I7與I13，I8與I10是同心的項(xiàng)目集：I4＝{[L∷=*·R,=/#],[R∷=·L,=/#],[L∷=·*R,=/#],[L∷=·i,=/#]}I11={[L∷=*·R,#],[R∷=·L,#],[L∷=·*R,#],[L∷=·i,#]}合并：I4,11={[L∷=*·R,=/#],[R∷=·L,=/#],[L∷=·*R,=/#],[L∷=·i,=/#]}同理：I5,12={[L∷=i·,=/#]}I7,13={[L∷=*R·,=/#]}I8,10={[R∷=L·,=/#]}

對(duì)合并同心集后的項(xiàng)目集的轉(zhuǎn)換函數(shù)GO(I,x)仍為同心集。例：GO(I4,11,i)=GO(I4,i)∪GO(I11,i)=I5∪

I12=I5,12GO(I4,11,R)=GO(I4,R)∪GO(I11,R)=I7∪

I13=I7,13GO(I4,11,*)=GO(I4,*)∪GO(I11,*)=I4∪

I11=I4,11GO(I4,11,L)=GO(I4,L)∪GO(I11,L)=I8∪

I10=I8,10二、LALR(1)分析表的構(gòu)造構(gòu)造LALR(1)分析表的過程：(1)構(gòu)造拓廣文法G’的LR(1)項(xiàng)目集族。(2)合并同心的項(xiàng)目集，構(gòu)造LALR(1)項(xiàng)目集族。例：上例LALR(1)項(xiàng)目集族：(3)若LALR(1)項(xiàng)目集族中不存在歸約－歸約沖突，則文法是LALR(1)文法。LALR(1)分析法分析表的構(gòu)造與LR(1)分析表的構(gòu)造基本相同。合并同心集后的LALR(1)分析表：ACTIONGOTOi*=#SLR0S5,12S4,111231acc2S6r53r24,11S5,12S4,118,107,135,12r4r46S5,12S4,118,1097,13r3r38,10r5r59r1三、LALR(1)分析法中的問題1.合并同心集后，若有沖突則只能是歸約-歸約沖突，而不可能是移進(jìn)-歸約沖突。若文法是LR(1)文法，即它的LR(1)項(xiàng)目集中不存在動(dòng)作沖突，但合并同心集后若出現(xiàn)沖突，則：①該文法只能是LR(1)文法，不是LALR(1)文法。②該沖突只能是歸約-歸約的沖突。例：設(shè)有拓廣文法G[S’]:0.S’

∷=S1.S∷=aAd2.S∷=bBd3.S∷=aBe4.S∷=bAe5.A∷=c6.B∷=c直接構(gòu)造它的LR(1)項(xiàng)目集如下：

I0＝{[S’∷=·S,#],[S∷=·aAd,#],[S∷=·bBd,#],[S∷=·aBe,#]}I1={[S’∷=S·,#]}I2＝{[S∷=a·Ad,#],[S∷=a·Be,#],[A∷=·c,d],[B∷=·c,e]}I3＝{[S∷=b·Bd,#],[S∷=b·Ae,#],[B∷=·c,e],[A∷=·c,e]}I4={[S∷=aA·d,#]}I5={[S∷=aB·e,#]}I6={[A∷=c·,d],[B∷=c·,e]}I7={[S∷=bB·d,#]}I8={[S∷=bA·e,#]}I9={[A∷=c·,e],[B∷=c·,d]}I10＝{[S∷=aAd·,#]I11＝{[S∷=aBe·,#]I12＝{[S∷=bBd·,#]I13＝{[S∷=bAe·,#]檢查每個(gè)項(xiàng)目集，都不含有沖突，因此，該文法是LR(1)文法。但存在同心項(xiàng)目集:I6和I9;I6={[A∷=c·,d],[B∷=c·,e]}I9={[A∷=c·,e],[B∷=c·,d]}合并成一個(gè)項(xiàng)目集：

{[A∷=c·,d/e],[B∷=c·,d/e]}

顯然，在這個(gè)項(xiàng)目集中出現(xiàn)了歸約－歸約的沖突。即面臨輸入符號(hào)d或e時(shí)，不知該用產(chǎn)生式A∷=c或B∷=c哪一條進(jìn)行歸約。因而可判斷該文法不是LALR(1)文法。 我什么合并同心集中若有沖突只能時(shí)歸約－歸約沖突，而不可能是移進(jìn)－歸約沖突呢？因?yàn)椋?假定LR(1)文法的項(xiàng)目集IK與Ij是同心集：

IK={[A∷=α·,a1],[B∷=β·αγ,b1]} Ij={[A∷=α·,a2],[B∷=β·αγ,b2]}合并后的項(xiàng)目集： Ii,j={[A∷=α·,a1/a2],[B∷=β·αγ,b1/b2]}假設(shè)文法是LR(1)的，在IK中{a1}∩{a}=Φ,在IK中{a2}∩{a}=Φ,顯然在在IK,j中({a1}∪{a2})∩{a}=Φ

。這說明合并同心集后，不可能有移進(jìn)－歸約沖突。2.同心集合并后，用LALR(1)分析含有錯(cuò)誤的句子時(shí)，LALR(1)方法發(fā)現(xiàn)錯(cuò)誤的時(shí)間晚于LR(1)發(fā)現(xiàn)錯(cuò)誤的時(shí)間。因?yàn)長ALR(1)方法要多做不必要的歸約。但能準(zhǔn)確地找出錯(cuò)誤的位置。

任何一個(gè)二義性文法決不是LR類文法，與其對(duì)應(yīng)的LR分析表一定含有多重定義的元素。但對(duì)于某些二義性文法，若在其含有多重定義的分析表中加入足夠的無二義性的規(guī)則(給出優(yōu)先性和結(jié)合性的規(guī)定)，則會(huì)構(gòu)造出比相應(yīng)非二義性文法更優(yōu)越的LR分析器。討論：如何在二義性文法的LR分析表中加入足夠的無二義性規(guī)則來分析二義性文法所定義的語言。例如，算術(shù)表達(dá)式的二義性文法：E∷=E+E|E*E|(E)|i,相應(yīng)無二義性文法為：§6.二義性文法在LR分析法中的應(yīng)用E∷=E+T|TT∷=T*F|FF∷=(E)|i現(xiàn)構(gòu)造算術(shù)表達(dá)式二義性文法的LR(0)項(xiàng)目集規(guī)范族：I8其中：I1,I7和I8存在移進(jìn)－歸約沖突：

對(duì)于I1：因?yàn)镕OLLOW(E’)∩{+,*}={#}∩{+,*}=Φ,即遇到“#”歸約，遇“+”和“*”則移進(jìn)。

對(duì)于I7和I8：因?yàn)镕OLLOW(E)∩{+,*}={#，+,*,)}∩{+,*}≠Φ,因而I7和I8的沖突不能用LR(1)方法解決，二義性的文法也不能用LR(K)方法解決。但是，可以用+,*的優(yōu)先級(jí)和結(jié)合性解決這類沖突。

若規(guī)定“*”優(yōu)先級(jí)高于“+”的優(yōu)先級(jí)，且服從左結(jié)合，那么： 在I7中，由于“*”優(yōu)先于“+”，所以狀態(tài)7面臨“*”則移進(jìn)；又因?yàn)椤?”服從左結(jié)合，所以狀態(tài)7面臨“+”則用E∷=E+E歸約。 在I8中，由于“*”優(yōu)先于“+”，且“*”服從左結(jié)合，因此狀態(tài)8面臨“+”或“*”都用E∷=E*E歸約。構(gòu)造該二義性文法的分析表如下：

ACTIONGoTo+i*()#E0

S3

S2

11S4

S5

acc

2

S3

S2

63r4

r4

r4r4

4

S3

S2

75

S3

S2

86S4

S5

S9

7r1

S5

r1r1

8r1

r2

r2r2

9r3

r2

r3r3

注：①二義性文法的LR分析表所含狀態(tài)數(shù)比相應(yīng)的非二義性文法的LR分析表所含的狀態(tài)數(shù)要少。②二義性文法規(guī)定了優(yōu)先關(guān)系和結(jié)合性后的LR分析速度比相應(yīng)的非二義性文法的LR分析速度要快。§7.小結(jié)及舉例一、小結(jié)1.LR分析法是一種規(guī)范歸約方法，關(guān)鍵部分是構(gòu)造LR分析表對(duì)LR(0)或SLR(1)分析表，構(gòu)造LR(0)項(xiàng)目集規(guī)范族，而對(duì)LR(1)或LALR(1)分析表，則構(gòu)造LR(1)項(xiàng)目集規(guī)范族。構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA將DFA轉(zhuǎn)換成相應(yīng)的LR分析表四種分析表的構(gòu)造基本相同，僅對(duì)含歸約項(xiàng)目的項(xiàng)目集，構(gòu)造分析表的元素有所不同，文法都要拓廣。2.LR文法的判別文法是否是二義性的根據(jù)項(xiàng)目集中是否含有沖突項(xiàng)目判斷3.LR類中4種文法的關(guān)系：

LR(0)SLR(1)LALR(1)LR(1)

是LR(0)文法一定是SLR(1)文法或LALR(1)文法或LR(1)文法。

是SLR(1)文法一定是LALR(1)，反之不一定成立。是LALR(1)文法一定是LR(1)，反之不一定成立。4.問題：構(gòu)造DFA構(gòu)造分析表及熟悉對(duì)給定句子的分析過程LR類文法的判別熟悉對(duì)給定優(yōu)先級(jí)和左結(jié)合性的二義性文法構(gòu)造分析表的處理方法。二、例子1LR(0),SLR(1),LR(1)及LALR(1)方法有何共同的特征？它們的本質(zhì)區(qū)別是什么？答：共同特性:用規(guī)范歸約的方法尋找句柄，即LR分析器的每一步工作都是由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所唯一確定的。本質(zhì)區(qū)別：尋找句柄的方法不同。如果當(dāng)前棧頂狀態(tài)為歸約狀態(tài)，則：對(duì)LR(0)，無論當(dāng)前輸入符號(hào)是什么，都認(rèn)為棧頂符號(hào)串為句柄而進(jìn)行歸約對(duì)SLR(1)，則對(duì)當(dāng)前輸入符號(hào)串加了一點(diǎn)限制，即該輸入符號(hào)必須屬于允許跟在句柄之后的字符范圍內(nèi)，才認(rèn)為棧頂符號(hào)串為句柄而進(jìn)行歸約。對(duì)LR(1)，對(duì)當(dāng)前輸入符號(hào)的限制更嚴(yán)格，它要求該輸入符號(hào)跟在棧頂符號(hào)串后面形成一個(gè)規(guī)范句柄的前綴時(shí)，才認(rèn)為棧頂?shù)倪@個(gè)符號(hào)串為句柄而進(jìn)行歸約。由于要對(duì)不同的輸入符號(hào)進(jìn)行判斷，所以LR(1)的狀態(tài)數(shù)要比LR(0),SLR(1)多。LALR(1):本質(zhì)上與LR(1)相同，只不過它把那些棧頂符號(hào)串相同，但當(dāng)前輸入符號(hào)不同（即認(rèn)為相同棧頂符號(hào)串為同心）的判斷合并為一（使?fàn)顟B(tài)數(shù)又減到與LR(0),SLR(1)一樣），只有在輸入符號(hào)跟在棧頂符號(hào)串后面形成一個(gè)規(guī)范句型的前綴時(shí)，才認(rèn)為棧頂?shù)倪@個(gè)符號(hào)串為句柄而進(jìn)行歸約。這樣存在：①由于棧頂符號(hào)串面對(duì)不同的輸入符號(hào)將會(huì)形成不同的規(guī)范句型的前綴，這樣，當(dāng)輸入時(shí)一個(gè)錯(cuò)誤的句子時(shí)，LALR(1)可能執(zhí)行多于的歸約動(dòng)作，而延誤發(fā)現(xiàn)錯(cuò)誤的時(shí)間。②合并同心集，可能帶來新的歸約－歸約沖突，但不會(huì)產(chǎn)生新的移進(jìn)－歸約沖突。例2：請(qǐng)指出下面的LR分析表(a),(b),(c)分別屬于LR(0),SLR(1)和LR(1)中的哪一種？并說明理由。狀態(tài)ACTIONGoTob#SB0S3

121

acc

2S4

53r2

4

r2

5

R1

狀態(tài)ACTIONGoToiK#P0S1S3