1、2022-4-13編譯原理與技術(shù)講義1編譯原理與技術(shù)自底向上分析2022-4-13編譯原理與技術(shù)講義2自底向上分析移進(jìn)歸約分析分析樹的構(gòu)建 從葉子結(jié)點(diǎn)開始，逐步構(gòu)造各內(nèi)部結(jié)點(diǎn)直至根結(jié)點(diǎn)出現(xiàn)。 分析技術(shù)的關(guān)鍵句柄的識(shí)別句柄（handle）是什么？ 簡(jiǎn)單講，句柄是一個(gè)產(chǎn)生式的右部；自底向上分析（移進(jìn)歸約分析）過程，其實(shí)就是發(fā)現(xiàn)句柄并將句柄（產(chǎn)生式右部）替換成相應(yīng)左部非終結(jié)符的過程。該替換稱為最左歸約，它對(duì)應(yīng)著某最右推導(dǎo)逆過程的一步。2022-4-13編譯原理與技術(shù)講義3自底向上分析分析技術(shù)的關(guān)鍵句柄的識(shí)別句柄（handle）是什么？ 一般地，如果有以下最右推導(dǎo)序列， 則產(chǎn)生式A及其在右句型中的位置

2、稱為右句型的句柄。,APA*Srmrm 2022-4-13編譯原理與技術(shù)講義4自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的分析過程。輸入串 a b b c d e $ a A b c d e $ a A d e $ a A B e $ S $最左歸約最右推導(dǎo)2022-4-13編譯原理與技術(shù)講義5自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ 2022-4-13編譯原理與技術(shù)講義6自底向上分析e.g.17 文法G6 1）Sa

3、ABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ 2022-4-13編譯原理與技術(shù)講義7自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ A2022-4-13編譯原理與技術(shù)講義8自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ A2022-4-13編譯原理與技術(shù)講義9自底向上分析e.g.17 文法G6 1）

4、SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ AA2022-4-13編譯原理與技術(shù)講義10自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ AAB2022-4-13編譯原理與技術(shù)講義11自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串a(chǎn)bbcde$的對(duì)應(yīng)分析樹的建立過程。輸入串 a b b c d e $ AABS2022-4-13編譯原理與技術(shù)講義12移進(jìn)歸約分析e.

5、g.17 用棧來實(shí)現(xiàn)用棧來實(shí)現(xiàn)串a(chǎn)bbcde$的分析（1）分析棧輸入串動(dòng)作$ a b b c d e $ ab b c d e $移進(jìn)a$ a bb c d e $移進(jìn)b$ a Ab c d e $歸約：Ab$ a A bc d e $移進(jìn)b$ a A b cd e $移進(jìn)c2022-4-13編譯原理與技術(shù)講義13移進(jìn)歸約分析e.g.17 用棧來實(shí)現(xiàn)用棧來實(shí)現(xiàn)串a(chǎn)bbcde$的分析（2）分析棧輸入串動(dòng)作$ a A b cd e $移進(jìn)c$ a Ad e $歸約: AAbc$ a A de $移進(jìn)d$ a A Be $歸約：Bd$ a A B e$移進(jìn)e$ S$r: SaABe分析成功！2022

6、-4-13編譯原理與技術(shù)講義14移進(jìn)歸約分析四種分析動(dòng)作（action） 移進(jìn)（shift）將當(dāng)前輸入符號(hào)移入棧頂top（why？） 歸約（reduce）當(dāng)“句柄”出現(xiàn)在棧頂（從棧中某處到棧頂top），則將“句柄”從棧頂彈彈出，并將相應(yīng)產(chǎn)生式左部非終結(jié)符置入棧頂top。（when？） 接受（accept）分析成功！ 報(bào)錯(cuò)（error）出現(xiàn)語法錯(cuò)誤，調(diào)錯(cuò)誤恢復(fù)例程2022-4-13編譯原理與技術(shù)講義15移進(jìn)歸約分析分析動(dòng)作沖突 移進(jìn)-歸約沖突（shift-reduce conflict）當(dāng)“句柄”處于棧頂時(shí)，分析動(dòng)作指示既可以將下一輸入符號(hào)移入棧頂top，又可以實(shí)施歸約操作。如何動(dòng)作呢？ 歸約-

7、歸約沖突（reduce-reduce conflict） 位于棧頂?shù)摹熬浔?，同時(shí)匹配兩個(gè)（以上）產(chǎn)生式的右部。選誰呢？怎么可能呢？2022-4-13編譯原理與技術(shù)講義16移進(jìn)歸約分析沖突二義文法G不適合移進(jìn)歸約分析 e.g. 18 移進(jìn)-歸約沖突文法G7： S if E then S | if E then S else S S a$. if E then S“句柄”？else. 分析棧輸入串：當(dāng)前輸入符號(hào)2022-4-13編譯原理與技術(shù)講義17$. if E then S else棧頂. 分析棧輸入串：$ Selse . 分析棧輸入串：歸約動(dòng)作移進(jìn)動(dòng)作文法G7: S if E then S

8、 | if E then S else S | a期待新的期待新的“長(zhǎng)長(zhǎng)句柄句柄”2022-4-13編譯原理與技術(shù)講義18e.g.19 二義性文法G8如下：EE+E | E * E | (E) | id 輸入串id+id+id$的最右推導(dǎo)：1）EE+EE+idE+E+idE+id+idid+id+id2）EE+EE+E+EE+E+idE+id+idid+id+id帶下劃線的符號(hào)串是相應(yīng)句型的句柄。移進(jìn)歸約分析沖突2022-4-13編譯原理與技術(shù)講義19e.g.19輸入串id+id+id$的棧分析過程分析1）輸入串分析2）$ id+id+id$ $id +id+id$ $id$E +id+id$

9、 $E $E+ id+id$ $E+$E+id +id$ $E+id$E+E +id$ $E+E$E +id$ id$ $E+E+歸約移進(jìn)2022-4-13編譯原理與技術(shù)講義20e.g.19輸入串id+id+id$的棧分析過程分析1） 輸入串分析2）$E+E +id$ +id$ $E+E$E +id$ id$ $E+E+$E+ id$ $ $E+E+id$E+id $ $ $E+E+E$E+E $ $ $E+E $E $ $ $E2022-4-13編譯原理與技術(shù)講義21移進(jìn)歸約分析沖突歸約-歸約沖突e.g.20 文法G91）Statid ( para_list ) | expr := expr

10、2）para_listpara_list , para | para3）paraid4）exprid ( expr_list ) 5）exprid6）expr_listexpr_list , expr | expr2022-4-13編譯原理與技術(shù)講義22e.g.20分析輸入串id(id,id)$分析棧輸入串 $ id ( id , id ) $1) $ id ( expr , id ) $2) $ id ( para , id ) $paraid，目標(biāo)：過程調(diào)用語句exprid 目標(biāo)：數(shù)組引用2022-4-13編譯原理與技術(shù)講義23LR分析器高效易實(shí)現(xiàn)的自底向上的分析方法文法限制少，適用于大多

11、數(shù)CFG（包括含左遞歸、左因子的文法）LR（k）分析器L 從左自右讀（read from Left to right）R 構(gòu)造最右推導(dǎo)的逆（for constructing a Rightmost derivation in reverse） k 向前看符號(hào)的個(gè)數(shù)（the number of input symbols of lookhead）2022-4-13編譯原理與技術(shù)講義24LR分析器輸入串LR控制程序LR分析表SmXm.S0a1.ai.$狀態(tài) 符號(hào) 棧輸出TopBottom動(dòng)作表Action轉(zhuǎn)移表GOTO2022-4-13編譯原理與技術(shù)講義25格局： 狀態(tài)符號(hào)棧 輸入串 分析表 動(dòng)作

12、表（Action）：S （$） shift , reduce, accept, error 轉(zhuǎn)移表（GOTO）：S VN SLR分析器2022-4-13編譯原理與技術(shù)講義26分析算法初始，狀態(tài)S0位于棧底（棧頂）；根據(jù)當(dāng)前棧頂狀態(tài)S和當(dāng)前輸入符號(hào)a，查action表，由actionS,a決定分析動(dòng)作： si輸入符a移入棧頂top（push a ）；狀態(tài)i移入棧頂top（push i）。 rj 按第j個(gè)產(chǎn)生式（A）進(jìn)行歸約，首先將從棧頂top往棧中的|個(gè)狀態(tài)和|個(gè)符號(hào)（計(jì)2|個(gè)）彈出分析棧；設(shè)此時(shí)棧頂狀態(tài)為T，再將符號(hào)A和狀態(tài)S=GOTOT,A 依次移入分析棧（S在棧頂top） acc 輸入串被

13、接受，分析成功！ error 輸入串有錯(cuò)，調(diào)錯(cuò)誤恢復(fù)程序2022-4-13編譯原理與技術(shù)講義27e.g.21 表達(dá)式文法G2的LR分析表文法G2：（1）EE + T（2）ET（3）TT * F（4）TF（5）F（ E ）（6）F id 2022-4-13編譯原理與技術(shù)講義28e.g.21 表達(dá)式文法G2的LR分析表狀態(tài)actiongotoid+*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4932022-4-13編譯原理與技術(shù)講義29e.g.21 表達(dá)式文法G2的LR分析表（續(xù)）狀態(tài)actiongotoid+*()$ET

14、F7s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r52022-4-13編譯原理與技術(shù)講義30e.g.21 id*(id+id)$的移進(jìn)-歸約分析過程分析棧輸入串輸出0id*(id+id)$0id5*(id+id)$s5:移進(jìn)id0F3*(id+id)$r6:Fid0T2*(id+id)$r4:TF0T2*7(id+id)$s7:移進(jìn)*0T2*7(4id+id)$s4:移進(jìn)(0T2*7(4id5+id)$s5:移進(jìn)id2022-4-13編譯原理與技術(shù)講義31e.g.21 id*(id+id)$的移進(jìn)-歸約分析過程輸入串輸出分析棧+id)$s5:移進(jìn)id0T2*7

15、(4id5+id)$r6:Fid0T2*7(4F3+id)$r4:TF0T2*7(4T2+id)$r2:ET0T2*7(4E8id)$s6:移進(jìn)+0T2*7(4E8+60T2*7(4E8+6id5)$s5:移進(jìn)id0T2*7(4E8+6F3)$r6:Fid2022-4-13編譯原理與技術(shù)講義32e.g.21 id*(id+id)$的移進(jìn)-歸約分析過程輸入串輸出分析棧0T2*7(4E8+6F3)$r6:Fid0T2*7(4E8+6T9)$r4:TF0T2*7(4E8)$r1:EE+T0T2*7(4E8)11$s11:移進(jìn))0T2*7F10$r5:F(E)0T2$r3:TT*F0E1$r2:ET0

16、E1$acc2022-4-13編譯原理與技術(shù)講義33活前綴（viable prefix）是規(guī)范（右）句型的前綴，它不包含句柄后的任何符號(hào)（即活前綴的長(zhǎng)度不會(huì)超過句柄的最右端）。若AP，有如下規(guī)范推導(dǎo)， 則，的前綴為右句型的活前綴。識(shí)別活前綴的DFA*RRSA2022-4-13編譯原理與技術(shù)講義34活前綴與句柄移進(jìn)移進(jìn)-歸約分析過程中，分析棧內(nèi)的符號(hào)串構(gòu)成活歸約分析過程中，分析棧內(nèi)的符號(hào)串構(gòu)成活前綴（這表明已掃描過的輸入串沒有語法錯(cuò)誤；前綴（這表明已掃描過的輸入串沒有語法錯(cuò)誤；事實(shí)上，也只有形成活前綴的符號(hào)才會(huì)被移入分事實(shí)上，也只有形成活前綴的符號(hào)才會(huì)被移入分析棧；析棧；分析的實(shí)質(zhì)就是判斷剩余輸

17、入串能否繼續(xù)分析的實(shí)質(zhì)就是判斷剩余輸入串能否繼續(xù)形成活前綴）形成活前綴） 活前綴不包含或部分包含句柄 此時(shí)期待著“匹配”句柄的輸入串并將之移入棧頂； $bottom2022-4-13編譯原理與技術(shù)講義35活前綴與句柄 活前綴已完全包含句柄 此時(shí)句柄位于棧頂，需要進(jìn)行歸約。 $bottom句柄A $bottom2022-4-13編譯原理與技術(shù)講義36識(shí)別活前綴的DFALR（0）項(xiàng)目產(chǎn)生式右部加 “” ； “”的左部表示已“看見”（分析識(shí)別過）的部分；而右部則是期望“看到”的部分。如：產(chǎn)生式AP，其LR（0）項(xiàng)目有：A 期望看到產(chǎn)生的串（移進(jìn)項(xiàng)目移進(jìn)項(xiàng)目） A 已分析期望看到產(chǎn)生的串（移進(jìn)項(xiàng)目）

18、A 、都分析完了 （ 歸約項(xiàng)目歸約項(xiàng)目）特別的，空產(chǎn)生式A 的LR（0）項(xiàng)目只有一個(gè)只有一個(gè)： A （ 歸約項(xiàng)目歸約項(xiàng)目）2022-4-13編譯原理與技術(shù)講義37識(shí)別活前綴的NFA拓展文法引入新產(chǎn)生式SS ， S為新的開始符號(hào)NFA的狀態(tài)：各個(gè)產(chǎn)生式的各個(gè)產(chǎn)生式的LR（0）項(xiàng)目；）項(xiàng)目；初態(tài)：初態(tài)：S S 終態(tài)終態(tài)（唯一） ： SS NFA的狀態(tài)轉(zhuǎn)換i: AXj: AXXh: ABk: B XVTVNBVN2022-4-13編譯原理與技術(shù)講義38采用子集構(gòu)造法轉(zhuǎn)換上述的NFA到DFA閉包 closure（I） / I：NFA的狀態(tài)子集即LR(0)項(xiàng)目集合1）I closure（I）2）若項(xiàng)目A

19、BI，BP，則項(xiàng)目 B closure（I）3）重復(fù)2）直至closure（I）不再增大 轉(zhuǎn)移 goto（I，X） / XVTVNJ=goto（I，X）=closure（AX| AX I）2022-4-13編譯原理與技術(shù)講義39DFA識(shí)別的活前綴從DFA初態(tài)I0到任一狀態(tài)Ij的路徑上所“讀過”的符號(hào)串。狀態(tài)Ij可以指示下一步的“動(dòng)作”。該DFA識(shí)別所有的活前綴；且只能識(shí)別活前綴。LR(0)項(xiàng)目規(guī)范族C=DFA的狀態(tài)LR(0)有效項(xiàng)目項(xiàng)目A，如果有則項(xiàng)目A 對(duì)活前綴有效。有效。對(duì)同一活前綴有效的（多個(gè)）對(duì)同一活前綴有效的（多個(gè)）LR（0）項(xiàng)目均在同）項(xiàng)目均在同一個(gè)項(xiàng)目集合（狀態(tài)）中；一個(gè)項(xiàng)目集合

20、（狀態(tài)）中；而且同一而且同一LR（0）項(xiàng)目）項(xiàng)目可以對(duì)多個(gè)活前綴有效（即該項(xiàng)目可以出現(xiàn)在不可以對(duì)多個(gè)活前綴有效（即該項(xiàng)目可以出現(xiàn)在不同的項(xiàng)目集合中）同的項(xiàng)目集合中）。*RRSA 2022-4-13編譯原理與技術(shù)講義40LR(0)有效項(xiàng)目如果項(xiàng)目AB對(duì)活前綴有效，即有最右推導(dǎo)如果BP 則有以下最右推導(dǎo)， 顯然，項(xiàng)目B對(duì)活前綴也有效。項(xiàng)目AB和B應(yīng)在同一個(gè)狀態(tài)(項(xiàng)目集合) 這就是closure（）函數(shù)*RRSBA*RRRRSBBA 2022-4-13編譯原理與技術(shù)講義41LR(0)有效項(xiàng)目如果項(xiàng)目AXI對(duì)活前綴有效，則項(xiàng)目AXJ=goto(I,X)顯然對(duì)活前綴X有效。2022-4-13編譯原理與技

21、術(shù)講義42e.g.22 識(shí)別文法G2活前綴的DFA拓展文法G2（0）EE（1）EE + T（2）ET（3）TT * F（4）TF（5）F（ E ）（6）F id DFA的初態(tài)I0= closure(EE)E EE E + TE TT T * FT FF （ E ）F id 2022-4-13編譯原理與技術(shù)講義43I1:EE E E + TI2:ET TT * FI3:T F I4:F(E) EE + T ET TT * F TF F(E) FidI5:F id I0:E E E E + T E T T T * F T F F (E) F idI7:TT * F F(E) FidI6:EE +

22、T TT * F TF F(E) FidI8:F(E) EE + TI11:F(E) I9:EE + T TT * F I10:TT*F ETidF(+*(ETFidTF(idF(id)+*2022-4-13編譯原理與技術(shù)講義44e.g.23 對(duì)活前綴E+T*有效的LR(0)項(xiàng)目E+T*的識(shí)別路徑：I0E I1+ I6T I9* I7項(xiàng)目集合（狀態(tài)）I7中的項(xiàng)目對(duì)E+T*有效： TT *F F(E) FidEE+T E+T*FEE+T E+T*F E+T*(E)EE+T E+T*F E+T*id=E+ = T* =F=E+T* = =(E) 或 id2022-4-13編譯原理與技術(shù)講義45LR

23、(0)分析僅取決于當(dāng)前（棧頂）狀態(tài)僅取決于當(dāng)前（棧頂）狀態(tài)，由狀態(tài)本身所包含的信息決定下一步動(dòng)作。如，LR(0)分析方法I7:TT * F / 轉(zhuǎn)移 F(E) / 移進(jìn)下一輸入符號(hào) Fid / 移進(jìn)下一輸入符號(hào) 至于移入棧頂?shù)姆?hào)不是 ( 或 id，則報(bào)錯(cuò)I10:TT*F / 歸約（不論下一輸入符號(hào)是誰） 2022-4-13編譯原理與技術(shù)講義46LR(0)分析方法LR(0)分析表的構(gòu)造 若AaI，且goto(I,a)=J，則actionI,a=sJ 若A I，則actionI,a = r A,a VT或或$ 若SS I，則actionI,$ = acc 若goto(I,B)=K，則GOTOI,

24、B=K 其它為空白/error文法G是LR(0)的，如果它的LR(0)分析表項(xiàng)沒有多重定義即動(dòng)作沖突；或者它的LR(0)項(xiàng)目規(guī)范族中的任一狀態(tài)不能同時(shí)含有移進(jìn)和歸約的LR(0)項(xiàng)目。e.g.23中表達(dá)式文法G2不是LR(0)文法。如狀態(tài)I1、I2、I9中有移進(jìn)-歸約沖突。（分析表略）2022-4-13編譯原理與技術(shù)講義47SLR（1）分析LR(0)分析能力很弱！解決LR(0)分析沖突通過向前看一個(gè)符號(hào)（當(dāng)前輸入符）來解決移進(jìn)-歸約沖突 若狀態(tài)I中同時(shí)含有移進(jìn)和歸約的LR(0)項(xiàng)目，如， Aa B 則 約定僅在當(dāng)前輸入符號(hào)僅在當(dāng)前輸入符號(hào) Follow(B)時(shí)進(jìn)行歸約時(shí)進(jìn)行歸約因?yàn)橥瓿葿的分析后

25、，讀到的輸入符號(hào)應(yīng)該是B的后繼符號(hào)。而當(dāng)前輸入符而當(dāng)前輸入符號(hào)是號(hào)是a時(shí)則進(jìn)行移進(jìn)。時(shí)則進(jìn)行移進(jìn)。如果如果a Follow(B)，沖突仍，沖突仍然存在！然存在！2022-4-13編譯原理與技術(shù)講義48SLR（1）分析解決LR(0)分析沖突通過向前看一個(gè)符號(hào)（當(dāng)前輸入符）來解決歸約-歸約沖突 若狀態(tài)I中同時(shí)含有兩個(gè)（或兩個(gè)以上）歸約LR(0)項(xiàng)目，如，A B 則 約定僅在僅在當(dāng)前輸入符號(hào)當(dāng)前輸入符號(hào)Follow(A)時(shí)進(jìn)行按時(shí)進(jìn)行按A歸歸約；僅當(dāng)前輸入符號(hào)約；僅當(dāng)前輸入符號(hào)Follow(B)時(shí)進(jìn)行按時(shí)進(jìn)行按B歸約；歸約； 如果如果Follow（A） Follow(B) ，沖突仍然存在！，沖突仍然

26、存在！2022-4-13編譯原理與技術(shù)講義49SLR（1）分析SLR(1)分析表構(gòu)造 若AaI，且goto(I,a)=J，則actionI,a=sJ 若A I，則actionI,b = r A,b Follow(A) 若SS I，則actionI,$ = acc 若goto(I,B)=K，則GOTOI,B=K 其它為空白/errorSLR(1)文法SLR分析表沒有多重定義條目表達(dá)式文法G2是SLR（1）的。分析表見e.g.212022-4-13編譯原理與技術(shù)講義50e.g.24 非SLR（1）的文法G9文法G9(1)SL = R (2)SR(3) L*R (4) Lid(5) RLL：左值表達(dá)

27、式R：右值表達(dá)式 文法G9是非二義性文法First(S)=*,id=First(L)=First(R) Follow(S)=$ Follow(L)= = , $ Follow(R)= =, $ 2022-4-13編譯原理與技術(shù)講義51e.g.24 識(shí)別G9活前綴的DFAI0:S S S L=R S R L *R L id R LI1:S S I2:S L =R R L I3:S R I4:L * R R L L * R L id I6:S L= R R L L * R L idI8:L * R I7:R L I5:L id I9:S L= R SLRid*=L*RLRidid*2022-4-1

28、3編譯原理與技術(shù)講義52狀態(tài)I2中存在移進(jìn)-歸約沖突項(xiàng)目S L =R 要求當(dāng)前輸入符是=時(shí)移進(jìn) ，即action2,= = s6 項(xiàng)目R L 則要求當(dāng)前輸入符是=或者$時(shí)歸約，即action2,= = r5 action2,$ = r5分析棧： 0L2= $ 輸入串移進(jìn)后分析棧： 0L2=6$ 輸入串歸約后分析棧： 0R3= $ 輸入串R= 卻不是文法G9的活前綴2022-4-13編譯原理與技術(shù)講義53LR（1）分析器SLR分析的歸約定義在Follow集合名下，可能導(dǎo)致歸約的“擴(kuò)大化”，引起不必要的沖突，造成了SLR分析能力不強(qiáng)。LR(1)分析規(guī)范的LR分析，能夠準(zhǔn)確地將歸約定義在有關(guān)符號(hào)名下

29、（僅是Follow的子集），即這些符號(hào)只能是最左歸約所對(duì)應(yīng)最即這些符號(hào)只能是最左歸約所對(duì)應(yīng)最右推導(dǎo)逆過程的那一步中跟在左部非終結(jié)符右推導(dǎo)逆過程的那一步中跟在左部非終結(jié)符后面的（終結(jié)）符號(hào)。后面的（終結(jié)）符號(hào)。LR(1)分析使得最左歸約的分析過程與最右推導(dǎo)過程精確地對(duì)應(yīng)，具有最強(qiáng)最強(qiáng)的分析能力。2022-4-13編譯原理與技術(shù)講義54LR(1)項(xiàng)目 A，a 識(shí)別活前綴的LR(1)項(xiàng)目集族（DFA）LR(0)項(xiàng)目搜索符1） ，移進(jìn)項(xiàng)目，與搜索符無關(guān)2） =，歸約項(xiàng)目，當(dāng)前輸入符是搜索符時(shí)才進(jìn)行歸約2022-4-13編譯原理與技術(shù)講義55有效項(xiàng)目LR(1)項(xiàng)目 A，a 對(duì)活前綴有效，如果有最右推導(dǎo)過

30、程，其中 a First( $ )$ )。 識(shí)別活前綴的LR(1)項(xiàng)目集族*RR$A$S a即是右句型A$中跟在A后面的終結(jié)符； 當(dāng)活前綴 出現(xiàn)在棧頂時(shí)，下一輸入符是a時(shí)，才能將歸約成A2022-4-13編譯原理與技術(shù)講義56識(shí)別活前綴的LR(1)項(xiàng)目集族有效項(xiàng)目如果LR(1)項(xiàng)目 AB，a 對(duì)活前綴有效，則對(duì)于BP, LR(1)項(xiàng)目B ,b對(duì)活前綴也有效。其最右推導(dǎo)過程如下， 其中 a First( $ ), 而b First( $ )=First( a) =First( a) 。顯然，顯然， 項(xiàng)目項(xiàng)目 AB，a 和 B ,b 應(yīng)在同一狀態(tài)(項(xiàng)目集合)*RRRR$A $SBB2022-4-1

31、3編譯原理與技術(shù)講義57識(shí)別活前綴的LR(1)項(xiàng)目集族closure(I) 1）I closure(I) 2）若項(xiàng)目AB,aI，BP，則項(xiàng)目 B,b closure(I), bFirst(a) 3）重復(fù)2）直至closure(I)不再增大goto(I,X) J=closure( AX,a | AX,a I )初始項(xiàng)目I0=closure( SS,$ )2022-4-13編譯原理與技術(shù)講義58LR(1)分析表構(gòu)造LR(1)分析表歸約動(dòng)作只填在搜索符名下歸約動(dòng)作只填在搜索符名下；其它同SLR(1)LR(1)文法其LR(1)分析表沒有多重定義表項(xiàng)。文法G9雖不是SLR文法，但卻是LR(1)文法。20

32、22-4-13編譯原理與技術(shù)講義59e.g.25 識(shí)別G9活前綴的LR(1)部分項(xiàng)目集族I0：SS,$ SL=R,$ SR,$ L*R,=/$ Lid,=/$ RL,$I2：SL=R,$ RL,$L下一輸入符是=時(shí)移進(jìn)只有碰到結(jié)束符$時(shí)才歸約沖突解決了！2022-4-13編譯原理與技術(shù)講義60e.g.26 文法G10的LR(1)分析表文法G10(0)SS(1)SBB(2)BbB(3)BaI0=closure( SS,$ )SS,$ S BB,$B bB, a/bB a, a/b Follow(S)=$ Follow(B)=a,b,$ First(S)=a,b First(B)=a,b2022-

33、4-13編譯原理與技術(shù)講義61I0:SS,$ SBB,$BbB, a/bBa, a/bI1:SS,$ I2:SBB,$BbB, $Ba, $I3:BbB, a/bBbB, a/bBa, a/bI4:Ba, a/bSBbaI5:SBB,$BI6:B bB, $BbB, $Ba, $bI7:Ba, $aI8:BbB, a/bBbabI9:B bB, $Bae.g.26 識(shí)別活前綴的LR(1)項(xiàng)目集族2022-4-13編譯原理與技術(shù)講義62e.g.26 文法G10的LR(1)分析表狀態(tài)actiongotoab$SB0s4s3121acc2s7s653s4s384r3r35r16s7s692022-4

34、-13編譯原理與技術(shù)講義63e.g.26 文法G10的LR(1)分析表（續(xù)）狀態(tài)actiongotoab$SB7r38r2r29r22022-4-13編譯原理與技術(shù)講義64I0:SS SBBBbBBaI1:SS I2:SBBBbBBaI3:BbBBbBBaI4:BaSBbaI5:SBBBI8:BbBBbae.g.27 識(shí)別文法G10活前綴的LR(0)項(xiàng)目項(xiàng)目集族集族ba2022-4-13編譯原理與技術(shù)講義65LALR(1)分析LR(1)分析功能最強(qiáng)，但分析表遠(yuǎn)比SLR(1) 大(狀態(tài)數(shù)多) 。同心集兩個(gè)（以上）LR(1)項(xiàng)目集合若忽略搜索符后它們的LR(0)項(xiàng)目集合相同。 e.g.26中狀態(tài)I

35、3與I6、I8與I9以及I4和I7分別是同心集。LALR(1)分析 通過合并LR(1)項(xiàng)目集族中的同心集（即保持同心集合的LR(0)項(xiàng)目集合不變，而對(duì)應(yīng)項(xiàng)目的搜索符加以合并同時(shí)調(diào)整相應(yīng)的狀態(tài)轉(zhuǎn)換）以減少狀態(tài)、壓縮分析表。（合并后其狀態(tài)數(shù)和相應(yīng)的SLR(1)狀態(tài)數(shù)一樣，但帶有搜索符） 若狀態(tài)I和J同心則goto(I,X)和goto(J,X)也同心。2022-4-13編譯原理與技術(shù)講義66I0:SS,$ SBB,$BbB, a/bBa, a/bI1:SS,$ I2:SBB,$BbB, $Ba, $I36:BbB, a/b/$BbB, a/b/$Ba, a/b/$I47:Ba, a/b/$SBbaI

36、5:SBB,$BI89:BbB, a/b/$Bbae.g.28 文法G10的LALR項(xiàng)目集族合并例26中同心集ba2022-4-13編譯原理與技術(shù)講義67LALR(1)分析合并同心集合后可能“新出現(xiàn)”的歸約-歸約沖突（由搜索符的合并而引起的）但合并同心集不會(huì)產(chǎn)生“新”的移進(jìn)-歸約沖突（若有移進(jìn)-歸約沖突，則在合并前已經(jīng)存在）。分析能力介于SLR和LR（1）之間（why？）LALR分析表構(gòu)造同LR(1)；其發(fā)現(xiàn)并報(bào)告錯(cuò)誤可能比LR(1)要遲（作了一些無用的歸約），但不會(huì)漏掉錯(cuò)誤。2022-4-13編譯原理與技術(shù)講義68e.g.29 合并同心集合文法G11S aAdS bBdS aBeS bAeA

37、 cB cG11只產(chǎn)生四個(gè)句子：acd ace bcd bce2022-4-13編譯原理與技術(shù)講義69e.g.29 合并同心集合文法G11S aAdS bBdS aBeS bAeA cB c對(duì)活前綴ac有效的LR(1)項(xiàng)目集I A c,d B c,e why? SaAdacd SaBeace而對(duì)活前綴bc有效的LR(1)項(xiàng)目集J A c,e B c,d why? SbAebce SbBdbcd2022-4-13編譯原理與技術(shù)講義70項(xiàng)目集I 和 J 顯然是同心集合并之！合并后的項(xiàng)目集合Iij A c,d/e B c,e/d 出現(xiàn)（新的）歸約-歸約沖突即面臨輸入符e或者d時(shí)，按Ac還是Bc來歸約

38、呢？而這一沖突在合并前是沒有的！e.g.29 合并同心集合2022-4-13編譯原理與技術(shù)講義71e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b3 移進(jìn)b0b3 移進(jìn)b0b36 移進(jìn)bb a $b a $b a $2022-4-13編譯原理與技術(shù)講義72e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a4 移進(jìn)a0b3a4 移進(jìn)a0b36a47 移進(jìn)ab a $b a $b a $2022-4-13編譯原理與技術(shù)講義73e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a40b3

39、a40b36a470b3B8 多余歸約error 立即報(bào)錯(cuò)0b36B89 多余歸約b a $b a $b a $2022-4-13編譯原理與技術(shù)講義74e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a40b3a40b36a470b3B8error 立即報(bào)錯(cuò)0b36B890B2 多余歸約0B2 多余歸約b a $b a $b a $2022-4-13編譯原理與技術(shù)講義75e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a40b3a40b36a470b3B8Error 立即報(bào)錯(cuò)0b36B890B20B2e

40、rror 報(bào)錯(cuò)error 報(bào)錯(cuò)b a $b a $b a $錯(cuò)誤定位點(diǎn)相同2022-4-13編譯原理與技術(shù)講義76非LR的上下文無關(guān)文法二義性文法絕不是LR類文法（LR（0）、SLR（1），LR（1），LALR（1）存在非二義的文法G不是LR類文法。e.g.31文法G12產(chǎn)生語言L12=R|(a|b)*G12： S a S a S b S b S G12不是LR（K）文法，K0。2022-4-13編譯原理與技術(shù)講義77e.g.31文法G12關(guān)于串a(chǎn)abbaa$的最右推導(dǎo)。S a S a a a S a a a a b S b a a a a b b a a a a b b a a非LR的上下文

41、無關(guān)文法“推導(dǎo)出”前一半串時(shí)才用產(chǎn)生式S。而在LR分析中無法通過移入當(dāng)前符號(hào)來判明是否到達(dá)串的中點(diǎn)（或讀完一半的串），即在什么時(shí)候使用該空產(chǎn)生式上存在二義性（矛盾）。2022-4-13編譯原理與技術(shù)講義78非LR的上下文無關(guān)文法識(shí)別文法G12活前綴的LR（0）部分項(xiàng)目集簇I0： S .S S . a S a S . b S b S . 僅狀態(tài)I0在面臨a或b或$時(shí)歸約；面臨a或b時(shí)移進(jìn)。存在移進(jìn)/歸約沖突！ 因而G12非SLR（1）文法！2022-4-13編譯原理與技術(shù)講義79識(shí)別文法G12活前綴的LR（1）部分項(xiàng)目集簇非LR的上下文無關(guān)文法I0: S .S, $ S . a S a, $ S

42、 . b S b, $ S . , $ I2: S a.S a, $ S . a S a, a S . b S b, a S . , a aI0中沖突解決I2中沖突依然存在2022-4-13編譯原理與技術(shù)講義80非LR的上下文無關(guān)文法類似的，文法G13：S a S a | a 也不是LR（K）文法。e.g.32 產(chǎn)生語言L14=ambn|mn0的3個(gè)文法。（1）二義性文法G14（2）非二義非LR文法G15 （3）LR（1）文法G162022-4-13編譯原理與技術(shù)講義81e.g.32 產(chǎn)生L14=ambn|mn0的3個(gè)文法（1）二義性文法G14S a S b | a S | a a a a b

43、 b bSaSb aaSbb aaaSbbbaaaaSbbb aaaa bbb aaaabbbSaS aaSb aaaSbbaaaaSbbb aaaa bbb aaaabbb2022-4-13編譯原理與技術(shù)講義82e.g.32 產(chǎn)生L14=ambn|mn0的3個(gè)文法（1）二義性文法G14S a S b | a S | SaSb aaSbb aaaSbbbaaaaSbbb aaaa bbb aaaabbbSaS aaSb aaaSbbaaaaSbbb aaaa bbb aaaabbb句柄不同 句柄已出現(xiàn)，應(yīng)歸約，即將棧頂?shù)腶看作多出來的。 句柄未出現(xiàn)，需移進(jìn)b后才形成句柄，以便棧頂a與b的“配對(duì)

44、” 。2022-4-13編譯原理與技術(shù)講義83e.g.32 產(chǎn)生L14=ambn|mn0的3個(gè)文法（2）非二義非LR文法G15S a S b | A A a A | a a a a b b bSaSb aaSbb aaaSbbb aaaAbbb aaaaAbbb aaaabbb aaaabbb2022-4-13編譯原理與技術(shù)講義84（2）識(shí)別文法G15活前綴的部分LR(1)項(xiàng)目簇：I0: S .S, $ S . a S b, $ S . A, $ A . a A, $ A . , $ I3: S a . S b, $ S . a S b, b S . A, b A a . A, $ A . a

45、 A, $/b A . , $/b aaI5: S a . S b, b S . a S b, b S . A, b A a . A, $/b A . a A, $/b A . , $/b aAI7: 歸歸沖突歸歸沖突 S A . , b A a A . , $/b 即在輸入串中含有多于一個(gè)的即在輸入串中含有多于一個(gè)的a，且含有，且含有b時(shí)，狀態(tài)時(shí)，狀態(tài)5面臨面臨b要進(jìn)行歸約（要進(jìn)行歸約（A的空產(chǎn)生的空產(chǎn)生式），然后進(jìn)入狀態(tài)式），然后進(jìn)入狀態(tài)7，此時(shí)面臨輸入符號(hào)，此時(shí)面臨輸入符號(hào)b存在歸歸沖突。也就是說，如何看待棧存在歸歸沖突。也就是說，如何看待棧頂?shù)捻數(shù)腶：它是多出來的，則按：它是多出來的，

46、則按A aA歸約；歸約；它和它和b“配對(duì)配對(duì)”，則按，則按 S A歸約（希望形歸約（希望形成成aSb）。）。2022-4-13編譯原理與技術(shù)講義85e.g.32 產(chǎn)生L14=ambn|mn0的3個(gè)文法（3）LR（1）文法G16S a S | A A a A b | a a a a b b b 輸入串含有多于一個(gè)a和b時(shí)，在讀到b時(shí)，將首先用A的空產(chǎn)生式進(jìn)行歸約，然后在移進(jìn)b，形成aAb，再歸約（再讀入b，等等）。等全部的b讀完后，將A歸約為S，進(jìn)一步形成aS而歸約。2022-4-13編譯原理與技術(shù)講義86二義文法的應(yīng)用二義文法不是LR文法，但文法簡(jiǎn)單，分析表較小分析沖突的解決 通過算符的優(yōu)先級(jí)

47、與結(jié)合性E+E * ( shift first ) E+E + ( reduce first ) E*E * ( reduce first )E*E + ( reduce first ) 優(yōu)先于移進(jìn)if E then S else $ 產(chǎn)生式規(guī)則靠前的優(yōu)先歸約 2022-4-13編譯原理與技術(shù)講義87LR分析的錯(cuò)誤恢復(fù)發(fā)現(xiàn)錯(cuò)誤僅在查找動(dòng)作表時(shí)，actionS,a=error/空白；一般地，SLR和LALR分析器報(bào)告錯(cuò)誤會(huì)比LR(1)分析器遲因?yàn)樽髁诵o效的歸約，但他們都不會(huì)把出錯(cuò)點(diǎn)后的輸入符號(hào)移入分析棧。緊急方式錯(cuò)誤恢復(fù) 分析棧：從棧頂往棧中尋找存在有非終結(jié)符A轉(zhuǎn)移的狀態(tài)S，即有S A S 或

48、gotoS,A=S，彈出狀態(tài)S以上的棧內(nèi)容；將A和狀態(tài)S壓入棧。2022-4-13編譯原理與技術(shù)講義88LR分析的錯(cuò)誤恢復(fù)緊急方式錯(cuò)誤恢復(fù) 輸入串：將輸入指針調(diào)整到aFollow(A)（同步符號(hào)） A的選擇：較大的語法單位，如表達(dá)式、語句、分程序等2022-4-13編譯原理與技術(shù)講義89YACCYet Another Compiler Compiler LALR分析器自動(dòng)生成工具YACC簡(jiǎn)介yacc描述文件yaccy.tab.cyyparse()y.tab.c lex.yy.c *.ccc 可執(zhí)行程序文件a.out2022-4-13編譯原理與技術(shù)講義90YACC描述文件由三部分組成 定義段（d

49、efinitions） 規(guī)則段（rules） 輔助程序段2022-4-13編譯原理與技術(shù)講義91定義段%/* 合法的C聲明、包含文件、宏定義等 */#include #include % 單詞符號(hào)的說明，如 %token digit 算符優(yōu)先級(jí)、結(jié)合性的說明（注意書寫的先后次序） %left+ - 低優(yōu)先級(jí)的算符說明位置在前 %left* / %right 優(yōu)先級(jí)越高，位置越后 開始符號(hào)（缺省時(shí)為第一個(gè)產(chǎn)生式的左部符號(hào)） %start symbol 2022-4-13編譯原理與技術(shù)講義92規(guī)則段A : 1 語義動(dòng)作1 | 2 語義動(dòng)作2 | | n 語義動(dòng)作n | 沒有,則使用缺省的語義動(dòng)作 ; 產(chǎn)生式結(jié)束用分號(hào)標(biāo)記 語義動(dòng)作是C的語句序列（在一對(duì)中間），可以引用聲明段中定義的C變量、宏等，還可以使用yacc的偽變量。 語義動(dòng)作的一般是在產(chǎn)生式右部分析完，歸約動(dòng)作進(jìn)行前執(zhí)行。2022-4-13編譯原理與技術(shù)講義93規(guī)則段（續(xù)）yacc中的偽變量（類型缺省為整型） $ - 產(chǎn)生式左部非終結(jié)符的“值” $i - 產(chǎn)生式右部第i個(gè)文法符號(hào)的“值” yacc中有一個(gè)與分析?！捌叫小钡?/p>