符號表的組織和管理課件

第五章:符號表的組織和管理符號表的作用符號表的主要屬性及其作用符號表的組織結(jié)構(gòu)名字的作用范圍第五章:符號表的組織和管理符號表的作用15.1符號表的作用

符號表是編譯程序中的一個重要的數(shù)據(jù)結(jié)構(gòu)，它象源程序的一個數(shù)據(jù)字典，存儲了源程序中每個名字及其屬性，使用在編譯的各個階段。(1)登記符號屬性值在源程序的各個分析階段，編譯程序根據(jù)標(biāo)識符的聲明信息收集它屬性的有關(guān)值，并把它們存放在符合表中。每種語言規(guī)則定義了不同的符號屬性；即使是同一個語言，不同的編譯程序也可能會定義并且收集不同的屬性信息?，F(xiàn)代編程語言中一般包括常數(shù)聲明、變量聲明、類型聲明和過程/函數(shù)聲明等四類聲明。對于每類聲明，編譯程序要收集、存儲和應(yīng)用的屬性完全不同。5.1符號表的作用符號表是編譯程序中的一個重要的數(shù)據(jù)結(jié)構(gòu)2例C語言的變量聲明shortinta;floatb=0.0;把標(biāo)識符a聲明為短整數(shù)型，把b聲明為浮點(diǎn)類型，而且初始化為0。那么，編譯程序?qū)γ總€變量要記錄它的類型，以便執(zhí)行類型檢查和分配存儲，比如短整型變量i占2個字節(jié)；要記錄它在存儲器中的位置（相對位移或絕對地址），以便目標(biāo)程序運(yùn)行時訪問；若像b有初始值，則還需要記錄這個初始值。例C語言的變量聲明3(2)查找符號的屬性符號表存放了源程序中的各種類型的信息，比如數(shù)值、變量類型、參數(shù)傳遞的地址等，在分析和翻譯源程序的過程中會被不斷地查詢。例如，對于上述的變量聲明，如果源程序有代碼

a+b時，就需要查找、計(jì)算表達(dá)式中運(yùn)算數(shù)的類型和值，以便計(jì)算出表達(dá)式。又如，在源程序中如果出現(xiàn)了函數(shù)調(diào)用factory(6)，編譯程序就需要查找到factory的聲明，找到實(shí)參6的地址并傳給形參n，執(zhí)行函數(shù)factory的體，并返回值等。(2)查找符號的屬性4(2)檢查符號的合法性例如，對于上述聲明，代碼a=a+b，C語言的編譯將檢查變量a和b的類型，把表達(dá)式a+b的結(jié)果轉(zhuǎn)換成短整型，僅取整數(shù)部分進(jìn)行賦值。在其它強(qiáng)類型語言，如Pascal和Ada，表達(dá)式運(yùn)算數(shù)的類型必須一致，不能進(jìn)行隱式類型轉(zhuǎn)換，對于這樣的表達(dá)式a+b，編譯程序在語義分析的過程中將發(fā)現(xiàn)并報告類型錯誤的信息。又如，面向?qū)ο笳Z言的繼承性和多態(tài)性允許同一個消息在不同的環(huán)境中調(diào)用不同的方法（函數(shù)），即調(diào)用同名但在不同的類中實(shí)現(xiàn)的方法。這就需要編譯或者運(yùn)行時在方法的符號表中查詢在參數(shù)、返回?cái)?shù)以及方法方面名字一致的實(shí)現(xiàn)。(2)檢查符號的合法性5(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)標(biāo)識符由它定義的存儲類型或它在程序中的位置來確定。首先是要確定變量存儲的區(qū)域。例如，在Java語言中，整數(shù)的類型（以及所占用的字節(jié)）有byte（1個字節(jié)）、short（2個字節(jié)）、int（4個字節(jié)）以及l(fā)ong（8個字節(jié)），而float類型占4個字節(jié)，double類型占8個字節(jié)。又如，對寄存器變量，編譯將盡可能地把它們保留在機(jī)器的寄存器當(dāng)中，以提高運(yùn)行速度；而對在一個文件中定義的外部變量，它們要在不同的源程序文件之間訪問，需要編譯程序把它們放在所有源程序文件都可以方便尋找到的存儲器的位置。其次，要根據(jù)標(biāo)識符出現(xiàn)的順序，決定標(biāo)識符在某個存儲區(qū)域中的具體位置，而有關(guān)區(qū)域的標(biāo)志及其相對位置都是作為該標(biāo)識符的語義信息存放在它的符號表中的。(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)65.2符號表的主要屬性及其作用不同的符號類別包含了不同的屬性，由于它們的信息不同，也就導(dǎo)致了符號表的組織有較大的差別。例如，數(shù)量類型的變量名字和過程名字：對于一個變量名要記錄其類型（如整型、實(shí)型、布爾型等）、占用的存儲字節(jié)以及相對與某個基準(zhǔn)位置的相對位置；對一個過程名要記錄的屬性包括參數(shù)的個數(shù)及其類型，該過程是否有返回值，過程中的變量聲明，甚至過程聲明（如果像Pascal語言允許嵌套過程聲明）等信息。

不同的程序語言規(guī)定了符號的不同性質(zhì)以及語法、語義和規(guī)則，幾種基本的符號屬性。5.2符號表的主要屬性及其作用不同的符號類別包含了不同的屬7(1)符號名語言中的符號名通常用標(biāo)識符來表示。根據(jù)語言的定義，程序中出現(xiàn)的重名標(biāo)識符定義將按照該標(biāo)識符在程序中的作用域和可視規(guī)則進(jìn)行相應(yīng)的處理。而在程序的運(yùn)行過程中，符號表中的符號名始終是唯一的標(biāo)志。在一些允許操作重載、類繼承的語言中，函數(shù)名、操作名允許重名，對于重載操作的標(biāo)識符，它們可以通過參數(shù)的個數(shù)與類型以及返回值的類型來區(qū)別；而對于操作的繼承，編譯器可以構(gòu)造繼承圖，同時保存類結(jié)構(gòu)，這樣就可以為每個操作和屬性找到唯一的定義。例如，對應(yīng)不同的參數(shù)類型，可以定義幾個求和重載函數(shù)：intsum(inta,intb)doublesum(doublea,doubleb)floatsum（floata,floatb,floatc）當(dāng)某個函數(shù)中調(diào)用到重載函數(shù)時，編譯器根據(jù)實(shí)參的類型和個數(shù)去調(diào)用相應(yīng)的函數(shù)。(1)符號名8(2)符號種屬

由于語言中符號所擁有的屬性可能不同，其組織就可以采用不同的數(shù)據(jù)結(jié)構(gòu)，可以用符號的種屬來區(qū)別每個符號的基本劃分。根據(jù)不同的語言，符號的種屬可以包括：簡單變量、結(jié)構(gòu)型變量、數(shù)組、過程、類型、類等。可以依據(jù)符號種屬的劃分來組織符號表，一種方式是為每個種屬的標(biāo)識符建立一張表，這樣，可以對符號表類似地安排組織結(jié)構(gòu)、進(jìn)行同樣的操作；另外一種方式把所有種屬的標(biāo)識符統(tǒng)一安排在一張表中，根據(jù)符號的種屬進(jìn)行條件判斷，對不同種屬的特殊型執(zhí)行不同的存儲安排和操作。(2)符號種屬9(3)符號類型

現(xiàn)代程序語言中的一個重要構(gòu)造就是數(shù)據(jù)類型（類型），它是變量標(biāo)識符的重要屬性，函數(shù)的數(shù)據(jù)類型指的是該函數(shù)返回值的數(shù)據(jù)類型。現(xiàn)代語言通常都有如下的基本類型：整型、實(shí)型、字符型、布爾型、邏輯型等；符號的類型屬性從源程序中該符號的定義中得到變量符號的數(shù)據(jù)類型屬性不但決定了該變量的數(shù)據(jù)在存儲器中的存儲格式，也規(guī)定了可以對該變量施加的操作運(yùn)算。每一個變量的類型是符號表中標(biāo)識符屬性的重要信息。(3)符號類型每一個變量的類型是符號表中標(biāo)識符屬性的重要10(4)存儲類別

大多數(shù)程序語言對變量的存儲類別采用兩種方式。一種是用關(guān)鍵字指定，例如，在FORTRAN語言中用COMMON來定義公共存儲區(qū)域，允許不同程序段都可以訪問這些數(shù)據(jù)；又如，C和C++語言規(guī)定static定義的變量屬于文件的靜態(tài)存儲變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存儲變量，這些變量在編譯時分配存儲空間，如果定義時沒有初值，編譯器還需要將它們初始化為0。另一種方式是根據(jù)定義變量的聲明在程序中的位置來決定。例如，C++規(guī)定在一個文件中定義的變量缺省為外部的，即程序的公共存儲變量；而在函數(shù)體內(nèi)缺省存儲類別關(guān)鍵字所定義的變量是內(nèi)部變量，是屬于該函數(shù)體所獨(dú)有的私有存儲變量，因而是動態(tài)地分配存儲空間。區(qū)別符號存儲類型地屬性是編譯過程中語義處理、檢查和存儲分配的重要依據(jù)。符號的存儲類別同時還決定了符號變量的作用域、可見性和它的生命周期等性質(zhì)。(4)存儲類別11(5)作用域一個標(biāo)識符在程序中起作用的范圍稱為其作用域。一般來說，定義一個符號的位置及存儲類型就決定了該符號的作用域，就是它可以出現(xiàn)的場合，可以在程序中作為參數(shù)、表達(dá)式的運(yùn)算數(shù)等被引用。C語言中外部變量的作用域是整個程序，一個外部符號的定義在整個策劃能夠許中只能出現(xiàn)一次，為了方便使用和編譯，同名標(biāo)識符的其它說明可以多次出現(xiàn)。FORTRAN語言中的COMMON變量的作用域則不是整個程序，而只能在定義這個COMMON塊的函數(shù)或過程中引用。面向?qū)ο笳Z言，如C++，的每個類都引入了一個獨(dú)立的類域。(5)作用域12作用域與可見性

標(biāo)識符的可見性從另外一個角度說明其有效性，它與作用域有一定一致性。標(biāo)識符的作用域包含可見范圍，但是，可見范圍不會超過作用域?？梢娦栽诶斫馔遣皇呛戏ǖ淖饔糜蚯短讜r十分直觀。對于外層塊域內(nèi)層塊定義的同名標(biāo)識符，在外層作用域中，內(nèi)層所定義的標(biāo)識符時不可見的，即外層所引用的是外層所定義的標(biāo)識符；同樣，在內(nèi)層作用域中，外層的標(biāo)識符將被內(nèi)層的同名標(biāo)識符所屏蔽，變得不可見，即外層中同名標(biāo)識符的可見范圍是作用域中挖去內(nèi)層塊的范圍，在內(nèi)存塊形成了作用域洞。作用域與可見性13(6)存儲分配信息編譯程序需要根據(jù)符號的存儲類別定義以及它們在程序中出現(xiàn)的位置和順序來確定每一個符號應(yīng)該分配的存儲區(qū)域及其具體位置。通常情況下，編譯為每個符號分配一個相對于某個基址的相對位移，而不是絕對的內(nèi)存地址。(6)存儲分配信息14(7)其它屬性數(shù)組內(nèi)情向量需要把描述數(shù)組屬性的信息如數(shù)組類型、維數(shù)、每個維的上下界、數(shù)組元素的首地址等登錄在符號表中，以便確定數(shù)組在存儲器占用的空間和數(shù)組元素的確定，并且完成數(shù)組的翻譯。記錄結(jié)構(gòu)型的成員信息一個記錄結(jié)構(gòu)型的變量包含若干成員，每個成員的數(shù)據(jù)類型可以彼此不同，因此，一個記錄結(jié)構(gòu)型變量在存儲分配時所占空間的大小由其成員來確定，而且，對每個成員的訪問還需要它所屬成員排列次序的屬性信息。函數(shù)或過程的形參函數(shù)或過程的形參作為其局部變量，同時又是對外部調(diào)用的接口。每個函數(shù)或過程形參的個數(shù)、類型、排列順序都體現(xiàn)了調(diào)用函數(shù)或過程時的屬性，它們都應(yīng)該反映在符號表中，以便在過程調(diào)用的時候進(jìn)行參數(shù)傳遞，并且執(zhí)行語義檢查（如處理函數(shù)名的重載）。在面相對象語言中，還必須把一個類或其超類所定義同名方法存放在一個方法表中，指向每個方法的實(shí)現(xiàn)操作，以便實(shí)現(xiàn)面相對象的繼承性質(zhì)。(7)其它屬性155.3符號表的組織結(jié)構(gòu)一個編譯程序從詞法分析、語法分析、語義分析到代碼生成的整個過程中，都要不斷地訪問和管理符號表。因此，符號表的組織管理直接關(guān)系到編譯程序的效率。三種常見的符號表的結(jié)構(gòu)：線性表、搜索樹和散列表組織線性表組織是按照符號被掃描到的先后順序填寫各個表項(xiàng)，可以用一個多維數(shù)組或多個一維數(shù)組來存放符號的信息。線性表需要兩個指針來方便管理和操作：一個指針指向該符號表的開始位置，另一個指針指向符號表的下一個可用位置。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)，可以方便、直接地實(shí)現(xiàn)上述的插入、查找和刪除三種基本操作，而且每種的操作時間都是符號表大小的線性函數(shù)，對于有N個表項(xiàng)的符號表，這些操作的平均時間都是N/2左右（算法時間復(fù)雜性為Θ(N)）。由于線性表無需附加空間，比較節(jié)省存儲。如果編譯器對處理時間要求不高，或者符號個數(shù)不大（如關(guān)鍵字），符號表就可以采用線性表結(jié)構(gòu)。5.3符號表的組織結(jié)構(gòu)一個編譯程序從詞法分析、語法分析、語16搜索樹結(jié)構(gòu)搜索樹可以在構(gòu)造符號表的同時，按照符號名的字典順序把表項(xiàng)整理排列，提高符號表查找操作的速度。這樣就可以采用折半查找的方式，加快搜索的速度。對于有N個表項(xiàng)的符號表，每次查找最多只需要做logN次比較（因此這種查找法也叫對數(shù)查找法）。但是，由于符號表在編譯過程中是邊填寫邊引用，動態(tài)地建立、更新以及刪除表項(xiàng)，這樣，每增加和刪除一個表項(xiàng)都需要對符號表進(jìn)行重新排序，這同樣浪費(fèi)時間。因此，搜索樹結(jié)構(gòu)不適合用于構(gòu)造符號表，除了需要額外的空間構(gòu)造搜索樹以外，整體而言，它們實(shí)現(xiàn)這三類操作效率不是最優(yōu)，而且刪除操作的實(shí)現(xiàn)過于復(fù)雜。

搜索樹結(jié)構(gòu)17符號表處理的關(guān)鍵問題散列組織統(tǒng)一了查詢與插入操作技術(shù)，相對來說具有較高的時空效率，為上述三種操作提供的時間基本上是常數(shù)。特別是散列表結(jié)構(gòu)符合編譯過程邊填寫邊引用符號表的特性，是實(shí)現(xiàn)符號表的最佳數(shù)據(jù)結(jié)構(gòu)，在實(shí)踐中的使用最多。

線性表結(jié)構(gòu)填表快，查詢慢；搜索樹結(jié)構(gòu)查詢快，填表慢。如何保證查詢與插入表項(xiàng)這兩個基本操作的都能高效地完成。符號表處理的關(guān)鍵問題線性表結(jié)構(gòu)填表快，查詢慢；搜索樹結(jié)構(gòu)查詢18散列方法散列方法在表項(xiàng)的存儲位置與它的關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系（哈希函數(shù)，雜湊函數(shù)，hash），使每個關(guān)鍵碼symbol與散列結(jié)構(gòu)（散列表，哈希表，雜湊表）中的唯一的存儲位置相對應(yīng)，即hash(symbol)。在搜索時，首先對表項(xiàng)的關(guān)鍵碼用哈希函數(shù)計(jì)算出對應(yīng)的表項(xiàng)的存儲位置，在散列表中按此位置取出表項(xiàng)進(jìn)行比較，若關(guān)鍵碼相等，則搜索成功。在填入表項(xiàng)時，依同樣函數(shù)計(jì)算存儲位置，并按此位置存放表項(xiàng)。由于使用這種方法進(jìn)行搜索時不必多次比較關(guān)鍵碼，因此搜速速度比較快，可以到達(dá)逼近具有此關(guān)鍵碼的表項(xiàng)的實(shí)際存放地址。散列方法19對哈希函數(shù)的基本要求①計(jì)算簡單、高效；②函數(shù)值能均勻地分布在1和N之間，③對不同的關(guān)鍵碼都返回一個代表存儲位置的不同值。構(gòu)造哈希函數(shù)的算法有許多，例如，若取N為素?cái)?shù)，就可以定義哈希函數(shù)為symbol/N的余數(shù)，其中symbol是某個符號的代碼。由于語言中的標(biāo)識符可以相互區(qū)別，它們的代碼值都是不同的。對哈希函數(shù)的基本要求20散列沖突的解決不同的關(guān)鍵碼經(jīng)過雜湊運(yùn)算以后，有可能得到相同的雜湊值，這種現(xiàn)象稱為散列沖突。一種常用的方法是鏈地址法。把有N個地址的散列表改為N個桶，桶號與散列地址一一對應(yīng)，第i（1≦i≦N）個桶號即為第i個散列地址，每個桶則是一個線性鏈表（稱為同義詞表），鏈表中的表項(xiàng)具有相同的散列函數(shù)值。若出現(xiàn)了沖突，即一個表項(xiàng)的散列值所對應(yīng)的地址已經(jīng)被占據(jù)，則需把這個表項(xiàng)放到該桶的鏈尾或鏈?zhǔn)?。散列沖突的解決215.4名字的作用范圍

名字的聲明和作用域

程序語言中的聲明是把信息聯(lián)系到名字（標(biāo)識符）的一種語法結(jié)構(gòu)。編程語言中一般包括5類聲明：常量聲明、變量聲明、類型聲明和過程/函數(shù)聲明以及類聲明常量聲明把值聯(lián)解到名字。類型聲明把名字綁定到新構(gòu)造的類型或者為已經(jīng)存在的名字創(chuàng)建一個別名。變量聲明通常把名字綁定到一個類型，同時還隱式地綁定了其它屬性。一個聲明起作用的程序部分稱為該聲明的作用域。過程中出現(xiàn)的名字，如果是在該過程的一個聲明的作用域內(nèi)，就稱為局部于該過程的；否則叫做非局部的。

5.4名字的作用范圍名字的聲明和作用域22先聲明后使用是一條在大多數(shù)程序中普遍采用的規(guī)則，它要求一個名字的聲明在程序的正文中在它的引用之前。這條規(guī)則允許編譯器一邊分析程序一邊建立符號表：一旦在程序代碼中遇到了名字引用才執(zhí)行符號表的查找操作；如果查找失敗，就出現(xiàn)了違反先聲明后使用的規(guī)則，編譯器就能發(fā)出一個適當(dāng)?shù)腻e誤消息。所以，這條規(guī)則允許一遍掃描的編譯構(gòu)造。先聲明后使用是一條在大多數(shù)程序中普遍采用的規(guī)則，它要求一個名23例

考察下列C語言代碼。它有5個塊：第一個塊是整個代碼，包含了整數(shù)i和j以及函數(shù)f的聲明;第二個塊是函數(shù)f自身，包含一個參數(shù)size；第三個塊是函數(shù)f體，有兩個變量i和temp的聲明；第四個塊是函數(shù)f內(nèi)的復(fù)合語句A，聲明了實(shí)數(shù)j；第五個塊也在函數(shù)f內(nèi)，復(fù)合語句B包含了聲明char*j函數(shù)f內(nèi)的變量size和temp在符號表中只有一個唯一的聲明，對這些名字的所有引用都參考這些聲明。名字i在函數(shù)f內(nèi)聲明為字符類型，按照最近嵌套規(guī)則，這個聲明覆蓋了函數(shù)f以外的把i聲明為int的聲明。（稱非局部聲明inti在函數(shù)f內(nèi)有一個洞）。函數(shù)f內(nèi)的兩個聲明也覆蓋了函數(shù)f以外的聲明intj。在這個例子中，直到退出局部聲明的塊程序才恢復(fù)i和j的原始聲明。inti,j;intf(intsize){ chari,temp; …… A:{ doublej; …… } …… B: { char*j; …… }}例考察下列C語言代碼。inti,j;24實(shí)現(xiàn)嵌套作用域和最近嵌套規(guī)則要實(shí)現(xiàn)嵌套作用域，符號表的插入操作不能覆蓋以前的聲明，但是，必須暫時隱藏它們，以便查找操作只能找到一個最近插入名字的聲明。同樣，刪除操作不能刪除對應(yīng)名字的所有聲明，而是刪除最近插入的那個，恢復(fù)任何先前的聲明。符號表可以這樣構(gòu)造：在每程序塊的入口處對所有聲明的名字執(zhí)行插入操作；在塊的出口處對同樣的名字執(zhí)行刪除操作。換言之，符號表的行為在處理嵌套作用域時就像一個棧結(jié)構(gòu)。實(shí)現(xiàn)嵌套作用域和最近嵌套規(guī)則25第五章:符號表的組織和管理符號表的作用符號表的主要屬性及其作用符號表的組織結(jié)構(gòu)名字的作用范圍第五章:符號表的組織和管理符號表的作用265.1符號表的作用

符號表是編譯程序中的一個重要的數(shù)據(jù)結(jié)構(gòu)，它象源程序的一個數(shù)據(jù)字典，存儲了源程序中每個名字及其屬性，使用在編譯的各個階段。(1)登記符號屬性值在源程序的各個分析階段，編譯程序根據(jù)標(biāo)識符的聲明信息收集它屬性的有關(guān)值，并把它們存放在符合表中。每種語言規(guī)則定義了不同的符號屬性；即使是同一個語言，不同的編譯程序也可能會定義并且收集不同的屬性信息。現(xiàn)代編程語言中一般包括常數(shù)聲明、變量聲明、類型聲明和過程/函數(shù)聲明等四類聲明。對于每類聲明，編譯程序要收集、存儲和應(yīng)用的屬性完全不同。5.1符號表的作用符號表是編譯程序中的一個重要的數(shù)據(jù)結(jié)構(gòu)27例C語言的變量聲明shortinta;floatb=0.0;把標(biāo)識符a聲明為短整數(shù)型，把b聲明為浮點(diǎn)類型，而且初始化為0。那么，編譯程序?qū)γ總€變量要記錄它的類型，以便執(zhí)行類型檢查和分配存儲，比如短整型變量i占2個字節(jié)；要記錄它在存儲器中的位置（相對位移或絕對地址），以便目標(biāo)程序運(yùn)行時訪問；若像b有初始值，則還需要記錄這個初始值。例C語言的變量聲明28(2)查找符號的屬性符號表存放了源程序中的各種類型的信息，比如數(shù)值、變量類型、參數(shù)傳遞的地址等，在分析和翻譯源程序的過程中會被不斷地查詢。例如，對于上述的變量聲明，如果源程序有代碼

a+b時，就需要查找、計(jì)算表達(dá)式中運(yùn)算數(shù)的類型和值，以便計(jì)算出表達(dá)式。又如，在源程序中如果出現(xiàn)了函數(shù)調(diào)用factory(6)，編譯程序就需要查找到factory的聲明，找到實(shí)參6的地址并傳給形參n，執(zhí)行函數(shù)factory的體，并返回值等。(2)查找符號的屬性29(2)檢查符號的合法性例如，對于上述聲明，代碼a=a+b，C語言的編譯將檢查變量a和b的類型，把表達(dá)式a+b的結(jié)果轉(zhuǎn)換成短整型，僅取整數(shù)部分進(jìn)行賦值。在其它強(qiáng)類型語言，如Pascal和Ada，表達(dá)式運(yùn)算數(shù)的類型必須一致，不能進(jìn)行隱式類型轉(zhuǎn)換，對于這樣的表達(dá)式a+b，編譯程序在語義分析的過程中將發(fā)現(xiàn)并報告類型錯誤的信息。又如，面向?qū)ο笳Z言的繼承性和多態(tài)性允許同一個消息在不同的環(huán)境中調(diào)用不同的方法（函數(shù)），即調(diào)用同名但在不同的類中實(shí)現(xiàn)的方法。這就需要編譯或者運(yùn)行時在方法的符號表中查詢在參數(shù)、返回?cái)?shù)以及方法方面名字一致的實(shí)現(xiàn)。(2)檢查符號的合法性30(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)標(biāo)識符由它定義的存儲類型或它在程序中的位置來確定。首先是要確定變量存儲的區(qū)域。例如，在Java語言中，整數(shù)的類型（以及所占用的字節(jié)）有byte（1個字節(jié)）、short（2個字節(jié)）、int（4個字節(jié)）以及l(fā)ong（8個字節(jié)），而float類型占4個字節(jié)，double類型占8個字節(jié)。又如，對寄存器變量，編譯將盡可能地把它們保留在機(jī)器的寄存器當(dāng)中，以提高運(yùn)行速度；而對在一個文件中定義的外部變量，它們要在不同的源程序文件之間訪問，需要編譯程序把它們放在所有源程序文件都可以方便尋找到的存儲器的位置。其次，要根據(jù)標(biāo)識符出現(xiàn)的順序，決定標(biāo)識符在某個存儲區(qū)域中的具體位置，而有關(guān)區(qū)域的標(biāo)志及其相對位置都是作為該標(biāo)識符的語義信息存放在它的符號表中的。(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)315.2符號表的主要屬性及其作用不同的符號類別包含了不同的屬性，由于它們的信息不同，也就導(dǎo)致了符號表的組織有較大的差別。例如，數(shù)量類型的變量名字和過程名字：對于一個變量名要記錄其類型（如整型、實(shí)型、布爾型等）、占用的存儲字節(jié)以及相對與某個基準(zhǔn)位置的相對位置；對一個過程名要記錄的屬性包括參數(shù)的個數(shù)及其類型，該過程是否有返回值，過程中的變量聲明，甚至過程聲明（如果像Pascal語言允許嵌套過程聲明）等信息。

不同的程序語言規(guī)定了符號的不同性質(zhì)以及語法、語義和規(guī)則，幾種基本的符號屬性。5.2符號表的主要屬性及其作用不同的符號類別包含了不同的屬32(1)符號名語言中的符號名通常用標(biāo)識符來表示。根據(jù)語言的定義，程序中出現(xiàn)的重名標(biāo)識符定義將按照該標(biāo)識符在程序中的作用域和可視規(guī)則進(jìn)行相應(yīng)的處理。而在程序的運(yùn)行過程中，符號表中的符號名始終是唯一的標(biāo)志。在一些允許操作重載、類繼承的語言中，函數(shù)名、操作名允許重名，對于重載操作的標(biāo)識符，它們可以通過參數(shù)的個數(shù)與類型以及返回值的類型來區(qū)別；而對于操作的繼承，編譯器可以構(gòu)造繼承圖，同時保存類結(jié)構(gòu)，這樣就可以為每個操作和屬性找到唯一的定義。例如，對應(yīng)不同的參數(shù)類型，可以定義幾個求和重載函數(shù)：intsum(inta,intb)doublesum(doublea,doubleb)floatsum（floata,floatb,floatc）當(dāng)某個函數(shù)中調(diào)用到重載函數(shù)時，編譯器根據(jù)實(shí)參的類型和個數(shù)去調(diào)用相應(yīng)的函數(shù)。(1)符號名33(2)符號種屬

由于語言中符號所擁有的屬性可能不同，其組織就可以采用不同的數(shù)據(jù)結(jié)構(gòu)，可以用符號的種屬來區(qū)別每個符號的基本劃分。根據(jù)不同的語言，符號的種屬可以包括：簡單變量、結(jié)構(gòu)型變量、數(shù)組、過程、類型、類等?？梢砸罁?jù)符號種屬的劃分來組織符號表，一種方式是為每個種屬的標(biāo)識符建立一張表，這樣，可以對符號表類似地安排組織結(jié)構(gòu)、進(jìn)行同樣的操作；另外一種方式把所有種屬的標(biāo)識符統(tǒng)一安排在一張表中，根據(jù)符號的種屬進(jìn)行條件判斷，對不同種屬的特殊型執(zhí)行不同的存儲安排和操作。(2)符號種屬34(3)符號類型

現(xiàn)代程序語言中的一個重要構(gòu)造就是數(shù)據(jù)類型（類型），它是變量標(biāo)識符的重要屬性，函數(shù)的數(shù)據(jù)類型指的是該函數(shù)返回值的數(shù)據(jù)類型?，F(xiàn)代語言通常都有如下的基本類型：整型、實(shí)型、字符型、布爾型、邏輯型等；符號的類型屬性從源程序中該符號的定義中得到變量符號的數(shù)據(jù)類型屬性不但決定了該變量的數(shù)據(jù)在存儲器中的存儲格式，也規(guī)定了可以對該變量施加的操作運(yùn)算。每一個變量的類型是符號表中標(biāo)識符屬性的重要信息。(3)符號類型每一個變量的類型是符號表中標(biāo)識符屬性的重要35(4)存儲類別

大多數(shù)程序語言對變量的存儲類別采用兩種方式。一種是用關(guān)鍵字指定，例如，在FORTRAN語言中用COMMON來定義公共存儲區(qū)域，允許不同程序段都可以訪問這些數(shù)據(jù)；又如，C和C++語言規(guī)定static定義的變量屬于文件的靜態(tài)存儲變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存儲變量，這些變量在編譯時分配存儲空間，如果定義時沒有初值，編譯器還需要將它們初始化為0。另一種方式是根據(jù)定義變量的聲明在程序中的位置來決定。例如，C++規(guī)定在一個文件中定義的變量缺省為外部的，即程序的公共存儲變量；而在函數(shù)體內(nèi)缺省存儲類別關(guān)鍵字所定義的變量是內(nèi)部變量，是屬于該函數(shù)體所獨(dú)有的私有存儲變量，因而是動態(tài)地分配存儲空間。區(qū)別符號存儲類型地屬性是編譯過程中語義處理、檢查和存儲分配的重要依據(jù)。符號的存儲類別同時還決定了符號變量的作用域、可見性和它的生命周期等性質(zhì)。(4)存儲類別36(5)作用域一個標(biāo)識符在程序中起作用的范圍稱為其作用域。一般來說，定義一個符號的位置及存儲類型就決定了該符號的作用域，就是它可以出現(xiàn)的場合，可以在程序中作為參數(shù)、表達(dá)式的運(yùn)算數(shù)等被引用。C語言中外部變量的作用域是整個程序，一個外部符號的定義在整個策劃能夠許中只能出現(xiàn)一次，為了方便使用和編譯，同名標(biāo)識符的其它說明可以多次出現(xiàn)。FORTRAN語言中的COMMON變量的作用域則不是整個程序，而只能在定義這個COMMON塊的函數(shù)或過程中引用。面向?qū)ο笳Z言，如C++，的每個類都引入了一個獨(dú)立的類域。(5)作用域37作用域與可見性

標(biāo)識符的可見性從另外一個角度說明其有效性，它與作用域有一定一致性。標(biāo)識符的作用域包含可見范圍，但是，可見范圍不會超過作用域?？梢娦栽诶斫馔遣皇呛戏ǖ淖饔糜蚯短讜r十分直觀。對于外層塊域內(nèi)層塊定義的同名標(biāo)識符，在外層作用域中，內(nèi)層所定義的標(biāo)識符時不可見的，即外層所引用的是外層所定義的標(biāo)識符；同樣，在內(nèi)層作用域中，外層的標(biāo)識符將被內(nèi)層的同名標(biāo)識符所屏蔽，變得不可見，即外層中同名標(biāo)識符的可見范圍是作用域中挖去內(nèi)層塊的范圍，在內(nèi)存塊形成了作用域洞。作用域與可見性38(6)存儲分配信息編譯程序需要根據(jù)符號的存儲類別定義以及它們在程序中出現(xiàn)的位置和順序來確定每一個符號應(yīng)該分配的存儲區(qū)域及其具體位置。通常情況下，編譯為每個符號分配一個相對于某個基址的相對位移，而不是絕對的內(nèi)存地址。(6)存儲分配信息39(7)其它屬性數(shù)組內(nèi)情向量需要把描述數(shù)組屬性的信息如數(shù)組類型、維數(shù)、每個維的上下界、數(shù)組元素的首地址等登錄在符號表中，以便確定數(shù)組在存儲器占用的空間和數(shù)組元素的確定，并且完成數(shù)組的翻譯。記錄結(jié)構(gòu)型的成員信息一個記錄結(jié)構(gòu)型的變量包含若干成員，每個成員的數(shù)據(jù)類型可以彼此不同，因此，一個記錄結(jié)構(gòu)型變量在存儲分配時所占空間的大小由其成員來確定，而且，對每個成員的訪問還需要它所屬成員排列次序的屬性信息。函數(shù)或過程的形參函數(shù)或過程的形參作為其局部變量，同時又是對外部調(diào)用的接口。每個函數(shù)或過程形參的個數(shù)、類型、排列順序都體現(xiàn)了調(diào)用函數(shù)或過程時的屬性，它們都應(yīng)該反映在符號表中，以便在過程調(diào)用的時候進(jìn)行參數(shù)傳遞，并且執(zhí)行語義檢查（如處理函數(shù)名的重載）。在面相對象語言中，還必須把一個類或其超類所定義同名方法存放在一個方法表中，指向每個方法的實(shí)現(xiàn)操作，以便實(shí)現(xiàn)面相對象的繼承性質(zhì)。(7)其它屬性405.3符號表的組織結(jié)構(gòu)一個編譯程序從詞法分析、語法分析、語義分析到代碼生成的整個過程中，都要不斷地訪問和管理符號表。因此，符號表的組織管理直接關(guān)系到編譯程序的效率。三種常見的符號表的結(jié)構(gòu)：線性表、搜索樹和散列表組織線性表組織是按照符號被掃描到的先后順序填寫各個表項(xiàng)，可以用一個多維數(shù)組或多個一維數(shù)組來存放符號的信息。線性表需要兩個指針來方便管理和操作：一個指針指向該符號表的開始位置，另一個指針指向符號表的下一個可用位置。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)，可以方便、直接地實(shí)現(xiàn)上述的插入、查找和刪除三種基本操作，而且每種的操作時間都是符號表大小的線性函數(shù)，對于有N個表項(xiàng)的符號表，這些操作的平均時間都是N/2左右（算法時間復(fù)雜性為Θ(N)）。由于線性表無需附加空間，比較節(jié)省存儲。如果編譯器對處理時間要求不高，或者符號個數(shù)不大（如關(guān)鍵字），符號表就可以采用線性表結(jié)構(gòu)。5.3符號表的組織結(jié)構(gòu)一個編譯程序從詞法分析、語法分析、語41搜索樹結(jié)構(gòu)搜索樹可以在構(gòu)造符號表的同時，按照符號名的字典順序把表項(xiàng)整理排列，提高符號表查找操作的速度。這樣就可以采用折半查找的方式，加快搜索的速度。對于有N個表項(xiàng)的符號表，每次查找最多只需要做logN次比較（因此這種查找法也叫對數(shù)查找法）。但是，由于符號表在編譯過程中是邊填寫邊引用，動態(tài)地建立、更新以及刪除表項(xiàng)，這樣，每增加和刪除一個表項(xiàng)都需要對符號表進(jìn)行重新排序，這同樣浪費(fèi)時間。因此，搜索樹結(jié)構(gòu)不適合用于構(gòu)造符號表，除了需要額外的空間構(gòu)造搜索樹以外，整體而言，它們實(shí)現(xiàn)這三類操作效率不是最優(yōu)，而且刪除操作的實(shí)現(xiàn)過于復(fù)雜。

搜索樹結(jié)構(gòu)42符號表處理的關(guān)鍵問題散列組織統(tǒng)一了查詢與插入操作技術(shù)，相對來說具有較高的時空效率，為上述三種操作提供的時間基本上是常數(shù)。特別是散列表結(jié)構(gòu)符合編譯過程邊填寫邊引用符號表的特性，是實(shí)現(xiàn)符號表的最佳數(shù)據(jù)結(jié)構(gòu)，在實(shí)踐中的使用最多。

線性表結(jié)構(gòu)填表快，查詢慢；搜索樹結(jié)構(gòu)查詢快，填表慢。如何保證查詢與插入表項(xiàng)這兩個基本操作的都能高效地完成。符號表處理的關(guān)鍵問題線性表結(jié)構(gòu)填表快，查詢慢；搜索樹結(jié)構(gòu)查詢43散列方法散列方法在表項(xiàng)的存儲位置與它的關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系（哈希函數(shù)，雜湊函數(shù)，hash），使每個關(guān)鍵碼symbol與散列結(jié)構(gòu)（散列表，哈希表，雜湊表）中的唯一的存儲位置相對應(yīng)，即hash(symbol)。在搜索時，首先對表項(xiàng)的關(guān)鍵碼用哈希函數(shù)計(jì)算出對應(yīng)的表項(xiàng)的存儲位置，在散列表中按此位置取出表項(xiàng)進(jìn)行比較，若關(guān)鍵碼相等，則搜索成功。在填入表項(xiàng)時，依同樣函數(shù)計(jì)算存儲位置，并按此位置存放表項(xiàng)。由于使用這種方法進(jìn)行搜索時不必多次比較關(guān)鍵碼，因此搜速速度比較快，可以到達(dá)逼近具有此關(guān)鍵碼的表項(xiàng)的實(shí)際存放地址。散列方法44對哈希函數(shù)的基本要求①計(jì)算簡單、高效；②函數(shù)值能均勻地分布在1和N之間，③對不同的關(guān)鍵碼都返回一個代表存儲位置的不同值。構(gòu)造哈希函數(shù)的算法有許多，例如，若取N為素?cái)?shù)，就可以定義哈希函數(shù)為symbol/N的余數(shù)，其中symbol是某個符號的代碼。由于語言中的標(biāo)識符可以相互區(qū)別，它們的代碼值都是不同的。對哈希函數(shù)的基本要求45散列沖突的解決不同的關(guān)鍵碼經(jīng)過