編譯原理課件chapter

第8章符號表管理SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重點(diǎn)：符號表的作用,符號表的組織結(jié)構(gòu),符號表與作用域。

難點(diǎn)：符號表的組織結(jié)構(gòu)及其性能評價(jià)。2023/5/72第8章

符號表管理8.1符號表的作用8.2符號表中存放的信息8.3符號表的組織結(jié)構(gòu)8.4符號表與作用域8.5本章小結(jié)2023/5/738.1符號表的作用編譯的各個(gè)階段都有可能會(huì)用到符號表中登記的信息協(xié)助進(jìn)行語義檢查(如檢查一個(gè)名字的引用和之前的聲明是否相符)和中間代碼生成在目標(biāo)代碼生成階段，當(dāng)需要為名字分配地址時(shí)，符號表中的信息將是地址分配的主要依據(jù)編譯器用符號表來記錄、收集和查找出現(xiàn)在源程序中的各種名字及其語義信息。2023/5/748.1符號表的作用符號表是以名字為關(guān)鍵字來記錄其信息的數(shù)據(jù)結(jié)構(gòu)，其上支持的兩個(gè)最基本操作應(yīng)該是添加表項(xiàng)和查找表項(xiàng)，這兩個(gè)操作必須是高效的2023/5/758.2符號表中存放的信息記錄源程序中出現(xiàn)的各種名字及其屬性信息是符號表的首要任務(wù)。顯然同一個(gè)名字在一段程序中應(yīng)該表示同一個(gè)對象，即同一個(gè)符號表中不能出現(xiàn)相同的名字，因此名字可以作為符號表的關(guān)鍵字。于是，每一個(gè)符號表表項(xiàng)中需要存放的基本信息就是符號的名字及其屬性。圖8.1符號表的基本格式2023/5/768.2.1符號表中的名字名字字段長度固定名字項(xiàng)的長度大小取決于標(biāo)識(shí)符允許的最大長度不適于標(biāo)識(shí)符長度變化范圍較大的語言空間浪費(fèi)名字字段長度可變標(biāo)識(shí)符的長度沒有限制符號表上的操作復(fù)雜而低效引入一個(gè)單獨(dú)的字符串表，將符號表中的全部標(biāo)識(shí)符集中放在這個(gè)字符串表中，而在符號表表項(xiàng)的名字部分只要給出相應(yīng)標(biāo)識(shí)符的首字符在字符串表中的位置即可2023/5/778.2.1符號表中的名字標(biāo)識(shí)符長度放在符號表中2023/5/788.2.1符號表中的名字(b)標(biāo)識(shí)符長度放在字符串中2023/5/798.2.1符號表中的名字(c)用’\0’表示標(biāo)識(shí)符的結(jié)束2023/5/7108.2.2符號表中的屬性符號所表達(dá)的含義不同，符號表中需要存放的屬性也就不同數(shù)組名字需要存放的屬性信息應(yīng)該包括數(shù)組的維數(shù)、各維的維長等函數(shù)(或過程)的名字應(yīng)該存放其參數(shù)個(gè)數(shù)、各參數(shù)的類型、返回值的類型等2023/5/7118.2.2符號表中的屬性建立多個(gè)符號表來管理源程序中出現(xiàn)的各種符號，如常數(shù)表、變量表、函數(shù)表、數(shù)組表等可能出現(xiàn)不同種類符號出現(xiàn)重名的問題建立一張共用的大表來管理各種符號，此時(shí)需要在符號表中增設(shè)一個(gè)標(biāo)志來表明符號的種屬不同種類符號所需存放屬性信息在數(shù)量上的差異將會(huì)造成符號表的空間浪費(fèi)8.2.2符號表中的屬性圖8.3多種符號共用符號表的一種實(shí)現(xiàn)結(jié)構(gòu)128.2.2符號表中的屬性圖8.4用擴(kuò)展屬性鏈組織函數(shù)形參的符號表132023/5/7148.2.3符號的地址屬性如果采用靜態(tài)存儲(chǔ)分配策略，則符號x綁定的地址等于靜態(tài)分配的基址base加上符號x的偏移量offset

如果采用的是棧式存儲(chǔ)分配或堆式存儲(chǔ)分配等動(dòng)態(tài)分配策略，則符號是在程序執(zhí)行過程中和地址動(dòng)態(tài)綁定的。如棧式存儲(chǔ)分配時(shí)，i的地址是以棧指針sp為基址加上i相對于活動(dòng)記錄起始地址的偏移量offseti符號表中各符號的地址屬性就是該符號相對于第一個(gè)符號的偏移地址2023/5/7158.3符號表的組織結(jié)構(gòu)

8.3.1符號表的線性表實(shí)現(xiàn)

用線性表實(shí)現(xiàn)符號表較為直觀數(shù)組實(shí)現(xiàn)：插入n個(gè)符號、執(zhí)行e次查找操作的時(shí)間復(fù)雜度為T(n,e)=O(n(n+e))有序數(shù)組實(shí)現(xiàn)：插入n個(gè)符號、執(zhí)行e次查找操作的時(shí)間復(fù)雜度為T(n,e)=elogn++

≤O(n+e)logn+O(n2)有序符號表結(jié)構(gòu)只有在下面的情況下才能取得較好效果：和插入操作次數(shù)相比，符號表表項(xiàng)上的查找操作次數(shù)占絕對多數(shù)，即e>>n。2023/5/7168.3.2符號表的散列表實(shí)現(xiàn)引入散列表不僅可以提高lookup操作的效率，同時(shí)也可以提高insert操作的效率，所以在許多實(shí)際編譯器的符號表實(shí)現(xiàn)中均采用了散列技術(shù)圖8.6一個(gè)符號表的散列表實(shí)現(xiàn)2023/5/7178.3.2符號表的散列表實(shí)現(xiàn)引入散列表不僅可以提高lookup操作的效率，同時(shí)也可以提高insert操作的效率，所以在許多實(shí)際編譯器的符號表實(shí)現(xiàn)中均采用了散列技術(shù)插入n個(gè)符號，查找e個(gè)符號的lookup操作和insert操作的時(shí)間復(fù)雜度T(n,e)還將與m(哈希桶數(shù))有關(guān)，記為T(n,e,m)，T(n,e,m)≈n(n+e)/m

S(n,m)=O(n)散列函數(shù)應(yīng)在滿足的前提下，使達(dá)到最小2023/5/7188.4符號表與作用域intmain(){intabc;abc=1;{intabc;abc=2;printf(“abcis%d\n”,abc);}printf(“abcis%d\n”,abc);}圖8.8一個(gè)具有程序塊結(jié)構(gòu)的C語言程序運(yùn)行結(jié)果為：

abcis2abcis1說明abc在不同的范圍內(nèi)有效。這個(gè)有效范圍就是符號的作用域2023/5/7198.4.1程序塊結(jié)構(gòu)的符號表變量的作用域滿足最近嵌套原則(1)intmain()(2){(3)inta=0;(4)intb=0;(5){(6)intb=1;(7){(8)inta=2;(9)printf(“%d%d\n”,a,b);(10)}(11){(12)intb=3;(13)printf(“%d%d\n”,a,b);(14)}(15)printf(“%d%d\n”,a,b);(16)}(17)printf(“%d%d\n”,a,b);(18)}

圖8.10一個(gè)C語言程序塊實(shí)例B0:line1toline18B1:line5toline16B2:line7toline10B3:line11toline142023/5/7208.4.1程序塊結(jié)構(gòu)的符號表為每個(gè)程序塊建立一個(gè)符號表，程序塊內(nèi)的符號記錄在該程序塊所對應(yīng)的符號表中,還要建立起這些符號表之間的聯(lián)系,以刻畫出符號的嵌套作用域圖8.11圖8.10中的程序所對應(yīng)的符號表2023/5/7218.4.2程序塊結(jié)構(gòu)符號表的其他實(shí)現(xiàn)[1]將所有塊的符號表放在一個(gè)大數(shù)組中，然后再引入一個(gè)程序塊表來描述各程序塊的符號表在大數(shù)組中的位置及其相互關(guān)系圖8.12圖8.10的另一種符號表結(jié)構(gòu)2023/5/7228.4.2程序塊結(jié)構(gòu)符號表的其他實(shí)現(xiàn)[2]

將符號所屬程序塊的編號放在符號表表項(xiàng)中。查找某個(gè)符號的名字name時(shí)，只有當(dāng)name和符號表中的名字字符串完全匹配，且符號表表項(xiàng)中的塊編號和當(dāng)前處理的塊編號完全相同時(shí)才算查找成功，否則要新建一個(gè)名字為name且塊號為當(dāng)前塊編號的符號表表項(xiàng)。程序塊編號可以通過在語法制導(dǎo)定義中的塊開始處和塊結(jié)束處添加適當(dāng)?shù)恼Z義規(guī)則計(jì)算得出。2023/5/7238.4.2程序塊結(jié)構(gòu)符號表的其他實(shí)現(xiàn)程序塊滿足最近嵌套原則內(nèi)層程序塊中的局部變量只有全部處理完成之后才進(jìn)入外層塊一旦進(jìn)入外層程序塊，內(nèi)層塊的局部變量就不會(huì)再使用了，可以從符號表中將這些符號刪除符號表中最前面的符號一定是當(dāng)前正在處理的塊中的局部變量符號表表項(xiàng)中可以不用存放塊編號，而是根據(jù)符號表表項(xiàng)在符號表中的位置來判斷。2023/5/7248.4.2程序塊結(jié)構(gòu)符號表的其他實(shí)現(xiàn)(a)處理到語句(5)時(shí)的符號表(b)處理到語句(7)時(shí)的符號表對圖8.10中的程序2023/5/7258.4.2程序塊結(jié)構(gòu)符號表的其他實(shí)現(xiàn)對圖8.10中的程序(c)處理到語句(9)時(shí)的符號表(d)處理到語句(13)時(shí)的符號表2023/5/7268.4.3C語言的符號表一個(gè)完整的C程序由一個(gè)或多個(gè)相對獨(dú)立的函數(shù)組成，函數(shù)之間的通信依靠參數(shù)傳遞和全局變量全局變量和函數(shù)名的作用域是整個(gè)程序，而其余變量的作用域則是定義它們的函數(shù)如果采取將每個(gè)函數(shù)分別編譯成目標(biāo)代碼然后連接裝配成一個(gè)可執(zhí)行程序的處理方式，則每個(gè)函數(shù)中的符號經(jīng)一遍處理即可，而且源程序中的多個(gè)函數(shù)是一個(gè)接一個(gè)處理的，不會(huì)出現(xiàn)交叉，此時(shí)可以按圖8.16的方式組織符號表。2023/5/7278.4.3C語言的符號表intg_array[10]intmain(){}intquick(){}圖8.16一個(gè)完整C程序的符號表2023/5/7288.4.4嵌套過程的符號表Pascal等允許在過程中嵌套定義其它過程programsort(input,output);procedurereadarray;begin…end{readarray};procedureexchange(i,j:integer);begin…end{exchange};procedurequicksort(m,n:integer);functionpartition(x,y:integer);

begin…end{partition};begin…end{quicksort};begin…end{sort};2023/5/7298.4.4嵌套過程的符號表2023/5/730本章小結(jié)符號表用來存放編譯器各階段收集來的各種名字的類型和特征等有關(guān)信息，并供編譯程序用于語法檢查、語義檢查、生成中間代碼及生成目標(biāo)代碼等；源程序中會(huì)出現(xiàn)各種各樣的名字，如函數(shù)名、函數(shù)參數(shù)名、函數(shù)中的局部變量名、全局變量名、數(shù)組名、結(jié)構(gòu)名