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

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

2、ringZhou, Erqiang3概述自上而下語法分析自上而下語法分析 從文法開始符從文法開始符S S出發(fā)出發(fā) 猜測輸入串猜測輸入串的推導序列的推導序列自下而上語法分析自下而上語法分析 從輸入串從輸入串出發(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每步操作稱為每步操作稱為歸約歸約對對句型的子串句型的子串進行歸約進行歸約將子串歸約為將子串歸約為非終結符非終結符本例中，每次歸約本例中，每次歸約 恰為恰為最左歸約最左歸約自下而上的方法自下而上的方法 是否就是找最左歸約呢？是否就是找最左歸約呢？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概述分析與總結自下而上語法分析自下而上語法分析 構建輸入串的語法樹構建輸入串的語法樹 每一步進行每一步進行“最左歸約最左歸約” 對語法樹進行剪枝對語法樹進行剪枝對對哪些串哪些串進行歸約？進行歸約？對哪些葉結點及邊進行剪枝？對哪些葉結點及邊進行剪枝？School

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

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

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

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

17、FEE+School of Information and Software EngineeringZhou, Erqiang29移進歸約分析示例E FE E + FF F * TF TT intT (E)TintFE+intintTF*intTFFEE+intTFET FESchool of Information and Software EngineeringZhou, Erqiang30分析方法分析方法 移進：把終結符從移進：把終結符從右區(qū)右區(qū)移動移動左區(qū)左區(qū) 歸約：把歸約：把左區(qū)左區(qū)的部分符號歸約的部分符號歸約句柄在哪里？句柄在哪里？ 左區(qū)的最右邊的符號左區(qū)的最右邊的符號 棧頂的符號

18、棧頂的符號移進歸約示例總結School of Information and Software EngineeringZhou, Erqiang31問題二：問題二： 如何確定句柄？如何確定句柄？ 如何在棧頂部分確定句柄符號串？如何在棧頂部分確定句柄符號串？ 句柄有哪些特征？句柄有哪些特征？移進歸約示例總結School of Information and Software EngineeringZhou, Erqiang32如何確定句柄？如何確定句柄？ 句柄在棧頂句柄在棧頂對棧頂符號詳細分析對棧頂符號詳細分析 棧里的符號有什么特征？棧里的符號有什么特征？ 棧里的符號是不是任意的？棧里的符號是不

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

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

21、intTFE+intTFE+int*int+intESchool of Information and Software EngineeringZhou, Erqiang37移進歸約示例再分析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移進歸約示例再分析E FE E + FF F * TF TT intT (E)E+F*intTFE+intTFE

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

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

24、：最左、直接短語School of Information and Software EngineeringZhou, Erqiang43關注當前位置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關注當前位置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關注當前位置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關注當前位置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關注當前位置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關注當前位置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關注當前位置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關注當前位置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關注當前位置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如何找出句柄？如何找出句柄？ 句柄在棧頂句柄在棧頂分析棧中的符號分析棧中的符號 與與 產生式有一定關系產生式有一定關系 分析過程分析過程 可以可以 不依賴語法樹！不依賴語法樹！ 分析過程分析過程 與與 語法規(guī)則直接相關語法規(guī)則直接相關識別棧頂符號School of Information and Software EngineeringZhou, Erqiang53任意時刻任意時刻, ,棧中符號可由下面步驟得到棧中符號可由下面步驟得到 1) 1)從開始符號起從開始符號起 跟蹤一系列的產生式跟蹤一系列的產生式 對每個產生式對每個產生式, ,跟蹤當前分析位置

30、跟蹤當前分析位置 2) 2)對每個產生式對每個產生式, ,按順序按順序, , 輸出當前分析位置之前所有符號輸出當前分析位置之前所有符號識別棧頂符號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ā)現重要發(fā)現 產生式個數有限產生式個數有限 產生式中位置有限產生式中位置有限 任一時刻任一時刻 只需關注在一個產生式中的位置只需關注在一個產生式中的位置 只有有限個選擇到下一個產生式只有有限個選擇到下一個產生式如何識別棧頂符號？如何識別棧頂符號？識別棧頂符號School of Informa

32、tion and Software EngineeringZhou, Erqiang57 有限自動機有限自動機識別棧頂符號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非終結符對應一個狀態(tài)非終結符對應一個狀態(tài)對每個產生式對每個產生式 A 對每個對每個A 創(chuàng)建一個狀態(tài)創(chuàng)建一個狀態(tài) 其中其中 = = + 在在A x 與與A x 之間之間 加入狀態(tài)轉移符加入狀態(tài)轉移符x x 對狀態(tài)對狀態(tài)A B與與B B之間加入之間加入轉移符轉移符 構建有限自動機School of Information and Software EngineeringZhou, Erqiang60有限自動機與句柄有什么關系？有限自動機與句柄有什么關系？初始問題初始問題 尋找句柄，根據句柄進行歸約尋找句柄，根據句柄進行歸約當我們運行這個自動機當我們運行這個自動機 如果一個狀態(tài)有如果一個狀態(tài)有A

34、那么那么就就有可能有可能是要尋找的是要尋找的句柄！句柄！用這樣的自動機可以尋找句柄！用這樣的自動機可以尋找句柄！“不確定不確定”轉化為轉化為“確定確定”的的構建有限自動機School of Information and Software EngineeringZhou, Erqiang61構建有限自動機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為文法開始符為文法開始符對每個狀態(tài)進行如下計算對每個狀態(tài)進行如下計算 1 1）如果狀態(tài)里含有）如果狀態(tài)里含有A B 則對每個產生式則對每個產生式B 將將B 加入到狀態(tài)中加入到狀態(tài)中 構建有限自動機School of Information and Software EngineeringZhou, Erqiang63對每個狀態(tài)進行如下計算對每個狀態(tài)進行如下計算 2 2）重復下面操作直到沒新狀態(tài)產生）重復下面操

36、作直到沒新狀態(tài)產生 如果如果狀態(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之間之間 加入轉移條件加入轉移條件 x構建有限自動機School of Information and Software EngineeringZhou, Erqiang64句柄在什么位置？句柄在什么位置？ 句柄在棧頂！句柄在棧頂！如何找出句柄？如何找出句柄？ 構建自動機！構建自動機！如何確認句柄？如何確認句柄？ 當發(fā)現一個可能的句柄，當發(fā)現一個可能的句柄， 如何知道該句柄是正確或錯誤的？如何知道該句柄是正確或錯誤的？自動機與句柄School of Infor

37、mation and Software EngineeringZhou, Erqiang65自動機告訴我們句柄已經出現自動機告訴我們句柄已經出現 但我們需要對此進行確認但我們需要對此進行確認算法算法1 1：LRLR（0 0） L: L: 從左向右對串進行掃描從左向右對串進行掃描 R: R: 最右推導最右推導 0: 0: 不檢查輸入串，直接預測不檢查輸入串，直接預測句柄識別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歸約后，重啟自動機歸約后，重啟自動機如何改進？如何改進？School of Information and Software EngineeringZhou, Erqiang76記錄自動機上一

46、次狀態(tài)記錄自動機上一次狀態(tài) 歸約后，不重啟自動機歸約后，不重啟自動機 而是從上一次狀態(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)分析方法如何表示？分析方法如何表示？ 兩個表：兩個表：actionaction表表 與與 gotogoto表表actionaction表將表將 狀態(tài)狀態(tài), , 終結符終結符 映射為：移進、歸約、接受、報錯映射為：移進、歸約、接受、報錯gotogoto表將表將 狀態(tài)狀態(tài), , 歸約后歸約后非終結符非終結符 映射為：狀態(tài)轉移映射為：狀態(tài)轉移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分析器結構驅動程序驅動程序分析

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

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

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