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

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

3、自上而下語法分析 從文法開始符從文法開始符S S出發(fā)出發(fā) 猜測輸入串猜測輸入串的的推導(dǎo)序列推導(dǎo)序列自下而上語法分析自下而上語法分析 從輸入串從輸入串出發(fā)出發(fā) 猜測猜測歸約序列歸約序列，使串，使串歸約到歸約到S S猜測猜測直覺直覺向向理論理論提升過程中的提升過程中的必由之路必由之路仍需要仍需要執(zhí)著執(zhí)著的思考！的思考！School of Information and Software EngineeringZhou, Erqiang6自上而下的分析法自上而下語法分析自上而下語法分析 從開始符號從開始符號S S開始開始 對每個(gè)源程序?qū)γ總€(gè)源程序 如何找出相應(yīng)的推導(dǎo)序列？如何找出相應(yīng)的推導(dǎo)序列？ 沒

4、有沒有任何可用信息可以利用任何可用信息可以利用 根據(jù)已有的經(jīng)驗(yàn)根據(jù)已有的經(jīng)驗(yàn)/ /直覺直覺從從語法規(guī)則語法規(guī)則出發(fā)檢驗(yàn)標(biāo)識符出發(fā)檢驗(yàn)標(biāo)識符 func1iden iden digit iden 1 iden nondigit 1 iden c1 iden nondigit c1 iden nc1 iden nondigit nc1 iden unc1 nondigit unc1 func1Zhou, Erqiang7語法規(guī)則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推導(dǎo)過程推導(dǎo)過程好像一條好像一條通路通路正確的推導(dǎo)過程總伴隨著錯(cuò)誤的推導(dǎo)正確的推導(dǎo)過程總伴隨著錯(cuò)誤的推導(dǎo)所有所有推導(dǎo)推導(dǎo)過程像是一個(gè)過程像是一個(gè)迷宮迷宮里的所有里的所有道路道路迷宮？！迷宮？！用什么實(shí)現(xiàn)？用什么實(shí)現(xiàn)？School of Information and Software EngineeringZhou, Erqiang8自上而下的分析法語法分析語法分析對對的搜索的搜索 圖的節(jié)點(diǎn)為句型圖的節(jié)點(diǎn)為句型 從節(jié)點(diǎn)從節(jié)點(diǎn)到節(jié)點(diǎn)到節(jié)點(diǎn)有條邊有條邊 當(dāng)且僅當(dāng)當(dāng)

6、且僅當(dāng) = = 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為一個(gè)為一個(gè)“句型句型”的隊(duì)列的隊(duì)列 初始時(shí)隊(duì)列僅有開始符號初始時(shí)隊(duì)列僅有開始符號S S當(dāng)隊(duì)列不為空當(dāng)隊(duì)列不為空 從隊(duì)列取一個(gè)句型從隊(duì)列取一個(gè)句型 如果該句型與輸入串匹配，停止如果該句型與輸入串匹配，停止 否則將該句型所有的一步推導(dǎo)句型加到否則將該句型所有的一步推導(dǎo)句型加到Q Q根據(jù)所使用的產(chǎn)生式確定語法樹根據(jù)所使用的產(chǎn)生式確定語法樹School of Information and Software Engineer

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

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

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

11、eeringZhou, Erqiang18算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊(duì)列隊(duì)列Q QT+E(E)+Eint+Eint+ESchool of Information and Software EngineeringZhou, Erqiang19算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊(duì)列隊(duì)列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隊(duì)列隊(duì)列Q Qint+Tint+(E)int+intint+T+Eint+intSchool of Information and Software EngineeringZhou, Erqiang21算法2：最左廣度搜索法E TE T + ET intT (E)int + int隊(duì)列隊(duì)列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隊(duì)列隊(duì)列Q Qint+intSchool of Information and Software EngineeringZhou, Erqiang23算法2：最左廣度搜索法總結(jié)：總結(jié)： 大大提高大大提高了分析的效率了分析的效率 “總能找出總能找出”輸入串的推導(dǎo)序列輸入串的推導(dǎo)序列 如果存在如果存在 萬事大吉？萬事大吉？School of Information and Software EngineeringZhou, Erqiang24算法2：存在問題(1)A Aa | Ab | ccaaaaaaa隊(duì)列隊(duì)列Q QAAaAbcAaAbSchool of Information and

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

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

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

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

18、 對串對串 產(chǎn)生式產(chǎn)生式School of Information and Software EngineeringZhou, Erqiang35算法2：存在問題算法問題算法問題 廣度搜索廣度搜索 同時(shí)考慮同時(shí)考慮多個(gè)多個(gè)分支！分支！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例例 算術(shù)表達(dá)式文法算術(shù)表達(dá)式文法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）任意排列遞歸的非終結(jié)符）任意排列遞歸的非終結(jié)符 S S、Q Q、R R排列排列2 2）依次代入產(chǎn)生式）依次代入產(chǎn)生式 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）任意排列遞歸的非終結(jié)符）任意排列遞歸的非終結(jié)符 R R、Q Q、S S排列排列2 2）依次代入產(chǎn)生式）依次代入產(chǎn)生式 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文法改造課堂練習(xí)課堂練習(xí)給定文法給定文法G:G: S Aa | Ab | c A Ad | Se | f消除左遞歸、并提取公共左因子消除左遞歸、并提取公共左因子School of Information and Software EngineeringZhou, Erqiang50算法3：最左深度搜索法思想：思想： 使用深度搜索法使用深度搜索法 空間：一次僅考慮空間

26、：一次僅考慮一個(gè)分支一個(gè)分支 時(shí)間：對很多文法，運(yùn)行時(shí)間：對很多文法，運(yùn)行極快極快！ 實(shí)現(xiàn)：可遞歸實(shí)現(xiàn)，實(shí)現(xiàn)：可遞歸實(shí)現(xiàn)，簡單簡單！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最左分析算法總結(jié)最左廣度搜索最左廣度搜索 所有所有文法文法 時(shí)間指數(shù)增長時(shí)間指數(shù)增長 空間空間指數(shù)指數(shù)增長增長 實(shí)際很少使用實(shí)際很少使用最左深度搜索最左深度搜索 文法文法無左遞歸無左遞歸 時(shí)間指數(shù)增長時(shí)間指數(shù)增長 空間空間線性線性增長增長 應(yīng)用在應(yīng)用在“遞歸下遞歸下降分析法降分析法”中中算法算法1 1至算法至算法3 3 使用搜索的方法使用搜索的方法 分析需要回溯、不確定分析需要回溯、不確定遞歸下降分析法遞歸下降

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

30、Engineering58Zhou, Erqiang每個(gè)非終結(jié)符對應(yīng)一個(gè)解析函數(shù)每個(gè)非終結(jié)符對應(yīng)一個(gè)解析函數(shù)產(chǎn)生式右側(cè)為其左側(cè)非終結(jié)符產(chǎn)生式右側(cè)為其左側(cè)非終結(jié)符 所對應(yīng)解析函數(shù)的所對應(yīng)解析函數(shù)的“函數(shù)體函數(shù)體”產(chǎn)生式右側(cè)終結(jié)符產(chǎn)生式右側(cè)終結(jié)符 對應(yīng)從輸入串中消耗該終結(jié)符對應(yīng)從輸入串中消耗該終結(jié)符產(chǎn)生式中的產(chǎn)生式中的| 對應(yīng)對應(yīng)“if-else”if-else”語句語句遞歸下降分析法School of Information and Software Engineering59Zhou, Erqiang例：對下列文法構(gòu)造分析程序例：對下列文法構(gòu)造分析程序遞歸下降分析法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表示當(dāng)前符號表示當(dāng)前符號函數(shù)函數(shù)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# 遞歸下降分析過程利用利用 正則表達(dá)式、有限自動機(jī)正則表達(dá)式、有限自動機(jī) 對文法、程序進(jìn)行簡化對文法、程序進(jìn)行簡化E E + T | TE T + T 自學(xué)自學(xué) ( (實(shí)驗(yàn)二內(nèi)容實(shí)驗(yàn)二內(nèi)容) )School of Information and Software Engineering64

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

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

36、68Zhou, Erqiang從開始符號開始，如何選產(chǎn)生式？從開始符號開始，如何選產(chǎn)生式？基本思想基本思想 向前看向前看 在選產(chǎn)生式時(shí)，查看當(dāng)前輸入串在選產(chǎn)生式時(shí)，查看當(dāng)前輸入串查看的字符個(gè)數(shù)查看的字符個(gè)數(shù)越多越多 支持的文法支持的文法越多越多 分析就分析就越復(fù)雜越復(fù)雜School of Information and Software EngineeringZhou, Erqiang69EE TBB | + ET intT (E)int+intint(+預(yù)測分析法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如何把如何把選擇產(chǎn)生式的經(jīng)驗(yàn)選擇產(chǎn)生式的經(jīng)驗(yàn)描述出來、描述出來、再提升至理論？再提升至理論？School of Information and Software EngineeringZhou, Erqiang70EE TBB | + ET intT (E)int+intint(+預(yù)測分析法TBint+Eint+TB)int+(E)Bint+(intB)Bint+(TB)BintBint()+EBTT (E)T intB +EE TBE TB預(yù)測分析法School of Information an

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

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

40、t)int()+*E12Op34E預(yù)測分析法School of Information and Software Engineering75Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#在輸入串在輸入串后后加上加上# #做標(biāo)記做標(biāo)記 表示輸入串已經(jīng)結(jié)束表示輸入串已經(jīng)結(jié)束第一個(gè)符號是開始符號第一個(gè)符號是開始符號 檢查分析表檢查分析表 確定推導(dǎo)的產(chǎn)生式確定推導(dǎo)的產(chǎn)生式這一步為這一步為預(yù)測預(yù)測預(yù)測分析法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對于所猜測的句型對于所猜測的句型 第一個(gè)符號是第一個(gè)符號是終結(jié)符終結(jié)符將將其其與輸入串與輸入串第一個(gè)符號第一個(gè)符號 進(jìn)行匹配進(jìn)行匹配句型句型左邊左邊的符號與的符號與 輸入串輸入串左邊左邊的符號匹配的符號匹配句型句型逆序逆序壓入棧壓入棧預(yù)測分析法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對于所猜測的句型對于所猜測的句型 第一個(gè)符號是第一個(gè)符號是終結(jié)符終結(jié)符將將其其與輸入串與輸入串第一個(gè)符號第一個(gè)符號 進(jìn)行匹配進(jìn)行匹配句型句型左邊左邊的符號與的符號與 輸入串輸入串左邊左邊的符號匹配的符號匹配句型句型逆序逆序壓入棧壓入棧預(yù)測分析法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)# )#)# )#)# #預(yù)測分析法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)# )#)# )#)# #預(yù)測分析法錯(cuò)誤處理一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#預(yù)測分析法錯(cuò)

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)#預(yù)測分析法總結(jié)School of Information and Software Engineering82Zhou, Erqiang組成組成 一個(gè)下推棧一個(gè)下推棧 一個(gè)分析表一個(gè)分析表分析過程初始狀

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

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

49、棧，將出棧，將串串逆序逆序壓入棧中壓入棧中 若若Mx，a中為出錯(cuò)標(biāo)志中為出錯(cuò)標(biāo)志 則調(diào)用出錯(cuò)處理程序則調(diào)用出錯(cuò)處理程序error( )預(yù)測分析法總結(jié)School of Information and Software Engineering86Zhou, Erqiang預(yù)測分析法的關(guān)鍵是預(yù)測分析法的關(guān)鍵是分析表分析表 如何構(gòu)造分析表？如何構(gòu)造分析表？ 手動構(gòu)造手動構(gòu)造 算法構(gòu)造算法構(gòu)造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預(yù)測分析表的構(gòu)造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