編譯原理第7章-符號表

1、編譯原理 符號符號表表第七講第七講編譯原理 符號表符號表的作用的作用符號表符號表 符號表的實(shí)現(xiàn)符號表的實(shí)現(xiàn) 符號表的常見屬性符號表的常見屬性 符號表體現(xiàn)作用域與可見性符號表體現(xiàn)作用域與可見性編譯原理 符號表符號表的作用的作用符號表符號表- 用來用來存放存放有關(guān)有關(guān)標(biāo)識符（符號）的屬性標(biāo)識符（符號）的屬性信息信息 這些信息會在編譯的不同階段用到這些信息會在編譯的不同階段用到 符號表的符號表的內(nèi)容將內(nèi)容將用于靜態(tài)語義檢查用于靜態(tài)語義檢查和產(chǎn)生中間代碼和產(chǎn)生中間代碼 在目標(biāo)代碼生成階段，符號表是對符號名進(jìn)行地址在目標(biāo)代碼生成階段，符號表是對符號名進(jìn)行地址 分配分配的依據(jù)的依據(jù) 對一個多遍掃描的編譯程

2、序，不同遍所用的符號表對一個多遍掃描的編譯程序，不同遍所用的符號表 也也會有所不同，因為每遍所關(guān)心的信息或所能得到會有所不同，因為每遍所關(guān)心的信息或所能得到 的的信息會有差異信息會有差異- 用來體現(xiàn)作用域與可見性信息用來體現(xiàn)作用域與可見性信息編譯原理符號表符號表 符號的常見屬性符號的常見屬性- 符號名符號名- 符號的類別符號的類別- 符號的類型符號的類型- 符號的存儲類別和存儲分配信息符號的存儲類別和存儲分配信息- 符號的作用域信息符號的作用域信息- 其他屬性其他屬性 數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量 記錄結(jié)構(gòu)的成員信息記錄結(jié)構(gòu)的成員信息 函數(shù)及過程的形參函數(shù)及過程的形參 編譯原理符號表符號表 符號表

3、的實(shí)現(xiàn)符號表的實(shí)現(xiàn)- 針對針對符號表的常見操作符號表的常見操作 創(chuàng)建創(chuàng)建符號表符號表 在編譯開始，或進(jìn)入一個作用域在編譯開始，或進(jìn)入一個作用域 插入表項插入表項 在遇到新的標(biāo)識符聲明時進(jìn)行在遇到新的標(biāo)識符聲明時進(jìn)行 查詢表項查詢表項 在引用標(biāo)識符時進(jìn)行在引用標(biāo)識符時進(jìn)行 修改表項修改表項 在獲得新的語義值信息時進(jìn)行在獲得新的語義值信息時進(jìn)行 刪除表項刪除表項 在標(biāo)識符成為不可見或不再需要它的任在標(biāo)識符成為不可見或不再需要它的任 何信息時進(jìn)行何信息時進(jìn)行 釋放符號表空間釋放符號表空間 在編譯結(jié)束前或退出一個作用域在編譯結(jié)束前或退出一個作用域編譯原理符號表符號表 符號表的實(shí)現(xiàn)符號表的實(shí)現(xiàn)- 實(shí)現(xiàn)符

4、號表的實(shí)現(xiàn)符號表的常用數(shù)據(jù)結(jié)構(gòu)常用數(shù)據(jù)結(jié)構(gòu) 一般的線性表一般的線性表 如：數(shù)組，鏈表，等如：數(shù)組，鏈表，等 有序表有序表 查詢較無序表快，如可以采用折半查找查詢較無序表快，如可以采用折半查找 二叉搜索樹二叉搜索樹 Hash表表編譯原理符號表符號表 符號表的實(shí)現(xiàn)符號表的實(shí)現(xiàn)- 存儲效率問題存儲效率問題 重要，但本課程不專門討論重要，但本課程不專門討論 兩方面：兩方面：省空間省空間，高效率高效率編譯原理符號表符號表 符號表體現(xiàn)作用域信息符號表體現(xiàn)作用域信息- 作用域與可見性作用域與可見性- 作用域與符號表組織作用域與符號表組織 所有作用域共用一個全局符號表所有作用域共用一個全局符號表 每個作用域都

5、有各自的符號表每個作用域都有各自的符號表編譯原理符號表符號表 作用域與可見性作用域與可見性- 嵌套的嵌套的作用域作用域（nested scopes）- 開作用域與閉作用域開作用域與閉作用域（相應(yīng)于程序中特殊點(diǎn)）（相應(yīng)于程序中特殊點(diǎn)） 該點(diǎn)所在的作用域為該點(diǎn)所在的作用域為當(dāng)前作用域當(dāng)前作用域 當(dāng)前作用域與包含它的程序單元所構(gòu)成的作用域稱當(dāng)前作用域與包含它的程序單元所構(gòu)成的作用域稱 為為開作用域開作用域（open scopes） 不屬于開作用域的作用域稱為不屬于開作用域的作用域稱為閉作用域閉作用域（close scopes）編譯原理符號表符號表 作用域與可見性作用域與可見性- 常用的可見性規(guī)則常用

6、的可見性規(guī)則（visibility rules） 在程序的任何一點(diǎn)，只有在該點(diǎn)的開作用域中聲明在程序的任何一點(diǎn)，只有在該點(diǎn)的開作用域中聲明 的名字才是可訪問的的名字才是可訪問的 若若一個名字在多個開作用域中被聲明，則把離該名一個名字在多個開作用域中被聲明，則把離該名 字的某個引用最近的聲明作為該引用的解釋字的某個引用最近的聲明作為該引用的解釋 新的聲明只能出現(xiàn)在當(dāng)前作用域新的聲明只能出現(xiàn)在當(dāng)前作用域編譯原理符號表符號表 作用域與符號表組織作用域與符號表組織- 作用域與單符號表組織作用域與單符號表組織 所有嵌套的作用域共用一個全局符號表所有嵌套的作用域共用一個全局符號表 每個作用域有一個作用域號

7、每個作用域有一個作用域號 僅記錄開作用域中的符號僅記錄開作用域中的符號 當(dāng)某個作用域成為閉作用域時，從符號表中刪除該當(dāng)某個作用域成為閉作用域時，從符號表中刪除該 作用域中所聲明的名字作用域中所聲明的名字編譯原理const a=25;var x,y;procedure p; var z; begin end; procedure r; var x, s; procedure t; var x; begin /*here*/ end; begin end; begin end. 例：例：右邊某語言程序在處理到右邊某語言程序在處理到/*here*/ 時的符號表（以哈希表為例）時的符號表（以哈希表為例

8、） 所有嵌套的作用域共用一個所有嵌套的作用域共用一個 全局符號表全局符號表符號表符號表t(2)p(1)a(1)s(2)r(1)y(1)x(3)x(2)x(1)Hash Table （表中數(shù)字代表層號）（表中數(shù)字代表層號）編譯原理 所有嵌套的作用域共用一個所有嵌套的作用域共用一個 全局符號表全局符號表符號表符號表const a=25;var x,y;procedure p; var z; begin end; procedure r; var x, s; procedure t; var v, x, y; begin end; begin /*here*/ end; begin end. Dx:

9、 基地址基地址 Cx: 棧幀中控制單元數(shù)目棧幀中控制單元數(shù)目LEV: 層號層號 例：例：右邊某語言程序在處理到右邊某語言程序在處理到/*here*/ 時的符號表（以時的符號表（以線性表線性表為例）為例）編譯原理符號表符號表 作用域與符號表組織作用域與符號表組織- 作用域與多符號表組織作用域與多符號表組織 每個作用域都有各自的符號表每個作用域都有各自的符號表 維護(hù)一個符號表的維護(hù)一個符號表的作用域棧作用域棧，每個開作用域?qū)?yīng)棧每個開作用域?qū)?yīng)棧 中的一個入口，當(dāng)前的開作用域出現(xiàn)在該棧的棧頂中的一個入口，當(dāng)前的開作用域出現(xiàn)在該棧的棧頂 當(dāng)一個新的作用域開放時，新符號表將被創(chuàng)建，并當(dāng)一個新的作用域開

10、放時，新符號表將被創(chuàng)建，并 將其入棧將其入棧 在當(dāng)前作用域成為閉作用域時，從棧頂彈出相應(yīng)的在當(dāng)前作用域成為閉作用域時，從棧頂彈出相應(yīng)的 符號表符號表編譯原理const a=25;var x,y;procedure p; var z; begin end; procedure r; var x, s; procedure t; var x; begin end; begin /*here*/ end; begin end. 例：例：右邊程序在處理到右邊程序在處理到/*here*/時時 的作用域棧如下所示的作用域棧如下所示 每個作用域都有各自的符號表每個作用域都有各自的符號表 符號表符號表a, x, y, p, rx, s, tzx開作用域開作用域閉作用域閉