編譯原理課件06符號(hào)表的組織與管理.ppt

1、第6章 符號(hào)表的組織與管理,6.1 符號(hào)表的作用 6.2 符號(hào)表的組織 6.3 符號(hào)表的建立和查找 本章小結(jié),知識(shí)結(jié)構(gòu),6.1 符號(hào)表的作用,一.符號(hào)表作用 存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息。 編譯程序護(hù)理標(biāo)識(shí)符時(shí)主要涉及兩部分信息： 標(biāo)識(shí)符本身 與標(biāo)識(shí)符相關(guān)的信息，如標(biāo)識(shí)符的類型、種屬、作用域等等,二.符號(hào)表的功能,收集有關(guān)標(biāo)識(shí)符的屬性，并在符號(hào)表中建立符號(hào)的相應(yīng)屬性信息 例如：int A; float B5; 上下文語(yǔ)義的合法性檢查的依據(jù)： 檢查標(biāo)識(shí)符屬性在上下文中的一致性和合法性 例如，在C語(yǔ)言中同一個(gè)標(biāo)識(shí)符可作引用說(shuō)明和定義說(shuō)明 int i3,5; /定義說(shuō)明i extern

2、float i; / 引用說(shuō)明i ,例如： int i3,5; float i4,2; int i3,5; ,3.作為目標(biāo)代碼生成階段地址分配的依據(jù) 除語(yǔ)言中規(guī)定的臨時(shí)分配存儲(chǔ)的變量i外，每個(gè)符號(hào)變量 在目標(biāo)代碼生成時(shí)需要確定其在存儲(chǔ)分配的位置（主要 是相對(duì)位置） 符號(hào)變量由它被定義的存儲(chǔ)類別或被定義的位置來(lái)確定 首先要確定其被分配的區(qū)域 其次是根據(jù)變量出現(xiàn)的次序 而有關(guān)區(qū)域的標(biāo)志及相對(duì)位置都是作為該變量的語(yǔ)義信息 被收集在該變量的符號(hào)表屬性中,符號(hào)的主要屬性及作用,語(yǔ)言符號(hào)可分為：關(guān)鍵字符號(hào)、操作符符號(hào)、標(biāo)識(shí)符符號(hào) 1.符號(hào)名： 標(biāo)識(shí)符：變量的名字、函數(shù)的名字、過(guò)程的名字 通常把一個(gè)標(biāo)識(shí)符在

3、符號(hào)表中的位置的整數(shù)值稱之為該標(biāo)識(shí)符的內(nèi)部代碼 在經(jīng)過(guò)分析處理的語(yǔ)言程序中標(biāo)識(shí)符不再是一個(gè)字符串而是一個(gè)整數(shù)值,2.符號(hào)的類型： 除過(guò)程標(biāo)識(shí)符之外函數(shù)和變量標(biāo)識(shí)符都具有數(shù)據(jù)類型屬性 對(duì)于函數(shù)的數(shù)據(jù)類型指的是該函數(shù)值的數(shù)據(jù)類型?；緮?shù) 據(jù)類型有整型、實(shí)型、字符型、邏輯型及位組型等，符號(hào) 的類型屬性是在語(yǔ)言程序中該符號(hào)的定義中得到 變量符號(hào)的類型屬性決定了該變量的數(shù)據(jù)在存儲(chǔ)空間的存 儲(chǔ)格式，還決定了該變量上可以施加的運(yùn)算操作 例如t*2n、a+b,3.符號(hào)的存儲(chǔ)類別： 一種是用關(guān)鍵字指定，例如在FORTRAN中用COMMAN來(lái) 定義公共存儲(chǔ)區(qū)變量，用SAVE來(lái)定義函數(shù)或過(guò)程的內(nèi)部靜 態(tài)存儲(chǔ)變量，在

4、C語(yǔ)言中用static定義是屬于文件的靜態(tài)存 儲(chǔ)變量或?qū)傩院瘮?shù)內(nèi)部的靜態(tài)存儲(chǔ)變量，用regist定義使用 寄存器存儲(chǔ)的變量,另一種方式是根據(jù)定義變量說(shuō)明在程序中的位置來(lái)決定， 例如在C語(yǔ)言中，在函數(shù)體外默認(rèn)存儲(chǔ)類關(guān)鍵字所定義的 變量是外部變量，即程序的公共存儲(chǔ)變量，而在函數(shù)體內(nèi) 默認(rèn)存儲(chǔ)類關(guān)鍵字所定義的變量是內(nèi)部變量，即屬性該函 數(shù)所獨(dú)有的私有存儲(chǔ)變量,4.符號(hào)的作用域及可視性： 一個(gè)符號(hào)變量在程序中起作用的范圍，稱為它的作用域 一般來(lái)說(shuō)，定義該符號(hào)的位置及存儲(chǔ)類關(guān)鍵字決定了該符 號(hào)的作用域 C語(yǔ)言中一個(gè)外部變量的作用域是整個(gè)程序 FORTRAN語(yǔ)言中的公共變量的作用域并不是整個(gè)語(yǔ)言程 序，而

5、僅是那些定義說(shuō)明了它所在公共塊的函數(shù)及過(guò)程。 除非程序中所有函數(shù)及過(guò)程中全部說(shuō)明了該公共塊時(shí)，該 公共變量的作用域才是整個(gè)程序,C語(yǔ)言中，函數(shù)外說(shuō)明的定義的靜態(tài)變量的作用域是定義該 靜態(tài)變量的文件，而在函數(shù)內(nèi)部定義的靜態(tài)變量與 FORTRAN的SAVE變量一樣，其作用域僅僅是該變量定義 所在的函數(shù)或過(guò)程中 一般來(lái)說(shuō)，一個(gè)變量的作用域就是該變量可以出現(xiàn)的場(chǎng)合 ，也就是說(shuō)在某個(gè)變量作用域范圍內(nèi)該變量是可引用的， 這就是變量可視性的作用域規(guī)則。但是變量可視性不僅僅 取決于它的作用域,還有兩種情況影響到一個(gè)變量的可視性,（1）函數(shù)的形式參數(shù)：通常函數(shù)的形式參數(shù)是作為函數(shù)的內(nèi) 部變量處理的。例如： in

6、t a; int func(a,b) float a; int b; a /引用float a ,上例改寫為： int a; int func(a,b) float a; int b; a/引用float a :a /引用int a ,（2）復(fù)合語(yǔ)句分程序結(jié)構(gòu)：在一個(gè)函數(shù)中可以建立一個(gè)程序 塊，該程序塊中有自己的說(shuō)明部分和執(zhí)行部分，且這程序 塊還可以具層次的嵌套結(jié)構(gòu)，例如： int a; char a; float a; a /引用char a; 符號(hào)表屬性中除了需要符號(hào)的存儲(chǔ)類別之外還需要表示該 符號(hào)在程序結(jié)構(gòu)上被定義的層次,5.符號(hào)變量的存儲(chǔ)分配信息： 根據(jù)符號(hào)變量的存儲(chǔ)類別定義及它們出現(xiàn)

7、的位置和次序來(lái) 確定每一個(gè)變量應(yīng)分配的存儲(chǔ)區(qū)及在該區(qū)中的具體位置,（1）靜態(tài)存儲(chǔ)區(qū)：該存儲(chǔ)區(qū)單元經(jīng)定義分配后成為靜態(tài)單 元，即在整個(gè)語(yǔ)言程序運(yùn)行過(guò)程中是不可改變的。作靜態(tài) 分配的符號(hào)變量是具有整個(gè)程序運(yùn)行過(guò)程的生命周期。分 為：公共靜態(tài)區(qū)、若干個(gè)局部靜態(tài)區(qū),（2）動(dòng)態(tài)存儲(chǔ)區(qū)：根據(jù)變量的局部定義和分程序結(jié)構(gòu)，編 譯程序設(shè)置動(dòng)態(tài)存儲(chǔ)區(qū)來(lái)適應(yīng)這些局部變量的生存和消亡 。通常在符號(hào)表中存放具體位置的信息是按該變量的存儲(chǔ) 區(qū)類分別依出現(xiàn)先后的次序排列下相對(duì)該存儲(chǔ)區(qū)表頭的相 對(duì)位移量來(lái)表示的,例如，對(duì)于外部量（C語(yǔ)言為例）： int a; float b; struct cc int d; float e

8、; c; ,其中a,b,c是3個(gè)外部量，d,e是結(jié)構(gòu)分量，則在符號(hào)表中， 這5個(gè)變量項(xiàng)有關(guān)存儲(chǔ)位置的屬性信息如圖9.1所示：,6.符號(hào)的其他屬性： （1）數(shù)組內(nèi)情向量：包括數(shù)組類型、維數(shù)、各維的上下界、 數(shù)組首地址 （2）記錄結(jié)構(gòu)型的成員信息：成員及成員排列次序確定結(jié)構(gòu) 型變量存儲(chǔ)分配時(shí)所占空間的尺寸及確定該結(jié)構(gòu)成員的位置 （3）函數(shù)及過(guò)程的形參：每個(gè)函數(shù)或過(guò)程的形參個(gè)數(shù)、形參 的排列次序及每個(gè)形參的類型都體現(xiàn)了調(diào)用該函數(shù)或過(guò)程屬 性。有關(guān)函數(shù)及過(guò)程的形參屬性信息用來(lái)作調(diào)用過(guò)程的匹配 處理和語(yǔ)義檢查,6.2 符號(hào)表的組織,一.符號(hào)表的總體組織 第1種：按照屬性種類完全相同的那些符號(hào)組織在一起

9、優(yōu)點(diǎn)：每個(gè)符號(hào)表中存放符號(hào)的屬性個(gè)數(shù)和結(jié)構(gòu)完全相同 缺點(diǎn)：一個(gè)編譯程序?qū)⑼瑫r(shí)管理若干個(gè)符號(hào)表，增加了總體管理的工作量和復(fù)雜度,第2種：把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào)表中 優(yōu)點(diǎn)：總體管理非常集中單一，且不同種類符號(hào)的共同屬 性可一致地管理和處理 缺點(diǎn)：增加了符號(hào)表管理的復(fù)雜度,假設(shè)有下列3類符號(hào)及其所需之屬性：,第1種組織方法得到三張符號(hào)表如圖9.2所示：,第2種組織方法得到一張符號(hào)表如圖9.3所示：,第3種：折中方式是根據(jù)符號(hào)屬性相似程度分類組織成若 干張表，每張表中記錄的符號(hào)都有比較多的相同屬性 按折中方式重新組織上例中的3類符號(hào)，可構(gòu)成2張符號(hào)表 如圖9.4所示：,屬性值3、4合并后如

10、圖9.5所示：,二.符號(hào)表項(xiàng)的排列 1.線性組織：這種方法規(guī)定符號(hào)表中表項(xiàng)按它的符號(hào)被掃 描到的先后順序登錄,例如，有一程序中出現(xiàn)符號(hào)的情況如下： a b a d c b ,則符號(hào)表中表項(xiàng)排列將如圖9.6所示： h表示該符號(hào)表之表頭，是表的開始位置 p表示該符號(hào)表的表項(xiàng)是符號(hào)表當(dāng)前的結(jié)束位置,2.排序組織及二分法： 排序組織的符號(hào)表，就是在符號(hào)表中的表項(xiàng)按其符號(hào)的字 符代碼串（可以看成一個(gè)整數(shù)值）的值的大小從大到小 （或從小到大）排列的 關(guān)于排序表的表項(xiàng)建立及符號(hào)查找，通常采用“二分法”,對(duì)上述例子中的符號(hào)出現(xiàn)情況按排序組織得到的符號(hào)表將 如圖9.7所示：,3.散列組織： 一個(gè)符號(hào)在散列表中的

11、位置，是由對(duì)該符號(hào)進(jìn)行某種函數(shù) 操作（雜湊函數(shù)）所得到的函數(shù)值來(lái)確定的 假設(shè)選定雜湊函數(shù)fhash，對(duì)符號(hào)代碼值雜湊運(yùn)算之后得 到雜湊值是Vhash，可表示為： Vhash=fhash() 設(shè)符號(hào)的散列位置Lhash則有：Lhash=mod(Vhash,N)， 其中N為散列表的表長(zhǎng) 一個(gè)具有符號(hào)代碼值為Vsymbol的表項(xiàng)散列如圖9.8：,散列沖突：不同符號(hào)散列到同一表項(xiàng)位置的現(xiàn)象 解決辦法：表長(zhǎng)N取一個(gè)素?cái)?shù)、多次散列 雜湊函數(shù)的選取是構(gòu)造散列表的關(guān)鍵 目前編譯程序中，一般采用對(duì)符號(hào)代碼的位操作作為雜湊 函數(shù)，見得最多的是符號(hào)代碼的字符段疊加或加權(quán)疊加 以及符號(hào)代碼的對(duì)折或多折等位操作,三.關(guān)

12、鍵字域的組織 在編譯程序中，符號(hào)表的關(guān)鍵字域就是符號(hào)本身，它可以 是語(yǔ)言的保留字，操作符號(hào)或標(biāo)識(shí)符（包括變量名、函 數(shù)名、記錄結(jié)構(gòu)標(biāo)志等） 規(guī)定外部規(guī)則的目的是考慮到操作系統(tǒng)、匯編程序及其需 要聯(lián)系的系統(tǒng)之間的匹配，而規(guī)定內(nèi)部規(guī)則的目的是考 慮到編譯程序本身對(duì)標(biāo)識(shí)符的識(shí)別和區(qū)分,比如上述C語(yǔ)言的關(guān)鍵字段長(zhǎng)度可以是32個(gè)（其中31個(gè)是 存放名字，余下一個(gè)是存放字符串結(jié)束標(biāo)志，這是C 語(yǔ)言處理所需要的），如圖9.9所示：,既要保證關(guān)鍵字段的等長(zhǎng)，又要減少甚至消除冗余，采用 關(guān)鍵字池的索引結(jié)構(gòu)是可取的 例如，一組標(biāo)識(shí)符： an exemplar of key-words field,關(guān)鍵字段的組織結(jié)

13、構(gòu)如圖9.10所示：,四.其他域的組織 1.等長(zhǎng)屬性值域組織： 可以取相應(yīng)的數(shù)據(jù)類型表達(dá)屬性值 表示該符號(hào)布爾性質(zhì)的屬性域，可用1個(gè)bit位來(lái)表示，也 可用1個(gè)布爾量表示： defined 1表示已定義defined 0表示沒定義 defined true 表示已定義defined false表示沒定義 表示符號(hào)的基本數(shù)據(jù)類型可以用3個(gè)bit位來(lái)表示，也可用 1個(gè)整型量來(lái)表示（C語(yǔ)言為例）：,data-type 3個(gè)bit位 char 0 0 0 short 0 0 1 int 0 1 0 long 0 1 1 unsigned 1 0 0 float 1 0 1 double 1 1 0,d

14、ata-type 整型值 char 0 short 1 int 2 long 3 unsigned 4 float 5 double 6,若一個(gè)函數(shù)是無(wú)參的，則該函數(shù)符號(hào)項(xiàng)中“函數(shù)形參”指 針域值為“空”，若某個(gè)形式參數(shù)是它所屬函數(shù)的最后一 個(gè)形式參數(shù)，則該形參符號(hào)項(xiàng)中“函數(shù)形參”指針域值 為“空” 例如，有函數(shù)： func1 (para1,para2,para3) func2 ( ),在符號(hào)表中得到如圖9.11的表示：,若某個(gè)成員是一個(gè)結(jié)構(gòu)量的最后一個(gè)成員，則該成員符號(hào) 項(xiàng)中“結(jié)構(gòu)成員”屬性域值為空,例如，有一個(gè)結(jié)構(gòu)： struct tag1 memb1 memb2 struct tag2

15、memb3 memb4 memb5 memb6 memb7 stv;,它在符號(hào)表中如圖9.12所示：,2.不等長(zhǎng)屬性值域的組織： 數(shù)組內(nèi)情向量屬性分成：維數(shù)的個(gè)數(shù)、每個(gè)維的元素個(gè)數(shù) 設(shè)有下列兩個(gè)數(shù)組： array1 (subscrip1,subscrip2) array2 (subscrip3, subscrip4, subscrip5, subscrip6) 數(shù)組符號(hào)在符號(hào)表項(xiàng)中可以設(shè)立一個(gè)指向內(nèi)情向量空間的 指針，而在內(nèi)情向量空間記錄關(guān)于該數(shù)組的維數(shù)個(gè)數(shù)和 每一維的元素個(gè)數(shù),圖9.13表示了array1、array2在符號(hào)表中內(nèi)情向量的組織,一個(gè)數(shù)組在C語(yǔ)言中被定義為（具有n維時(shí)）： ty

16、pe arraysubscrip1subscrip2subscripn arraynumb1,arraynumb1numb2,arraynumb1 numbn-1 arraynumb1是指向n-1維的數(shù)組的指針，指向的目標(biāo)長(zhǎng) 為:subscrip2*subscripn*sizeof(type) arraynumb1numb2是指向n-2維的數(shù)組的指針，指向的 目標(biāo)長(zhǎng)為:subscrip3*subscripn*sizeof(type) arraynumb1numb2numbn-1是指向一維的數(shù)組的 指針，指向的目標(biāo)長(zhǎng)為:subscripn*sizeof(type),在C語(yǔ)言中可以定義如下一個(gè)數(shù)組

17、： type arraysubscrip2subscripn 例如，int abc34的排列和各種指針?biāo)赶虻奈恢?，?圖9.14所示：,對(duì)于C語(yǔ)言中一個(gè)一般形式定義的數(shù)組： type arrays1s2sn array 指針值addr目標(biāo)長(zhǎng)l1 array0 指針值addr 目標(biāo)長(zhǎng)l2 array00 指針值addr 目標(biāo)長(zhǎng)l3 array000 指針值addr 目標(biāo)長(zhǎng)ln 其中：addr是數(shù)組分配的地址： lk=sk*sk+1*sn*sizeof(type) k=1,2,n 而array000是該數(shù)組的第1個(gè)元素,有關(guān)指針值的計(jì)算是： arrayi1=array0+i1 arrayi1i2

18、=array00+(i1*s2+i2) arrayi1i2i3=array000+(i1*s2+i2)*s3+i3) arrayi1i2ik=array00+(i1*s2+i2)*s3+ik) (k=1,2,n-1) 數(shù)組元素的地址計(jì)算： arrayi1i2in= array00+(i1*s2+i2)*s3+in)*sizof(type),用成員的索引結(jié)構(gòu)來(lái)構(gòu)造結(jié)構(gòu)量，這時(shí)結(jié)構(gòu)標(biāo)志符號(hào)在符 號(hào)表項(xiàng)中設(shè)一個(gè)指向成員索引區(qū)的指針，索引區(qū)包含兩 種屬性信息：該結(jié)構(gòu)的空間尺寸、成員索引信息 上述結(jié)構(gòu)例子struct tag1的不等長(zhǎng)索引結(jié)構(gòu)可用圖9.15所 示的組織,在一個(gè)符號(hào)表中若有若干個(gè)用位信息表

19、示的屬性時(shí)，可把 他們組織到一起，甚至可用一個(gè)整型數(shù)來(lái)表達(dá)這樣的幾 個(gè)位信息屬性。這種組織與上述合并不同的是各屬性有 各自的表項(xiàng)中的位置,例如，有下列的一些符號(hào)屬性： 該變量符號(hào)是否已初始化 該符號(hào)是否是結(jié)構(gòu)成員 該符號(hào)是否是標(biāo)號(hào) 該符號(hào)是否是保留字,這些屬性都可用1個(gè)信息位表示，在符號(hào)表中可以把它們 組織在一個(gè)整型字段中作為一個(gè)屬性域，而其中相應(yīng)的 信息位置表示上述相應(yīng)的屬性，我們稱這種域?yàn)閺?fù)合屬 性域，如圖9.16所示：,五.下推鏈域的組織 為實(shí)現(xiàn)這種同名標(biāo)識(shí)符的語(yǔ)義功能，符號(hào)表中需要設(shè)立下 推鏈域的組織 下推鏈域的組織要求在進(jìn)入一個(gè)內(nèi)層結(jié)構(gòu)并發(fā)生重名標(biāo)識(shí) 符定義時(shí)，需把當(dāng)前符號(hào)表中外層的

20、該符號(hào)表項(xiàng)下推到 下推鏈中而在符號(hào)表被下推的表項(xiàng)處建立內(nèi)層的同名識(shí) 符的表項(xiàng) 例如，設(shè)有一個(gè)程序（C語(yǔ)言程序）如圖9.17所示：,當(dāng)逐個(gè)退出分程序時(shí)，下推鏈被逐次回推到符號(hào)表項(xiàng)中， 其具體結(jié)構(gòu)如圖9.18所示：,6.3 符號(hào)表的建立和查找,一.符號(hào)表的初始化 在編譯過(guò)程中某個(gè)時(shí)刻，符號(hào)表的狀態(tài)反映了該時(shí)刻被編譯的語(yǔ)言程序正被編譯的位置的狀態(tài)。具體來(lái)說(shuō)主要是反映了在該時(shí)刻語(yǔ)言程序中可視標(biāo)識(shí)符的狀態(tài) 符號(hào)表的初始化，就是在對(duì)語(yǔ)言程序開始編譯的時(shí)刻，定義建立符號(hào)表的初始狀態(tài),1.符號(hào)表的表長(zhǎng)是漸增變化的情況： 在9.3.2中提到的線性組織和二分法組織的符號(hào)表，其表的長(zhǎng) 度在編譯開始時(shí)通常為0,而隨著

21、符號(hào)的逐步登錄，表長(zhǎng)增長(zhǎng) 按這類方法組織的符號(hào)表，其初始化方法只需將表尾推向表 頭即可，如圖9.19所示：,2.符號(hào)表的表長(zhǎng)是確定的情況： 在9.3.2中提到的散列組織的符號(hào)表，其表長(zhǎng)通常是確定的， 這時(shí)表長(zhǎng)并不反映已登錄的表項(xiàng)個(gè)數(shù)，是否已有表項(xiàng)登錄 是取決于該符號(hào)表中是否存在已有表項(xiàng)值的表項(xiàng) 因此，對(duì)這類符號(hào)表的初始化方法，需要將表中全部表項(xiàng)值 清除。由于通常表示表項(xiàng)值的關(guān)鍵因素是登錄標(biāo)識(shí)符的符 號(hào)欄（也可能是指向符號(hào)的指針），因此在清除表項(xiàng)值時(shí) ，實(shí)際上可僅清除符號(hào)欄,圖9.20表示定長(zhǎng)符號(hào)表初始化的狀態(tài)：,二.符號(hào)的登錄 當(dāng)編譯程序從語(yǔ)言程序中獲得一個(gè)標(biāo)識(shí)符符號(hào)并確定該符號(hào) 在符號(hào)表中還

22、不存在，就要將此符號(hào)登錄在符號(hào)表中 登錄符號(hào)到符號(hào)表中，首先要確定登錄的位置,但對(duì)于線性方法和二分方法組織的符號(hào)表，首先要在符號(hào)表 中創(chuàng)立一個(gè)新的表項(xiàng)，通常該表的尾指針指向的表項(xiàng)是作 為新創(chuàng)建的表項(xiàng)，而尾指針推向下一個(gè)備用表項(xiàng) 對(duì)于線性組織符號(hào)表，該新創(chuàng)建的表項(xiàng)就是登錄符號(hào)的表項(xiàng),圖9.21表示登錄新符號(hào)symbol i的前后情況：,對(duì)于二分法組織的符號(hào)表，在創(chuàng)建了新的表項(xiàng)后，根據(jù)登 錄符號(hào)在符號(hào)表中按詞典排序所確定的位置，把該位置 以后的所有原表項(xiàng)下移一個(gè)表項(xiàng)的位置，然后在選定位 置登錄新符號(hào),圖9.22表示登錄新符號(hào)symbol k的前后情況：,symbol k,對(duì)于散列表，新符號(hào)的登錄是

23、通過(guò)雜湊算法決定登錄表項(xiàng) 的位置 一個(gè)符號(hào)表項(xiàng)的登錄基本的是該符號(hào)的名字登錄，還有屬 性登錄，名字屬性大都取決于編譯程序獲得某個(gè)符號(hào)時(shí) 編譯所處的程序掃描點(diǎn)的狀態(tài),下例中符號(hào)a的屬性取決于編譯程序掃描到anm時(shí)的有 關(guān)狀態(tài)：,類型屬性： 存儲(chǔ)類別屬性： 符號(hào)作用域?qū)傩裕?存儲(chǔ)分配屬性： 數(shù)組內(nèi)情向量屬性：,三.符號(hào)的查找 查找符號(hào)表的目的是建立或確認(rèn)該符號(hào)的語(yǔ)義屬性 符號(hào)表的查找算法：順序查找、折半查找、雜湊查找,四.符號(hào)表中分程序結(jié)構(gòu)層次的管理 （1）分表結(jié)構(gòu)： 分表結(jié)構(gòu)的組織管理的基本思想：每當(dāng)編譯程序掃描到一個(gè) 分程序結(jié)構(gòu)開始時(shí)，為該分程序建立一張符號(hào)表，在該分程 序中定義的標(biāo)識(shí)符，都被

24、登錄在該符號(hào)表中。而當(dāng)編譯程序 掃描到一個(gè)分程序的結(jié)束時(shí)，編譯程序釋放為該分程序所建 立的符號(hào)表,編譯程序掃描到某個(gè)分程序時(shí)，符號(hào)的登錄是在為該分程 序所建立的符號(hào)表中進(jìn)行，而符號(hào)的查找是首先在該分程 序符號(hào)表中進(jìn)行；若沒有查到，再根據(jù)分程序的層次結(jié)構(gòu) ，逐層向外地依次查找各層符號(hào)表。一直到查到為止。若 所有符號(hào)表都已查完仍未找到，則表示有詞法錯(cuò)誤,圖9.23給出了一個(gè)分程序結(jié)構(gòu)的例子：,圖9.24給出了相應(yīng)的分表結(jié)構(gòu)組織：,（2）單表結(jié)構(gòu)： 單表結(jié)構(gòu)的組織管理的基本思想是：所有分程序中定義的標(biāo) 識(shí)符都集中在單張符號(hào)表中 在這種單表組織的符號(hào)表中，有三個(gè)主要的特定要求： 首先，為了標(biāo)志一個(gè)符號(hào)

25、所屬的分程序?qū)哟?，在符?hào)表中可 設(shè)立一個(gè)屬性域用來(lái)登錄符號(hào)所在分程序的層次,其次，在編譯程序掃描進(jìn)入一個(gè)分程序時(shí)，表示分程序?qū)哟?的狀態(tài)量要增加一層，使進(jìn)入分程序后定義的標(biāo)識(shí)符登錄 符號(hào)表時(shí)，有相應(yīng)的層次量作為層次屬性登錄 最后，對(duì)于具有分程序結(jié)構(gòu)的源程序，在不同的分程序中（ 指嵌套的分程序中）允許定義重名的標(biāo)識(shí)符,編譯過(guò)程中符號(hào)表的動(dòng)態(tài)管理過(guò)程如下： 圖9.25表示編譯程序掃描進(jìn)入第1層分程序后單表結(jié)構(gòu)的 符號(hào)表情況,圖9.26表示編譯程序掃描進(jìn)入第2層分程序后單表結(jié)構(gòu)的符 號(hào)表情況：,圖9.27表示編譯程序掃描進(jìn)入第3層分程序后單表結(jié)構(gòu)的符 號(hào)表情況：,圖9.28表示編譯程序掃描進(jìn)入第4層分程序后單表結(jié)