1、第四章(02) (02) 自上而下的語法分析詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義分析語義分析中間代碼優化中間代碼優化目標代碼優化目標代碼優化目標代碼生成目標代碼生成源程序機器代碼編譯的步驟2Zhou, ErqiangSchool of Information and Software EngineeringSchool of Information and Software EngineeringZhou, Erqiang3關于語法分析語法分析的目標語法分析的目標 找出詞法記號序列的結構找出詞法記號序列的結構 恢復出一棵語法樹恢復出一棵語法樹語法描述工具語法描述工具 2

2、 2型型文文法：上下文無關文法法：上下文無關文法無關文法無關文法G=(VT, VN, S, P)及符號串及符號串 判斷判斷是否是是否是G G的句子的句子School of Information and Software EngineeringZhou, Erqiang4關于語法分析語法分析方法的類型語法分析方法的類型 自上而下自上而下( (自頂向下自頂向下) )的分析文法的分析文法 自下而上自下而上( (自底向上自底向上) )的分析文法的分析文法School of Information and Software EngineeringZhou, Erqiang5關于語法分析自上而下語法分析

3、自上而下語法分析 從文法開始符從文法開始符S S出發出發 猜測輸入串猜測輸入串的的推導序列推導序列自下而上語法分析自下而上語法分析 從輸入串從輸入串出發出發 猜測猜測歸約序列歸約序列，使串，使串歸約到歸約到S S猜測猜測直覺直覺向向理論理論提升過程中的提升過程中的必由之路必由之路仍需要仍需要執著執著的思考！的思考！School of Information and Software EngineeringZhou, Erqiang6自上而下的分析法自上而下語法分析自上而下語法分析 從開始符號從開始符號S S開始開始 對每個源程序對每個源程序 如何找出相應的推導序列？如何找出相應的推導序列？ 沒

4、有沒有任何可用信息可以利用任何可用信息可以利用 根據已有的經驗根據已有的經驗/ /直覺直覺從從語法規則語法規則出發檢驗標識符出發檢驗標識符 func1iden iden digit iden 1 iden nondigit 1 iden c1 iden nondigit c1 iden nc1 iden nondigit nc1 iden unc1 nondigit unc1 func1Zhou, Erqiang7語法規則School of Information and Software Engineeringiden nondigit iden iden nondigit iden ide

5、n digit digit 0 | 1 | 2 | | 9 nondigit _ | A | B | | Z | a | b | | z推導過程推導過程好像一條好像一條通路通路正確的推導過程總伴隨著錯誤的推導正確的推導過程總伴隨著錯誤的推導所有所有推導推導過程像是一個過程像是一個迷宮迷宮里的所有里的所有道路道路迷宮？！迷宮？！用什么實現？用什么實現？School of Information and Software EngineeringZhou, Erqiang8自上而下的分析法語法分析語法分析對對的搜索的搜索 圖的節點為句型圖的節點為句型 從節點從節點到節點到節點有條邊有條邊 當且僅當當

6、且僅當 = = School of Information and Software EngineeringZhou, Erqiang9自上而下的分析法E TE T + ET intT (E)ET+E(E)TintT+T(T+E)(T)T+T+Eint+E(int)(E)T+(E)int+Tint+intint+(E)int+T+ESchool of Information and Software EngineeringZhou, Erqiang10自上而下的分析法int + intET+E(E)TintT+T(T+E)(T)T+T+Eint+E(int)(E)T+(E)int+Tint+i

7、ntint+(E)int+T+ESchool of Information and Software EngineeringZhou, Erqiang11算法1：廣度搜索法Q Q為一個為一個“句型句型”的隊列的隊列 初始時隊列僅有開始符號初始時隊列僅有開始符號S S當隊列不為空當隊列不為空 從隊列取一個句型從隊列取一個句型 如果該句型與輸入串匹配，停止如果該句型與輸入串匹配，停止 否則將該句型所有的一步推導句型加到否則將該句型所有的一步推導句型加到Q Q根據所使用的產生式確定語法樹根據所使用的產生式確定語法樹School of Information and Software Engineer

8、ingZhou, Erqiang12算法1：廣度搜索法E TE T + ET intT (E)int + int隊列隊列Q QEET+ETT+ETSchool of Information and Software EngineeringZhou, Erqiang13存在問題：存在問題： 效率低下！效率低下！ 時間、空間資源耗費大時間、空間資源耗費大原因分析：原因分析： 檢查很多檢查很多不可能匹配不可能匹配的句型的句型 高高“分支因子分支因子”如何改進？如何改進？算法1：廣度搜索法School of Information and Software EngineeringZhou, Erqia

9、ng14針對針對“不可能匹配不可能匹配的句型的句型” 假設輸入串為假設輸入串為 對句型對句型 T = ，其中，其中 為為終結符終結符串串 為終結符與非終結符串為終結符與非終結符串 如果如果不是不是的前綴的前綴 那那T T的句子不可能與的句子不可能與匹配匹配算法1：廣度搜索法School of Information and Software EngineeringZhou, Erqiang15針對高針對高“分支因子分支因子” 句型中有多個非終結符句型中有多個非終結符 分支數為各非終結符分支數為各非終結符 所對應產生式個數之和所對應產生式個數之和 限制選用的產生式，降低分支因子限制選用的產生式，

10、降低分支因子 最左推導最左推導算法1：廣度搜索法School of Information and Software EngineeringZhou, Erqiang16算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊列隊列Q QEET+ETT+ETSchool of Information and Software EngineeringZhou, Erqiang17算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊列隊列Q QT(E)intT+ESchool of Information and Software Engin

11、eeringZhou, Erqiang18算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊列隊列Q QT+E(E)+Eint+Eint+ESchool of Information and Software EngineeringZhou, Erqiang19算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊列隊列Q Qint+Eint+T+Eint+Tint+Tint+T+ESchool of Information and Software EngineeringZhou, Erqiang20算法2：最左廣度搜索法E TE

12、T + ET intT (E)int + int隊列隊列Q Qint+Tint+(E)int+intint+T+Eint+intSchool of Information and Software EngineeringZhou, Erqiang21算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊列隊列Q Qint+T+Eint+(E)+Eint+int+Eint+intSchool of Information and Software EngineeringZhou, Erqiang22算法2：最左廣度搜索法E TE T + ET intT (E)int

13、+ int隊列隊列Q Qint+intSchool of Information and Software EngineeringZhou, Erqiang23算法2：最左廣度搜索法總結：總結： 大大提高大大提高了分析的效率了分析的效率 “總能找出總能找出”輸入串的推導序列輸入串的推導序列 如果存在如果存在 萬事大吉？萬事大吉？School of Information and Software EngineeringZhou, Erqiang24算法2：存在問題(1)A Aa | Ab | ccaaaaaaa隊列隊列Q QAAaAbcAaAbSchool of Information and

14、 Software EngineeringZhou, Erqiang25算法2：存在問題(1)A Aa | Ab | ccaaaaaaa隊列隊列Q QAbAaAaaAbacaAaaAbaSchool of Information and Software EngineeringZhou, Erqiang26算法2：存在問題(1)A Aa | Ab | ccaaaaaaa隊列隊列Q QAaaAbAabAbbcbAbaAabAbb左遞歸左遞歸School of Information and Software EngineeringZhou, Erqiang27算法2：存在問題(2)S aASS

15、fA fASA af隊列隊列Q QSaASfaASSchool of Information and Software EngineeringZhou, Erqiang28算法2：存在問題(2)S aASS fA fASA af隊列隊列Q QaASafASSaSaS舍棄？舍棄？S School of Information and Software EngineeringZhou, Erqiang29算法2：存在問題(2)S aASS fA fASA af隊列隊列Q QaSaaASafabSchool of Information and Software EngineeringZhou, E

16、rqiang30算法2：存在問題(2)S aASS fA fASA af隊列隊列Q QafSchool of Information and Software EngineeringZhou, Erqiang31算法2：存在問題(3)S xAyA abA axay隊列隊列Q QSxAyxAyxX X已經匹配已經匹配School of Information and Software EngineeringZhou, Erqiang32算法2：存在問題(3)S xAyA abA axay隊列隊列Q QxAyxabyxayaaa僅向前檢查一個字符僅向前檢查一個字符 還是檢查多個？還是檢查多個？因產

17、生式有因產生式有公共左因子公共左因子 不能立即判斷該舍棄不能立即判斷該舍棄 哪個分支哪個分支 School of Information and Software EngineeringZhou, Erqiang33算法2：存在問題總結：總結： 時間成時間成指數指數式增長式增長 空間也成空間也成指數指數式增長式增長原因？原因？ 文法文法本身問題本身問題 算法算法處理問題處理問題School of Information and Software EngineeringZhou, Erqiang34算法2：存在問題文法問題文法問題 公共左因子公共左因子 A 1 | 2 左遞歸左遞歸 A =* A

18、 對串對串 產生式產生式School of Information and Software EngineeringZhou, Erqiang35算法2：存在問題算法問題算法問題 廣度搜索廣度搜索 同時考慮同時考慮多個多個分支！分支！School of Information and Software EngineeringZhou, Erqiang36文法改造公共左因子公共左因子 A 1 | 2 提取公共左因子提取公共左因子文法中有左遞歸文法中有左遞歸 消除左遞歸消除左遞歸School of Information and Software EngineeringZhou, Erqiang3

19、7文法改造公共左因子公共左因子 A 1 | 2 提取公共左因子提取公共左因子SxAyAaba SxAyAaBBb SxAyAa(b ) School of Information and Software EngineeringZhou, Erqiang38文法改造A 1| n|1|m 公共左因子為公共左因子為 1 1| | |m m 不含公共左因子不含公共左因子改造方法改造方法 A B|1|m B 1| n 若在若在 i、 j、 k中仍有中仍有, ,則再提取則再提取School of Information and Software EngineeringZhou, Erqiang39文法改

20、造文法中有左遞歸文法中有左遞歸 消除消除直接、間接直接、間接左遞歸左遞歸直接左遞歸的消除直接左遞歸的消除 PP|改寫為右遞歸形式改寫為右遞歸形式 P P PP| PP 1| | |P n| | 1| | | m （ i ， j不以不以P P開頭開頭）按公式：按公式： P P( 1| | | | n) | | ( 1| | | m) P ( 1| | | | m ) P P ( 1| | | | m ) P文法改造School of Information and Software Engineering40Zhou, Erqiang PP 1| | |P n| | 1| | | m （ i ，

21、 j不以不以P P開頭）開頭）改寫為改寫為: : P 1P| | | | mP P 1P| | | | nP文法改造School of Information and Software Engineering41Zhou, Erqiang例例 算術表達式文法算術表達式文法E E + T | T（ T + T . . . + T ）T T F | F（ F F . . . F ）F ( E ) | id求消除左遞歸后文法求消除左遞歸后文法文法改造School of Information and Software Engineering42Zhou, Erqiang消除左遞歸消除左遞歸E E +

22、 T | T E TE E + TE | T T F | F T FT T F T | 文法改造School of Information and Software Engineering43Zhou, Erqiang消除左遞歸后文法消除左遞歸后文法 E TE E + TE | T FT T F T | F ( E ) | id文法改造School of Information and Software Engineering44Zhou, Erqiang間接左遞歸間接左遞歸S Aa | bA Sd | 先變換成直接左遞歸先變換成直接左遞歸S Aa | bA Aad | bd | 再消除左遞歸

23、再消除左遞歸文法改造S Aa | bA (bd | ) AAadA | S Aa | bA bdA| AAadA | School of Information and Software Engineering45Zhou, Erqiang間接左遞歸間接左遞歸 SQcc QRbb RSaa求消除左遞歸后的文法求消除左遞歸后的文法 文法改造School of Information and Software Engineering46Zhou, Erqiang解：解：1 1）任意排列遞歸的非終結符）任意排列遞歸的非終結符 S S、Q Q、R R排列排列2 2）依次代入產生式）依次代入產生式 SQ

24、cc 不變不變 QRbb 不變不變 R?文法改造SQccQRbbRSaaRa|Sa a|ca|Qca a|ca|bca|RbcaR bcaRcaRaRR bcaR School of Information and Software Engineering47Zhou, Erqiang解：解：1 1）任意排列遞歸的非終結符）任意排列遞歸的非終結符 R R、Q Q、S S排列排列2 2）依次代入產生式）依次代入產生式 RSaa 不變不變 QRbb 不變不變 S?文法改造SQccQRbbRSaaSc|Qc c|bc|Rbc c|bc|abc|SabcS abcSbcScSS abcS School

25、 of Information and Software Engineering48Zhou, ErqiangSchool of Information and Software EngineeringZhou, Erqiang49文法改造課堂練習課堂練習給定文法給定文法G:G: S Aa | Ab | c A Ad | Se | f消除左遞歸、并提取公共左因子消除左遞歸、并提取公共左因子School of Information and Software EngineeringZhou, Erqiang50算法3：最左深度搜索法思想：思想： 使用深度搜索法使用深度搜索法 空間：一次僅考慮空間

26、：一次僅考慮一個分支一個分支 時間：對很多文法，運行時間：對很多文法，運行極快極快！ 實現：可遞歸實現，實現：可遞歸實現，簡單簡單！School of Information and Software EngineeringZhou, Erqiang51算法3：最左深度搜索法E TE T + ET intT (E)int + intET+ETint(E)School of Information and Software EngineeringZhou, Erqiang52算法3：最左深度搜索法ET+ET(E)(E)E TE T + ET intT (E)int + intSchool of

27、Information and Software EngineeringZhou, Erqiang53算法3：最左深度搜索法ET+ETE TE T + ET intT (E)int + intSchool of Information and Software EngineeringZhou, Erqiang54算法3：最左深度搜索法ET+ET+EE TE T + ET intT (E)int + intint+E(E)+Eint+Tint+T+Eint+intSchool of Information and Software EngineeringZhou, Erqiang55算法3：存在

28、問題AAaA Aa | ccAaaAaaaAaaaa左遞歸左遞歸School of Information and Software EngineeringZhou, Erqiang56最左分析算法總結最左廣度搜索最左廣度搜索 所有所有文法文法 時間指數增長時間指數增長 空間空間指數指數增長增長 實際很少使用實際很少使用最左深度搜索最左深度搜索 文法文法無左遞歸無左遞歸 時間指數增長時間指數增長 空間空間線性線性增長增長 應用在應用在“遞歸下遞歸下降分析法降分析法”中中算法算法1 1至算法至算法3 3 使用搜索的方法使用搜索的方法 分析需要回溯、不確定分析需要回溯、不確定遞歸下降分析法遞歸下降

29、分析法和和預測分析法預測分析法 確定的分析方法確定的分析方法 ( (僅針對一些僅針對一些特定特定的文法的文法) )最左分析算法總結School of Information and Software Engineering57Zhou, Erqiang利用函數之間的遞歸調用利用函數之間的遞歸調用 模擬語法樹自上而下的構造過程模擬語法樹自上而下的構造過程文法要求文法要求 無左遞歸無左遞歸 無公共左因子無公共左因子 每次所選的產生式確定每次所選的產生式確定有可能有可能構造出不帶回溯的分析程序構造出不帶回溯的分析程序遞歸下降分析法School of Information and Software

30、Engineering58Zhou, Erqiang每個非終結符對應一個解析函數每個非終結符對應一個解析函數產生式右側為其左側非終結符產生式右側為其左側非終結符 所對應解析函數的所對應解析函數的“函數體函數體”產生式右側終結符產生式右側終結符 對應從輸入串中消耗該終結符對應從輸入串中消耗該終結符產生式中的產生式中的| 對應對應“if-else”if-else”語句語句遞歸下降分析法School of Information and Software Engineering59Zhou, Erqiang例：對下列文法構造分析程序例：對下列文法構造分析程序遞歸下降分析法E TE E + TE |

31、T FT T F T | F ( E ) | iSchool of Information and Software Engineering60Zhou, Erqiang遞歸下降分析法E TE E + TE | T FT T F T | F ( E ) | ivoid E( )T()；E1()；void E1( )if( sym = + ) advance()； T()； E1()；School of Information and Software Engineering61Zhou, Erqiangvoid T( ) F()； T1()；變量變量sym表示當前符號表示當前符號函數函數adv

32、ance()() 讀取下一字符讀取下一字符遞歸下降分析法E TE E + TE | T FT T F T | F ( E ) | ivoid T1()if( sym = * ) advance()； F()； T1()；void F() if ( sym = ( ) advance()； E()； if ( sym = ) ) advance()； else error()；else if ( sym = i ) advance()；else error()；School of Information and Software Engineering62Zhou, ErqiangETFiiM(

33、i)ETFiiM(i)ETFT+M(+)*#*M(*)i#M( )#M(i)M( )T+M( )School of Information and Software Engineering63Zhou, ErqiangE TE E + TE | T FT T F T | F ( E ) | i串 i+i*i# 遞歸下降分析過程利用利用 正則表達式、有限自動機正則表達式、有限自動機 對文法、程序進行簡化對文法、程序進行簡化E E + T | TE T + T 自學自學 ( (實驗二內容實驗二內容) )School of Information and Software Engineering64

34、Zhou, Erqiang擴充的文法課堂練習課堂練習P 216, 9-3P 216, 9-3對文法對文法 S (L) | a L L,S | S消除左遞歸，寫出遞歸下降分析過程。消除左遞歸，寫出遞歸下降分析過程。School of Information and Software Engineering65Zhou, Erqiang遞歸下降分析法總結預測分析法School of Information and Software Engineering66Zhou, Erqiang算法算法1 1至算法至算法3 3需要需要“回溯回溯” 猜測猜測使用哪個產生式使用哪個產生式 分析時需要分析時需要運氣

35、運氣（不確定）（不確定）另一類算法稱為另一類算法稱為“預測預測”算法算法 根據剩余輸入串（事實）根據剩余輸入串（事實） 預測預測哪個產生式（確定）哪個產生式（確定）預測分析法School of Information and Software Engineering67Zhou, Erqiang預測預測算法更算法更“快快” 線性運行時間線性運行時間 表驅動表驅動預測算法更預測算法更“脆弱脆弱” 不支持所有的文法不支持所有的文法在在文法表達力文法表達力與與運行速度運行速度之間尋求平衡之間尋求平衡預測分析法School of Information and Software Engineering

36、68Zhou, Erqiang從開始符號開始，如何選產生式？從開始符號開始，如何選產生式？基本思想基本思想 向前看向前看 在選產生式時，查看當前輸入串在選產生式時，查看當前輸入串查看的字符個數查看的字符個數越多越多 支持的文法支持的文法越多越多 分析就分析就越復雜越復雜School of Information and Software EngineeringZhou, Erqiang69EE TBB | + ET intT (E)int+intint(+預測分析法TBint+Eint+TB)int+(E)Bint+(intB)Bint+(int+E)Bint+(int+TB)Bint+(in

37、t+intB)Bint+(TB)Bint+(int+int)Bint+(int+int)intB如何把如何把選擇產生式的經驗選擇產生式的經驗描述出來、描述出來、再提升至理論？再提升至理論？School of Information and Software EngineeringZhou, Erqiang70EE TBB | + ET intT (E)int+intint(+預測分析法TBint+Eint+TB)int+(E)Bint+(intB)Bint+(TB)BintBint()+EBTT (E)T intB +EE TBE TB預測分析法School of Information an

38、d Software Engineering71Zhou, ErqiangLL(1)LL(1)分析法分析法 L L：從左到右掃描輸入串：從左到右掃描輸入串 L L：使用：使用最左推導最左推導 （1 1）：每次只檢查）：每次只檢查1 1個個“詞法記號詞法記號”對于輸入的對于輸入的“詞法記號詞法記號”序列序列 構建該序列的最左推導構建該序列的最左推導預測分析法School of Information and Software Engineering72Zhou, ErqiangLL(1)LL(1)預測分析表預測分析表E intE (E Op E)Op +Op *int()+*EEintE(E O

39、p E)OpOp+Op*(int + (int * int)預測分析法School of Information and Software Engineering73Zhou, ErqiangLL(1)LL(1)預測分析表預測分析表1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)int()+*E12Op34預測分析法School of Information and Software Engineering74Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * in

40、t)int()+*E12Op34E預測分析法School of Information and Software Engineering75Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#在輸入串在輸入串后后加上加上# #做標記做標記 表示輸入串已經結束表示輸入串已經結束第一個符號是開始符號第一個符號是開始符號 檢查分析表檢查分析表 確定推導的產生式確定推導的產生式這一步為這一步為預測預測預測分析法School of Information and Software Engin

41、eering76Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#2對于所猜測的句型對于所猜測的句型 第一個符號是第一個符號是終結符終結符將將其其與輸入串與輸入串第一個符號第一個符號 進行匹配進行匹配句型句型左邊左邊的符號與的符號與 輸入串輸入串左邊左邊的符號匹配的符號匹配句型句型逆序逆序壓入棧壓入棧預測分析法School of Information and Software Engineering77Zhou, Erqi

42、ang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#int + (int * int)#E Op E)#2對于所猜測的句型對于所猜測的句型 第一個符號是第一個符號是終結符終結符將將其其與輸入串與輸入串第一個符號第一個符號 進行匹配進行匹配句型句型左邊左邊的符號與的符號與 輸入串輸入串左邊左邊的符號匹配的符號匹配句型句型逆序逆序壓入棧壓入棧預測分析法School of Information and Software Engineering78Zh

43、ou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#int + (int * int)#E Op E)#1int + (int * int)#int Op E)#+ (int * int)#Op E)#3+ (int * int)#+ E)# (int * int)#E)#2 (int * int)#(E Op E)# int * int)#E Op E)# int * int)#int Op E)# * int)#Op E)#4

44、 * int)#* E)# int)#E)# int)#int)# )#)# )#)# #預測分析法School of Information and Software Engineering79Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#int + (int * int)#E Op E)#int + (int * int)#int Op E)#+ (int * int)#Op E)#+ (int * int)#+ E

45、)# (int * int)#E)# (int * int)#(E Op E)# int * int)#E Op E)# int * int)#int Op E)# * int)#Op E)# * int)#* E)# int)#E)# int)#int)# )#)# )#)# #預測分析法錯誤處理一School of Information and Software Engineering80Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *int + int#int()+*E12Op34E#1int + int#int#+ int#預測分析法錯

46、誤處理二School of Information and Software Engineering81Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int (int)#int()+*E12Op34E#2(int (int)#(E Op E)#int (int)#E Op E)#int (int)#int Op E)#1(int)#Op E)#預測分析法總結School of Information and Software Engineering82Zhou, Erqiang組成組成 一個下推棧一個下推棧 一個分析表一個分析表分析過程初始狀

47、態分析過程初始狀態 棧：結束符棧：結束符# # 和和 開始符開始符S S 指針：輸入串指針：輸入串的第一個符號的第一個符號預測分析法總結School of Information and Software Engineering83Zhou, Erqiang分析過程中某一時刻：分析過程中某一時刻： 棧頂符號為棧頂符號為x x，輸入符號為，輸入符號為a a分析器的動作有下列三種選擇：分析器的動作有下列三種選擇： 1) 1)若若 x = a = #x = a = # 則符號串和棧均為空則符號串和棧均為空 則輸入串則輸入串是文法的一個合法句子是文法的一個合法句子 分析過程結束分析過程結束預測分析法總

48、結School of Information and Software Engineering84Zhou, Erqiang分析器的動作有下列三種選擇：分析器的動作有下列三種選擇： 2) 2)若若 x = a # 則則x x出棧，指針移向下一個符號出棧，指針移向下一個符號 繼續下一次匹配繼續下一次匹配預測分析法總結School of Information and Software Engineering85Zhou, Erqiang分析器的動作有下列三種選擇：分析器的動作有下列三種選擇： 3) 3)若若x x為非終結符，則查分析表為非終結符，則查分析表 若若Mx，a中存放中存放 x 則則x出

49、棧，將出棧，將串串逆序逆序壓入棧中壓入棧中 若若Mx，a中為出錯標志中為出錯標志 則調用出錯處理程序則調用出錯處理程序error( )預測分析法總結School of Information and Software Engineering86Zhou, Erqiang預測分析法的關鍵是預測分析法的關鍵是分析表分析表 如何構造分析表？如何構造分析表？ 手動構造手動構造 算法構造算法構造School of Information and Software Engineering87Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT |

50、 while while EXPREXPR do do STMTSTMT | EXPREXPR ; ;EXPREXPR TERMTERM - id - id | zero? zero? TERMTERM | not not EXPREXPR | + id+ id | - id- idTERMTERM id id | constantconstant預測分析表的構造id - id;id - id;while not zero? idwhile not zero? id do do -id;id;if not zero? id thenif not zero? id then if not zer

51、o? id then if not zero? id then constant - id; constant - id;School of Information and Software Engineering88Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (

52、5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPRTERMSchool of Information and Software Engineering89Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR d

53、o do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)910ifthenwhiledozero?not+-idconst;-STMTEXPRTERMSchool of Information and Soft

54、ware Engineering90Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9)

55、 | constant constant (10)(10)567ifthenwhiledozero?not+-idconst;-STMTEXPRTERM9108School of Information and Software Engineering91Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero

56、? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)567844ifthenwhiledozero?not+-idconst;-STMTEXPRTERM910School of Information and Software Engineering92Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)

57、(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPR567844TER

58、M91012School of Information and Software Engineering93Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | -

59、 id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPR567844TERM910123333School of Information and Software Engineering94Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)

60、(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPR567844TERM91012333333School of Information and Software Engineering95Zhou, Er