《電子商務(wù)概論》多媒體電子教案

1、1,LR分析法,掌握：LR（0）分析，SLR（1）分析理解：活前綴，可歸前綴了解：LR(1)、LALR(1)分析思想,回顧：自底向上分析實(shí)現(xiàn)的基本思想——“移進(jìn)－歸約”方法(1) S→aAcBe (2)   A→b(3)   A→Ab (4) B→d 判斷輸入串 abbcde# 是否為該文法的句子,,3,LR分析法：根據(jù)當(dāng)前分析棧

2、中的符號(hào)串（通常以狀態(tài)表示）和向右順序查看輸入串的K個(gè)（K>=0）符號(hào)就可唯一地確定句柄。LR(K)的含義：L表示從左到右掃描輸入串R表示最左規(guī)約（即最右推導(dǎo)的逆過程）K表示向右查看輸入串符號(hào)的個(gè)數(shù)當(dāng)K=1時(shí)，能滿足當(dāng)前絕大多數(shù)高級(jí)語言編譯程序的需要，所以著重介紹LR(0),SLR(1),LR(1),LALR(1)方法,$1 LR分析概述,,4,,LR分析的特點(diǎn)：是規(guī)范歸約適用范圍廣，適用于大多數(shù)上下文無關(guān)文法描

3、述的語言分析速度快，能準(zhǔn)確定位錯(cuò)誤 缺點(diǎn)：LR分析器的構(gòu)造工作量大,5,LR分析器的組成總控程序：所有LR分析器總控程序相同。分析表：不同文法有不同的分析表同一文法采用的LR分析器不同，分析表也不同分析表分為ACTION表（動(dòng)作表）和GOTO表（狀態(tài)轉(zhuǎn)換表）。分析棧：包括狀態(tài)棧S和文法符號(hào)棧X。分析表是LR分析器的核心,LR分析表：行標(biāo)題為狀態(tài)，列標(biāo)題為文法符號(hào),GOTO表示當(dāng)前狀態(tài)面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)

4、狀態(tài)。ACTION表示當(dāng)前狀態(tài)面臨輸入符號(hào)時(shí)應(yīng)采取的動(dòng)作,為了節(jié)省空間，將ACTION和GOTO中關(guān)于終結(jié)符號(hào)的各列合并起來,,ACTION表中的動(dòng)作有4種：移進(jìn)(Sk)：把狀態(tài)k移入狀態(tài)棧，若當(dāng)前狀態(tài)是i，且k=GOTO[i,a]，把a(bǔ)移入符號(hào)棧歸約(rk)：用第k條產(chǎn)生式進(jìn)行歸約，此時(shí)棧頂形成了句柄β，文法中第k條產(chǎn)生式為A->β，且|β|=r，歸約時(shí)從狀態(tài)棧和符號(hào)棧中彈出r個(gè)符號(hào)，把A移入符號(hào)棧，j=GOTO[

5、i,A]移入狀態(tài)棧，其中狀態(tài)i為修改指針后的棧頂狀態(tài)接受(acc)：當(dāng)符號(hào)棧只剩文法開始符S，并且當(dāng)前輸入符為‘?！?，則分析成功報(bào)錯(cuò)：當(dāng)狀態(tài)棧頂?shù)臓顟B(tài)遇到了不應(yīng)該出現(xiàn)的文法符號(hào)，則報(bào)錯(cuò)，說明輸入串不是該文法的句子,,,LR分析器的工作過程示意圖,狀態(tài)棧,文法符號(hào)棧,棧指針,LR分析器：在分析的每一步，通用的總控程序按照狀態(tài)棧棧頂狀態(tài)Si和當(dāng)前輸入符號(hào)a查LR分析表，并執(zhí)行其中ACTION和GOTO規(guī)定的操作。,LR分析例（

6、LR(0)分析）,文法G[S]：(1)S->aAcBe (2)A->b (3)A->Ab (4)B->d,對(duì)輸入串a(chǎn)bbcde＃進(jìn)行LR分析,,LR(0)分析表為：,對(duì)輸入串a(chǎn)bbcde#的分析過程(1)S->aAcBe (2)A->b (3)A->Ab (4)B->d,GOTO,ACTION,輸入串,符號(hào)棧,狀態(tài)棧,步驟,,,,,,,,,,,,,,,,,,,,,,,A,

7、3,3,3,A,3,7,B,7,1,S,1,,12,$2 LR(0) 分析,使用LR(0)分析表的LR分析器稱為LR(0)分析器。LR(0)分析器在分析的過程中只根據(jù)符號(hào)棧的內(nèi)容就能確定句柄，不需要向右查看輸入符號(hào)對(duì)文法的限制較大，對(duì)絕大多數(shù)高級(jí)語言的語法分析器不適用構(gòu)造LR(0)分析表的思想和方法是構(gòu)造其他LR分析表的基礎(chǔ)。,13,2.1 規(guī)范句型的可歸約前綴和活前綴,什么是可歸前綴？什么是活前綴？可歸前綴和活前綴在LR

8、分析中起什么作用？,14,,前綴如果Z=xy是一符號(hào)串，則x是Z的前綴，其中x,y為任意符號(hào)串（包括空串ε ）例：abc的前綴有ε，a，ab，abc。可歸前綴規(guī)范句型中句柄之前包括句柄在內(nèi)的串稱為可歸前綴。,15,,活前綴定義：形成可歸前綴之前(包括可歸前綴在內(nèi))的所有規(guī)范句型的前綴稱為活前綴。即規(guī)范句型的不含句柄右邊符號(hào)的前綴稱為活前綴。 例：規(guī)范句型 aAbcde (下劃線為句柄)的可歸前綴為aAb

9、，活前綴為： ε，a，aA，aAb,16,,可歸前綴和活前綴在LR分析中的作用在LR分析過程中，實(shí)際上是把活前綴列出放在符號(hào)棧中，一旦在棧中出現(xiàn)可歸前綴，即句柄已經(jīng)形成，就用相應(yīng)的產(chǎn)生式進(jìn)行歸約，在分析的過程中，只要符號(hào)棧中的符號(hào)串是一個(gè)活前綴，就可保證已被分析過的部分是該文法規(guī)范句型的正確部分。,17,18,2.2 識(shí)別活前綴的有窮自動(dòng)機(jī),回顧：有窮自動(dòng)機(jī)——一種識(shí)別裝置分DFA和NFA,19,用有

10、窮自動(dòng)機(jī)來識(shí)別活前綴和可歸前綴有窮自動(dòng)機(jī)的輸入字符：終結(jié)符和非終結(jié)符狀態(tài)轉(zhuǎn)換：每把一個(gè)符號(hào)進(jìn)棧，就看成識(shí)別過了該符號(hào)，進(jìn)行狀態(tài)轉(zhuǎn)換。因?yàn)長R分析時(shí)棧中始終保持是活前綴，所以有窮自動(dòng)機(jī)識(shí)別過的符號(hào)串也是活前綴。終態(tài)：當(dāng)識(shí)別到可歸約前綴（表明在棧中形成句柄），認(rèn)為到達(dá)了識(shí)別句柄的終態(tài)，執(zhí)行歸約,20,例如：識(shí)別可歸前綴aAcBe的有窮自動(dòng)機(jī),1. LR(0)項(xiàng)目,文法的識(shí)別活前綴的有窮自動(dòng)機(jī)以“項(xiàng)目”作為它的狀態(tài)在文法G中每個(gè)產(chǎn)生

11、式的右部適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成項(xiàng)目例：產(chǎn)生式 U→XYZ 對(duì)應(yīng)有4個(gè)項(xiàng)目 [0] U→ ? XYZ[1] U→X ? YZ [2] U→XY ? Z[3] U→XYZ ? 產(chǎn)生式A→ε只有一個(gè)項(xiàng)目A→?,22,項(xiàng)目的含義：圓點(diǎn)在最左部（ U→ ? XYZ ）表示希望用產(chǎn)生式的右部歸約圓點(diǎn)的左部（ U→X ? YZ ）表示分析過程中已識(shí)別過的部分圓點(diǎn)的右部（ U→X

12、? YZ ）表示待識(shí)別部分圓點(diǎn)達(dá)到最右邊（ U→XYZ ? ）表示句柄已形成，可以進(jìn)行歸約。,LR(0)項(xiàng)目分類移進(jìn)項(xiàng)目：形如A→α?аβ的項(xiàng)目，其中а∈VT, α,β ∈V*。即圓點(diǎn)后面為終結(jié)符的項(xiàng)目。分析時(shí)把а移進(jìn)符號(hào)棧。待約項(xiàng)目：形如A→α?Bβ的項(xiàng)目，其中B∈VN, α,β ∈V* 。即圓點(diǎn)后面為非終結(jié)符的項(xiàng)目。表明用產(chǎn)生式A的右部歸約時(shí)，首先要將B的產(chǎn)生式右部歸約為B，對(duì)A的右部才能繼續(xù)進(jìn)行分析。也就是期待著

13、繼續(xù)分析過程中首先能歸約得到B,歸約項(xiàng)目：形如A→α?的項(xiàng)目，α∈V*,α= ε對(duì)應(yīng)的項(xiàng)目為A-> ?即圓點(diǎn)在最右端的項(xiàng)目。表明該產(chǎn)生式的右部已分析完，句柄已形成，可以把α歸約為A。接受項(xiàng)目：當(dāng)歸約項(xiàng)目為S’→S?，其中S'是文法開始符即對(duì)文法開始符的歸約項(xiàng)目。表明輸入串可歸約為文法開始符，分析結(jié)束。開始項(xiàng)目：形如S’→?S的項(xiàng)目，其中S'是文法開始符。即括廣文法開始符的產(chǎn)生式圓點(diǎn)在最左邊的項(xiàng)目

14、。,25,2. 構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī),構(gòu)造識(shí)別活前綴的NFA拓廣文法G[S]為G’[S’]，即加入產(chǎn)生式S’→S以G’[S’]的每個(gè)項(xiàng)目為NFA的一個(gè)狀態(tài)，S’→?S為初態(tài)，其余每個(gè)狀態(tài)都為活前綴的識(shí)別態(tài)，所有歸約項(xiàng)目為終態(tài)(句柄識(shí)別態(tài))，S’→S?為接受態(tài)確定狀態(tài)轉(zhuǎn)換關(guān)系：若有項(xiàng)目i：A→α?Xβ，項(xiàng)目j：A→αX?β，則從狀態(tài)i到狀態(tài)j連一條標(biāo)記為X的箭弧。若X∈VN，對(duì)于X的所有產(chǎn)生式圓點(diǎn)在最左邊的狀態(tài)k:X→?

15、r，都從狀態(tài)i到狀態(tài)k連一條標(biāo)記為ε的箭弧。用子集法把NFA確定化為DFA,例 文法G：E→aA | bB A→cA | d B→cB | d,拓廣文法G’：S’→E E→aA | bB A→cA|d B→cB | d,G’的所有LR(0)項(xiàng)目為：1．S’→?E2．S’→E? 3．E→?aA4．E→a?A 5．E→aA

16、?6．A→?cA7．A→c?A8．A→cA?9．A→?d10. A→d?11. E→?bB12. E→b?B 13. E→bB?14. B→?cB15. B→c?B16. B→cB?17. B→?d18. B→d?,識(shí)別G’活前綴的NFA,G’的所有LR(0)項(xiàng)目為：1．S’→?E2．S’→E? 3．E→?aA4．E→a?A 5．E→aA?6．A→?cA7．A→

17、c?A8．A→cA?9．A→?d10. A→d?11. E→?bB12. E→b?B E→bB?14. B→?cB15. B→c?BB→cB?B→?dB→d?,識(shí)別G’活前綴的DFA,,29,,通過列出拓廣文法的所有項(xiàng)目，進(jìn)而構(gòu)造識(shí)別活前綴的NFA，再確定化為DFA的方法，工作量較大，不實(shí)用實(shí)用的方法是直接構(gòu)造以項(xiàng)目集為狀態(tài)的識(shí)別活前綴的DFA,30,2.3 構(gòu)造以LR(0)項(xiàng)目集為狀

18、態(tài)的識(shí)別活前綴的DFA,LR(0)項(xiàng)目集規(guī)范族識(shí)別一個(gè)文法活前綴的DFA的每個(gè)狀態(tài)都是一個(gè)項(xiàng)目集，項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。識(shí)別活前綴的DFA的構(gòu)造如何構(gòu)造DFA的一個(gè)狀態(tài)（項(xiàng)目集）如何由DFA的一個(gè)狀態(tài)求其他狀態(tài),,1 項(xiàng)目集I的閉包CLOSURE(I)如果I是文法G的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：I的項(xiàng)目均在CLOSURE(I)中；若A→α?Bβ屬于CLOS

19、URE(I)，B ∈VN，則每一形如B→?r的項(xiàng)目也屬于CLOSURE(I)重復(fù)b）直到CLOSURE(I)不再擴(kuò)大為止。說明：圓點(diǎn)后為終結(jié)符或在一個(gè)產(chǎn)生式的最后，求閉包時(shí)不會(huì)增加新的項(xiàng)目例 S’→E E→aA | bB A→cA|dB→cB | d I={ S’→?E }則CLOSURE(I)={ S’→?E，E→?aA，E→?bB }CLOSURE(I)作為DAF的一個(gè)狀態(tài),2. 狀態(tài)轉(zhuǎn)換函數(shù)

20、GO(I, X)由DFA的一個(gè)狀態(tài)求其他狀態(tài)通過狀態(tài)轉(zhuǎn)換函數(shù)設(shè)I為文法G的某一項(xiàng)目集(狀態(tài))，X∈VN∪VT ,則GO(I, X) = CLOSURE(J)其中J = {任何形如A→αX?β的項(xiàng)目│A→α? Xβ∈I }稱J為“核”例 S’→E E→aA | bB A→cA|dB→cB | d I = { S’→?E，E→?aA，E→?bB }，則GO(I, E)=CLOSURE({ S’→E?

21、})={ 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)項(xiàng)目集為狀態(tài)的DFA構(gòu)造初始狀態(tài)IS0=CLOSURE({S’→?S})，并且它是未被標(biāo)記的。從已經(jīng)構(gòu)造的DFA部分圖中選擇一個(gè)未被標(biāo)記的狀態(tài)ISi，標(biāo)記ISi，若項(xiàng)目集ISi中含有項(xiàng)目U-&g

22、t;x?Ry(R∈V,x,y為任一符號(hào)串)，且GO(ISi,R)=ISj，若ISj不在DFA中，則將ISj作為未被標(biāo)記的加入DFA中，且從ISi出發(fā)引一條標(biāo)記為R的弧到ISj，重復(fù)b)直到?jīng)]有未被標(biāo)記的狀態(tài)為止。,例 拓廣文法G’：S’→EE→aA | bBA→cA|dB→cB | d 構(gòu)造以LR(0)項(xiàng)目集為狀態(tài)的DFA,S’→?E,S’→E?,E→a?A,E→b?B,E→aA?,A→c?A,A→d?,E→bB?,B→c?B

23、,B→d?,A→cA?,B→cB?,E→?aAE→?bB,I0,I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,A→?cAA→?d,B→?cBB→?d,A→?cAA→?d,B→?cBB→?d,35,2.4 LR(0)分析表的構(gòu)造,分析表的組成：動(dòng)作表(ACTION) ：表示當(dāng)前狀態(tài)下面臨輸入符應(yīng)做的動(dòng)作是移進(jìn)、歸約、接受或出錯(cuò)，面臨的輸入符只包含終結(jié)符和‘?！D(zhuǎn)換表(GOTO)：表示在當(dāng)前狀態(tài)下面臨

24、文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)為了節(jié)省存儲(chǔ)空間，把關(guān)于終結(jié)符部分的GOTO表和ACTION表重疊，也就是把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)做的移進(jìn)－歸約動(dòng)作和轉(zhuǎn)向動(dòng)作表示在一起,LR(0)分析表的構(gòu)造算法設(shè)已構(gòu)造出LR(0)項(xiàng)目集規(guī)范族為C={ I0，I1，…，In }，令項(xiàng)目集Ik對(duì)應(yīng)的狀態(tài)為k，含S’→?S項(xiàng)目的項(xiàng)目集對(duì)應(yīng)的狀態(tài)為初始狀態(tài)分析表的ACTION表和GOTO表構(gòu)造步驟為：若項(xiàng)目A→α?aβ∈Ik，a∈VT，且GO(Ik

25、,a)=Ij，則置ACTION[k,a]=‘Sj’若項(xiàng)目A→α?Bβ∈Ik，B∈VN，且GO(Ik,B)=Ij，則置GOTO[k,B]=‘j’若項(xiàng)目A→α?∈Ik，且產(chǎn)生式A→α的編號(hào)為j，則對(duì)任何a（終結(jié)符和‘#’），置ACTION[k,a]=‘rj’若項(xiàng)目S’→S?∈Ik，則置ACTION[k,#]=‘a(chǎn)cc’不能用上述方法填入的分析表的元素均應(yīng)填上“報(bào)錯(cuò)標(biāo)志”。,拓廣文法G’：(0) S’→E(1) E→aА(2

26、) E→bB(3) A→cА(4) A→d(5) B→cB(6) B→d,識(shí)別活前綴的DFA：,,,,,,,,,,10,,,,,,,,,,,,a,ACTION,,,,,,,,,,,,b,,,,,,,,,,,,c,,,,,,,,,,,,d,,,,,,,,,,,,#,,,,,,,,,,,,E,GOTO,,,,,,,,,,,,A,狀態(tài),,11,,9,,8,,7,,6,,5,,4,,3,,2,,1,,0,B,,,,,,,,,,

27、,,,,,,,,,,,,,,,,LR(0)分析表,,1,S2,S3,acc,4,S5,S6,7,S8,S9,r1 r1 r1 r1 r1,10,S5,S6,r4 r4 r4 r4 r4,r2 r2 r2 r2

28、 r2,11,S9,S8,r6 r6 r6 r6 r6,r3 r3 r3 r3 r3,r5 r5 r5 r5 r5,,39,2.5 LR(0)分析器的工作過程,工作過程：根據(jù)分析棧的

29、棧頂狀態(tài)和輸入串的當(dāng)前符號(hào)查分析表確定應(yīng)采取的動(dòng)作（移進(jìn)、歸約、接受或報(bào)錯(cuò)），對(duì)狀態(tài)棧和符號(hào)棧進(jìn)行相應(yīng)的操作。具體說明如下：,若ACTION[S,a]=Sj，a為終結(jié)符，則把a(bǔ)移入符號(hào)棧，j移入狀態(tài)棧；若ACTION[S,a]=rj，a為終結(jié)符或＃，則用第j個(gè)產(chǎn)生式（ A->β ）歸約，將兩個(gè)棧彈出k個(gè)元素，其中k為第j個(gè)產(chǎn)生式右部符號(hào)串長度，這時(shí)當(dāng)前面臨符號(hào)為第j個(gè)產(chǎn)生式左部的非終結(jié)符（A）；若狀態(tài)棧當(dāng)前的棧頂狀態(tài)

30、為Sk，且GOTO[Sk,A]=j，則非終結(jié)符A移入符號(hào)棧，j移入狀態(tài)棧；若ACTION[S,a]=acc,a為＃，則為接受，表明分析成功；若ACTION[S,a]=空白，則轉(zhuǎn)向出錯(cuò)處理。,(0) S’→E(1) E→aА(2) E→bB(3) A→cА(4) A→d(5) B→cB(6) B→d 輸入串bccd＃的分析過程,,,0,#,bccd#,S3,03,#b,ccd#,S8,038,#bc,c

31、d#,S8,0388,#bcc,d#,S9,03889,#bccd,#,#,#,#,#,r6,11,0388,#bcc,r5,11,038,#bc,r5,7,03,#b,r2,1,0,#,acc,B,(11),B,(11),B,7,E,1,42,$3 SLR(1)分析,項(xiàng)目集中的沖突一個(gè)項(xiàng)目集中存在下列情況稱為項(xiàng)目沖突：移進(jìn)—?dú)w約沖突移進(jìn)項(xiàng)目A→α?aβ和歸約項(xiàng)目B→r?同在一個(gè)項(xiàng)目集中，當(dāng)面臨輸入符a時(shí)，不能確定移進(jìn)a還是

32、把r歸約為B；歸約—?dú)w約沖突歸約項(xiàng)目A→β?和歸約項(xiàng)目B→r?同在一個(gè)項(xiàng)目集中，不管面臨什么輸入符都不能確定把β歸約為A還是把r歸約為B。一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族中的項(xiàng)目集不存在移進(jìn)—?dú)w約沖突，也不存在歸約—?dú)w約沖突時(shí)，稱該文法為LR(0)文法。,例：文法G’(0) S’→S(1) S→rD(2) D→D,i(3) D→i,識(shí)別文法活前綴的DFA：,在項(xiàng)目集I3中S→rD?為歸約項(xiàng)目，D→D?,i為移

33、進(jìn)項(xiàng)目，存在移進(jìn)－歸約沖突，該文法不是LR(0)文法,44,,2. 解決沖突的SLR(1)方法基本思想：對(duì)于LR(0)有沖突的項(xiàng)目集用向前查看輸入符號(hào)串的一個(gè)符號(hào)的辦法加以解決解決方法：對(duì)歸約項(xiàng)目A→r?, 只有當(dāng)輸入符號(hào)a∈FOLLOW(A)才進(jìn)行歸約，縮小歸約范圍，有可能解決沖突。,例：文法G’(0) S’→S(1) S→rD(2) D→D,i(3) D→i,識(shí)別文法活前綴的DFA：,對(duì)項(xiàng)目集I3，若

34、當(dāng)前輸入符為‘#’時(shí)，進(jìn)行歸約，若當(dāng)前輸入符為‘,’，進(jìn)行移進(jìn)操作，沖突得以解決,46,SLR(1)的處理方法：例：一個(gè)LR(0)規(guī)范族中項(xiàng)目集I含有沖突項(xiàng)目I={X→α?bβ?Α→r??Β→δ?}, 其中b∈VT，如果FOLLOW(A)和FOLLOW(B)互不相交，且不含b，則當(dāng)狀態(tài)I面臨某輸入符a時(shí)，可采用下列動(dòng)作：若a=b，則移進(jìn)；若a∈FOLLOW(A)，則用產(chǎn)生式A→r歸約；若a∈FOLLOW(B)，則用產(chǎn)

35、生式B→δ歸約；此外，報(bào)錯(cuò)。,一般地，一個(gè)LR(0)規(guī)范族中的項(xiàng)目集I有m個(gè)移進(jìn)項(xiàng)目：A1→α1?a1β1 ，A2→α2?a2β2 ，… ，Am→αm?amβm n個(gè)歸約項(xiàng)目：B1→r1? ，B2→r2? ，… ，Bn→rn? ，若移進(jìn)符號(hào)集{a1，a2，…，am}和FOLLOW(B1)，F(xiàn)OLLOW(B2)，…，F(xiàn)OLLOW(Bn)兩兩交集為空，則當(dāng)狀態(tài)I面臨某輸入符a時(shí)，可采用以下動(dòng)作：若a∈{a1，a2，…

36、，am}，則移進(jìn)；若a∈FOLLOW(Bi)，i=1,2,…,n，則用Bi→ri歸約；此外，報(bào)錯(cuò)。,48,上述解決項(xiàng)目集(狀態(tài))中沖突的方法稱為SLR(1)方法（Simple因?yàn)橹粚?duì)有沖突的狀態(tài)才向前查看一個(gè)符號(hào)，以確定動(dòng)作）如果一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族中某些項(xiàng)目集所含有的動(dòng)作沖突都能用SLR(1)方法解決，則稱這個(gè)文法為SLR(1)文法,49,SLR(1)分析表的構(gòu)造算法與LR(0)分析表的構(gòu)造類似，僅在含有沖突的

37、項(xiàng)目集中分別進(jìn)行處理。改進(jìn)的SLR(1)方法：對(duì)所有的歸約項(xiàng)目僅對(duì)當(dāng)前輸入符號(hào)包含在該歸約項(xiàng)目左部非終結(jié)符的FOLLOW集中，才采取歸約動(dòng)作。,改進(jìn)的SLR(1)分析表的構(gòu)造方法：設(shè)已構(gòu)造出LR(0)項(xiàng)目集規(guī)范族為C={ I0，I1，…，In }，令項(xiàng)目集Ik對(duì)應(yīng)的狀態(tài)為k，含S’→?S項(xiàng)目的項(xiàng)目集為初態(tài)，分析表的ACTION表和GOTO表構(gòu)造步驟為：若項(xiàng)目A→α?aβ∈Ik， a∈VT，且GO(Ik,a)=Ij，則置

38、ACTION[k,a]=‘Sj’；若項(xiàng)目A→α?Bβ∈Ik， B∈VN，且GO(Ik,B)=Ij，則置GOTO[k,B]=‘j’；若項(xiàng)目A→α?∈Ik，且產(chǎn)生式A→α的編號(hào)為j， 則對(duì)任何a(終結(jié)符和‘#’)，且a∈FOLLOW(A)，置ACTION[k,a]=‘rj’；若項(xiàng)目S’→S?∈Ik，則置ACTION[k,#]=‘a(chǎn)cc’；不能用上述方法填入的分析表元素均應(yīng)填上“報(bào)錯(cuò)標(biāo)志”。,例 文法G’：(0)

39、S’→S(1) S→rD (2) D→D, i (3) D→i,FOLLOW(S’)={#}FOLLOW(S)={#}FOLLOW(D)={# ，},,52,$4 LR(1)、LALR(1)分析思想,仍有許多文法構(gòu)造的LR(0)項(xiàng)目集規(guī)范族存在的動(dòng)作沖突不能用SLR(1)方法解決,例如：文法G:(0) S' →S (1) S → L=R (2) S →R (3) L →*R (4) L →i (5) R

40、→L,識(shí)別文法活前綴的DFA,I6: S →L= ? R R →L ? R → ? L L → ? i L → ? *R,Follow(R)={#,=}與移進(jìn)符號(hào)集{ *, i}交集為空，可用SLR(1)方法解決沖突,I2: S-> L ? =R R-> L ?,Follow(R)={#,=}與移進(jìn)符號(hào)集{=}交集不為空，SLR(1)方法不能解決沖突，該文法不是

41、SLR(1)文法。,S' →SS →L=R |R L →*R | i R →L,55,SLR(1)用FOLLOW信息作為展望信息（只對(duì)屬于FOLLOW集的輸入符號(hào)歸約），縮小了歸約范圍，消除了一些無效歸約，解決了項(xiàng)目集中的一些簡單的沖突。盡管FOLLOW(A)中包含了所有含A的句型中A后的可能終結(jié)符，但并不是每個(gè)含有A的句型中，A的后面都可以出現(xiàn)Follow(A)中的每一個(gè)符號(hào)，所以SLR(1)未能從根本上消除所有無效歸

42、約。,S' →SS →L=R |R L →*R | i R →L,LR(1)方法正是要解決SLR(1)方法在某些情況下存在的無效歸約問題。,57,4.1 LR(1) 分析思想,LR(1)分析的基本思想LR(1)方法按每個(gè)具體的句型設(shè)置展望信息。例：如果存在如下的一些句型…αAa…，…βAb…，…γAc…，則FOLLOW(A)={a,b,c}處理到句型…αA，只當(dāng)輸入符號(hào)為a時(shí)歸約；處理到句型…βA，只

43、當(dāng)輸入符號(hào)為b時(shí)歸約；處理到句型…γA，只當(dāng)輸入符號(hào)為c時(shí)歸約；,58,LR(1)分析若[A→??B?]屬于項(xiàng)目集I時(shí)，則[B→??]也屬于I，把FIRST(?)作為用產(chǎn)生式B→?歸約的搜索符（用以代替SLR(1)分析中的FOLLOW(B)），并把此搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面，這種處理方法即為LR(1)方法closure(I)按如下方式構(gòu)造(1) I的任何項(xiàng)目屬closure(I)；(2)若[A→β1．Bβ2，a

44、]∈closure(I)，B→δ是一產(chǎn)生式，那么對(duì)于FIRST(β2a)中的每個(gè)終結(jié)符b，如果[B→．δ,b]不在closure(I)中，則把它加進(jìn)去；(3)重復(fù)（1）（2），直至closure(I)不再增大。,59,GO函數(shù),若I是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào)GO(I, X)= closure(J) 其中 J={ 任何形如[A→αX．β,a]的項(xiàng)目∣[A→α.Xβ,a]∈I}LR(I)項(xiàng)目規(guī)范族C的構(gòu)造算法類同LR(0)的

45、，只是初始時(shí)：C={ closure({[S’→．S,#]})};,文法G‘：(0)S’ ? S (1)B ? aB (2)S ? BB (3)B ? bLR(1)項(xiàng)目集和轉(zhuǎn)換函數(shù),,61,,LR(1)的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：LR(1)分析對(duì)搜索符的計(jì)算方法比較確切，沒有無效歸約，適應(yīng)的文法更廣缺點(diǎn)：LR(1)分析表的狀態(tài)數(shù)目龐大。,,62,4.2 LALR(1)分析思想,LALR(1)方法是介于SLR(1)和LR(

46、1)之間的一種方法，即其功能比SLR(1)強(qiáng)，比LR(1)弱。它具有SLR(1)的狀態(tài)數(shù)少的優(yōu)點(diǎn)和LR(1)的適用范圍廣的優(yōu)點(diǎn)。LALR(1)分析對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集，若合并同心集后不產(chǎn)生新的沖突，則為LALR(1)項(xiàng)目集LALR(1)分析大大減少項(xiàng)目集（狀態(tài)）的數(shù)目。,分析可發(fā)現(xiàn)I3和I6 ， I4和I7 ， I8和I9分別為同心集,同心集合并后不包含沖突，是LALR(1)項(xiàng)目集,本章小結(jié)LR(0)、SLR

47、(1)、LR(1)、LALR(1)方法比較實(shí)際上不同LR方法之間的主要區(qū)別就在于歸約的判定方法上：LR(0)是不看展望符判定歸約；SLR(1)是看展望符，但把所有B→? ? 的展望符集均定義為Follow(B)。即把符號(hào)棧頂上的句柄?歸約為B的條件是：展望符為Follow(B)中的元素。換句話說，歸約任何位置上的B，都用統(tǒng)一的展望符集；LR(1)也是看展望符，但歸約不同位置上的B時(shí)，采用不同的展望符集。每個(gè)項(xiàng)由心與向前搜索符組成

48、，搜索符長度為1。由于LR(1)方法對(duì)于歸約條件的判定比SLR(1)更精確，可大大減少移入/歸約沖突；LALR(1): 對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集,65,LR(0)、SLR(1)、LR(1)、LALR(1)分析表比較LR(0)分析表局限性大，但其構(gòu)造方法是其他構(gòu)造方法的基礎(chǔ)；SLR分析表雖然不是對(duì)所有文法都存在，但這種分析表較易實(shí)現(xiàn)又極有使用價(jià)值；LR分析表的分析能力最強(qiáng)，能適用于一大類文法，但是，實(shí)現(xiàn)代價(jià)過高（表過大）