1、1北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日S.PO.P語義分析、生成中間代碼語義分析、生成中間代碼生成目標(biāo)程序生成目標(biāo)程序代碼優(yōu)化代碼優(yōu)化語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理2北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日第第6 6章符號表管理和錯誤處理章符號表管理和錯誤處理1.1. 明確符號表的作用、內(nèi)容、組織明確符號表的作用、內(nèi)容、組織2.2. 明確錯誤處理的兩種方法：錯誤校正和局部化處理明確錯誤處理的兩種方法：錯誤校正和局部化處理教學(xué)目標(biāo)教學(xué)目標(biāo)3北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日

2、 6.1 6.1 符號表管理符號表管理 6.2 6.2 錯誤處理錯誤處理 6.3 PL/06.3 PL/0編譯程序的錯誤處理編譯程序的錯誤處理教學(xué)內(nèi)容教學(xué)內(nèi)容4北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日編譯程序中使用最多的數(shù)據(jù)結(jié)構(gòu)是表編譯程序中使用最多的數(shù)據(jù)結(jié)構(gòu)是表源程序中的各種信息，以便查詢或修改源程序中的各種信息，以便查詢或修改, ,在這些表中，尤以在這些表中，尤以符號表符號表最為重要最為重要生存期最長生存期最長使用最為頻繁使用最為頻繁 6.16.1符號表管理符號表管理5北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日6.1.1 符號表的作用和內(nèi)容符號表的作用

3、和內(nèi)容 作用：作用：（1）收集符號的各種信息）收集符號的各種信息 （2）語義檢查的依據(jù)）語義檢查的依據(jù) （3）目標(biāo)代碼生成階段地址分配的依據(jù)）目標(biāo)代碼生成階段地址分配的依據(jù) 內(nèi)容：內(nèi)容：名字欄信息欄名字欄信息欄 6北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日6.1.2 符號表的組織符號表的組織 操作：操作：（1）向表中填入一個新標(biāo)識符。）向表中填入一個新標(biāo)識符。（2）對于給定一個標(biāo)識符：）對于給定一個標(biāo)識符： 查找是否在表中；查找是否在表中； 訪問它在表中的相關(guān)信息；訪問它在表中的相關(guān)信息； 在表中填寫或更新它的某些信息。在表中填寫或更新它的某些信息。（3）更新或刪除一個或一組

4、無用的項(xiàng)。）更新或刪除一個或一組無用的項(xiàng)。7北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日6.1.2 符號表的組織符號表的組織 符號表的總體組織：符號表的總體組織：（1）多張）多張（2） 一張一張 （3）前兩種的折中）前兩種的折中符號表項(xiàng)的組織：符號表項(xiàng)的組織：（1）線性組織）線性組織（2）排序組織）排序組織 （3）散列組織）散列組織:效率高，為多數(shù)編譯程序采用效率高，為多數(shù)編譯程序采用8北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日Hash表的基本思想是：表的基本思想是：p為符號表設(shè)置一個足夠大的空間為符號表設(shè)置一個足夠大的空間Mp為符號構(gòu)造一個散列函數(shù)為符號構(gòu)造

5、一個散列函數(shù)Hash(Ki)，使得，使得0 Hash(Ki) M-1,i=1，2，np這樣查找這樣查找Ki時，時，Hash(Ki)就決定了就決定了Ki在符號表中在符號表中的位置的位置 9北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日構(gòu)造構(gòu)造Hash函數(shù)的方法：函數(shù)的方法：p將標(biāo)識符中的每個字符轉(zhuǎn)換為一個非負(fù)整數(shù)將標(biāo)識符中的每個字符轉(zhuǎn)換為一個非負(fù)整數(shù)p將得到的各個整數(shù)組合成一個整數(shù)（可以將第一將得到的各個整數(shù)組合成一個整數(shù)（可以將第一個、中間的和最后一個字符值加在一起，也可以將個、中間的和最后一個字符值加在一起，也可以將所有字符的值加起來）所有字符的值加起來）p將結(jié)果數(shù)調(diào)整到將結(jié)果

6、數(shù)調(diào)整到0M-1范圍內(nèi)，可以利用取模的范圍內(nèi)，可以利用取模的方法，方法，Ki%M（M為素?cái)?shù)）為素?cái)?shù)）10北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日解決地址沖突的方法：解決地址沖突的方法：由于用戶定義標(biāo)識符的隨機(jī)性，由于用戶定義標(biāo)識符的隨機(jī)性，Hash函數(shù)值在函數(shù)值在0M-1范圍內(nèi)范圍內(nèi)不一定唯一不一定唯一若兩個標(biāo)識符具有相同的函數(shù)值，則可用開放地址法或鏈地若兩個標(biāo)識符具有相同的函數(shù)值，則可用開放地址法或鏈地址法解決沖突，有關(guān)內(nèi)容可以參考址法解決沖突，有關(guān)內(nèi)容可以參考數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的教材。的教材。11北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日詞法詞法錯誤錯誤

7、語法語法錯誤錯誤語義語義錯誤錯誤違反了語言的環(huán)境限制違反了語言的環(huán)境限制數(shù)組維數(shù)太大數(shù)組維數(shù)太大循環(huán)嵌套層數(shù)太多循環(huán)嵌套層數(shù)太多6.26.2錯誤處理錯誤處理12北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日詞法錯誤、語法錯誤和語義錯誤詞法錯誤：不合法單詞詞法錯誤：不合法單詞例：mian( ) int 3sum; 語法錯誤：語法錯誤：源程序在語法上不符合文法源程序在語法上不符合文法例：例：Ax , y =B+*C13北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日超越系統(tǒng)限制：超越系統(tǒng)限制：(計(jì)算機(jī)系統(tǒng)和編譯系統(tǒng)計(jì)算機(jī)系統(tǒng)和編譯系統(tǒng))1. 數(shù)據(jù)溢出錯誤，常數(shù)太大，計(jì)算結(jié)

8、果溢出。數(shù)據(jù)溢出錯誤，常數(shù)太大，計(jì)算結(jié)果溢出。2. 符號表、靜態(tài)存儲分配數(shù)據(jù)區(qū)溢出。符號表、靜態(tài)存儲分配數(shù)據(jù)區(qū)溢出。3. 動態(tài)存儲分配數(shù)據(jù)區(qū)溢出。動態(tài)存儲分配數(shù)據(jù)區(qū)溢出。語義規(guī)則語義規(guī)則1. 標(biāo)識符先說明后引用標(biāo)識符先說明后引用2. 標(biāo)識符引用要符合作用域規(guī)定標(biāo)識符引用要符合作用域規(guī)定3. 過程調(diào)用時實(shí)參與形參類型一致過程調(diào)用時實(shí)參與形參類型一致4. 參與運(yùn)算的操作數(shù)類型一致參與運(yùn)算的操作數(shù)類型一致5. 下標(biāo)變量的下標(biāo)不能越界下標(biāo)變量的下標(biāo)不能越界語義錯誤主要包括：語義錯誤主要包括：程序不符合語義規(guī)則程序不符合語義規(guī)則或或 超越具體計(jì)算機(jī)系統(tǒng)的限制超越具體計(jì)算機(jī)系統(tǒng)的限制14北京林業(yè)大學(xué)信息學(xué)

9、院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日錯誤處理方法有兩種：錯誤處理方法有兩種：錯誤校正法：錯誤校正法： 根據(jù)文法進(jìn)行錯誤改正根據(jù)文法進(jìn)行錯誤改正錯誤局部化法：錯誤局部化法： 把錯誤的影響限制在一個局部的范圍，避免把錯誤的影響限制在一個局部的范圍，避免錯誤擴(kuò)散和影響程序其他部分的分析錯誤擴(kuò)散和影響程序其他部分的分析15北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日錯誤局部化法錯誤局部化法詞法分析：詞法分析：發(fā)現(xiàn)不合法字符，顯示錯誤，并跳發(fā)現(xiàn)不合法字符，顯示錯誤，并跳 過該過該標(biāo)識符標(biāo)識符(單詞單詞)繼續(xù)往下分析。繼續(xù)往下分析。語法語義分析：語法語義分析：跳過所在的語法成分跳過所

10、在的語法成分(短語或語短語或語 句句)，一般是，一般是跳到語句右界符跳到語句右界符， 然后從新語句繼續(xù)往下分析。然后從新語句繼續(xù)往下分析。16北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日錯誤局部化處理的實(shí)現(xiàn)（遞歸下降分析法）錯誤局部化處理的實(shí)現(xiàn)（遞歸下降分析法）err: 全局變量，存放錯誤信息。全局變量，存放錯誤信息。用遞歸下降分析時，如果發(fā)現(xiàn)錯誤，便將有關(guān)用遞歸下降分析時，如果發(fā)現(xiàn)錯誤，便將有關(guān)錯誤信息（錯誤信息（字符串或者編號字符串或者編號）送）送err，然后轉(zhuǎn)錯，然后轉(zhuǎn)錯誤處理程序；誤處理程序； 出錯程序先打印或顯示出錯位置以及出錯信息，出錯程序先打印或顯示出錯位置以及出

11、錯信息，然后跳出一段源程序然后跳出一段源程序,直到跳到語句的右界符或直到跳到語句的右界符或正在分析的語法成分的合法后繼符號為止正在分析的語法成分的合法后繼符號為止,然后然后再往下分析。再往下分析。17北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日if_ statement( ) getsym( ); /*讀下個單詞符號讀下個單詞符號*/ C( ) ; /*表達(dá)式處理程序表達(dá)式處理程序*/ if not sym=“then” err :=“缺缺then” ; error( ); /*出錯處理程序出錯處理程序*/ else getsym( ); statement( ); if sy

12、m=“else” getsym( ); statement( ); if then else;error( ) printf(linecnt, err); do getsym( ); while(sym!=“;” or sym!=“end” ) 發(fā)現(xiàn)錯誤立即跳到語句結(jié)尾發(fā)現(xiàn)錯誤立即跳到語句結(jié)尾處處(語句右界符語句右界符 ; 或或end),這這樣處理較粗糙樣處理較粗糙,將跳過太多將跳過太多18北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日(3) 提高錯誤局部化程度的方法提高錯誤局部化程度的方法設(shè)設(shè) S1: 合法后繼符號集合法后繼符號集 (某語法成分的后繼符號某語法成分的后繼符號)

13、S2: 停止符號集停止符號集 (跳讀必須停止的符號集跳讀必須停止的符號集)error(S1,S2 ) printf(linecnt, err); do getsym( ); while(sym not in S1 or not in S2 ) 若若有錯有錯,則可跳到則可跳到then若若statement有錯有錯,則可跳到則可跳到elseif then else;19北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日6.36.3PL/0PL/0編譯程序的錯誤處理編譯程序的錯誤處理錯誤局部化處理遵循以下兩條原則。錯誤局部化處理遵循以下兩條原則。（1）鎮(zhèn)定原則）鎮(zhèn)定原則（2）關(guān)鍵字原則）關(guān)

14、鍵字原則在在進(jìn)入進(jìn)入某個語法單位時，調(diào)用某個語法單位時，調(diào)用test檢查當(dāng)前符號是否屬檢查當(dāng)前符號是否屬于該語法單位的首符號集。若不屬于，則濾去首符號和于該語法單位的首符號集。若不屬于，則濾去首符號和后繼符號集合外的所有符號。后繼符號集合外的所有符號。在語法單位分析在語法單位分析結(jié)束結(jié)束時，調(diào)用時，調(diào)用test，檢查當(dāng)前符號是否，檢查當(dāng)前符號是否屬于調(diào)用該語法單位時應(yīng)有的后繼符號集合。若不屬于，屬于調(diào)用該語法單位時應(yīng)有的后繼符號集合。若不屬于，則濾去后繼符號和首符號集合外的所有符號。則濾去后繼符號和首符號集合外的所有符號。 20北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日tes

15、ttest過程有三個參數(shù)：過程有三個參數(shù)：s1s1、s2s2、n nS1S1：可允許的下一個符號集合，如果當(dāng)前符：可允許的下一個符號集合，如果當(dāng)前符號不在此集合中，當(dāng)即得到一個錯誤號；號不在此集合中，當(dāng)即得到一個錯誤號；S2S2：另加的停止符號集合，在某上出錯狀態(tài)：另加的停止符號集合，在某上出錯狀態(tài)下，可恢復(fù)語法分析繼續(xù)正常工作的補(bǔ)充單下，可恢復(fù)語法分析繼續(xù)正常工作的補(bǔ)充單詞符號集合；詞符號集合；整數(shù)整數(shù)n n，表示有關(guān)錯誤的診斷號。，表示有關(guān)錯誤的診斷號。21北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日 在進(jìn)入某個語法單位時，調(diào)用在進(jìn)入某個語法單位時，調(diào)用TESTTEST濾去

16、濾去開始符號前的所有符號。開始符號前的所有符號。 在語法單位分析結(jié)束時，調(diào)用在語法單位分析結(jié)束時，調(diào)用TESTTEST濾去濾去當(dāng)前符號到后繼符號之間的所有符號。當(dāng)前符號到后繼符號之間的所有符號。 TEST TEST TEST TEST22北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日非終結(jié)符名非終結(jié)符名開始符號集合開始符號集合后繼符號集合后繼符號集合分程序分程序const var procedureconst var procedureident if call beginident if call beginwhile read writewhile read write. ;

17、. ;語句語句ident call beginident call beginif while read writeif while read write. ; end. ; end條件條件odd + - (odd + - (ident numberident numberThen doThen do表達(dá)式表達(dá)式+ - (+ - (ident numberident number. ; ) rop. ; ) ropend then doend then do項(xiàng)項(xiàng)ident number (ident number (. ; ) rop + -. ; ) rop + -end then doen

18、d then do因子因子ident number (ident number (. ; ) rop + -. ; ) rop + -* / end then do* / end then do開始符號集合與后繼符號集合開始符號集合與后繼符號集合23北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日TEST測試過程流程圖測試過程流程圖24北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日void factor(fsys)void factor(fsys)struct node struct node * *fsys;fsys;void expression();void e

19、xpression(); int m=0,n=0,i; int m=0,n=0,i; char char * *tempset =rpsren,NULL;tempset =rpsren,NULL; struct node struct node * *temp;temp; temp=(struct node temp=(struct node* *)malloc(sizeof(struct node);)malloc(sizeof(struct node); while(tempsetm!=NULL) while(tempsetm!=NULL) temp-pan+=tempsetm+; tem

20、p-pan+=tempsetm+; temp-pan=NULL; temp-pan=NULL; test(facbegsys,fsys,24); test(facbegsys,fsys,24); / /* * 24:24:表達(dá)式的開始符不能是此符號表達(dá)式的開始符不能是此符號* */ / while(in(sym,facbegsys)=1) while(in(sym,facbegsys)=1) if(strcmp(sym,ident)=0) if(strcmp(sym,ident)=0) i=position(id); i=position(id); if(i=0) error(11); if(i=0) error(11); else switch(tablei.kind) else switch(tablei.kind) 因子的處理過程因子的處理過程25北京林業(yè)大學(xué)信息學(xué)院北京林業(yè)大學(xué)信息學(xué)院2021年12月1日 case constant: gen(lit,0,tablei.val); break;c