1、第第8 8章章 符號表與錯誤處理符號表與錯誤處理 第第8章章 符號表與錯誤處理符號表與錯誤處理 8.1 符號表符號表 8.2 錯誤處理錯誤處理 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.1 符符 號號 表表 8.1.1 符號表的作用 在編譯程序工作的過程中，需要不斷收集、記錄、查證和使用源程序中的一些語法符號(簡稱為符號)的類型和特征等相關信息。為方便起見，一般的做法是讓編譯程序在其工作過程中建立并保存一批表格，如常數(shù)表、變量名表、數(shù)組內(nèi)情向量表、過程或子程序名表及標號表等，將它們統(tǒng)稱為符號表或名字表。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 符號表中的每一項包括兩個部分

2、：一部分填入名字(標識符)；另一部分是與此名字有關的信息，這些信息將全面地反映各個語法符號的屬性以及它們在編譯過程中的特征，諸如名字的種屬(常數(shù)、變量、數(shù)組、標號等)、名字的類型(整型、實型、邏輯型、字符型等)、特征(當前是定義性出現(xiàn)還是使用性出現(xiàn)等)、給此名字分配的存儲單元地址及與此名語義有關的其它信息等。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 根據(jù)編譯程序工作階段的不同劃分，名字表中的各種信息將在編譯程序工作過程中的適當時候填入。對于在詞法分析階段就建立符號表的編譯程序，當掃描源程序識別出一個單詞(名字)時，就以此名字查找符號表；若表中無此名的登記項，就將此名字填入符號表中；至于

3、與此名相關的其它信息，可視工作方便分別在語法分析、語義分析及中間代碼生成等階段陸續(xù)填入。在語義分析時，符號表中的信息可以用于語義檢查；在代碼優(yōu)化時，編譯程序則利用符號表提供的信息選出恰當?shù)拇a進行優(yōu)化； 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 而目標代碼生成時，編譯程序?qū)⒁罁?jù)符號表中的符號名來分配目標地址。幾乎在編譯程序工作的全過程中，都需要對符號表進行頻繁地訪問(查表或填表)，其耗費的時間在整個編譯過程中占有很大的比例。因此，合理地組織符號表并相應選擇好的查、填表方法是提高編譯程序工作效率的有效辦法。 對于編譯程序所用的符號表來說，它所涉及的基本操作大致可以歸納為五類：第第8 8章

4、章 符號表與錯誤處理符號表與錯誤處理 (1) 判斷一個給定的名字是否在表中；(2) 在表中填入新的名字；(3) 對給定的名字訪問它在表中的有關信息；(4) 對給定的名字填入或更新它在表中的某些信息；(5) 從表中刪去一個或一組無用的項。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.1.2 符號表的組織 由于處理對象的作用和作用域可以有多種，所以符號表也有多種組織方式。按照處理對象的特點，符號表的組織方式一般可分為直接方式和間接方式。 直接方式是指在符號表中直接填入源程序中定義的標識符及相關信息(如圖8-1所示)。在圖81所示的符號表中，Name(名字)欄的長度是固定的，這種欄目長度固定

5、的表格易于組織、填寫或查找，因而是最簡單的一種符號表組織方式， 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-1 直接組織方式的符號表NameInformatronWanchexue第第8 8章章 符號表與錯誤處理符號表與錯誤處理 它適合于規(guī)定標識符長度的程序語言。 然而，并不是所有高級語言都規(guī)定標識符的長度，如果對標識符長度不加限制，則上述定長方式必須按最大長度來定長，這顯然浪費存儲空間。因此，對不定長標識符一般采用間接方式來組織符號表。 間接方式是指單獨設置一個字符串數(shù)組來存放所有的標識符，并在符號表的名字欄中設置兩項內(nèi)容：一是指針，用來指向標識符在數(shù)組中的起始位置；二是一整數(shù)值

6、，用來表示該標識符的長度。圖82給出了符號表的間接組織方式。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-2 間接組織方式的符號表 STU D EN TG R A N D A G ENameInformatron753第第8 8章章 符號表與錯誤處理符號表與錯誤處理 另一種組織方式是按標識符的種屬，如簡單變量、數(shù)組、過程等分別建立不同的符號表，如簡單變量名表、數(shù)組名表、過程名表等。例如，下面的函數(shù)： int f(int a,int b) int c; if(ab) c=1; else c=0; return c; 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-3 按標識符種

7、屬組織的各種符號表(a) 簡單變量名表；(b) 常數(shù)表；(c) 函數(shù)入口名表NameabcInformation整型，變量，形參整型，變量，形參整型，變量(a)value10(b)NamefInformation二目子程序，入口地址(c)第第8 8章章 符號表與錯誤處理符號表與錯誤處理 根據(jù)符號表名字欄的組織特點，符號表信息欄的組織方式也分為兩類：固定信息內(nèi)容和僅記錄信息存放地址。 如果名字欄中的標識符按種屬分類，則因同類標識符其基本特征一致，故可將這些信息一一記錄在信息欄中。 如果符號表的名字不分種屬，則由于不同種屬的標識符其特征不一致，也即它們所需存儲的信息不一致，因而不容易確定一個固定長

8、度的空間來統(tǒng)一安排。這時，可在符號表外另設一組存儲空間，并在符號表信息欄中放一指針來指向這個存儲空間始址。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 例如，對數(shù)組標識符需要存儲有關數(shù)組維數(shù)，每維上、下界值，數(shù)組類型及數(shù)組存放的起始地址等信息。如果將信息與名字一起全部放在符號表中，則因維數(shù)不同而使記錄該信息的空間大小不易確定，因此，通常給它們另外安排一個內(nèi)情向量表來記錄數(shù)組的全部信息，同時在符號表的信息欄設置一指針指向內(nèi)情向量的入口地址(見圖8-4)。此外，對像函數(shù)名、過程名等含有較多信息且不容易規(guī)范信息長度的名字都可以采取這種辦法。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-

9、4 記錄數(shù)組內(nèi)情向量的符號表NameaInformation數(shù)組符號表維數(shù)首地址下界i1上界u1內(nèi)情向量表第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.1.3 分程序結構語言的符號表建立 所謂分程序結構的語言，是指用這種語言編寫的分程序中可以再包含嵌套的分程序，并且可以定義屬于它自己的一組局部變量。由于分程序的嵌套導致名字作用域的嵌套，故有時也將允許名字作用域嵌套的語言稱為具有分程序結構的語言。典型的分程序結構語言是PASCAL；雖然通常不把C語言視為嵌套分程序結構的語言，但在它的函數(shù)定義中， 函數(shù)體可以是一個嵌套的分程序，因而其中所涉及的各個局部變量的作用域也具有嵌套特征。第第8 8

10、章章 符號表與錯誤處理符號表與錯誤處理 對于嵌套的作用域，同名的變量在不同層次出現(xiàn)可能有不同的類型。因此，為了使編譯程序在語義及其它有關處理上不致于發(fā)生混亂，可采用分層建立和處理符號表的方式。 在PASCAL程序中，標識符的作用域是包含說明(定義)該標識符的一個最小分程序；也即PASCAL程序中的標識符(或標號)的作用域總是與說明(定義)這些標識符的分程序的層次相關聯(lián)。為了表征一個PASCAL程序中各個分程序的嵌套層次關系，可將這些分程序按其開頭符號在源程序中出現(xiàn)的先后順序進行編號。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 這樣，在從左至右掃描源程序時就可以按分程序在源程序中的這種自

11、然順序(靜態(tài)層次)，對出現(xiàn)在各個分程序中的標識符進行處理，具體方法如下： (1) 當在一個分程序首部某說明中掃描到一個標識符時，就以此標識符查找相應于本層分程序的符號表，如果符號表中已有此名字的登記項，則表明此標識符已被重復說明(定義)，應按語法錯誤進行處理；否則，應在符號表中新登記一項，并將此標識符及有關信息(種屬、類型、所分配的內(nèi)存單元地址等)填入。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (2) 當在一分程序的語句中掃描到一個標識符時，首先在該層分程序的符號表中查找此標識符；若查不到，則繼續(xù)在其外層分程序的符號表中查找。如此下去，一旦在某一外層分程序的符號表中找到此標識符，則從表

12、中取出有關的信息并作相應的處理；如果查遍所有外層分程序的符號表都無法找到此標識符，則表明程序中使用了一個未經(jīng)說明(定義)的標識符，此時可按語法錯誤予以處理。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 為了實現(xiàn)上述查、填表功能，可以按如下方式組織符號表： (1) 分層組織符號表的登記項，使各分程序的符號表登記項連續(xù)地排列在一起，而不許為其內(nèi)層分程序的符號表登記項所分割。 (2) 建立一個“分程序表”，用來記錄各層分程序符號表的有關信息。分程序表中的各登記項是在自左至右掃描源程序中按分程序出現(xiàn)的自然順序依次填入的，且對每一分程序填寫一個登記項。因此，分程序表各登記項的序號也就隱含地表征了各分

13、程序的編號。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 分程序表中的每一登記項由三個字段組成：OUTERN字段用來指明該分程序的直接外層分程序的編號；COUNT字段用來記錄該分程序符號表登記項的個數(shù)；POINTER字段是一個指示器，它指向該分程序符號表的起始位置。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 下面，我們給出建造滿足上述要求符號表的算法。為了使各分程序的符號表登記項連續(xù)地排列在一起，并結合在掃描具有嵌套分程序結構的源程序時總是按先進后出的順序來掃描其中各個分程序的特點，可設置一個臨時工作棧，每當進入一層分程序時，就在這個棧的頂部預造該分程序的符號表，而當遇到該層分程序

14、的結束符END時(此時該分程序的全部登記項都出現(xiàn)在棧的頂部)，再將該分程序的全部登記項移至正式符號表中。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 建立符號表的算法描述如下： (1) 給各指示器賦初值。 (2) 自左至右掃描源程序： 每當進入分程序的首符號或過程(函數(shù))時，就在分程序表中登記一項，并使之成為當前的分程序。 當掃描到當前分程序中一個定義性出現(xiàn)的標識符時，將該名字及其有關信息填入臨時工作棧的頂部(當然，在填入前應在臨時工作棧本層分程序已登入的項中檢查是否已有重名問題)；然后在分程序表中，把當前分程序相應登記項的COUNT值加1且使POINTER指向新的棧頂。 第第8 8章章

15、 符號表與錯誤處理符號表與錯誤處理 當掃描到分程序的結束符END時，將記入臨時工作棧的本層分程序全部登記項移至正式的符號表中，且修改POINTER值使其指向本層分程序全部名字登記項在符號表中的起始位置。此外，在退出此層分程序時，還應使它的直接外層分程序成為當前的分程序。 (3) 重復上面的步驟(2)，直至掃描完整個源程序為止。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 對一遍掃描的編譯程序而言，在它工作過程中，當遇到某分程序的結束符END時，該分程序中的全部標識符已經(jīng)完成它們的使命。因此，只需將它們從棧中逐出，也即將棧頂部指示器回調(diào)至剛進入本分程序時的情況即可，而不再需要把這些登記項上移

16、。事實上，如上所述的工作棧就完全可作為編譯程序的符號表來使用，我們將這種符號表稱為棧式符號表。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 例8.1 一示意性源程序如下：PROGRAM PP (input,output); COUNT norw=13; VAR ll,kk:integer; word:ARRAY1.norw OF char;PROCEDURE getsym; VAR i,j: integer; PROCEDURE getch; BEGIN END; getch BEGIN第第8 8章章 符號表與錯誤處理符號表與錯誤處理 j:=1; kk:=i+j END; getsymBE

17、GIN END. pp第第8 8章章 符號表與錯誤處理符號表與錯誤處理 當編譯程序掃描上述源程序時，生成棧式符號表，試就此符號表回答以下問題： (1) 畫出“掃描到getsym過程體之前”的棧符號表； (2) 畫出“掃描完getsym過程說明(即掃描完END; getsym)”時的棧符號表。 解答 假定所有的名字在數(shù)據(jù)區(qū)中都只需要一個單元。 (1)“掃描到getsym過程體之前”的棧符號表如圖8-5所示。 (2)“掃描完getsym過程說明”時的棧符號表如圖8-6所示。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-5 “掃描到getsym過程體之前”的棧符號表 getchjigets

18、ymwordkkllnorw標識符名11100000所屬層次214321相對地址其它屬性87654321POINTER0OUTERN24COUNTTOP棧符號表分程序表第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-6 “掃描完getsym過程說明”的棧符號表 getsymwordkkllnorw標識符名00000所屬層次4321相對地址其它屬性54321POINTEROUTERN4COUNTTOP棧符號表分程序表第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.1.4 非分程序結構語言的符號表建立 典型的非分程序結構語言就是FORTRAN語言。FORTRAN語言是一種塊結構的程序

19、設計語言，一個FORTRAN可執(zhí)行程序由一個或若干個相對獨立的程序段組成，其中有且僅有一個主程序段，其余的則是子程序段。程序段之間的數(shù)據(jù)傳送主要是通過過程調(diào)用時的形參與實參的結合，或訪問公共區(qū)中的元素來進行的。對于一個FORTRAN程序來說，第第8 8章章 符號表與錯誤處理符號表與錯誤處理 除了程序段名和公共區(qū)名的作用域是整個程序之外，其余的變量名、數(shù)組名、語句函數(shù)名以及標號等，都分別是定義它們的那個程序段中的局部量。此外，由于語句函數(shù)定義句中的形參與程序段中的其它變量名毫不相干，因此，它們的作用域就是該語句函數(shù)定義句本身。 根據(jù)FORTRAN程序中各類名字作用域的特點，原則上可把程序中每一程

20、序段均視為一個可獨立進行編譯的程序單元，即對各程序段分別進行編譯并產(chǎn)生相應的目標代碼，然后再連接裝配成一個完整的目標程序。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 這樣，當一個程序段編譯完成后，該程序段的全部局部名登記項即完成了使命，可以將它們從符號表中刪除。至于全局名登記項，因為它們還可能為其它程序段所引用，故需繼續(xù)保留。因此，對于FORTRAN編譯程序而言，可分別建立一張全局符號表和一張局部符號表，前者供編譯各程序使用，后者則只用來登記當前正編譯的程序段中的局部符號名。一旦將該程序段編譯完成，就可將局部符號表空白區(qū)首地址指針再調(diào)回到開始位置，以便騰出空間供下一個要編譯的程序段建立

21、局部符號表使用。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 在考慮全局優(yōu)化的多遍掃描編譯系統(tǒng)中，由于一般并不是在編譯當前程序段時就產(chǎn)生該程序段的目標代碼，而是先生成各程序段的相應中間代碼，待進行優(yōu)化處理之后再產(chǎn)生目標代碼。因此，當一個程序段被處理完之后，不能立即將相應的局部名表撤消，而應將它們暫存起來。在生成中間代碼時，對于各程序段中的局部變量名，如果都用該名字的名表登記項序號去代替，那么局部名表的名字欄就用不著再繼續(xù)保留，因為只要知道了登記項的序號就同樣可以查到該登記項的有關信息。然而，對于同一個登記項序號而言，所在的局部名表的不同將代表完全不同的登記項，這一點也必須注意。第第8 8章

22、章 符號表與錯誤處理符號表與錯誤處理 8.1.5 常用符號表結構 由于在整個編譯過程中需要不斷地訪問符號表，因而如何構造符號表以及如何查填符號表就成為編譯程序設計的重要問題之一。除了上述我們介紹的用于嵌套結構程序語言的棧式符號表外，還有其它幾種常用符號表結構。 1線性符號表 符號表中最簡單且最容易實現(xiàn)的數(shù)據(jù)結構是線性表，它是按程序中標識符出現(xiàn)的先后次序建立的符號表，編譯程序不做任何整理次序的工作。線性符號表如圖87所示。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 在掃描源程序時，根據(jù)各標識符在程序說明部分出現(xiàn)的先后順序?qū)俗R符及其有關信息填入符號表中。當編譯過程中需要查找符號表中的某個標

23、識符時，只能采用線性查找方法，即從符號表的第一項開始直到表尾一項一項地順序查找。這種查找方法的缺點是效率較低。 2有序符號表 為了提高查表速度，可以在造表的同時把各標識符按照一定的順序進行排列。顯然，這樣的符號表是有序的，對圖87所示的線性符號表排序后的情況如圖88所示。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖87 線性符號表 NameInformationsumabsave序號123be4第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖88 有序符號表NameInformationabsavesum序號123be4第第8 8章章 符號表與錯誤處理符號表與錯誤處理 對于有序符號

24、表，一般采用折半查找法進行查表，即首先從表的中項開始比較，如果未找到則將查找范圍縮小一半，然后繼續(xù)查找，直到找到或查找失敗為止。使用這種折半查找法對一個含有N項的符號表來說，查找其中的一項最多只需做1+lbN次比較。雖然這種查找法的效率有所提高，但是對于一個邊填寫邊引用的動態(tài)查找符號表來說，每填進一項就引起表中內(nèi)容重新排序，這無疑會增加時間的開銷。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 圖8-9 二叉排序樹 ixrootjbta第第8 8章章 符號表與錯誤處理符號表與錯誤處理 對于動態(tài)查找的符號表，可以采用二叉樹結構來組織有序符號表。對二叉樹中的任一結點P來說，它的左子樹上的任何結點

25、都大于結點P的值，而右子樹上任何結點都小于結點P的值(見圖89)，這樣一棵二叉樹實際上是二叉排序樹。每當向符號表中填入一項時，總是將其作為二叉排序樹的葉結點插入到合適位置。查找的過程也是這樣，第第8 8章章 符號表與錯誤處理符號表與錯誤處理 首先將給定值K與二叉排序樹根結點值比較，若相等則查找成功；若不等，則當根結點值小于K時到根的左子樹去繼續(xù)查找，否則到根的右子樹去繼續(xù)查找。在隨機情況下，二叉排序樹的平均查找長度為1+4lbN。較之折半查找法，雖然二叉排序樹的查找速度略有降低，但它大大減少了生成有序符號表的時間，是一種較好的有序符號表結構。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 3

26、散列符號表 散列符號表是大多數(shù)編譯程序采用的一種符號表。符號表采用散列技術，相對來講具有較高的運行效率，特別適用于邊填寫邊引用的動態(tài)查找符號表。 散列符號表又稱哈希符號表，其關鍵在于引進了一種函數(shù)哈希函數(shù)，并將程序中出現(xiàn)的標識符通過哈希函數(shù)進行映射，得到的函數(shù)值作為該標識符在符號表中的位置。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 哈希函數(shù)(Hash)一般具有如下性質(zhì)： (1) 函數(shù)值只依賴于對應的標識符； (2) 函數(shù)的計算簡單且高效； (3) 函數(shù)值能比較均勻地分布在一定范圍內(nèi)。 構造散列函數(shù)的方法很多，如直接定址法、數(shù)字分析法、平方取中法和除留余數(shù)法等。散列表的表長通常是一個定值

27、N，因此散列函數(shù)應該將標識符的編碼散列成0N?1之間的某一個值，以便每一個標識符都能散列到這樣的符號表中。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 由于用戶使用的標識符是隨機的，所以很難找到一種散列函數(shù)使得標識符與函數(shù)值一一對應；兩個或兩個以上的不同標識符散列到同一表項地址的情況稱為散列沖突。由于沖突是不可避免的，因此，解決沖突問題也是構造散列符號表要考慮的重要問題。關于沖突的處理，詳見數(shù)據(jù)結構有關內(nèi)容。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.1.6 符號表的內(nèi)容 對于常見的程序設計語言而言，其變量名及過程名登記項的信息欄通常包含如下信息： (1) 變量名： 種屬(簡單變

28、量、數(shù)組、記錄結構等)； 類型(整型、實型、雙精度實型、邏輯型、字符串型、標號或指針等)；第第8 8章章 符號表與錯誤處理符號表與錯誤處理 所分配的數(shù)據(jù)區(qū)地址(一般為相對地址)； 若為數(shù)組，應填寫其內(nèi)情向量并給出內(nèi)情向量的首址； 若為記錄結構，則應把該登記項與其各分量(即域)按某種方式連接起來；第第8 8章章 符號表與錯誤處理符號表與錯誤處理 是否為形式參數(shù)，若是則應記錄其類型； 定義性出現(xiàn)或引用性出現(xiàn)標志(指標號)； 是否對該變量進行過賦值的標志，等等。 (2) 過程名： 是否為程序的外部過程； 若為函數(shù)，應指出它的類型； 是否處理過相應的過程或函數(shù)定義； 是否遞歸定義； 指出過程的形參，并

29、按形參排列的順序?qū)⑺鼈兊姆N屬、類型等信息與過程名相聯(lián)系，以便其后檢查實參在順序、種屬及類型上是否與形參一致。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.2 錯錯 誤誤 處處 理理 由于編譯程序處理的源程序總是或多或少地包含有錯誤，因而一個好的編譯程序應具有較強的查錯或改錯能力。所謂查錯，是指編譯程序在工作過程中能夠準確、及時地將源程序中的各種錯誤查找出來，并以簡明的形式報告錯誤的性質(zhì)及出錯位置。所謂改錯，就是當編譯程序發(fā)現(xiàn)源程序中的錯誤時，適當?shù)刈鲆恍┬扪a工作，使得編譯工作不至于因此而中止，以便能夠在一次編譯過程中盡可能多地發(fā)現(xiàn)源程序中的錯誤。 第第8 8章章 符號表與錯誤處理符號表

30、與錯誤處理 然而，更正所發(fā)現(xiàn)的錯誤并不是一件容易的事，許多編譯程序?qū)嶋H上并不做改正錯誤的工作，而只是對源程序中的錯誤進行適當?shù)奶幚聿⑻^錯誤所在的語法成分，如單詞、說明、表達式或語句等，然后繼續(xù)對源程序的后繼部分進行編譯。 源程序中的錯誤通常分為語法錯誤和語義錯誤兩類。所謂語法錯誤，是指編譯程序在詞法分析階段和語法分析階段所發(fā)現(xiàn)的錯誤，如關鍵字拼寫錯誤、語法成分不符合語法規(guī)則等等。一般來說，編譯程序查找此類錯誤比較容易，并且也能準確地確定出錯位置。至于語義錯誤， 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 則主要來源于對源程序中某些量的不正確使用，如使用了未經(jīng)說明的變量，某些變量被重復說

31、明或不符合有關作用域的規(guī)定，運算的操作數(shù)類型不相容、實參與形參在種屬或類型上不一致等等，都是典型的語義錯誤，這些錯誤也能被編譯程序查出。此外，由于編譯實現(xiàn)的技術原因，或為目標計算機的資源條件所限，在實現(xiàn)某一程序語言時，編譯系統(tǒng)對語言的使用又提出了進一步的限制，例如對各類變量數(shù)值范圍的限制，對數(shù)組維數(shù)、形參個數(shù)、循環(huán)嵌套層數(shù)的限制等。對于違反這些限制而出現(xiàn)的語義錯誤，多半要到目標程序運行時才能查出，但這時源程序已被翻譯成目標代碼程序，要確定源程序中的錯誤位置就比較困難。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 8.2.1 語法錯誤的校正 對源程序錯誤的處理通常有兩類不同方法：一類是對錯誤

32、進行適當?shù)男扪a，以便編譯工作能夠繼續(xù)下去；另一類是跳過有錯誤的那個語法成分，以便把錯誤限制在一個盡可能小的局部范圍內(nèi)，從而減少因某一錯誤而引起的一連串假錯。第二類方法又稱為錯誤的局部化法。 1單詞錯誤的校正 詞法分析的主要任務是把字符串形式的源程序轉(zhuǎn)換為一個單詞系列。由于每一類單詞都可以用某一正規(guī)式表示，因而在識別源程序中的單詞符號時，通常采用一種匹配最長子串的策略。如果在識別單詞的過程中發(fā)現(xiàn)當前余留的輸入字符串的任何前綴都不能和所有詞型相匹配， 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 則調(diào)用單詞出錯程序進行處理。然而，由于詞法分析階段不能收集到足夠的源程序信息，因此讓詞法分析程序擔

33、負校正單詞錯誤的工作是不恰當?shù)模聦嵣线€沒有一種適用于各種詞法錯誤的校正方法。最直接的做法是，每當發(fā)現(xiàn)一個詞法錯誤時，就跳過其后的字符直到出現(xiàn)下一個單詞為止。 單詞中的錯誤多數(shù)屬于字符拼寫錯誤，通常采用一種“最小海明距離法”來糾正單詞中的錯誤。當發(fā)現(xiàn)源程序中的一個單詞錯誤時，試圖將錯誤單詞的字符串修改成一個合法的單詞。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 我們以插入、刪除和改變字符個數(shù)最小為準則考慮下面幾種情況： (1) 若知道下一步是處理一個關鍵字，但當前掃描的余留輸入字符串的頭幾個字符卻無法構成一個關鍵字，此時可查關鍵字表并從中選出一個與此開頭若干字符最接近的關鍵字來替換。

34、(2) 如果源程序中某標識符有拼寫錯誤，則以此標識符查符號表，并用符號表中與之最接近的標識符取代它。 在多數(shù)編譯程序中不是采用“最小海明距離法”來校正錯誤，而是采用一種更為簡單、有效的方法。這種方法的依據(jù)是程序中所有錯誤多半屬于下面幾種情況之一：第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (1) 拼錯了一個字符； (2) 遺漏了一個字符； (3) 多寫了一個字符； (4) 相鄰兩字符顛倒了順序。 通過檢測這四種情況，編譯程序可查出源程序中大部分的拼寫錯誤。對這些錯誤進行簡單的檢測與校正的方法為： (1) 從符號表中選出一個子集，使此子集包含所有那些可能被拼錯的符號； (2) 檢查此子集中

35、的各個符號，看是否可按上述四種情況之一把它變?yōu)槟骋徽_的符號，然后用它去替換源程序中的錯誤符號。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 2自上而下分析中的錯誤校正 編譯過程中大部分查錯和改錯工作集中在語法分析階段。由于程序語言的語法通常是用上下文無關文法描述的，并且該語言可通過語法分析器得到準確的識別，因而源程序中的語法錯誤總會被語法分析程序自動查出。當分析器根據(jù)當前的狀態(tài)(分析棧的內(nèi)容以及現(xiàn)行輸入符號)判明不存在下一個合法的分析動作時，就查出了源程序中的一個語法錯誤。此時，編譯程序應準確地確定出錯位置并校正錯誤，然后對當前的狀態(tài)(格局)進行相應的修改，使語法工作得以繼續(xù)進行。上述過

36、程雖然可以實現(xiàn)，但卻不能保證錯誤校正總會獲得成功，而校正錯誤的方法則因語法分析方法的不同而異。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 首先討論自上而下分析中的錯誤校正問題。在語法分析過程的每一時刻，總可以把源程序輸入符號串a(chǎn)1 a2an劃分為如下形式： a1a2 an= w1aiw2 (8.1) 其中w1是已經(jīng)掃描和加工過的部分，ai為現(xiàn)行輸入符號，而w2則是輸入串的余留部分。假定編譯程序現(xiàn)在發(fā)現(xiàn)了源程序中的一個語法錯誤，這對自上而下分析來說，就意味著分析器目前已為輸入串建立了一棵部分語法樹，并且此部分語法樹已經(jīng)覆蓋了子串w1，但卻無法再擴大而覆蓋ai。此時，就必須確定如何修改源程序

37、來“更生”這個錯誤。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 施如下： (1) 刪去符號ai再進行分析。 (2) 在w1與ai之間插入一終結符號串，即把式(8.1)修改為 w1 a iw2 (8.2) 然后再從aiw2的首部開始分析。 (3) 在w1與ai之間插入終結符號串(見式(8.2)，但從ai開始分析。 (4) 從w1的尾部刪去若干個符號。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 以上各種修改措施既可單獨使用，也可聯(lián)合使用。但(3)、(4)兩種措施需對源程序已加工部分進行修改，從而可能更改相應語義信息，因此實現(xiàn)起來比較困難而較少采用。 假定在語法分析過程中，當掃描到輸入

38、符號ai時發(fā)現(xiàn)了一個語法錯誤(見式(8.1)，且已構造的部分語法樹不能進行擴展，則可執(zhí)行下面的算法對該語法錯誤進行校正： (1) 建立一個符號表L，它由所有未完成分支的各個未完成部分中的符號組成。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (2) 對于從出錯點開始的余留輸入串a(chǎn)iw2，刪去ai并考察w2 = ai+1 w3，看L中是否存在這樣的一個符號U且滿足U(ai+1。如果這樣的U不存在，則再刪去ai+1并繼續(xù)考察w3=ai+2w4，直到找到某個aj滿足U(aj為止。 (3) 根據(jù)(2)所得到的U確定它所在的那個未完成分支。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (4) 確

39、定一個符號串，使得若把插入到aj之前便能使分析繼續(xù)下去。為了確定這樣的，只需要考察(3)所找到的那個未完成分支以及其各子樹的未完成分支，并對它們都確定一個終結符號串以補齊相應的分支，最后再把這些終結符號串依次排列在一起就得到了所需的。 (5) 把插到aj之前并從的首部開始繼續(xù)分析過程。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 例8.2 已知文法GP： PA; Ai=E ET+T TF*F F(E) i 試用自上而下分析中的錯誤校正方法說明校正輸入串“i=i+)”的錯誤過程。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 解答 從建立語法樹的角度看，經(jīng)語法分析之后，我們總能得到一棵或

40、若干棵分支不完全的語法樹。對于輸入串“i=i+)”，經(jīng)過若干步語法分析后可得到如圖810所示的不完全語法樹。圖中，實線表示已完成的部分樹，虛線表示如何去完成那些名為P和E的分枝。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 iP；)T+TTEAF輸入串：i圖810 輸入串“i=i+)”的不完全語法樹 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 名為U的一個未完成分支對應下面的規(guī)則： UX1X2Xi-1XiXn 其中，X1X2Xi-1是該分支的已完成部分，而XiXi+1Xn是該分支的未完成部分。在圖8-10中，名為P的未完成分支對應于使用規(guī)則“PA;”，而“;”是該分支的未完成部分。名

41、為E的未完成分支對應于使用規(guī)則“ET+T”，為了完成此分支，我們需要一個T再跟上0個或若干個“+T”，從而知其未完成部分為T+T。分支中這些未完成部分在錯誤校正中起著重要作用，它告訴我們在源程序后面應該出現(xiàn)些什么。下面執(zhí)行語法錯誤校正算法來校正輸入串“i=i+)”中的錯誤。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (1) 建立一個符號表L，它由所有未完成分支的各未完成部分中的符號組成，由此得 L=; ,T,+。 (2) 對從出錯點開始的余留輸入串a(chǎn)iw2，刪去其首符號ai，考察w2=ai+1w3，看L中是否存在這樣的一個符號U，它滿足 U(ai+1；如果不存在則再刪去ai+1并繼續(xù)考察

42、w3=ai+2w4，直到找到某個aj滿足U(aj 為止。對輸入串“i=i+)”來說，出錯點從“)”開始，把“)”刪去(L中無此符號)后只剩下未完成的“;”，而L中恰有此符號，故所求的aj就是“;”。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (3) 根據(jù)(2)所得的U，確定它所在那個未完成分支，即使得“;”放入L中的未完成分支只能是“PA;”。 (4) 確定一個符號串，使得把插到aj之前就能使分析繼續(xù)下去。為了確定這樣的，只需考察(3)所找到的那個未完成分支以及其各子樹的未完成分支，并對它們都確定一個終結符號串以補齊相應的分支，最后再把這些終結符號串依次排列在一起就得到所需的。因此，由

43、(3)得知未完成的分支名為P，而它的子樹中有名為E的不完全分支，即必須插入一符號串去補全“ET+T”這個分支，所要插入的最簡單符號串是標識符i(即=i)。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (5) 把插到aj之前，并從的首部開始繼續(xù)分析，即將i插入到“i=i+;”中,得到“i=i+i;”。至此，我們完成了對輸入串“i=i+)”的錯誤校正。 對遞歸下降分析器來說，雖然原則上可用上述校正錯誤的方法，但因無法將語法樹已構造部分明顯表示出來，故上述方法未必可行。考慮到遞歸下降分析器實際上是由一組遞歸程序組成的，其中每一遞歸程序都對應一個文法的非終結符號，并且在語法分析的每一時刻，當前正在

44、執(zhí)行的遞歸程序也代表了與之對應的非終結符的未完成分支。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 因此，我們可以采用這樣的策略來校正源程序中的語法錯誤：在執(zhí)行某遞歸程序中，當掃描到輸入符號ai時發(fā)現(xiàn)一個語法錯誤，則除報錯之外還將根據(jù)ai及它所表示的未完成分支的結構，盡量設法插入或刪除一些符號對該錯誤進行校正，使語法分析能夠繼續(xù)進行下去；若無法做到這一點，則帶著該語法錯誤的有關信息返回到調(diào)用此過程的上一層過程，在那里再謀求對語法錯誤進行校正。 此外，對LL(1)分析器和算符優(yōu)先分析器，我們還可以用分析表作為工具來進行錯誤校正。例如，使用LL(1)分析表會遇到兩種語法分析錯誤：第第8 8章

45、章 符號表與錯誤處理符號表與錯誤處理 (1) 棧頂終結符與輸入字符不匹配。 (2) 棧頂非終結符為A而輸入字符為a，但分析表MA,a中為空。 處理這兩種出錯情況的基本思想是跳過一些分析步驟，繼續(xù)進行分析。具體有兩種處理方法： (1) 將輸入指針移向下一個輸入字符，即跳過當前輸入字符a，但分析棧不變。這種處理方法是把輸入字符a作為多余的字符來處理，以尋求棧頂符號與下一個輸入字符的匹配。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (2) 將棧頂符號彈出而輸入字符不變，這意味著輸入串中缺少了與棧頂終結符匹配的輸入字符或與棧頂非終結符匹配的短語，由此可以跳過棧頂符號繼續(xù)分析下去。 例如，表3.3

46、的LL(1)分析表在增加了錯誤處理功能后如表8.1所示。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 表8.1 具有錯誤處理的LL(1)分析表 i+*()#EETE ETEeeE E+TE EETTFTe TFTeeT TT*FT TTFFieeF(E)ee第第8 8章章 符號表與錯誤處理符號表與錯誤處理 在這個分析表中，有兩種錯誤入口：一種仍用空白符，即輸入指針移向下一個字符；另一種用e標記，即彈出棧頂符號。 不難發(fā)現(xiàn)所有標記e的位置是由FOLLOW(E)=)，#、FOLLOW(T)=+，)，#和FOLLOW(F)=*，+，)，#所確定的。第第8 8章章 符號表與錯誤處理符號表與錯誤處理

47、 3自下而上分析中的錯誤校正 對于算符優(yōu)先分析器來說，會產(chǎn)生這樣一類錯誤：棧頂終結符和當前輸入字符之間無優(yōu)先關系。此時，可在優(yōu)先關系表中的相應位置標記錯誤處理子程序編號。表8.2就是表3.7優(yōu)先關系表增加了錯誤處理后的結果。其中： (1) e1：棧頂符號為“i”或“)”而當前輸入字符為“i”或“(”，即缺少運算符，這時可在當前輸入字符之前插入假想運算符“+”。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (2) e2：棧頂符號為“(”而當前輸入符號為“#”，即缺少右括號“)”，故從棧中彈出“(”。 (3) e3：棧頂符號為“#”而當前輸入符號為“)”，即右括號不配對，故從輸入串中刪去“)”

48、。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 表8.2 帶錯誤信息的算符優(yōu)先關系表 +*i()#+*ie1e1(e2)e1e1#e3第第8 8章章 符號表與錯誤處理符號表與錯誤處理 算符優(yōu)先分析器會產(chǎn)生的另一類錯誤是：當按優(yōu)先關系表進行歸約時，卻發(fā)現(xiàn)沒有一個產(chǎn)生式的候選式可與分析棧中的“可歸約串”匹配，這時應按下述幾種情況處理： (1) 按“+”、“*”歸約時，其兩端均應有非終結符，否則表示缺少運算對象。 (2) 按“i”歸約時，其兩端若有非終結符，則表示缺少運算符。 (3) 按“(”、“)”歸約時，在括號之間若沒有非終結符，則表示缺少表達式。 第第8 8章章 符號表與錯誤處理符號表與錯

49、誤處理 LR分析器是根據(jù)分析表來確定各個分析動作的。當分析器處于某一狀態(tài)s并面臨輸入符號為a時，就以符號對(s,a)查LR分析表。如果分析表中ACTIONs,a欄為“空”(即在分析器當前格局下既不能移進輸入符號a也不能將其歸約)，就表明已經(jīng)發(fā)現(xiàn)了一個語法錯誤，此時分析器應調(diào)用相應的出錯處理子程序進行處理。因此，可以在ACTION表的每一空白項中填入一個指向相應出錯處理子程序的編號。至于每一出錯處理子程序所完成的操作，則可根據(jù)各類語法錯誤所在語法結構的特點預先進行設計。 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 通常各出錯處理子程序所要完成的校錯操作無非是從分析棧或(和)余留輸入字符串中

50、插入、刪除或修改一些符號。由于LR分析器的各個歸約動作總是正確的(因為在每次歸約之后，分析棧中的內(nèi)容必然是文法的一個活前綴，而此活前綴即代表輸入的那一部分已被成功分析)，故在設計出錯處理程序時，應避免將那些與非終結符相對應的狀態(tài)從棧中彈出。 例如，表3.20算術表達式的SLR(1)分析表(略有改動，實際上改為LR(0)在增加了錯誤處理功能后如表8.3所示。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 表8.3 具有錯誤處理的LR分析表狀態(tài)ACTIONGOTOi+*()#E0s3e1e1s2e2e111e3s4s5e3e2acc 2s3e1e1s2e2e163r4r4r4r4r4r4 4s3

51、e1e1s2e2e175s3e1e1s2e2e186e3s4s5e3s9e4 7r1r1s5r1r1r1 8r2r2r2r2r2r2 9r3r3r3r3r3r3 第第8 8章章 符號表與錯誤處理符號表與錯誤處理 其中，錯誤處理子程序e1e4的含義和功能如下： (1) e1：在分析器狀態(tài)0、2、4或5時，所掃描的輸入符號應為“i”或“(”；若此時輸入符號為“+”、“*”或“#”，就調(diào)用此子程序?qū)⒁患傧氲摹癷”與狀態(tài)3壓棧并給出“缺少運算量”錯誤信息。 (2) e2：在分析器狀態(tài)05且掃描的輸入符號為“)”時，調(diào)用此程序刪除符號“)”，并給出“右括號不匹配”錯誤信息。第第8 8章章 符號表與錯誤處理符號表與錯誤處理 (3) e3：在分析器狀態(tài)1或6時，所掃描的輸入符號應為一運算符；若此時輸入符號為“i”或“(”，則調(diào)用此程序?qū)⒓傧脒\算符“+”及狀態(tài)4壓棧并給出“缺少運算符”錯誤信息。 (4) e4：當分析器處于狀態(tài)6時，所掃描的輸入符號應為運算符或右括號；若此時掃描的輸入符號為“#”，則調(diào)用此程序?qū)ⅰ?”和狀態(tài)9壓棧并給出“缺少右括號”錯誤信息。 例8.3 試根據(jù)表8.3分析輸入串(i+(*i)#的錯誤校正處理過程。 解答 按表8.3對輸入串(i+(*i)#的分析及錯誤校正處理過程如表8.4所示。第第8 8章章 符號表與錯誤處理符