第六章 符號(hào)表的組織與管理

第六章符號(hào)表的組織與管理符號(hào)表(SymbolTable）作用：記錄源程序中各種標(biāo)識(shí)符的屬性和特征等有關(guān)信息。內(nèi)容：名字，有關(guān)信息（種屬、類型等）表項(xiàng)的建立：運(yùn)用：語義檢查、產(chǎn)生中間代碼、地址分配的依據(jù)6.1符號(hào)表的作用在編譯的各個(gè)階段，每當(dāng)遇到標(biāo)識(shí)符時(shí)，都要查找符號(hào)表。因此，合理組織符號(hào)表，使其占用的存儲(chǔ)空間較少、易于訪問，對(duì)提高編譯的效率很重要。根據(jù)說明語句的功能，記錄標(biāo)識(shí)符的相關(guān)信息為上下文語義的合法性檢查提供依據(jù)生成目標(biāo)代碼時(shí)，符號(hào)表的內(nèi)容是分配存儲(chǔ)地址的依據(jù)

符號(hào)表的表項(xiàng)包括名字欄和信息欄查填符號(hào)表一般通過匹配名字來實(shí)現(xiàn)。對(duì)符號(hào)表的操作一般有：對(duì)給定的名字，查詢其是否已在表中；添加新名字；訪問某個(gè)名字的某些信息；添加或更新某個(gè)名字的某些信息；刪除一個(gè)或一組無用的項(xiàng)。6.2符號(hào)表的組織符號(hào)表的內(nèi)容:名字欄、信息欄符號(hào)表的信息欄中記錄了每個(gè)名字的有關(guān)性質(zhì)，如類型、種屬、大小、以及相對(duì)數(shù)等。不同的程序語言對(duì)于名字性質(zhì)的定義各有不同。一個(gè)名字的有關(guān)信息常常是分幾次填入信息欄中的。符號(hào)表中信息欄的具體組織取決于所翻譯的具體的源語言和目標(biāo)機(jī)器。6.2符號(hào)表的組織直接方式：表中各項(xiàng)各欄的長(zhǎng)度固定。間接方式：符號(hào)表中的相應(yīng)欄存指針，指向存儲(chǔ)具體信息的位置。符號(hào)表NAMEINFORMATION

，6

，4SAMPLELOOP6.2符號(hào)表的組織按標(biāo)識(shí)符的種屬分別建立符號(hào)表。簡(jiǎn)單變量名表數(shù)組名表函數(shù)名表．．．符號(hào)表信息欄的組織方式：固定信息欄內(nèi)容的符號(hào)表；僅記載信息地址的間接方式。設(shè)置信息欄內(nèi)容時(shí)，要考慮標(biāo)識(shí)符的作用域。

符號(hào)表的實(shí)現(xiàn)：可采用鏈?zhǔn)奖斫Y(jié)構(gòu)：所有的標(biāo)識(shí)符構(gòu)成一個(gè)標(biāo)識(shí)符鏈所有函數(shù)名構(gòu)成一條函數(shù)鏈每個(gè)函數(shù)都有一條函數(shù)參數(shù)鏈每個(gè)函數(shù)都有一條局部變量鏈表單元的具體結(jié)構(gòu)如P140-1416.3符號(hào)表的建立與查找編譯工作的相當(dāng)一大部分時(shí)間是花費(fèi)在查填符號(hào)表上。如何構(gòu)造和處理符號(hào)表？線性表、二叉樹、Hash表1、線性表實(shí)現(xiàn)最簡(jiǎn)單，節(jié)省空間，效率低按名字出現(xiàn)的順序填寫各個(gè)項(xiàng)；查找時(shí)可以從表頭順序查找，也可以從表尾反序查找。平均查找時(shí)間n/2改進(jìn)方法：自適應(yīng)線性表2、二分查找與二叉樹在構(gòu)造表的時(shí)候，各項(xiàng)按名字的“大小”順序排列；查找時(shí)可用對(duì)折法；最長(zhǎng)查找時(shí)間為1+log2N。缺點(diǎn)：順序化費(fèi)時(shí)。把符號(hào)表組織成一棵二叉樹。比對(duì)折查找效率低一點(diǎn)、需要附加的存儲(chǔ)空間，但順序化效率更高。P142圖6.7圖6.83、Hash表與查找使查表與填表都能高效地進(jìn)行。引進(jìn)Hash函數(shù)，函數(shù)的構(gòu)造要求：計(jì)算簡(jiǎn)單高效，函數(shù)值分布均勻，有好的解決“地址沖突”的方法。效率與裝填因子有關(guān)。使用Hash表通過間接方式查填符號(hào)表P143圖6.9第8章運(yùn)行時(shí)的存儲(chǔ)組織與管理在生成目標(biāo)代碼前，需要把程序靜態(tài)的正文和實(shí)現(xiàn)這個(gè)程序的運(yùn)行時(shí)的環(huán)境聯(lián)系起來。存儲(chǔ)組織與管理：靜態(tài)、動(dòng)態(tài)（棧式、堆式）8.1概述生成目標(biāo)代碼前要進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配。運(yùn)行時(shí)的環(huán)境：目標(biāo)計(jì)算機(jī)的存儲(chǔ)器和寄存器結(jié)構(gòu)，管理存儲(chǔ)器并保存執(zhí)行過程所需的信息。3種存儲(chǔ)環(huán)境：完全靜態(tài)、基于棧的、基于堆的目標(biāo)程序運(yùn)行時(shí)所需的存儲(chǔ)空間：程序的各種數(shù)據(jù)對(duì)象的存儲(chǔ)、過程調(diào)用所需的連接單元、輸入/輸出所需的緩沖區(qū)、保留中間結(jié)果和傳遞參數(shù)的臨時(shí)單元。運(yùn)行時(shí)存儲(chǔ)器的劃分為使目標(biāo)程序能夠運(yùn)行,要從操作系統(tǒng)中獲得一塊存儲(chǔ)空間。并對(duì)這塊空間進(jìn)行劃分，以便存放目標(biāo)代碼、數(shù)據(jù)對(duì)象、棧等。目標(biāo)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)棧堆用來管理過程的活動(dòng)存放動(dòng)態(tài)數(shù)據(jù)

活動(dòng)記錄活動(dòng)記錄(activationrecord)：為了管理過程在一次執(zhí)行中所需要的信息，而使用的一個(gè)連續(xù)的存儲(chǔ)塊。TOPSP參數(shù)空間返回地址局部數(shù)據(jù)的空間局部臨時(shí)變量的空間

存儲(chǔ)分配策略靜態(tài)分配策略：編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，并且在運(yùn)行時(shí)始終保持不變。棧式動(dòng)態(tài)分配策略：在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，“先申請(qǐng)后歸還,后申請(qǐng)先歸還”堆式動(dòng)態(tài)分配策略：運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，更便于申請(qǐng)和歸還。按需申請(qǐng)和歸還。

具體采用那種分配策略，取決于程序語言關(guān)于名稱的作用域和生存期的定義規(guī)則。8.2靜態(tài)存儲(chǔ)分配在編譯時(shí)就確定目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間，和每個(gè)數(shù)據(jù)項(xiàng)的單元地址。例如，F(xiàn)ORTRAN語言，適合靜態(tài)分配。靜態(tài)存儲(chǔ)分配是一種非常簡(jiǎn)單的策略。目標(biāo)代碼靜態(tài)數(shù)據(jù)區(qū)P169圖8.48.3棧式存儲(chǔ)分配考慮一種語言：允許過程的遞歸調(diào)用。(如C)這樣，關(guān)于局部變量的存儲(chǔ)分配，可以直接采用棧式存儲(chǔ)分配策略。把存儲(chǔ)空間組織成一個(gè)棧，運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程，就把它的活動(dòng)記錄壓入棧，從而在棧頂形成過程工作時(shí)的數(shù)據(jù)區(qū)；該活動(dòng)結(jié)束時(shí)，把它的活動(dòng)記錄彈出棧。過程的每一次調(diào)用都需要一個(gè)活動(dòng)記錄。8.3.1簡(jiǎn)單棧式存儲(chǔ)分配沒有分程序結(jié)構(gòu)，過程定義不允許嵌套，但允許過程的遞歸調(diào)用。該語言可以采用簡(jiǎn)單棧式存儲(chǔ)分配策略。(如C語言)C語言的活動(dòng)記錄C的非局部量可采用靜態(tài)分配策略，編譯時(shí)確定其地址；局部變量和形式參數(shù)運(yùn)行時(shí)在棧上的絕對(duì)地址：

X[SP]=活動(dòng)記錄基地址(SP)+相對(duì)地址臨時(shí)單元內(nèi)情向量簡(jiǎn)單局部變量形式單元參數(shù)個(gè)數(shù)返回地址老SP值TOPSP局部數(shù)據(jù)連接數(shù)據(jù)簡(jiǎn)單棧式存儲(chǔ)分配示例：P的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)區(qū)C程序運(yùn)行時(shí)的存儲(chǔ)空間組織TOPSPSP指向現(xiàn)行過程活動(dòng)記錄的起點(diǎn)；TOP始終指向棧頂單元。P170圖8.6圖8.7Intx=2;Voidp(int);Voidq(intn);{…p(n);…}Voidp(intm){…if(m>1){q(m-1);x--;p(m-1);}

…}Main(){p(x);}Q的活動(dòng)記錄P的活動(dòng)記錄TOPSP簡(jiǎn)單棧式存儲(chǔ)分配示例：P的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)區(qū)C程序運(yùn)行時(shí)的存儲(chǔ)空間組織SP指向現(xiàn)行過程活動(dòng)記錄的起點(diǎn)；TOP始終指向棧頂單元。P170圖8.6圖8.7Intx=2;Voidp(int);Voidq(intn);{…p(n);…}Voidp(intm){…if(m>1){q(m-1);x--;p(m-1);}

…}Main(){p(x);}Q的活動(dòng)記錄P的活動(dòng)記錄P的活動(dòng)記錄TOPSPC的過程調(diào)用、過程進(jìn)入、過程返回過程調(diào)用的四元式系列：

parT1……parTncallP,n每個(gè)parTi可以翻譯成目標(biāo)指令：

(i+3)[TOP]=Ti

（傳值）或(i+3)[TOP]=addr(Ti)(傳地址)callP,n翻譯成目標(biāo)指令：

1[TOP]=SP（保存現(xiàn)行SP）

3[TOP]=n(傳送參數(shù)個(gè)數(shù))JSRP（轉(zhuǎn)子指令，轉(zhuǎn)向P的第一條指令）返回值對(duì)應(yīng)指令：return(E)過程返回時(shí)，應(yīng)先執(zhí)行指令：

TOP=SP-1SP=0[SP]X=2[TOP]UJ0[X]轉(zhuǎn)進(jìn)過程P后,首先應(yīng)執(zhí)行指令：

SP=TOP+1（定義新SP）

1[SP]=返回地址(保護(hù)返回地址)TOP=TOP+L(定義新TOP)L(活動(dòng)記錄的大小)在編譯時(shí)可以靜態(tài)地計(jì)算出來。8.3.2嵌套過程語言的棧式存儲(chǔ)分配允許過程嵌套定義的語言(如Pascal)層數(shù)：嵌套的層次主程序的層數(shù)為0直接外層過程、內(nèi)層過程層數(shù)作為過程名的一個(gè)屬性levellevel遇過程定義開始則+1，遇過程定義結(jié)束則-1對(duì)于Pascal語言，在運(yùn)行時(shí)，過程中的局部變量和形式參數(shù)在棧上的存儲(chǔ)可以用簡(jiǎn)單棧式存儲(chǔ)分配來解決；但由于允許嵌套，非局部量的訪問就比較復(fù)雜。圖8.8程序非局部名字的訪問的實(shí)現(xiàn)為了在活動(dòng)記錄中查找非局部名字所對(duì)應(yīng)的存儲(chǔ)單元，過程運(yùn)行時(shí)必須知道它的所有外層過程的最新活動(dòng)記錄的地址；由于允許遞歸，過程的活動(dòng)記錄的位置往往是變動(dòng)的。跟蹤每個(gè)外層過程的最新活動(dòng)記錄的位置：通過嵌套層次顯示表（display）嵌套層次顯示表(display)和活動(dòng)記錄引用一個(gè)指針數(shù)組，嵌套層次顯示表：每進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)，建立一張display。display的體積在編譯時(shí)可以靜態(tài)確定。非局部量的絕對(duì)地址的計(jì)算：display[靜態(tài)層數(shù)]+相對(duì)地址為便于處理，將display作為活動(dòng)記錄的一部分。臨時(shí)單元內(nèi)情向量局部變量display形參單元參數(shù)個(gè)數(shù)全局display地址返回地址動(dòng)態(tài)鏈(老SP值)TOPSP通過display訪問非局部變量：在現(xiàn)行過程中引用某一外層過程（層數(shù)為k）的變量X，變址指令得到X的值。當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2如何建立自己的display表？(若P2的層數(shù)為I2，則其display表含有I2+1項(xiàng))方法：從P1的display表自底向上地取I2項(xiàng)，再添上進(jìn)入P2后新建立的SP值，就構(gòu)成了P2的display表。圖8.9、8.10、8.118.4堆式動(dòng)態(tài)存儲(chǔ)分配允許用戶自由地申請(qǐng)數(shù)據(jù)空間和歸還數(shù)據(jù)空間?？臻g被分成許多大小不一的“塊”分配時(shí)必須考慮以下情況：當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，分配哪一塊比N大的給它；當(dāng)運(yùn)行程序要求一塊體積為N的空間，沒有比N大的塊，但所有空閑塊的總和比N大；當(dāng)運(yùn)行程序要求一塊體積為N的空間，但所有空閑塊的總和也不夠N。堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn)1.定長(zhǎng)塊管理:

初始化時(shí)，將堆存儲(chǔ)空間分成長(zhǎng)度相等的若干塊，每塊中指定一個(gè)鏈域。占用占用占用空閑空閑空閑AVAILABLE歸還時(shí)，把所歸還的塊插入鏈表。如，插到鏈表頭。占用空閑占用空閑空閑空閑AVAILABLE2.變長(zhǎng)塊管理根據(jù)需要分配長(zhǎng)度不同的存儲(chǔ)塊，初始化時(shí)堆存儲(chǔ)空間是一個(gè)整塊。初次分配時(shí)，按需要分割整塊來分配；歸還時(shí)，需要將新歸還的塊與現(xiàn)有空閑塊進(jìn)行合并，不能合并時(shí)，鏈成一個(gè)鏈表；再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿足要求的一塊進(jìn)行分配。有多個(gè)滿足要求的塊時(shí)，按以下三種策略進(jìn)行分配：(1)首次匹配法：(2)最優(yōu)匹配法：(3)最差匹配法：(2)適用于請(qǐng)求分配的內(nèi)存大小范圍較廣的情況；(3)適用于請(qǐng)求分配的內(nèi)存大小范圍較窄的情況。8.5臨時(shí)變量的存儲(chǔ)分配臨時(shí)變量是編譯時(shí)為暫存中間結(jié)果而引進(jìn)的，對(duì)于代碼優(yōu)化很有好處。都是簡(jiǎn)單變量。如果兩個(gè)臨時(shí)變量名的作用域不相交，則可以共用一個(gè)存儲(chǔ)單元。因此，對(duì)新的臨時(shí)變量名分配存儲(chǔ)單元時(shí)，只有當(dāng)它的作用域與所有已分配的臨時(shí)變量的作用域沖突時(shí)，才分配一個(gè)新單元。此時(shí)，單元的分配信息包括相應(yīng)變量名的作用域。例如，用于暫存表達(dá)式中間結(jié)果的臨時(shí)變量，只存在一次定值和一次引用，并且在定值和引用之間不存在分叉轉(zhuǎn)移。其作用域的確定非常簡(jiǎn)單，因而其存儲(chǔ)分配也可以用一種非常簡(jiǎn)易的辦法（棧）實(shí)現(xiàn)。臨時(shí)變量的棧式地址分配：賦值語句：X=A*B-C*D+E*F四元式序列：四元式臨時(shí)變量名

(1)*ABT1T1(2)*CDT2T2(3)-T1T2T3T3

(4)*EFT4T4(5)+T3T4T5T5(6)=T5XSTACKk對(duì)于引進(jìn)的五個(gè)臨時(shí)