編譯原理(清華)第七章LR分析法

第7章LR分析法學(xué)習(xí)目標：掌握：LR（0）分析，SLR（1）分析理解：活前綴，可歸前綴了解：LR(1)、LALR(1)分析思想2023最新整理收集do

something7.1 LR分析概述7.2 LR(0)分析7.3 SLR(1)分析7.4 LR(1)、LALR(1)分析思想回顧：自底向上分析實現(xiàn)的基本思想——“移進－歸約”方法

(1)

S→aAcBe(2)

A→b (3)

A→Ab(4)B→d判斷輸入串a(chǎn)bbcde#是否為該文法的句子歸約（S→aAcBe）##aAcBe10）接受##S11）移進ee##aAcB9）歸約（B→d）e##aAcd8）移進dde##aAc7）歸約（A→Ab）cde##aAb5）移進ccde##aA6）移進bbcde##aA4）歸約（A→b）bcde##ab3）移進bbbcde##a2）移進aabbcde##1）動作輸入符號串符號棧步驟LR分析法： 根據(jù)當前分析棧中的符號串（通常以狀態(tài)表示）和向右順序查看輸入串的K個（K>=0）符號就可唯一地確定句柄。LR(K)的含義：L表示從左到右掃描輸入串R表示最左規(guī)約（即最右推導(dǎo)的逆過程）K表示向右查看輸入串符號的個數(shù) 當K=1時，能滿足當前絕大多數(shù)高級語言編譯程序的需要，所以著重介紹LR(0),SLR(1),LR(1),LALR(1)方法7.1LR分析概述LR分析的特點：是規(guī)范歸約適用范圍廣，適用于大多數(shù)上下文無關(guān)文法描述的語言分析速度快，能準確定位錯誤缺點：LR分析器的構(gòu)造工作量大LR分析器的組成總控程序：所有LR分析器總控程序相同。分析表：不同文法有不同的分析表同一文法采用的LR分析器不同，分析表也不同分析表分為ACTION表（動作表）和GOTO表（狀態(tài)轉(zhuǎn)換表）。分析棧： 包括狀態(tài)棧S和文法符號棧X。 分析表是LR分析器的核心LR分析表：列標題為狀態(tài)，行標題為文法符號GOTO表示當前狀態(tài)面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)。ACTION表示當前狀態(tài)面臨輸入符號時應(yīng)采取的動作ACTIONGOTOacebd#acebd#SAB0S211acc2SS133r2r2r2r2r2r2為了節(jié)省空間，將ACTION和GOTO中關(guān)于終結(jié)符號的各列合并起來ACTIONGOTOacebd#acebd#SAB0S211acc2SS133r2r2r2r2r2r2ACTIONGOTOacebd#SAB0S211acc2S1S33r2r2r2r2r2r2ACTION表中的動作有4種：移進(Sk)： 把狀態(tài)k移入狀態(tài)棧，若當前狀態(tài)是i，且k=GOTO[i,a]，把a移入符號棧歸約(rk)： 用第k條產(chǎn)生式進行歸約，此時棧頂形成了句柄β，文法中第k條產(chǎn)生式為A->β，且|β|=r，歸約時從狀態(tài)棧和符號棧中彈出r個符號，把A移入符號棧，j=GOTO[i,A]移入狀態(tài)棧，其中狀態(tài)i為修改指針后的棧頂狀態(tài)接受(acc)： 當符號棧只剩文法開始符S，并且當前輸入符為‘?！?，則分析成功報錯： 當狀態(tài)棧頂?shù)臓顟B(tài)遇到了不應(yīng)該出現(xiàn)的文法符號，則報錯，說明輸入串不是該文法的句子LR分析器的工作過程示意圖輸入串a(chǎn)1a2…an#總控程序ACTION表GOTO表nXn。。。。10X1#SP輸出狀態(tài)棧文法符號棧棧指針LR分析器：在分析的每一步，通用的總控程序按照狀態(tài)棧棧頂狀態(tài)i和當前輸入符號a查LR分析表，并執(zhí)行其中ACTION和GOTO規(guī)定的操作。LR分析例（LR(0)分析）文法G[S]：(1)S->aAcBe (2)A->b (3)A->Ab (4)B->d對輸入串a(chǎn)bbede＃進行LR分析ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR(0)分析表為：對輸入串a(chǎn)bbcde#的分析過程(1)S->aAcBe (2)A->b (3)A->Ab (4)B->dacc##011R1##aAcBe02357910S9e##aAc02359R4e##aAcd023588S8de##aAc02357S5cde##a026R3cde##aAb02365S6bcde##a024R2bcde##ab0243S4bbcde##a022S2abbcde##01GOTOACTION輸入串符號棧狀態(tài)棧步驟A333A37B71S17.2LR(0)分析使用LR(0)分析表的LR分析器稱為LR(0)分析器。LR(0)分析器在分析的過程中只根據(jù)符號棧的內(nèi)容就能確定句柄，不需要向右查看輸入符號對文法的限制較大，對絕大多數(shù)高級語言的語法分析器不適用構(gòu)造LR(0)分析表的思想和方法是構(gòu)造其他LR分析表的基礎(chǔ)。例文法： (1)

S→aAcBe (2)

A→b (3)

A→Ab (4)B→d判斷輸入串a(chǎn)bbcde#是否為該文法的句子歸約（S→aAcBe）##aAcBe10）接受##S11）移進ee##aAcB9）歸約（B→d）e##aAcd8）移進dde##aAc7）歸約（A→Ab）cde##aAb5）移進ccde##aA6）移進bbcde##aA4）歸約（A→b）bcde##ab3）移進bbbcde##a2）移進aabbcde##1）動作輸入符號串符號棧步驟LR(k)分析法通過活前綴來幫助確定句柄規(guī)范句型的可歸約前綴和活前綴(7.2.1)構(gòu)造文法的識別活前綴及可歸前綴的DFA(7.2.2，7.2.3)按DFA構(gòu)造相應(yīng)分析表——狀態(tài)轉(zhuǎn)換表和動作表(7.2.4)按分析表進行LR(k)分析(7.2.5)7.2.1規(guī)范句型的可歸約前綴和活前綴什么是可歸前綴？什么是活前綴？可歸前綴和活前綴在LR分析中起什么作用？前綴 如果Z=xy是一符號串，則x是Z的前綴，其中x,y為任意符號串（包括空串ε） 例：abc的前綴有ε，a，ab，abc。可歸前綴 規(guī)范句型中句柄之前包括句柄在內(nèi)的串稱為可歸前綴。例：文法G[S]，其中產(chǎn)生式后[i]是其編號S→aAcBe[1] A→b[2] A→Ab[3] B→d[4]輸入串a(chǎn)bbcde的最右推導(dǎo)（規(guī)范推導(dǎo)）過程：

S=>aAcBe[1]=>aAcd[4]e[1]=>aAb[3]cd[4]e[1] =>ab[2]b[3]cd[4]e[1]最左歸約(規(guī)范歸約)過程： ab[2]b[3]cd[4]e[1] 用產(chǎn)生式[2]歸約├aAb[3]cd[4]e[1] 用產(chǎn)生式[3]歸約├aAcd[4]e[1] 用產(chǎn)生式[4]歸約├aAcBe[1]

用產(chǎn)生式[1]歸約├S可歸前綴有：ab[2]，aAb[3]，aAcd[4]，aAcBe[1]活前綴定義： 形成可歸前綴之前(包括可歸前綴在內(nèi))的所有規(guī)范句型（符號棧內(nèi)部分）的前綴稱為活前綴。即規(guī)范句型的不含句柄右邊符號的前綴稱為活前綴。

例：規(guī)范句型aAbcde(下劃線為句柄)的可歸前綴為aAb，活前綴為：

ε，a，aA，aAb可歸前綴和活前綴在LR分析中的作用 在LR分析過程中，實際上是把活前綴列出放在符號棧中， 一旦在棧中出現(xiàn)可歸前綴，即句柄已經(jīng)形成，就用相應(yīng)的產(chǎn)生式進行歸約， 在分析的過程中，只要符號棧中的符號串是一個活前綴，就可保證已被分析過的部分是該文法規(guī)范句型的正確部分。歸約（S→aAcBe）##aAcBe10）接受##S11）移進ee##aAcB9）歸約（B→d）e##aAcd8）移進dde##aAc7）歸約（A→Ab）cde##aAb5）移進ccde##aA6）移進bbcde##aA4）歸約（A→b）bcde##ab3）移進bbbcde##a2）移進aabbcde##1）動作輸入符號串符號棧步驟7.2.2識別活前綴的有窮自動機回顧：有窮自動機——一種識別裝置分DFA和NFA0X13104

Y151識別1(0|1)*101的NFA用有窮自動機來識別活前綴和可歸前綴有窮自動機如何構(gòu)造？一個特例：構(gòu)造識別活前綴和可歸前綴的有窮自動機由文法的產(chǎn)生式構(gòu)造識別活前綴和可歸前綴的有窮自動機的方法用有窮自動機來識別活前綴和可歸前綴有窮自動機的輸入字符：終結(jié)符和非終結(jié)符狀態(tài)轉(zhuǎn)換：每把一個符號進棧，就看成識別過了該符號，進行狀態(tài)轉(zhuǎn)換。因為LR分析時棧中始終保持是活前綴，所以有窮自動機識別過的符號串也是活前綴。終態(tài)：當識別到可歸約前綴（表明在棧中形成句柄），認為到達了識別句柄的終態(tài)，執(zhí)行歸約例如：識別可歸前綴aAcBe的有窮自動機12aA3c46B5e構(gòu)造識別活前綴和可歸約前綴的有窮自動機的一個例子：由句子規(guī)范推導(dǎo)的逆過程直觀的看出它的活前綴和可歸前綴按活前綴和可歸前綴構(gòu)造識別它們的有窮自動機例文法G： S→aAcBe[1] A→b[2] A→Ab[3] B→d[4]拓廣文法為： S’->S[0] S→aAcBe[1] A→b[2] A→Ab[3] B→d[4]拓廣原因：文法開始符S可能出現(xiàn)在產(chǎn)生式的右部，在歸約過程中，不能判斷是歸約到文法的最初開始符，還是歸約到在產(chǎn)生式右部出現(xiàn)的開始符，S’只在產(chǎn)生式左部出現(xiàn)，確保不會混淆。S’->S[0] S→aAcBe[1] A→b[2] A→Ab[3] B→d[4]輸入串a(chǎn)bbcde的最右推導(dǎo)過程：S’=>S[0]=>aAcBe[1]=>aAcd[4]e[1]=>aAb[3]cd[4]e[1]=>ab[2]b[3]cd[4]e[1]可歸前綴有： ab[2]，aAb[3]，aAcd[4]， aAcBe[1]，S[0]輸入串a(chǎn)bbcde的可歸前綴有：S[0]，ab[2]，aAb[3]，aAcd[4]，aAcBe[1]識別其活前綴和可歸前綴的NFA為：X025914εεεεε1S*3a4b6aA78b10aA11c1213d15aA16c1719B18e識別活前綴和可歸前綴的NFA所有的狀態(tài)都是活前綴的識別狀態(tài)終態(tài)是句柄的識別態(tài)帶“*”號的狀態(tài)既是句柄識別態(tài)又是句子識別態(tài)，句子識別態(tài)僅有一個符號棧輸入串動作#abbcde#移進a#abbcde#移進b#abbcde#歸約(A->b)#aAbcde#移進b#aAbcde#歸約(A->Ab)#aAcde#移進c#aAcde#移進d#aAcde#歸約(B->d)#aAcBe#移進e#aAcBe#歸約(S->aAcBe)#S#接受X2a1*SA45b3b6c7dB89e識別活前綴和可歸前綴的DFA理解識別活前綴和可歸前綴的DFA和分析過程的對應(yīng)將NFA確定化得到：S[0]，ab[2]，aAb[3]，aAcd[4]，aAcBe[1]ACTIONGOTOacebd#SABXS211acc2S343r2r2r2r2r2r24S6S55r3r3r3r3r3r36S787r4r4r4r4r4r48S99r1r1r1r1r1r1對任何一個上下文無關(guān)文法只要構(gòu)造出它的識別活前綴和可歸前綴的有窮自動機，就可以構(gòu)造其相應(yīng)的分析表（ACTION表和GOTO表），進行LR分析S[0]，ab[2]，aAb[3]，aAcd[4]，aAcBe[1]X2a1*SA45b3b6c7dB89e識別活前綴和可歸前綴的DFA 以上示例中構(gòu)造DFA的方法是通過一個句子的歸約過程確定可歸前綴，但是：對于一個復(fù)雜的文法，其可歸前綴不是如此簡單就能計算出來示例中用一個句子歸約過程的所有活前綴和可歸前綴構(gòu)造出的DFA，恰好也是識別整個文法的活前綴和可歸前綴的DFA，這僅是一個特殊情況。對一個上下文無關(guān)文法需要求出它的所有活前綴和可歸前綴后才能構(gòu)造其識別該文法活前綴的DFA由文法的產(chǎn)生式構(gòu)造識別活前綴和可歸前綴的DFA的方法1.LR(0)項目文法的識別活前綴的有窮自動機以“項目”作為它的狀態(tài)在文法G中每個產(chǎn)生式的右部適當位置添加一個圓點構(gòu)成項目例：產(chǎn)生式U→XYZ對應(yīng)有4個項目[0]U→?XYZ [1]U→X?YZ[2]U→XY?Z [3]U→XYZ?

產(chǎn)生式A→ε只有一個項目A→?項目的含義：圓點在最左部（U→?XYZ）表示希望用產(chǎn)生式的右部歸約圓點的左部（U→X?YZ）表示分析過程中已識別過的部分圓點的右部（U→X?YZ）表示待識別部分圓點達到最右邊（U→XYZ?

）表示句柄已形成，可以進行歸約。LR(0)項目分類移進項目：形如A→α?аβ的項目，其中а∈VT,α,β∈V*。即圓點后面為終結(jié)符的項目。分析時把а移進符號棧。待約項目：形如A→α?Bβ的項目，其中B∈VN,α,β∈V*。即圓點后面為非終結(jié)符的項目。表明用產(chǎn)生式A的右部歸約時，首先要將B的產(chǎn)生式右部歸約為B，對A的右部才能繼續(xù)進行分析。也就是期待著繼續(xù)分析過程中首先能歸約得到B歸約項目：形如A→α?的項目，α∈V*,α=ε對應(yīng)的項目為A->?即圓點在最右端的項目。表明該產(chǎn)生式的右部已分析完，句柄已形成，可以把α歸約為A。接受項目：當歸約項目為S’→S?，其中S'是文法開始符即對文法開始符的歸約項目。表明輸入串可歸約為文法開始符，分析結(jié)束。開始項目：形如S’→?S的項目，其中S'是文法開始符。即拓廣文法開始符的產(chǎn)生式圓點在最左邊的項目。2.構(gòu)造識別活前綴的有窮自動機構(gòu)造識別活前綴的NFA拓廣文法G[S]為G’[S’]，即加入產(chǎn)生式S’→S以G’[S’]的每個項目為NFA的一個狀態(tài)，S’→?S為初態(tài)，其余每個狀態(tài)都為活前綴的識別態(tài)，所有歸約項目為終態(tài)(句柄識別態(tài))，S’→S?為接受態(tài)確定狀態(tài)轉(zhuǎn)換關(guān)系：若有項目i：A→α?Xβ，項目j：A→αX?β，則從狀態(tài)i到狀態(tài)j連一條標記為X的箭弧。若X∈VN，對于X的所有產(chǎn)生式圓點在最左邊的狀態(tài)k:X→?r，都從狀態(tài)i到狀態(tài)k連一條標記為ε的箭弧。用子集法把NFA確定化為DFA例文法G： E→aA|bB A→cA|d B→cB|d拓廣文法G’：S’→E E→aA|bB A→cA|d B→cB|dG’的所有LR(0)項目為：1．S’→?E 2．S’→E? 3．E→?aA4．E→a?A 5．E→aA? 6．A→?cA7．A→c?A 8．A→cA? 9．A→?d10.A→d? 11.E→?bB 12.E→b?B13.E→bB? 14.B→?cB 15.B→c?B16.B→cB? 17.B→?d 18.B→d?識別G’活前綴的NFA

ε*

dcddaB

BA

AEε

εεε

εε

ε111123245141517697810181613cG’的所有LR(0)項目為：1．S’→?E 2．S’→E? 3．E→?aA4．E→a?A 5．E→aA? 6．A→?cA7．A→c?A 8．A→cA? 9．A→?d10.A→d? 11.E→?bB 12.E→b?BE→bB? 14.B→?cB 15.B→c?BB→cB? B→?d B→d?

識別G’活前綴的DFAcba

I0：S’→·EE→·aAE→·bB

I4：A→c·AA→·cAA→·d

I2：E→a·AA→·cAA→·d

I3：E→b·BB→·cBB→·d

I5：B→c·BB→·cBB→·dI1：S’→E·

I8：A→cA·

I10：A→d·

I6：E→aA·

I7：E→bB·

I11：B→d·

I9：B→cB·EccBddBAddAc 通過列出拓廣文法的所有項目，進而構(gòu)造識別活前綴的NFA，再確定化為DFA的方法，工作量較大，不實用 實用的方法是直接構(gòu)造以項目集為狀態(tài)的識別活前綴的DFA7.2.3構(gòu)造以LR(0)項目集為狀態(tài)的識別活前綴的DFALR(0)項目集規(guī)范族 識別一個文法活前綴的DFA的每個狀態(tài)都是一個項目集，項目集(狀態(tài))的全體稱為這個文法的LR(0)項目集規(guī)范族。識別活前綴的DFA的構(gòu)造如何構(gòu)造DFA的一個狀態(tài)（項目集）如何由DFA的一個狀態(tài)求其他狀態(tài)1項目集I的閉包CLOSURE(I)如果I是文法G的一個項目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：I的項目均在CLOSURE(I)中；若A→α?Bβ屬于CLOSURE(I)，B∈VN，則

每一形如B→?r的項目也屬于CLOSURE(I)重復(fù)b）直到CLOSURE(I)不再擴大為止。說明：圓點后為終結(jié)符或在一個產(chǎn)生式的最后，求閉包時不會增加新的項目例S’→EE→aA|bB A→cA|d B→cB|d I={S’→?E}則CLOSURE(I)={S’→?E，E→?aA，E→?bB}CLOSURE(I)作為DAF的一個狀態(tài)2.狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)由DFA的一個狀態(tài)求其他狀態(tài)通過狀態(tài)轉(zhuǎn)換函數(shù)設(shè)I為文法G的某一項目集(狀態(tài))，X∈VN∪VT,則 GO(I,X)=CLOSURE(J) 其中J={任何形如A→αX?β的項目│A→α?Xβ∈I}稱J為“核”例S’→EE→aA|bB A→cA|d B→cB|dI={S’→?E，E→?aA，E→?bB}，則GO(I,E)=CLOSURE({S’→E?})={S’→E?}GO(I,a)=CLOSURE({E→a?A})={E→a?A,A→?cA,A→?d}GO(I,b)=CLOSURE({E→b?B})={E→b?B,B→?cB,B→?d}3.構(gòu)造以LR(0)項目集為狀態(tài)的DFA 構(gòu)造初始狀態(tài)IS0=CLOSURE({S’→?S})，并且它是未被標記的。從已經(jīng)構(gòu)造的DFA部分圖中選擇一個未被標記的狀態(tài)ISi，標記ISi，若項目集ISi中含有項目 U->x?Ry(R∈V,x,y為任一符號串)，且GO(ISi,R)=ISj，若ISj不在DFA中，則將ISj作為未被標記的加入DFA中，且從ISi出發(fā)引一條標記為R的弧到ISj，重復(fù)b)直到?jīng)]有未被標記的狀態(tài)為止。例拓廣文法G’：S’→E E→aA|bB A→cA|d B→cB|d構(gòu)造以LR(0)項目集為狀態(tài)的DFAS’→?ES’→E?E→a?A

aE→b?B

EbE→aA?A→c?A

cAA→d?E→bB?B→c?B

cB→d?A→cA?AB→cB?BdcddBcdE→?aAE→?bBI0I1I2I3I4I5I6I7I8I9I10I11A→?cAA→?dB→?cBB→?dA→?cAA→?dB→?cBB→?d7.2.4LR(0)分析表的構(gòu)造分析表的組成：動作表(ACTION)： 表示當前狀態(tài)下面臨輸入符應(yīng)做的動作是移進、歸約、接受或出錯，面臨的輸入符只包含終結(jié)符和‘?！D(zhuǎn)換表(GOTO)： 表示在當前狀態(tài)下面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài) 為了節(jié)省存儲空間，把關(guān)于終結(jié)符部分的GOTO表和ACTION表重疊，也就是把當前狀態(tài)下面臨終結(jié)符應(yīng)做的移進－歸約動作和轉(zhuǎn)向動作表示在一起LR(0)分析表的構(gòu)造算法設(shè)已構(gòu)造出LR(0)項目集規(guī)范族為C={I0，I1，…，In}，令項目集Ik對應(yīng)的狀態(tài)為k，含S’→?S項目的項目集對應(yīng)的狀態(tài)為初始狀態(tài)分析表的ACTION表和GOTO表構(gòu)造步驟為：若項目A→α?aβ∈Ik，a∈VT，且GO(Ik,a)=Ij，則置ACTION[k,a]=‘Sj’若項目A→α?Bβ∈Ik，B∈VN，且GO(Ik,B)=Ij，則置GOTO[k,B]=‘j’若項目A→α?∈Ik，且產(chǎn)生式A→α的編號為j，則對任何a（終結(jié)符和‘#’），置ACTION[k,a]=‘rj’若項目S’→S?∈Ik，則置ACTION[k,#]=‘a(chǎn)cc’不能用上述方法填入的分析表的元素均應(yīng)填上“報錯標志”。拓廣文法G’：(0)S’→E (1)E→aA (2)E→bB (3)A→cA(4)A→d (5)B→cB (6)B→d識別活前綴的DFA：S’→?ES’→E?E→a?A

aE→b?B

EbE→aA?A→c?A

cAA→d?E→bB?B→c?B

cB→d?A→cA?AB→cB?BdcddBcdE→?aAE→?bBI0I1I2I3I4I5I6I7I8I9I10I11A→?cAA→?dB→?cBB→?dA→?cAA→?dB→?cBB→?d10

aACTION

b

c

d

#EGOTOA狀態(tài)119876543210BLR(0)分析表1S2S3acc4S5S67S8S9r1r1r1r1r110S5S6r4r4r4r4r4r2r2r2r2r211S9S8r6r6r6r6r6r3r3r3r3r3r5r5r5r5r57.2.5LR(0)分析器的工作過程工作過程： 根據(jù)分析棧的棧頂狀態(tài)和輸入串的當前符號查分析表確定應(yīng)采取的動作（移進、歸約、接受或報錯），對狀態(tài)棧和符號棧進行相應(yīng)的操作。 具體說明如下：若ACTION[S,a]=Sj，a為終結(jié)符， 則把a移入符號棧，j移入狀態(tài)棧；若ACTION[S,a]=rj，a為終結(jié)符或＃， 則用第j個產(chǎn)生式（A->β）歸約，將兩個棧彈出k個元素，其中k為第j個產(chǎn)生式右部符號串長度，這時當前面臨符號為第j個產(chǎn)生式左部的非終結(jié)符（A）；若狀態(tài)棧當前的棧頂狀態(tài)為Sk，且GOTO[Sk,A]=j，則非終結(jié)符A移入符號棧，j移入狀態(tài)棧；若ACTION[S,a]=acc,a為＃， 則為接受，表明分析成功；若ACTION[S,a]=空白，則轉(zhuǎn)向出錯處理。(0)S’→E (1)E→aА (2)E→bB (3)A→cА(4)A→d (5)B→cB (6)B→d輸入串bccd＃的分析過程步驟狀態(tài)棧符號棧輸入串ACTIONGOTO1

2

3

4

56789

0#bccd#S303#bccd#S8038#bccd#S80388#bccd#S903889#bccd#####r6110388#bccr511038#bcr5703#br210#accB(11)B(11)B7E17.3SLR(1)分析項目集中的沖突 一個項目集中存在下列情況稱為項目沖突：移進—歸約沖突 移進項目A→α?aβ和歸約項目B→r?同在一個項目集中，當面臨輸入符a時，不能確定移進a還是把r歸約為B；歸約—歸約沖突 歸約項目A→β?和歸約項目B→r?同在一個項目集中，不管面臨什么輸入符都不能確定把β歸約為A還是把r歸約為B。 一個文法的LR(0)項目集規(guī)范族中的項目集不存在移進—歸約沖突，也不存在歸約—歸約沖突時，稱該文法為LR(0)文法。例：文法G’(0)S’→S (1)S→rD (2)D→D,i (3)D→i識別文法活前綴的DFA：

S’→?S

S’→S?

S→r?D

rS

S→rD?D→D?,iDD→i?D→D,?i,iS→?rDI0I1I2I3I4I5D→?D,iD→?iD→D,i?iI6在項目集I3中S→rD?為歸約項目，D→D?,i為移進項目，存在移進－歸約沖突，該文法不是LR(0)文法2.解決沖突的SLR(1)方法基本思想： 對于LR(0)有沖突的項目集用向前查看輸入符號串的一個符號的辦法加以解決解決方法： 對歸約項目A→r?,只有當輸入符號a∈FOLLOW(A)才進行歸約，縮小歸約范圍，有可能解決沖突。例：文法G’(0)S’→S (1)S→rD (2)D→D,i (3)D→i識別文法活前綴的DFA：

S’→?S

S’→S?

S→r?D

rS

S→rD?D→D?,iDD→i?D→D,?i,iS→?rDI0I1I2I3I4I5D→?D,iD→?iD→D,i?iI6Follow集S’#S#D#,對項目集I3，若當前輸入符為‘#’時，進行歸約，若當前輸入符為‘,’，進行移進操作，沖突得以解決SLR(1)的處理方法(算法)： 例：一個LR(0)規(guī)范族中項目集I含有沖突項目I={X→α?bβ?Α→r??Β→δ?},其中b∈VT， 如果FOLLOW(A)和FOLLOW(B)互不相交，且不含b，則當狀態(tài)I面臨某輸入符a時，可采用下列動作：若a=b，則移進；若a∈FOLLOW(A)，則用產(chǎn)生式A→r歸約；若a∈FOLLOW(B)，則用產(chǎn)生式B→δ歸約；此外，報錯。 一般地，一個LR(0)規(guī)范族中的項目集I 有m個移進項目：A1→α1?a1β1， A2→α2?a2β2，…，Am→αm?amβm n個歸約項目：B1→r1?，B2→r2?，…，Bn→rn?， 若移進符號集{a1，a2，…，am}和FOLLOW(B1)，F(xiàn)OLLOW(B2)，…，F(xiàn)OLLOW(Bn)兩兩交集為空， 則當狀態(tài)I面臨某輸入符a時，可采用以下動作：若a∈{a1，a2，…，am}，則移進；若a∈FOLLOW(Bi)，i=1,2,…,n，則用Bi→ri歸約；此外，報錯。

上述解決項目集(狀態(tài))中沖突的方法稱為SLR(1)方法（Simple因為只對有沖突的狀態(tài)才向前查看一個符號，以確定動作） 如果一個文法的LR(0)項目集規(guī)范族中某些項目集所含有的動作沖突都能用SLR(1)方法解決，則稱這個文法為SLR(1)文法SLR(1)分析表的構(gòu)造算法與LR(0)分析表的構(gòu)造類似，僅在含有沖突的項目集中分別進行處理。改進的SLR(1)方法： 對所有的歸約項目僅對當前輸入符號包含在該歸約項目左部非終結(jié)符的FOLLOW集中，才采取歸約動作。改進的SLR(1)分析表的構(gòu)造方法：

設(shè)已構(gòu)造出LR(0)項目集規(guī)范族為C={I0，I1，…，In}， 令項目集Ik對應(yīng)的狀態(tài)為k，含S’→?S項目的項目集為初態(tài)，分析表的ACTION表和GOTO表構(gòu)造步驟為：若項目A→α?aβ∈Ik，a∈VT，且GO(Ik,a)=Ij， 則置ACTION[k,a]=‘Sj’；若項目A→α?Bβ∈Ik，B∈VN，且GO(Ik,B)=Ij， 則置GOTO[k,B]=‘j’；若項目A→α?∈Ik，且產(chǎn)生式A→α的編號為j，

則對任何a(終結(jié)符和‘#’)，且a∈FOLLOW(A)， 置ACTION[k,a]=‘rj’；若項目S’→S?∈Ik，則置ACTION[k,#]=‘a(chǎn)cc’；不能用上述方法填入的分析表元素均應(yīng)填上“報錯標志”。例文法G’：(0)S’→S (1)S→rD (2)D→D,i (3)D→iFOLLOW(S’)={#} FOLLOW(S)={#} FOLLOW(D)={#，}

S’→?S

S’→S?

S→r?D

rS

S→rD?D→D?,iD→i?D→D,?i,iS→?rDI0I1I2I3I4I5D→?D,iD→?iD→D,i?iI6D狀態(tài)ACTIONGOTOr,i#SD0S2

1

1

acc2

S4

33S5

r14r3

r35

S6

6

r2

r27.4LR(1)、LALR(1)分析思想 仍有許多文法構(gòu)造的LR(0)項目集規(guī)范族存在的動作沖突不能用SLR(1)方法解決例如：文法G:(0)S'→S(1)S→L=R(2)S→R(3)L→*R(4)L→i(5)R→L識別文法活前綴的DFAI0:S’->?S

S->?L=RS->?RL->?*RL->?iR->?LI5:L→i?I2:S->L?=RR->L?I3:S->R?I4:L→*?RR→?LL→?*RL→?iI1:S’->S?I6:S→L=?RR→L?R→?LL→?iL→?*RI7:

L→*R?I8:

R→L?I9:S→L=R?SLR*i=RL*iRLi*I6:S→L=?RR→L?R→?LL→?iL→?*RFollow(R)={#,=}與移進符號集{*,i}交集為空，可用SLR(1)方法解決沖突I2:S->L?=RR->L?Follow(R)={#,=}與移進符號集{=}交集不為空，SLR(1)方法不能解決沖突，該文法不是SLR(1)文法。S'→SS→L=R|RL→*R|iR→LFollowS’#S#L=，#R#，=SLR(1)用FOLLOW信息作為展望信息（只對屬于FOLLOW集的輸入符號歸約），縮小了歸約范圍，消除了一些無效歸約，解決了項目集中的一些簡單的沖突。盡管FOLLOW(A)中包含了所有含A的句型中A后的可能終結(jié)符，但并不是每個含有A的句型中，A的后面都可以出現(xiàn)Follow(A)中的每一個符號，所以SLR(1)未能從根本上消除所有無效歸約。S'→S S→L=R|R L→*R|i R→LS’SL=R*RL在*L=R中，L可以被歸約為R，此時L后只能是‘=’，而不能是Follow(R)={#,=}中的‘?！疭’SL1=RL2在L1=L2中，L2可以被歸約為R，此時L2后只能是‘#’，而不能是Follow(R)={#,=}中的‘=’LR(1)方法正是要解決SLR(1)方法在某些情況下存在的無效歸約問題。7.4.1LR(1)分析思想LR(1)分析的基本思想 LR(1)方法按每個具體的句型設(shè)置展望信息。 例：如果存在如下的一些句型

…αAa…，…βAb…，…γAc…，則FOLLOW(A)={a,b,c} 處理到句型…αA，只當輸入符號為a時歸約； 處理到句型…βA，只當輸入符號為b時歸約； 處理到句型…γA，只當輸入符號為c時歸約；LR(1)分析 若[A→

?B]屬于項目集I時，則[B→?

]也屬于I，把FIRST(

)作為用產(chǎn)生式B→

歸約的搜索符（用以代替SLR(1)分析中的FOLLOW(B)），并把此搜索符號的集合也放在相應(yīng)項目的后面，這種處理方法即為LR(1)方法I0:S’??S,#S

?BB,#B?aB,a/bB?b,a/bI1:S’?S?,#I2:SB?B,#B?aB,#B?b,#I5:SBB?,#I6:Ba?B,#B?aB,#B?b,#I9:BaB?,#I4:Bb?,a/bI3:Ba?B,a/bB?aB,a/bB?b,a/bI8:BaB?,a/bI7:Bb?,#SBbbBbbaaaBBa文法G‘：(0)S’

S(1)BaB (2)SBB(3)BbLR(1)項目集和轉(zhuǎn)換函數(shù)心向前搜索符集合LR(1)的優(yōu)缺點：優(yōu)點：LR(1)分析對搜索符的計算方法比較確切，沒有無效歸約，適應(yīng)的文法更廣缺點：LR(1)分析表的狀態(tài)數(shù)目龐大。7.4.2LALR(1)分析思想LALR(1)方法是介于SLR(1)和LR(1)之間的一種方法，即其功能比SLR(1)強，比LR(1)弱。它具有SLR(1)的狀態(tài)數(shù)少的優(yōu)點和LR(1)的適用范圍廣的優(yōu)點。LALR(1)分析 對LR(1)項目集規(guī)范族合并同心集，若合并同心集后不產(chǎn)生新的沖突，則為LALR(1)項目集 LALR(1)分析大大減少項目集（狀態(tài)）的數(shù)目。分析可發(fā)現(xiàn)I3和I6，I4和I7，I8和I9分別為同心集I3:Ba?B,a/bB?aB,a/bB?b,a/bI6:Ba?B,#B?aB,#B?b,#I4:Bb?,a/bI7:Bb?,#I8:BaB?,a/bI9:BaB?,#I3,6:Ba?B,a/b/#B?aB,a/b/#B?b,a/b/#合并為I4,7:Bb?,a/b/#合并為I8,9:BaB?,a/b/#合并為同心集合并后不包含沖突，是LALR(1)項目集本章小結(jié)LR(0)、SLR(1)、LR(1)、LALR(1)方法比較實際上不同LR方法之間的主要區(qū)別就在于歸約的判定方法上：LR(0)是不看展望符判定歸約；SLR(1)是看展望符，但把所有B→

的展望符集均定義為Follow(B)。即把符號棧頂上的句柄

歸約為B的條件是：展望符為Follow(B)中的元素。換句話說，歸約任何位置上的B，都用統(tǒng)一的展望符集；LR(1)也是看展望符，但歸約不同位置上的B時，采用不同的展望符集。每個項由心與向前搜索符組成，搜索符長度為1。由于LR(1)方法對于歸約條件的判定比SLR(1)更精確，可大大減少移入/歸約沖突；LALR(1):對LR(1)項目集規(guī)范族合并同心集LR(0)、SLR(1)、LR(1)、LALR(1)分析表比較LR(0)分析表局限性大，但其構(gòu)造方法是其他構(gòu)造方法的基礎(chǔ)；SLR分析表雖然不是對所有文法都存在，但這種分析表較易實現(xiàn)又極有使用價值；LR分析表的分析能力最強，能適用于一大類文法，但是，實現(xiàn)代價過高（表過大）；LALR分析表的能力介于SLR和LR之間，實現(xiàn)效率較高。語法分析語法分析器的功能 識別輸入字符串的合法性和語法結(jié)構(gòu)，檢查程序是否有語法上的錯誤語法分析器的輸入如果詞法分析作為獨立的一遍，那么語法分析器的輸入是詞法分析后的結(jié)果——Token序列如果詞法分析不是獨立的一遍，那么詞法分析是語法分析器的一個子程序，每調(diào)用一次詞法分析就讀出一個單詞，并將其Token碼送給語法分析器總之，語法分析器的處理對象是單詞的Token碼例：有源程序beginx:=y+1;ifx=10theny:=10end語法分析器的掃描對象是下面的Token序列：beginid:=id+num;ifid=numthenid:=numend保留字、界符、算符的Token，我們用其本身代替標識符和常量的Token中實際還包含標識符的名字和常量值的信息，這些信息語法分析時不用（語義分析的時候使用）語法錯誤類別 語法錯誤及其處理由語法分析器來完成。常見的語法錯誤有下面一些：程序的開始單詞錯，表達式的開始單詞錯，語句的開始單詞錯，表達式的后繼單詞錯，語句的后繼單詞錯等等；標識符和常量單詞錯。如在const,var,procedure等保留字后面不是標識符，常量說明中‘=’后不是數(shù)字括號類錯誤：如begin－end不配對，if－else不配對分隔符錯：如賦值語句左部變量后不是賦值號等語法分析方法 在實際編譯器中用得最多的是LL(1)和LALR(1)分析技術(shù)（或它們的變種——遞歸下降和SLR(1)） LL(1)與LALR(1)的比較簡單性： LL(1)和LALR(1)的驅(qū)動器都簡單，但LL(1)的概念比LALR(1)簡單得多，LL(1)比LALR(1)更簡單些

一般性

兩者都不能處理二義性文法。但所有LL(1)文法都是LALR(1)文法。LL(1)分析不能處理含左遞歸和左公共因子的文法。LALR(1)在一般性方面具有優(yōu)勢。語義動作的插入

LL(1)允許語義動作出現(xiàn)在產(chǎn)生式右部的任何地方；LALR(1)只允許語義動作出現(xiàn)在產(chǎn)生式右部的末尾，LL(1)語義動作的插入更靈活錯誤校正

LL(1)分析棧中保存著待匹配的語法符號，這些信息對于確定可能的錯誤校正是有用的；而LALR(1)分析棧則保存著已被掃描過的信息，因此確定錯誤校正不那么簡單?？傊琇L(1)的錯誤校正相對好做一些。

分析表大小

在空間需求上LL(1)具有明顯的優(yōu)勢

結(jié)論：LL(1)除了在一般性方面比LALR(1)差以外，其它方面都占有優(yōu)勢。語法錯誤的處理處理原則：希望能準確地指出出錯位置和錯誤性質(zhì)并盡量校正,以便使編譯程序能繼續(xù)工作。錯誤處理的分類：錯誤恢復(fù)(Recovery):當發(fā)現(xiàn)錯誤時，跳過一段程序，從輸入流找到一個新起點錯誤修復(fù)(Repair):試圖把用戶的錯誤輸入修復(fù)為合法的。1遞歸下降法的錯誤恢復(fù)遞歸下降法對每個非終結(jié)符A設(shè)計相應(yīng)的分析子程序，該子程序匹配由A產(chǎn)生的終結(jié)符串為進行錯誤恢復(fù)，對每個子程序設(shè)置一個參數(shù)，它是終結(jié)符的集合，而這些符號是子程序返回時可被匹配的符號，稱為后繼同步符號，記為FollowSet例：S->id:=E1S->ifE2thenS1elseS2S->whileE3doS3S->repeatS4untilE4S->beginSLend設(shè)S的后繼同步符號集為FollowSetS，則FollowSetE1=FollowSetSFollowSetE2={then}FollowSetS1={else}FollowSetS2=FollowSetSFollowSetE3={do}FollowSetS3=FollowSetSFollowSetS4={until}FollowSetE4=FolowSetSFollowSetSL={end}涉及三種符號集：validSet：若當前子程序是A，則ValidSet包含F(xiàn)irst(A)，如果A是可空的，則ValidSet還包含F(xiàn)ollowSetHeaderSet：為引導(dǎo)符號集，它們是引導(dǎo)出重要部分的符號，如條件語句中的then和else，循環(huán)語句中的do。引進引導(dǎo)符號的目的是避免因為輸入符的錯誤而跳過大段程序。FollowSet：同前例：S->id:=E1S->ifE2thenS1elseS2S->whileE3doS3S->repeatS4untilE4S->beginSLendVallidSetS={id,if,while,repeat,begin}HeaderSetS={then,else,do,until,:=}錯誤恢復(fù)的主要思想：每個分析子程序的開頭，檢查當前輸入符是否屬于ValidSet如果不屬于，則尋找第一個屬于ValidSetHeaderSetFollowSet的符號，并從該符號開始繼續(xù)分析當子程序返回時保證輸入流的頭符為FollowSet中的符號

每個分析子程序用到ValidSet、HeadSet和FollowSet集合，其中前兩者對子程序來說時固定的，因此在調(diào)用時只需給出FollowSet從當前輸入流尋找第一個同步符號(Token)ProcedureCheckInput(ValidSet,HeaderSet,FollowSet:VtSet);begin ifSymb

V