第六章 符號表的組織與管理

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

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

，6

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

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

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

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

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

X[SP]=活動記錄基地址(SP)+相對地址臨時單元內(nèi)情向量簡單局部變量形式單元參數(shù)個數(shù)返回地址老SP值TOPSP局部數(shù)據(jù)連接數(shù)據(jù)簡單棧式存儲分配示例：P的活動記錄Main的活動記錄全局?jǐn)?shù)據(jù)區(qū)C程序運行時的存儲空間組織TOPSPSP指向現(xià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的活動記錄P的活動記錄TOPSP簡單棧式存儲分配示例：P的活動記錄Main的活動記錄全局?jǐn)?shù)據(jù)區(qū)C程序運行時的存儲空間組織SP指向現(xià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的活動記錄P的活動記錄P的活動記錄TOPSPC的過程調(diào)用、過程進入、過程返回過程調(diào)用的四元式系列：

parT1……parTncallP,n每個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ù)個數(shù))JSRP（轉(zhuǎn)子指令，轉(zhuǎn)向P的第一條指令）返回值對應(yīng)指令：return(E)過程返回時，應(yīng)先執(zhí)行指令：

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

SP=TOP+1（定義新SP）

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

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

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

(4)*EFT4T4(5)+T3T4T5T5(6)=T5XSTACKk對于引進的五個臨時