編譯原理課件第8章符號(hào)表與錯(cuò)誤處理

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

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

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

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

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

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

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

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

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

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