編譯原理課件第8章符號表與錯誤處理

1、第第8章章 符號表與錯誤處理符號表與錯誤處理8.1 符號表符號表 8.1.1 符號表的作用符號表的作用 編譯過程中需不斷收集、記錄、查證和使用源程序中的一些名字的類型和特征等相關(guān)信息。為方便起見，讓編譯程序在其工作過程中建立并保存一批表格建立并保存一批表格，如常數(shù)表、變量名表、數(shù)組內(nèi)情向量表、過程或子程序名表及標(biāo)號表等，這些表格統(tǒng)稱為符號表符號表或名字表。 符號表中的每一項(xiàng)包括兩部分：名字、與名字有關(guān)的信息，這些信息全面反映各個語法符號的屬性及它們在編譯過程中的特征，如名字的種屬、名字的類型、特征(定義性還是使用性出現(xiàn)等)、給此名字分配的存儲單元地址及與此名字語義有關(guān)的其它信息等。 根據(jù)編譯程

2、序階段的不同劃分，名字表中的各種信息將在編譯過程中的適當(dāng)時候填入。對于詞法分析階段就建立符號表的編譯程序，當(dāng)掃描源程序識別出一個單詞時，就以此名字查找符號表。若表中無此名的登記項(xiàng)，則將此名字填入符號表中。 語義分析時，符號表中的信息可用于語義檢查；代碼優(yōu)化時，編譯程序利用符號表提供的信息選出恰當(dāng)?shù)拇a進(jìn)行優(yōu)化；目標(biāo)代碼生成時，編譯程序?qū)⒁罁?jù)符號表中的符號名來分配目標(biāo)地址?？梢?，幾乎在編譯程序工作的全過程中，都需要對符號表進(jìn)行頻繁地訪問(查表或填表)，其耗費(fèi)的時間在整個編譯過程中占有很大的比例。因此，合理地組織符號表并選擇好的查表、填表方法是提高編譯程序工作效率的有效辦法。 對于編譯程序所用的符

3、號表，它涉及的基本操作大致可歸納為五類： (1) 判斷一個給定的名字是否在表中； (2) 在表中填入新的名字； (3) 對給定名字訪問它在表中的有關(guān)信息； (4) 對給定名字填入或更新它在表中的某 些信息； (5) 從表中刪去一個或一組無用的項(xiàng)。8.1.2 符號表的組織符號表的組織 符號表有多種組織方式。按處理對象的特點(diǎn)，符號表的組織方式一般可分為直接方式直接方式和間接方式間接方式。 直接方式直接方式是指在符號表中直接填入源程序中定義的標(biāo)識符及相關(guān)信息。 間接方式間接方式是指單獨(dú)設(shè)置一個字符串?dāng)?shù)組字符串?dāng)?shù)組來存放所有標(biāo)識符，并在符號表名字欄中設(shè)置兩項(xiàng)內(nèi)容：一是指針指針，用來指向標(biāo)識符在數(shù)組中的

4、起始位置；二是一整數(shù)值一整數(shù)值，用來表示該標(biāo)識符的長度。 根據(jù)符號表名字欄的組織特點(diǎn)，符號表符號表信息欄的組織方式信息欄的組織方式也分為兩類：固定信息內(nèi)容和僅記錄信息存放地址。 如果名字欄中的標(biāo)識符按種屬分類，則因同類標(biāo)識符其基本特征一致，故可將這些信息一一記錄在信息欄中。 如果符號表的名字不分種屬，則由于不同種屬的標(biāo)識符其特征不一致，即它們所需存儲的信息不一致，因而不易確定一個固定長度的空間來統(tǒng)一安排。這時可在符號表外另設(shè)一組存儲空間，并在符號表信息欄中放一指針來指向這個存儲空間始址。8.1.3 分程序結(jié)構(gòu)語言的符號表建立（分程序結(jié)構(gòu)語言的符號表建立（P231） 所謂分程序結(jié)構(gòu)的語言，是指用

5、這種語言編寫的分程序中可以再包含嵌套的分程序，并且可以定義屬于它自己的一組局部變量。由于分程序的嵌套導(dǎo)致名字作用域的嵌套，故有時也將允許名字作用域嵌套的語言稱為具有分程序結(jié)構(gòu)的語言。 典型的分程序結(jié)構(gòu)語言是PASCAL；雖然通常不把C語言視為嵌套分程序結(jié)構(gòu)的語言，但在它的函數(shù)定義中，函數(shù)體可以是一個嵌套的分程序，因而其中所涉及的各個局部變量的作用域也具有嵌套特征。 對于嵌套作用域，同名變量在不同層次出現(xiàn)可能有不同類型。因此，為使編譯程序在語義及其它有關(guān)處理上不發(fā)生混亂，可采用分層建立和處理符號表分層建立和處理符號表的方式。 PASCAL程序中，標(biāo)識符的作用域是包含說明該標(biāo)識符的最小分程序，即P

6、ASCAL程序中標(biāo)識符的作用域總是與說明這些標(biāo)識符的分程序的層次相關(guān)聯(lián)。為表征PASCAL程序中各分程序的嵌套層次關(guān)系，可將這些分程序按其開頭符號在源程序中出現(xiàn)的先后順序進(jìn)行編號。這樣從左至右掃描源程序時可按分程序在源程序中自然順序，對各分程序中的標(biāo)識符進(jìn)行處理，具體方法具體方法如下： (1)當(dāng)一個分程序首部某說明中分程序首部某說明中掃描到一標(biāo)識符時，以此標(biāo)識符查找相應(yīng)于本層分程序的符號表，如果符號表中已有此名字的登記項(xiàng)，則表明此標(biāo)識符已說明，應(yīng)按語法錯誤進(jìn)行處理；否則應(yīng)在符號表中新登記一項(xiàng)，并將此標(biāo)識符及有關(guān)信息填入。 (2)當(dāng)在一分程序語句中分程序語句中掃描到一個標(biāo)識符時，先在該層分程序的

7、符號表中查找此標(biāo)識符；若查不到，則繼續(xù)在其外層分程序的符號表中查找。如此下去，一旦找到，則作相應(yīng)處理；如果查遍所有外層都無法找到，則程序中使用了一個未說明的標(biāo)識符。為實(shí)現(xiàn)上述查填表, 按如下方式組織符號表: (1) 分層組織符號表的登記項(xiàng)，使各分程序的符號表登記項(xiàng)連續(xù)地排列在一起，不允許被其內(nèi)層分程序的符號表登記項(xiàng)所分割。 (2) 建立一個分程序表，記錄各層分程序符號表的有關(guān)信息。分程序表中的各登記項(xiàng)在自左至右掃描源程序中按分程序出現(xiàn)的自然順序依次填入，且對每一分程序填寫一個登記項(xiàng)。因此，分程序表各登記項(xiàng)的序號隱含地表征了各分程序的編號。建立符號表的算法建立符號表的算法：(1) 給各指示器賦初

8、值。(2) 自左至右掃描源程序： 每當(dāng)進(jìn)入分程序的首符號或過程時，就在分程序表中登記一項(xiàng)，并使之成為當(dāng)前的分程序。 當(dāng)掃描到當(dāng)前分程序中一個定義性出現(xiàn)的標(biāo)識符時，將該名字及有關(guān)信息填入臨時工作棧頂部；再在分程序表中，把當(dāng)前分程序相應(yīng)登記項(xiàng)的COUNT值加1且使POINTER指向新的棧頂。 當(dāng)掃描到分程序的結(jié)束符END時，將記入臨時工作棧的本層分程序全部登記項(xiàng)移至正式的符號表中，且修改POINTER值使其指向本層分程序全部名字登記項(xiàng)在符號表中的起始位置。此外，退出此層分程序時，應(yīng)使其直接外層分程序成為當(dāng)前分程序。 (3) 重復(fù)步驟(2)，直至掃描完整個源程序?yàn)橹埂?對一遍掃描的編譯程序而言，在它

9、工作過程中，當(dāng)遇到某分程序的結(jié)束符END時，該分程序中的全部標(biāo)識符已經(jīng)完成它們的使命。因此，只需將它們從棧中逐出，也即將棧頂部指示器回調(diào)至剛進(jìn)入本分程序時的情況即可，而不再需要把這些登記項(xiàng)上移。事實(shí)上，如上所述的工作棧就完全可作為編譯程序的符號表來使用，將這種符號表稱為棧式符號表。8.2 常用符號表結(jié)構(gòu)常用符號表結(jié)構(gòu) 由于在整個編譯過程中需不斷地訪問符號表，因而如何構(gòu)造符號表以及如何查填符號表就成為編譯程序設(shè)計(jì)的重要問題之一。除了上述介紹的用于嵌套結(jié)構(gòu)程序語言的棧棧式符號表式符號表外，還有其它常用符號表結(jié)構(gòu)。 1線性符號表線性符號表 符號表中最簡單且最容易實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是線性表，它是按程序中標(biāo)

10、識符出現(xiàn)的先后次序建立的符號表，編譯程序不做任何整理次序的工作。2有序符號表有序符號表 為了提高查表速度，可以在造表的同時把各標(biāo)識符按照一定的順序進(jìn)行排列。顯然，這樣的符號表是有序的。3散列符號表散列符號表 散列符號表是大多數(shù)編譯程序采用的一種符號表。符號表采用散列技術(shù)，相對來講具有較高的運(yùn)行效率，特別適用于邊填寫邊引用的動態(tài)查找符號表。 散列符號表又稱哈希符號表，其關(guān)鍵在于引進(jìn)一種函數(shù)哈希函數(shù)，并將程序中出現(xiàn)的標(biāo)識符通過哈希函數(shù)進(jìn)行映射，得到的函數(shù)值作為該標(biāo)識符在符號表中的位置。 哈希函數(shù)(Hash)一般具有如下性質(zhì)： (1) 函數(shù)值只依賴于對應(yīng)的標(biāo)識符； (2) 函數(shù)的計(jì)算簡單且高效； (3) 函數(shù)值均勻分布在一定范圍內(nèi)。 構(gòu)造散列函數(shù)的方法很多，如直接定址法、數(shù)字分析法、平方取中法、除留余數(shù)法。8.4 符號表的內(nèi)容（符號表的內(nèi)容（P234） 對于常見的程序設(shè)計(jì)語言而言，其變量名及過程名登記項(xiàng)的信息欄通常包含如下信息： (1) 變量名 種屬(簡單變量、數(shù)組、記錄結(jié)構(gòu)等)； 類型(整型、實(shí)型、雙精度實(shí)型、邏輯 型、字符串型、標(biāo)號或指針等)； 所分配的數(shù)據(jù)區(qū)地址； 若為數(shù)組，應(yīng)填其內(nèi)情向量并給出內(nèi)情 向量的首址； 若為記錄結(jié)構(gòu)，則應(yīng)把該登記項(xiàng)與其各 分量按某種方式連接起來； 是否為