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

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

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

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

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

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

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

7、abc = 1; int abc; abc = 2; printf(“abc is %dn”, abc); printf(“abc is %dn”, abc); ,圖8.8 一個(gè)具有程序塊結(jié)構(gòu)的C語(yǔ)言程序,運(yùn)行結(jié)果為： abc is 2 abc is 1 說(shuō)明abc在不同的范圍內(nèi)有效。 這個(gè)有效范圍就是符號(hào)的作用域,18,8.4.1 程序塊結(jié)構(gòu)的符號(hào)表,變量的作用域滿足最近嵌套原則 (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 一個(gè)C語(yǔ)言程序塊實(shí)例,19,8.4.1 程序塊結(jié)構(gòu)的符號(hào)表,為每個(gè)程序塊建立一個(gè)符號(hào)表，程序塊內(nèi)的符號(hào)記錄在該程序塊所對(duì)應(yīng)的符號(hào)表中,還要建立起這些符號(hào)表之間的聯(lián)系,以刻畫出符號(hào)的嵌套作用域,圖8.11 圖8.10中的程序所對(duì)應(yīng)的符號(hào)表,20,8.4.2 程序塊結(jié)構(gòu)符號(hào)表的其他實(shí)現(xiàn),將所有塊的符號(hào)表放在一個(gè)大數(shù)組中，然后再引入一個(gè)

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

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

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