編譯原理蔣宗禮課件第8章.ppt

1、1,第8章符號表管理,8.1 符號表的作用 8.2 符號表中存放的信息 8.3 符號表的組織結(jié)構(gòu) 8.4 符號表與作用域 8.5 本章小結(jié),2,8.1 符號表的作用,編譯的各個階段都有可能會用到符號表中登記的信息 協(xié)助進行語義檢查(如檢查一個名字的引用和之前的聲明是否相符)和中間代碼生成 在目標代碼生成階段，當需要為名字分配地址時，符號表中的信息將是地址分配的主要依據(jù) 編譯器用符號表來記錄、收集和查找出現(xiàn)在源程序中的各種名字及其語義信息。,3,8.1 符號表的作用,符號表是以名字為關(guān)鍵字來記錄其信息的數(shù)據(jù)結(jié)構(gòu)，其上支持的兩個最基本操作應該是填加表項和查找表項，這兩個操作必須是高效的,4,8.2

2、 符號表中存放的信息,記錄源程序中出現(xiàn)的各種名字及其屬性信息是符號表的首要任務。 顯然同一個名字在一段程序中應該表示同一個對象，即同一個符號表中不能出現(xiàn)相同的名字，因此名字可以作為符號表的關(guān)鍵字。于是，每一個符號表表項中需要存放的基本信息就是符號的名字及其屬性 。,圖8.1 符號表的基本格式,5,8.1.1 符號表中的名字,名字字段長度固定 名字項的長度大小取決于標識符允許的最大長度 不適于標識符長度變化范圍較大的語言 空間浪費 名字字段長度可變 標識符的長度沒有限制 符號表上的操作復雜而低效 引入一個單獨的字符串表，將符號表中的全部標識符集中放在這個字符串表中，而在符號表表項的名字部分只要給

3、出相應標識符的首字符在字符串表中的位置即可,6,8.1.1 符號表中的名字,標識符長度放在符號表中,7,8.1.1 符號表中的名字,(b) 標識符長度放在字符串中,8,8.1.1 符號表中的名字,(c) 用0表示標識符的結(jié)束,9,8.1.2 符號表中的屬性,符號所表達的含義不同，符號表中需要存放的屬性也就不同 數(shù)組名字需要存放的屬性信息應該包括數(shù)組的維數(shù)、各維的維長等 函數(shù)(或過程)的名字應該存放其參數(shù)個數(shù)、各參數(shù)的類型、返回值的類型等,10,8.1.2 符號表中的屬性,建立多個符號表來管理源程序中出現(xiàn)的各種符號，如常數(shù)表、變量表、函數(shù)表、數(shù)組表等 可能出現(xiàn)不同種類符號出現(xiàn)重名的問題 建立一張

4、共用的大表來管理各種符號，此時需要在符號表中增設一個標志來表明符號的種屬 不同種類符號所需存放屬性信息在數(shù)量上的差異將會造成符號表的空間浪費,11,8.1.2 符號表中的屬性,圖8.3 多種符號共用符號表的一種實現(xiàn)結(jié)構(gòu),12,8.1.2 符號表中的屬性,圖8.4 用擴展屬性鏈組織函數(shù)形參的符號表,13,8.1.3 符號的地址屬性,如果采用靜態(tài)存儲分配策略，則符號x綁定的地址等于靜態(tài)分配的基址base加上符號x的偏移量offset 如果采用的是棧式存儲分配或堆式存儲分配等動態(tài)分配策略，則符號是在程序執(zhí)行過程中和地址動態(tài)綁定的。 如棧式存儲分配時，i的地址是以棧指針sp為基址加上i相對于活動記錄起

5、始地址的偏移量offseti 符號表中各符號的地址屬性就是該符號相對于第一個符號的偏移地址,14,8.3 符號表的組織結(jié)構(gòu)8.3.1 符號表的線性表實現(xiàn),用線性表實現(xiàn)符號表較為直觀 數(shù)組實現(xiàn)：插入n個符號、執(zhí)行e次查找操作的時間復雜度為T(n, e) = O(n(n+e) 有序數(shù)組實現(xiàn)：插入n個符號、執(zhí)行e次查找操作的時間復雜度為T(n, e) = elog n+ + (n+e)log n+O(n2) 有序符號表結(jié)構(gòu)只有在下面的情況下才能取得較好效果：和插入操作次數(shù)相比，符號表表項上的查找操作次數(shù)占絕對多數(shù)，即en。,15,8.3.2 符號表的散列表實現(xiàn),引入散列表不僅可以提高lookup操作

6、的效率，同時也可以提高insert操作的效率，所以在許多實際編譯器的符號表實現(xiàn)中均采用了散列技術(shù),圖8.6 一個符號表的散列表實現(xiàn),16,8.3.2 符號表的散列表實現(xiàn),引入散列表不僅可以提高lookup操作的效率，同時也可以提高insert操作的效率，所以在許多實際編譯器的符號表實現(xiàn)中均采用了散列技術(shù) 插入n個符號，查找e個符號的lookup操作和insert操作的時間復雜度T(n,e)還將與m有關(guān)，記為T(n,e,m) ，T(n,e,m)n(n+e)/m S(n,m)=O(n) 散列函數(shù)應在滿足 的前提下，使 達到最小,17,8.4 符號表與作用域,int main() int abc;

7、abc = 1; int abc; abc = 2; printf(“abc is %dn”, abc); printf(“abc is %dn”, abc); ,圖8.8 一個具有程序塊結(jié)構(gòu)的C語言程序,運行結(jié)果為： abc is 2 abc is 1 說明abc在不同的范圍內(nèi)有效。 這個有效范圍就是符號的作用域,18,8.4.1 程序塊結(jié)構(gòu)的符號表,變量的作用域滿足最近嵌套原則 (1) int main() (2) (3) int a=0; (4) int b=0; (5) (6) int b=1; (7) (8) int a=2; (9) printf(“%d %dn”, a, b );

8、 (10) (11) (12) int b=3; (13) printf(“%d %dn”, a, b); (14) (15) printf(“%d %dn”, a, b); (16) (17) printf(“%d %dn”, a, b); (18) ,圖8.10 一個C語言程序塊實例,19,8.4.1 程序塊結(jié)構(gòu)的符號表,為每個程序塊建立一個符號表，程序塊內(nèi)的符號記錄在該程序塊所對應的符號表中,還要建立起這些符號表之間的聯(lián)系,以刻畫出符號的嵌套作用域,圖8.11 圖8.10中的程序所對應的符號表,20,8.4.2 程序塊結(jié)構(gòu)符號表的其他實現(xiàn),將所有塊的符號表放在一個大數(shù)組中，然后再引入一個

9、程序塊表來描述各程序塊的符號表在大數(shù)組中的位置及其相互關(guān)系,圖8.12 圖8.10的另一種符號表結(jié)構(gòu),21,8.4.2 程序塊結(jié)構(gòu)符號表的其他實現(xiàn),將符號所屬程序塊的編號放在符號表表項中。查找某個符號的名字name時，只有當name和符號表中的名字字符串完全匹配，且符號表表項中的塊編號和當前處理的塊編號完全相同時才算查找成功，否則要新建一個名字為name且塊號為當前塊編號的符號表表項。 程序塊編號可以通過在語法制導定義中的塊開始處和塊結(jié)束處添加適當?shù)恼Z義規(guī)則計算得出。,22,8.4.2 程序塊結(jié)構(gòu)符號表的其他實現(xiàn),程序塊滿足最近嵌套原則 內(nèi)層程序塊中的局部變量只有全部處理完成之后才進入外層塊

10、一旦進入外層程序塊，內(nèi)層塊的局部變量就不會再使用了，可以從符號表中將這些符號刪除 符號表中最前面的符號一定是當前正在處理的塊中的局部變量 符號表表項中可以不用存放塊編號，而是根據(jù)符號表表項在符號表中的位置來判斷。,23,8.4.2 程序塊結(jié)構(gòu)符號表的其他實現(xiàn),(a) 處理到語句(5)時的符號表,(b) 處理到語句(7)時的符號表,對圖8.10中的程序,24,8.4.2 程序塊結(jié)構(gòu)符號表的其他實現(xiàn),對圖8.10中的程序,(c) 處理到語句(9)時的符號表,(d) 處理到語句(13)時的符號表,25,8.4.3 C語言的符號表,如果采取將每個函數(shù)分別編譯成目標代碼然后連接裝配成一個可執(zhí)行程序的處理

11、方式，則每個函數(shù)中的符號經(jīng)一遍處理即可，而且源程序中的多個函數(shù)是一個接一個處理的，不會出現(xiàn)交叉，此時可以按圖8.16的方式組織符號表。,圖8.16 一個完整C程序的符號表,26,8.4.4 嵌套過程的符號表,Pascal等允許在過程中嵌套定義其它過程 program sort(input, output); procedure readarray; begin end readarray ; procedure exchange( i, j : integer ); begin end exchange ; procedure quicksort( m, n : integer ); function partition( x, y : integer ); begin end partition ; begin end quicksort ; begin end sort ;,27,8.4.4 嵌套過程的符號表,28,本章小結(jié),符號表用來存放編譯器各階段收集來的各種名字的類型和特征等有關(guān)信息，并供編譯程序用于語法檢查、語義檢查、生成中間代碼及生成目標代碼等； 源程序中會出現(xiàn)各種各樣的名字，如函數(shù)名、函數(shù)參數(shù)名、函數(shù)中的局部變量名、全局變量名、數(shù)組名、結(jié)構(gòu)名、文件名等，相應的屬性可以是種屬、類型、地址等; 根據(jù)符號所需的屬性個數(shù)和類型的不同，可以組成不同的符號表，也