基礎(chǔ)編譯原理

1Sm不僅表征了從分析開始到目前已掃描過的輸入符號(hào)被歸約成$E+TSm可預(yù)測(cè)：根據(jù)歸約時(shí)所用的產(chǎn)1Sm不僅表征了從分析開始到目前已掃描過的輸入符號(hào)被歸約成$E+TSm可預(yù)測(cè)：根據(jù)歸約時(shí)所用的產(chǎn)生式（非終結(jié)符T的產(chǎn)生式推測(cè)未來可遇到的輸入符號(hào)僅是FOLLOW（T）＝，*),$}任意－符號(hào)：若讀的符號(hào)是*，根據(jù)文法可知+<*棧頂未形成句柄。*進(jìn)若讀的輸入符號(hào)是+，），$之一時(shí)，>+或），$E+為E若輸入不是上述4個(gè)符號(hào)，則表示輸入串有語法分析表由動(dòng)作表ACTION和狀態(tài)轉(zhuǎn)換表GOTO組狀態(tài)轉(zhuǎn)換表GOTOGOO[Si，X]規(guī)定了當(dāng)前狀態(tài)S面臨文法符號(hào)X應(yīng)轉(zhuǎn)換到下一個(gè)狀態(tài)。T.+E$一個(gè)LR分析器由3個(gè)部分組成進(jìn)、歸約、報(bào)錯(cuò)或接受不同的文法分析表內(nèi)容不LR分析器的關(guān)鍵部分是分析表的構(gòu)造二、LR分析器的組LR分析器的邏輯結(jié)輸入狀態(tài)棧符號(hào)棧 Sn...S1S0總控程分析表ACTIONLR分析器的工作原理和過一、LR方法的優(yōu)LR分析法：LR(0)分析SLR(1)方LR(1)方LALR(1)方2輸入串a(chǎn)acbb$的分析過步棧中狀棧中符輸入動(dòng)1232輸入串a(chǎn)acbb$的分析過步棧中狀棧中符輸入動(dòng)1234567890$$$$用第4條產(chǎn)生式歸用第3條產(chǎn)生式歸相應(yīng)于文法的LRSi當(dāng)前輸入符號(hào)a及?r表示按第j條產(chǎn)生式歸?acc表示接注意：ACTION和GOTO結(jié)合在一個(gè)數(shù)組abcdSA0123456789 r1r1r1r1r1r2r2r2r2r2S4S5S6r4r4r4r4r6r6r6r6r6r3r3r3r3r3r5r5r5r5127分析【例4.14】設(shè)文法G‘為{}elseif{用第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)棧}elseerror(}2.LR分析法及輸出：若W是句子則有正確信息，否則報(bào)移進(jìn)：把狀態(tài)S＝GOTO[S,a]和輸入符號(hào)a移入分析接受（acc）：表示分析成功報(bào)3.·注(1)文法3.·注(1)文法G的全部LR(0)項(xiàng)目是構(gòu)造識(shí)別文法所有規(guī)范2、LR(0)活前綴與句柄有以下三種情況活前綴中已含有句柄的全部符號(hào)，表明此時(shí)某一產(chǎn)生式A→的右邊已出現(xiàn)在棧頂，其相應(yīng)的分析動(dòng)作是用此產(chǎn)生式進(jìn)行歸約活前綴中已含有句柄的部分符號(hào)，此時(shí)意味著形如:A→αα2產(chǎn)生式右邊的子串α1已出現(xiàn)在棧頂，正期待著從剩余的輸入串中進(jìn)行歸約得到α2。活前綴中不含有句柄的任何符號(hào)，此時(shí)意味著正期待從剩余的輸入串中能看到由某個(gè)產(chǎn)生式A→α右部的α所推出的符號(hào)串。為了刻畫在分析過程中，文法的一個(gè)產(chǎn)生式右邊的符號(hào)串已有多大一示。針對(duì)上述三種情況，標(biāo)有園點(diǎn)的產(chǎn)A→α·A→α1·α2A→·αaAbAaA;Ab,a,a,aA,。注1)可歸前綴也是規(guī)范句型的活前綴活前綴可以是一個(gè)或多個(gè)規(guī)范句型的前綴綴。 用產(chǎn)生式4歸 <=aaAbb用產(chǎn)生式3<= 用產(chǎn)生式3歸 <= 用產(chǎn)生式1歸 歸約時(shí)，只參考當(dāng)前規(guī)范句型的前部分，它們依次為 aaAbaaAb是規(guī)范句型aaAbb的可歸約前綴aAbaAb是規(guī)范句型aAb的可歸約前綴 A是規(guī)范句型A的可歸約前注：它們正是上節(jié)分析過程表中，每次采用歸約動(dòng)作前，符號(hào)棧中的內(nèi)容，即4，6，8，91、文法規(guī)范句型的活前例：設(shè)有文法G[S]：(上下文無關(guān)文法4.5.2LR(0)分析LR(0)分析法表示的含義約；（規(guī)范歸約）;0：表示不必向后面查看輸入符號(hào)。LR分析方法的重點(diǎn)：分析表的構(gòu)造分析表的構(gòu)造過程構(gòu) 轉(zhuǎn)上下文無關(guān)文法＝＝>識(shí)別文法所有規(guī)范句型活前綴的 ＝＝>LR分析什么是文法所有規(guī)范句型的活前綴如何構(gòu)造識(shí)別活前綴的如何構(gòu)造LR的分析表4⑶初態(tài)：令I(lǐng)={S’→·S4⑶初態(tài)：令I(lǐng)={S’→·S⑷由I0求GO函數(shù)，得出I0后繼項(xiàng)目集利用GO(I0,xClosure(J)，可以求I0后繼項(xiàng)目集。I1：GO(I0,S)=Closure({S’→S·})={S’→S·}I2：GO(I0,A)=Closure({S→A·})={S→A·}⑵列出文法所有的LR(0)項(xiàng)1. 2. 3. 4. 5. 6. 7. 8. 9. 例：已知文法⑴拓廣文法G：加入0.S’→S（使"接受"項(xiàng)目唯一LR(0)項(xiàng)目集規(guī)范族的構(gòu)造DFA方法1o拓廣文法G為G’，方法：加入0.S’→S(S為G2o列出所有G’的LR(0)項(xiàng)目3o求DFA的初態(tài)①I中每一個(gè)LR(0)項(xiàng)目屬于②若開始A→α·Bβ屬于closure(I)(B則文法中關(guān)于B的產(chǎn)生式B→·γ的項(xiàng)目也屬于③重復(fù)上述過程，直到closure(I)不再增大為止④再由I0求狀態(tài)轉(zhuǎn)換GO(I0,x)=closure(J)J={A→αX·β|A→α·Xβ∈I從而得出I0后繼項(xiàng)目集。⑤根據(jù)求出的項(xiàng)目集畫 構(gòu)造識(shí)別文法所有規(guī)范句型活前綴DFA移進(jìn)項(xiàng)目：U→x·ay(x，y為符號(hào)串，a∈VT)即圓點(diǎn)待約項(xiàng)目：U→x·By(B∈VN)即圓點(diǎn)后為非終結(jié)符歸約項(xiàng)目：形如U→x·(x∈VT)即圓點(diǎn)在最右端的項(xiàng)目接受項(xiàng)目：對(duì)識(shí)別符號(hào)的歸約項(xiàng)目，形如：U→E·(E為注：可按照一定的規(guī)則，將這些項(xiàng)目組合成一些狀態(tài)，這些狀態(tài)實(shí)際上就是將要構(gòu)造的LR分析表的狀態(tài)。也可看作某個(gè)DFA的狀態(tài)集(一個(gè)狀態(tài))。DFA就能識(shí)別文法所有規(guī)范句型的活前綴。53o若項(xiàng)目S’S·∈IK，則置ACTION[K，$]=”acc“,表示接4oIA)j,則置O[53o若項(xiàng)目S’S·∈IK，則置ACTION[K，$]=”acc“,表示接4oIA)j,則置O[A=AVKAA移入文法符號(hào)棧，5o凡不能用上述1o---4o方法填入分析表中的元素，均置【例4.15自學(xué)習(xí)題4.54.8(1)(2)4、構(gòu)造LR(0)I1,I2….In；令包含項(xiàng)目S’·S的項(xiàng)目集Ik的下標(biāo)k為分ACTION和GOTO表的構(gòu)造步驟1o若項(xiàng)目Aα·aβ∈IK,且轉(zhuǎn)換函數(shù)G0(IK,a)=Ij,當(dāng)a為終結(jié)棧；狀態(tài)j移入狀態(tài)棧。－－移2o若項(xiàng)目Aα·∈IK,則對(duì)任何終結(jié)符號(hào)a和結(jié)束符號(hào)$，臨的符號(hào))－－歸約2.LR(0)文①移進(jìn)項(xiàng)目和歸約項(xiàng)目同時(shí)存在：如A→a·Aβ移進(jìn)項(xiàng)目 B→γ·歸約項(xiàng)②多個(gè)歸約項(xiàng)目并存：如 則稱文法G’為L(zhǎng)R(0)文法對(duì)歸約與歸約的沖突；面臨什么符號(hào)輸入都不能確定歸約A，或者為B②僅文法為L(zhǎng)R(0)時(shí)，才能構(gòu)造不會(huì)沖突的LR(0)分析表構(gòu)成識(shí)別一個(gè)文法 前綴的項(xiàng)目集（ S 態(tài)）的全體稱為該 法的LR(0)項(xiàng)目集S’· 范族S· DFA圖中A· 歸約項(xiàng)目的項(xiàng)A· 集，如 I2,I3,I5,I6,I8,I10，表S→· DFA達(dá)到這些狀B→·aBb B→·d B→aB·b柄，這些狀態(tài)稱為句 柄識(shí)別態(tài)dI： ： 接受狀態(tài)；表示成完成輸入串的識(shí)別用S’→S.進(jìn)行最后次歸約.：B→B→A→A→aA·A→·aAbA→a·AbA→·CB→·aBbB→a·BbB→·dAIBIaS→A→：S→S’→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,I9I8：G0(I7,b)=Closure({A→aAb·})={A→aAb·}I10：G0(I9,b)=Closure({B→aBb·})={B→aBb·}又因?yàn)镮8,I10無后繼項(xiàng)目，結(jié)束。I3：GO(I0,B)=Closur