編譯技術(shù)：第04章03 自下而上的語法分析

1、第04章(03) 自下而上的語法分析概述什么是自下而上的語法分析什么是自下而上的語法分析 從輸入串開始分析，直到開始符號從輸入串開始分析，直到開始符號可以使用廣度、深度搜索法可以使用廣度、深度搜索法 但實(shí)際中很少使用但實(shí)際中很少使用本章重點(diǎn)介紹本章重點(diǎn)介紹“有向的有向的”“”“預(yù)測預(yù)測”方法方法 有向：從左向右掃描串有向：從左向右掃描串 預(yù)測：猜測使用哪個(gè)產(chǎn)生式歸約預(yù)測：猜測使用哪個(gè)產(chǎn)生式歸約Zhou, Erqiang2School of Information and Software EngineeringSchool of Information and Software Enginee

2、ringZhou, Erqiang3概述自上而下語法分析自上而下語法分析 從文法開始符從文法開始符S S出發(fā)出發(fā) 猜測輸入串猜測輸入串的推導(dǎo)序列的推導(dǎo)序列自下而上語法分析自下而上語法分析 從輸入串從輸入串出發(fā)出發(fā) 猜測猜測歸約序列歸約序列，使串，使串歸約到歸約到S S概述Zhou, Erqiang4School of Information and Software EngineeringE TE E + TT intT (E)ETint+(int+int+int)ETEEETTTSchool of Information and Software EngineeringZhou, Erqia

3、ng5概述E TE E + TT intT (E) int + ( int + int + int ) T + (int + int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T ESchool of Information and Software EngineeringZhou, Erqiang6概述E TE E + TT intT (E) int + ( int + int + in

4、t ) T + (int + int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T ESchool of Information and Software EngineeringZhou, Erqiang7概述 int + ( int + int + int ) T + (int + int + int) E + (int + int + int) E + (T + int + int)

5、E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T E每步操作稱為每步操作稱為歸約歸約對對句型的子串句型的子串進(jìn)行歸約進(jìn)行歸約將子串歸約為將子串歸約為非終結(jié)符非終結(jié)符本例中，每次歸約本例中，每次歸約 恰為恰為最左歸約最左歸約自下而上的方法自下而上的方法 是否就是找最左歸約呢？是否就是找最左歸約呢？School of Information and Software EngineeringZhou, Erqiang8概述 int + ( int + int + int ) T + (int +

6、 int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EETint+(int+int+int)ETEEETTTint+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang9概述 int + ( int + int + int ) T + (int + int + int) E + (int + i

7、nt + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EETint+(int+int+int)ETEEETTTint+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang10概述 T + (int + int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int)

8、 E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EETint+(int+int+int)ETEEETTT+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang11概述 E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+

9、int)ETEEETTT+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang12概述 E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEEETTT+()+intint+School of Information and Software EngineeringZhou, Erqiang13概述 E + (E + i

10、nt + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEEETT+()+intint+School of Information and Software EngineeringZhou, Erqiang14概述 E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEEETT+()+int+School of Information and Software Engi

11、neeringZhou, Erqiang15概述 E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEET+()+intSchool of Information and Software EngineeringZhou, Erqiang16概述 E + (E + T) E + (E) E + T EEint+(int+int+int)ETEET+()+School of Information and Software EngineeringZhou, Erqiang17概述 E + (E) E + T EEint+(i

12、nt+int+int)ETE+()School of Information and Software EngineeringZhou, Erqiang18概述 E + T EEint+(int+int+int)ET+School of Information and Software EngineeringZhou, Erqiang19概述分析與總結(jié)自下而上語法分析自下而上語法分析 構(gòu)建輸入串的語法樹構(gòu)建輸入串的語法樹 每一步進(jìn)行每一步進(jìn)行“最左歸約最左歸約” 對語法樹進(jìn)行剪枝對語法樹進(jìn)行剪枝對對哪些串哪些串進(jìn)行歸約？進(jìn)行歸約？對哪些葉結(jié)點(diǎn)及邊進(jìn)行剪枝？對哪些葉結(jié)點(diǎn)及邊進(jìn)行剪枝？School

13、 of Information and Software EngineeringZhou, Erqiang20概述分析與總結(jié)考查：每一步進(jìn)行考查：每一步進(jìn)行“最左歸約最左歸約”E FE E + FF F * TF TT intT (E)int+int*intTFETFE不是不是對對“句柄句柄” 進(jìn)行歸約進(jìn)行歸約School of Information and Software EngineeringZhou, Erqiang21相關(guān)概念把每次進(jìn)行處理的子串稱為把每次進(jìn)行處理的子串稱為“句柄句柄” 處理：處理：handle - “handle”handle - “handle” 處理：歸約、剪

14、枝處理：歸約、剪枝問題一：問題一： 句柄在哪里？句柄在哪里？ 句柄在什么位置？句柄在什么位置？School of Information and Software EngineeringZhou, Erqiang22移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)int+int*int+intSchool of Information and Software EngineeringZhou, Erqiang23移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)TintintTFFEE+int*int+intSchool of Inform

15、ation and Software EngineeringZhou, Erqiang24移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)TintFEE+int*int+intSchool of Information and Software EngineeringZhou, Erqiang25移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)TintFEE+int*int+intintTFT FSchool of Information and Software EngineeringZhou, Erqiang26移進(jìn)歸約分析示例E F

16、E E + FF F * TF TT intT (E)TintFEE+*int+intintTFF*School of Information and Software EngineeringZhou, Erqiang27移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)TintFEE+*int+intintTFF*intTTFFEESchool of Information and Software EngineeringZhou, Erqiang28移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)TintFE+intintTF*intT

17、FEE+School of Information and Software EngineeringZhou, Erqiang29移進(jìn)歸約分析示例E FE E + FF F * TF TT intT (E)TintFE+intintTF*intTFFEE+intTFET FESchool of Information and Software EngineeringZhou, Erqiang30分析方法分析方法 移進(jìn)：把終結(jié)符從移進(jìn)：把終結(jié)符從右區(qū)右區(qū)移動(dòng)移動(dòng)左區(qū)左區(qū) 歸約：把歸約：把左區(qū)左區(qū)的部分符號歸約的部分符號歸約句柄在哪里？句柄在哪里？ 左區(qū)的最右邊的符號左區(qū)的最右邊的符號 棧頂?shù)姆?/p>

18、棧頂?shù)姆栆七M(jìn)歸約示例總結(jié)School of Information and Software EngineeringZhou, Erqiang31問題二：問題二： 如何確定句柄？如何確定句柄？ 如何在棧頂部分確定句柄符號串？如何在棧頂部分確定句柄符號串？ 句柄有哪些特征？句柄有哪些特征？移進(jìn)歸約示例總結(jié)School of Information and Software EngineeringZhou, Erqiang32如何確定句柄？如何確定句柄？ 句柄在棧頂句柄在棧頂對棧頂符號詳細(xì)分析對棧頂符號詳細(xì)分析 棧里的符號有什么特征？棧里的符號有什么特征？ 棧里的符號是不是任意的？棧里的符號是不

19、是任意的？如果找出棧里出現(xiàn)符號的特征如果找出棧里出現(xiàn)符號的特征 也許可以根據(jù)特征確定也許可以根據(jù)特征確定句柄句柄移進(jìn)歸約示例總結(jié)School of Information and Software EngineeringZhou, Erqiang33移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEint+int*int+intSchool of Information and Software EngineeringZhou, Erqiang34移進(jìn)歸約示例再分析E FE E + FF F * TF TT int

20、T (E)TintFE+intTF*intTFE+intTFEint+int*int+intSchool of Information and Software EngineeringZhou, Erqiang35移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEint+int*int+intT F ESchool of Information and Software EngineeringZhou, Erqiang36移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)E+intTF*

21、intTFE+intTFE+int*int+intESchool of Information and Software EngineeringZhou, Erqiang37移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)E+intTF*intTFE+intTFE+int*int+intET F將將 E+F 歸約為歸約為 E 嗎？嗎？School of Information and Software EngineeringZhou, Erqiang38移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)E+F*intTFE+intTFE

22、+*int+intEFSchool of Information and Software EngineeringZhou, Erqiang39移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)E+F*intTFE+intTFE+*int+intEFTFESchool of Information and Software EngineeringZhou, Erqiang40移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)E+intTFE+intESchool of Information and Software Engineerin

23、gZhou, Erqiang41移進(jìn)歸約示例再分析E FE E + FF F * TF TT intT (E)E+intTFE+intET FESchool of Information and Software EngineeringZhou, Erqiang42移進(jìn)歸約示例再分析句柄有什么特點(diǎn)？句柄有什么特點(diǎn)？每次每次歸約的串歸約的串的什么特點(diǎn)？的什么特點(diǎn)？句柄：最左、僅有一代的子樹邊緣句柄：最左、僅有一代的子樹邊緣短語：任何子樹的邊緣是子樹根的短語短語：任何子樹的邊緣是子樹根的短語直接短語：僅有一代的子樹邊緣是子樹根的短語直接短語：僅有一代的子樹邊緣是子樹根的短語句柄：最左、直接短語句柄

24、：最左、直接短語School of Information and Software EngineeringZhou, Erqiang43關(guān)注當(dāng)前位置S EE FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEint+int*int+intS EE E+FE E+FE FF TT intSchool of Information and Software EngineeringZhou, Erqiang44關(guān)注當(dāng)前位置S EE FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEi

25、nt+int*int+intS EE E+FE E+FE FF TT intT F ET intF TE FE E+FE E+FSchool of Information and Software EngineeringZhou, Erqiang45關(guān)注當(dāng)前位置E+intTF*intTFE+intTFE+int*int+intS EE FE E + FF F * TF TT intT (E)E E+FS EEE E+FSchool of Information and Software EngineeringZhou, Erqiang46關(guān)注當(dāng)前位置E+intTF*intTFE+intTFES

26、 EE FE E + FF F * TF TT intT (E)F F*TF TT intE E+FS EE E+F+int*int+intESchool of Information and Software EngineeringZhou, Erqiang47關(guān)注當(dāng)前位置E+intTF*intTFE+intTFES EE FE E + FF F * TF TT intT (E)F F*TF TT intE E+FS EE E+F+int*int+intET intTF TFF F*TSchool of Information and Software EngineeringZhou, Er

27、qiang48關(guān)注當(dāng)前位置E+F*intTFE+intTFES EE FE E + FF F * TF TT intT (E)E E+FS EE E+F+*int+intEFF F*TF F*TT intSchool of Information and Software EngineeringZhou, Erqiang49關(guān)注當(dāng)前位置E+F*intTFE+intTFES EE FE E + FF F * TF TT intT (E)E E+FS EE E+F+*int+intEFF F*TT intT intTF F*TFE E+FEE E+FSchool of Information an

28、d Software EngineeringZhou, Erqiang50關(guān)注當(dāng)前位置E+intTFES EE FE E + FF F * TF TT intT (E)S E+intEE E+FE E+FT intF TSchool of Information and Software EngineeringZhou, Erqiang51關(guān)注當(dāng)前位置E+intTFES EE FE E + FF F * TF TT intT (E)S EE E+F+intET intF TT intF TT FE E+FES ESchool of Information and Software Engine

29、eringZhou, Erqiang52如何找出句柄？如何找出句柄？ 句柄在棧頂句柄在棧頂分析棧中的符號分析棧中的符號 與與 產(chǎn)生式有一定關(guān)系產(chǎn)生式有一定關(guān)系 分析過程分析過程 可以可以 不依賴語法樹！不依賴語法樹！ 分析過程分析過程 與與 語法規(guī)則直接相關(guān)語法規(guī)則直接相關(guān)識別棧頂符號School of Information and Software EngineeringZhou, Erqiang53任意時(shí)刻任意時(shí)刻, ,棧中符號可由下面步驟得到棧中符號可由下面步驟得到 1) 1)從開始符號起從開始符號起 跟蹤一系列的產(chǎn)生式跟蹤一系列的產(chǎn)生式 對每個(gè)產(chǎn)生式對每個(gè)產(chǎn)生式, ,跟蹤當(dāng)前分析位置

30、跟蹤當(dāng)前分析位置 2) 2)對每個(gè)產(chǎn)生式對每個(gè)產(chǎn)生式, ,按順序按順序, , 輸出當(dāng)前分析位置之前所有符號輸出當(dāng)前分析位置之前所有符號識別棧頂符號School of Information and Software EngineeringZhou, Erqiang54識別棧頂符號+*int+intEFS EE FE E + FF F * TF TT intT (E)E E+FS EE E+FF F*TT intE E+FE E+FF F*TF F*TT intSchool of Information and Software EngineeringZhou, Erqiang55識別棧頂符號+

31、*int+intEFS EE FE E + FF F * TF TT intT (E)E E+FS EE E+FF F*TT intE E+FE E+FF F*TF F*TT intSchool of Information and Software EngineeringZhou, Erqiang56重要發(fā)現(xiàn)重要發(fā)現(xiàn) 產(chǎn)生式個(gè)數(shù)有限產(chǎn)生式個(gè)數(shù)有限 產(chǎn)生式中位置有限產(chǎn)生式中位置有限 任一時(shí)刻任一時(shí)刻 只需關(guān)注在一個(gè)產(chǎn)生式中的位置只需關(guān)注在一個(gè)產(chǎn)生式中的位置 只有有限個(gè)選擇到下一個(gè)產(chǎn)生式只有有限個(gè)選擇到下一個(gè)產(chǎn)生式如何識別棧頂符號？如何識別棧頂符號？識別棧頂符號School of Informa

32、tion and Software EngineeringZhou, Erqiang57 有限自動(dòng)機(jī)有限自動(dòng)機(jī)識別棧頂符號School of Information and Software EngineeringZhou, Erqiang58識別棧頂符號S ES EE T+EE T+EE T+EE T+EE T;E T;E T;T (E)T (E)T (E)T (E)T intT intET+ET;(E)intSET開始開始S EE T + EE T ;T intT (E)School of Information and Software EngineeringZhou, Erqiang5

33、9非終結(jié)符對應(yīng)一個(gè)狀態(tài)非終結(jié)符對應(yīng)一個(gè)狀態(tài)對每個(gè)產(chǎn)生式對每個(gè)產(chǎn)生式 A 對每個(gè)對每個(gè)A 創(chuàng)建一個(gè)狀態(tài)創(chuàng)建一個(gè)狀態(tài) 其中其中 = = + 在在A x 與與A x 之間之間 加入狀態(tài)轉(zhuǎn)移符加入狀態(tài)轉(zhuǎn)移符x x 對狀態(tài)對狀態(tài)A B與與B B之間加入之間加入轉(zhuǎn)移符轉(zhuǎn)移符 構(gòu)建有限自動(dòng)機(jī)School of Information and Software EngineeringZhou, Erqiang60有限自動(dòng)機(jī)與句柄有什么關(guān)系？有限自動(dòng)機(jī)與句柄有什么關(guān)系？初始問題初始問題 尋找句柄，根據(jù)句柄進(jìn)行歸約尋找句柄，根據(jù)句柄進(jìn)行歸約當(dāng)我們運(yùn)行這個(gè)自動(dòng)機(jī)當(dāng)我們運(yùn)行這個(gè)自動(dòng)機(jī) 如果一個(gè)狀態(tài)有如果一個(gè)狀態(tài)有A

34、那么那么就就有可能有可能是要尋找的是要尋找的句柄！句柄！用這樣的自動(dòng)機(jī)可以尋找句柄！用這樣的自動(dòng)機(jī)可以尋找句柄！“不確定不確定”轉(zhuǎn)化為轉(zhuǎn)化為“確定確定”的的構(gòu)建有限自動(dòng)機(jī)School of Information and Software EngineeringZhou, Erqiang61構(gòu)建有限自動(dòng)機(jī)S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET

35、 (E) T( int(School of Information and Software EngineeringZhou, Erqiang62以含有以含有S A的狀態(tài)開始的狀態(tài)開始 S為文法開始符為文法開始符對每個(gè)狀態(tài)進(jìn)行如下計(jì)算對每個(gè)狀態(tài)進(jìn)行如下計(jì)算 1 1）如果狀態(tài)里含有）如果狀態(tài)里含有A B 則對每個(gè)產(chǎn)生式則對每個(gè)產(chǎn)生式B 將將B 加入到狀態(tài)中加入到狀態(tài)中 構(gòu)建有限自動(dòng)機(jī)School of Information and Software EngineeringZhou, Erqiang63對每個(gè)狀態(tài)進(jìn)行如下計(jì)算對每個(gè)狀態(tài)進(jìn)行如下計(jì)算 2 2）重復(fù)下面操作直到?jīng)]新狀態(tài)產(chǎn)生）重復(fù)下面操

36、作直到?jīng)]新狀態(tài)產(chǎn)生 如果如果狀態(tài)狀態(tài)m m中有中有A x 且且狀態(tài)狀態(tài)n n中有中有A x 那么在狀態(tài)那么在狀態(tài)m m與狀態(tài)與狀態(tài)n n之間之間 加入轉(zhuǎn)移條件加入轉(zhuǎn)移條件 x構(gòu)建有限自動(dòng)機(jī)School of Information and Software EngineeringZhou, Erqiang64句柄在什么位置？句柄在什么位置？ 句柄在棧頂！句柄在棧頂！如何找出句柄？如何找出句柄？ 構(gòu)建自動(dòng)機(jī)！構(gòu)建自動(dòng)機(jī)！如何確認(rèn)句柄？如何確認(rèn)句柄？ 當(dāng)發(fā)現(xiàn)一個(gè)可能的句柄，當(dāng)發(fā)現(xiàn)一個(gè)可能的句柄， 如何知道該句柄是正確或錯(cuò)誤的？如何知道該句柄是正確或錯(cuò)誤的？自動(dòng)機(jī)與句柄School of Infor

37、mation and Software EngineeringZhou, Erqiang65自動(dòng)機(jī)告訴我們句柄已經(jīng)出現(xiàn)自動(dòng)機(jī)告訴我們句柄已經(jīng)出現(xiàn) 但我們需要對此進(jìn)行確認(rèn)但我們需要對此進(jìn)行確認(rèn)算法算法1 1：LRLR（0 0） L: L: 從左向右對串進(jìn)行掃描從左向右對串進(jìn)行掃描 R: R: 最右推導(dǎo)最右推導(dǎo) 0: 0: 不檢查輸入串，直接預(yù)測不檢查輸入串，直接預(yù)測句柄識別School of Information and Software EngineeringZhou, Erqiang66LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T

38、 int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T) intint+(int+int;);(School of Information and Software EngineeringZhou, Erqiang67LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T

39、 int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T) intint+(int+int;);T(School of Information and Software EngineeringZhou, Erqiang68LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) )

40、+(int+int;);TTint(School of Information and Software EngineeringZhou, Erqiang69LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(int+int;);TTint(School of Information and Software Engin

41、eeringZhou, Erqiang70LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(int+int;);TTint(School of Information and Software EngineeringZhou, Erqiang71LR(0)分析方法S EE T + EE T ;T intT (E)S E

42、E T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(int+int;);TTint(TSchool of Information and Software EngineeringZhou, Erqiang72LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE

43、 T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(+int;);TTint(TSchool of Information and Software EngineeringZhou, Erqiang73LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)

44、ET (E) ) +(+int;);TTint(TSchool of Information and Software EngineeringZhou, Erqiang74LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(+int;);TTint(TTSchool of Information and Software

45、 EngineeringZhou, Erqiang75LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(+;);TTint(TT歸約后，重啟自動(dòng)機(jī)歸約后，重啟自動(dòng)機(jī)如何改進(jìn)？如何改進(jìn)？School of Information and Software EngineeringZhou, Erqiang76記錄自動(dòng)機(jī)上一

46、次狀態(tài)記錄自動(dòng)機(jī)上一次狀態(tài) 歸約后，不重啟自動(dòng)機(jī)歸約后，不重啟自動(dòng)機(jī) 而是從上一次狀態(tài)開始識別而是從上一次狀態(tài)開始識別LR(0)分析方法優(yōu)化School of Information and Software EngineeringZhou, Erqiang77LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( intin

47、t+(int+int;);(01234567890School of Information and Software EngineeringZhou, Erqiang78LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( intint+(int+int;);(01234567890T3 9School of Inform

48、ation and Software EngineeringZhou, Erqiang79LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T5School of Information and Software EngineeringZhou, Erqiang80

49、LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58School of Information and Software EngineeringZhou, Erqiang81LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE

50、T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58T3 9School of Information and Software EngineeringZhou, Erqiang82LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; T

51、E T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58T35School of Information and Software EngineeringZhou, Erqiang83LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT

52、 (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58T35T3 9School of Information and Software EngineeringZhou, Erqiang84LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T

53、( int+(+;);(012345678903T58T35T3EE742School of Information and Software EngineeringZhou, Erqiang85LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+();(012345678903T58T E7T36ESchool

54、of Information and Software EngineeringZhou, Erqiang86LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int開始開始S ET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+;(012345678903T5T3EE S421School of Information and Software EngineeringZhou, Er

55、qiang87LR(0)分析方法如何表示？分析方法如何表示？ 兩個(gè)表：兩個(gè)表：actionaction表表 與與 gotogoto表表actionaction表將表將 狀態(tài)狀態(tài), , 終結(jié)符終結(jié)符 映射為：移進(jìn)、歸約、接受、報(bào)錯(cuò)映射為：移進(jìn)、歸約、接受、報(bào)錯(cuò)gotogoto表將表將 狀態(tài)狀態(tài), , 歸約后歸約后非終結(jié)符非終結(jié)符 映射為：狀態(tài)轉(zhuǎn)移映射為：狀態(tài)轉(zhuǎn)移LR(0)分析方法School of Information and Software EngineeringZhou, Erqiang88LR(0)分析方法狀狀態(tài)態(tài)actiongotoint+;()#ET01234567891): S

56、E2): E T + E3): E T ;4): T int5): T (E)School of Information and Software EngineeringZhou, Erqiang89LR(0)分析方法1): S E2): E T + E3): E T ;4): T int5): T (E)ES EE T+EE T;T (E)T int開始開始S ET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int(0123456789Sc

57、hool of Information and Software EngineeringZhou, Erqiang90LR(0)分析方法狀態(tài)狀態(tài)actiongotoint+;()#ET0s9s8131acc2r2r2r2r2r2r23s5s44r3r3r3r3r3r35s9s8236r5r5r5r5r5r57s68s9s8739r4r4r4r4r4r41): S E2): E T + E3): E T ;4): T int5): T (E)School of Information and Software EngineeringZhou, Erqiang91LR分析器結(jié)構(gòu)驅(qū)動(dòng)程序驅(qū)動(dòng)程序分析

58、表分析表輸入串輸入串分析棧分析棧輸出輸出actiongotos0.sm-1sma1ai.b0.bm-1bm符符號號棧棧狀狀態(tài)態(tài)棧棧School of Information and Software EngineeringZhou, Erqiang92LR分析器結(jié)構(gòu)分析棧分析棧 符號棧：存放已識別符號符號棧：存放已識別符號 狀態(tài)棧：狀態(tài)信息，隱含分析歷史狀態(tài)棧：狀態(tài)信息，隱含分析歷史初始時(shí)初始時(shí) 符號棧：符號棧： # 狀態(tài)棧狀態(tài)棧 ：0School of Information and Software EngineeringZhou, Erqiang93LR分析器結(jié)構(gòu)分析表之分析表之Acti

59、on表表 狀態(tài)狀態(tài)與與終結(jié)符終結(jié)符的二維矩陣的二維矩陣actions, a 狀態(tài)為狀態(tài)為s ，輸入符號為，輸入符號為 a 時(shí)的動(dòng)作時(shí)的動(dòng)作 移進(jìn)、歸約、接受、出錯(cuò)移進(jìn)、歸約、接受、出錯(cuò)移進(jìn)：移進(jìn)：actions, a = sj 狀態(tài)狀態(tài) j j 進(jìn)棧，進(jìn)棧，符號符號 a a 進(jìn)棧進(jìn)棧 指針指向下一符號指針指向下一符號School of Information and Software EngineeringZhou, Erqiang94LR分析器結(jié)構(gòu)歸約：歸約：actions, a = rj 按第按第j j個(gè)產(chǎn)生式個(gè)產(chǎn)生式A歸約歸約 分析棧中分析棧中| | | |個(gè)狀態(tài)個(gè)狀態(tài)出棧出棧 如果當(dāng)前

60、棧頂狀態(tài)為如果當(dāng)前棧頂狀態(tài)為i, i, 則根據(jù)則根據(jù)i及及A, , 查查goto表表, , 并將狀態(tài)并將狀態(tài)gotoi,A=k壓入棧壓入棧School of Information and Software EngineeringZhou, Erqiang95LR分析器結(jié)構(gòu)接受：接受：actions, # = acc 結(jié)束分析結(jié)束分析, ,輸入串被接受輸入串被接受出錯(cuò)：出錯(cuò)：actions, a或或gotos, A為空為空 轉(zhuǎn)出錯(cuò)處理程序轉(zhuǎn)出錯(cuò)處理程序School of Information and Software EngineeringZhou, Erqiang96LR分析器結(jié)構(gòu)分析表之