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

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

3、置。符號表 NAMEINFORMATION ，6 ，4S A MP L E L O O P6.2 符號表的組織符號表的組織按標識符的種屬分別建立符號表。 簡單變量名表數組名表函數名表符號表信息欄的組織方式：固定信息欄內容的符號表；僅記載信息地址的間接方式。設置信息欄內容時，要考慮標識符的作用域。 符號表的實現：符號表的實現：可采用鏈式表結構：所有的標識符構成一個標識符鏈所有函數名構成一條函數鏈每個函數都有一條函數參數鏈每個函數都有一條局部變量鏈表單元的具體結構如P140-141 P140-141 6.3 符號表的建立與查找符號表的建立與查找編譯工作的相當一大部分時間是花費在查填符號表上。如何構

4、造和處理符號表？線性表、二叉樹、Hash表1、 線性表線性表實現最簡單，節省空間，效率低按名字出現的順序填寫各個項；查找時可以從表頭順序查找，也可以從表尾反序查找。平均查找時間n/2改進方法：自適應線性表2、二分查找與二叉樹、二分查找與二叉樹在構造表的時候，各項按名字的“大小”順序排列；查找時可用對折法對折法；最長查找時間為1+log2N。缺點：順序化費時。把符號表組織成一棵二叉樹。比對折查找效率低一點、需要附加的存儲空間，但順序化效率更高。P142 圖6.7 圖6.83、Hash表與查找表與查找使查表與填表都能高效地進行。引進HashHash函數函數，函數的構造要求：計算簡單高效，函數值分布

5、均勻，有好的解決“地址沖突”的方法。效率與裝填因子有關。使用Hash表通過間接方式查填符號表P143 P143 圖圖6.96.9第第8章章 運行時的存儲組織與管理運行時的存儲組織與管理n在生成目標代碼前，需要把程序靜態的正文和實現這個程序的運行時的環境聯系起來。n存儲組織與管理：靜態、 動態（棧式、堆式）8.1 概述概述生成目標代碼前要進行目標程序運行環境的設計和數據空間的分配。n運行時的環境：目標計算機的存儲器和寄存器結構，管理存儲器并保存執行過程所需的信息。3種存儲環境：完全靜態、基于棧的、基于堆的n目標程序運行時所需的存儲空間：程序的各種數據對象的存儲、過程調用所需的連接單元、輸入/輸出

6、所需的緩沖區、保留中間結果和傳遞參數的臨時單元。運行時存儲器的劃分運行時存儲器的劃分為使目標程序能夠運行,要從操作系統中獲得一塊存儲空間。并對這塊空間進行劃分，以便存放目標代碼、數據對象、棧等。目標代碼區靜態數據區棧堆用來管理過程的活動存放動態數據 活動記錄活動記錄活動記錄(activation record)：為了管理過程在一次執行中所需要的信息，而使用的一個連續的存儲塊。TOPSP參數空間返回地址局部數據的空間局部臨時變量的空間 存儲分配策略存儲分配策略靜態分配策略靜態分配策略：編譯時對所有數據對象分配固定的存儲單元，并且在運行時始終保持不變。棧式動態分配策略棧式動態分配策略：在運行時把存

7、儲器作為一個棧進行管理，“先申請后歸還,后申請先歸還”堆式動態分配策略：式動態分配策略：運行時把存儲器組織成堆結構，更便于申請和歸還。按需申請和歸還。 具體采用那種分配策略，取決于程序語言關具體采用那種分配策略，取決于程序語言關于名稱的作用域和生存期的定義規則。于名稱的作用域和生存期的定義規則。8.2 靜態存儲分配靜態存儲分配在編譯時就確定目標程序運行時的數據空間，和每個數據項的單元地址。例如，FORTRAN語言，適合靜態分配。靜態存儲分配是一種非常簡單的策略。目標代碼靜態數據區P169 P169 圖圖8.48.48.3 棧式存儲分配棧式存儲分配考慮一種語言：允許過程的遞歸調用。(如C)這樣，

8、關于局部變量的存儲分配，可以直接采用棧式存儲分配策略。把存儲空間組織成一個棧，運行時，每當進入一個過程，就把它的活動記錄壓入棧，從而在棧頂形成過程工作時的數據區；該活動結束時，把它的活動記錄彈出棧。過程的每一次調用都需要一個活動記錄。8.3.1 簡單棧式存儲分配簡單棧式存儲分配沒有分程序結構，過程定義不允許嵌套，但允許過程的遞歸調用。該語言可以采用簡單棧式存儲分配策略。 (如C語言) C語言的活動記錄語言的活動記錄C的非局部量可采用靜態分配策略，編譯時確定其地址；局部變量和形式參數運行時在棧上的絕對地址： XSP=活動記錄基地址(SP)+相對地址臨時單元內情向量簡單局部變量形式單元參數個數返回

9、地址老SP值TOPSP局部數據連接數據簡單棧式存儲分配示例：簡單棧式存儲分配示例：P的活動記錄Main的活動記錄全局數據區C程序運行時的存儲空間組織TOP SPSP指向現行過程活動記錄的起點；TOP始終指向棧頂單元。P170P170圖圖8.6 8.6 圖圖8.78.7Int x=2;Void p(int);Void q(int n); p(n); Void p(int m) if(m1) q(m-1);x-;p(m-1); Main( ) p(x); Q的活動記錄P的活動記錄TOP SP簡單棧式存儲分配示例：簡單棧式存儲分配示例：P的活動記錄Main的活動記錄全局數據區C程序運行時的存儲空間組

10、織SP指向現行過程活動記錄的起點；TOP始終指向棧頂單元。P170P170圖圖8.6 8.6 圖圖8.78.7Int x=2;Void p(int);Void q(int n); p(n); Void p(int m) if(m1) q(m-1);x-;p(m-1); Main( ) p(x); Q的活動記錄P的活動記錄P的活動記錄TOP SPC的過程調用、過程進入、過程返回的過程調用、過程進入、過程返回過程調用的四元式系列： par T1 par Tn call P, n每個par Ti可以翻譯成目標指令： (i+3)TOP= Ti （傳值）或(i+3)TOP= addr(Ti) (傳地址)

11、call P, n翻譯成目標指令： 1TOP= SP （保存現行SP） 3TOP=n (傳送參數個數) JSR P （轉子指令，轉向P的第一條指令）返回值對應指令：return(E)過程返回時，應先執行指令： TOP=SP-1 SP=0SP X=2TOP UJ 0X轉進過程P后, 首先應執行指令： SP= TOP+1 （定義新SP） 1SP=返回地址 (保護返回地址) TOP=TOP+L (定義新TOP)L(活動記錄的大小)在編譯時可以靜態地計算出來。8.3.2 嵌套過程語言的棧式存儲分配嵌套過程語言的棧式存儲分配允許過程嵌套定義的語言(如Pascal)層數：嵌套的層次n主程序的層數為0直接外

12、層過程、內層過程層數作為過程名的一個屬性levelnlevel遇過程定義開始則+1，遇過程定義結束則-1 對于Pascal語言，在運行時，過程中的局部變量和形式參數在棧上的存儲可以用簡單棧式存儲分配來解決；但由于允許嵌套，非局部量的訪問就比較復雜。圖圖8.8程序程序非局部名字的訪問的實現非局部名字的訪問的實現為了在活動記錄中查找非局部名字所對應的存儲單元，過程運行時必須知道它的所有外層過程的最新最新活動記錄的地址；由于允許遞歸，過程的活動記錄的位置往往是變動的。跟蹤每個外層過程的最新活動記錄的位置：n通過嵌套層次顯示表（display）嵌套層次顯示表嵌套層次顯示表(display)和活動記錄和

13、活動記錄引用一個指針數組，嵌套層次顯示表：每進入一個過程后，在建立它的活動記錄區的同時，建立一張display。display的體積在編譯時可以靜態確定。非局部量的絕對地址的計算：display靜態層數+相對地址為便于處理，將display作為活動記錄的一部分。臨時單元內情向量局部變量display形參單元參數個數全局display地址返回地址動態鏈(老SP值)TOPSP通過通過display訪問非局部變量：訪問非局部變量：在現行過程中引用某一外層過程（層數為k）的變量X，變址指令得到X的值。當過程P1調用過程P2而進入P2后，P2如何建立自己的display表？(若P2的層數為I2，則其di

14、splay表含有I2+1項)方法：從P1的display表自底向上地取I2項，再添上進入P2后新建立的SP值，就構成了P2的display表。圖圖8.9、8.10、8 .118.4 堆式動態存儲分配堆式動態存儲分配允許用戶自由地申請數據空間和歸還數據空間。空間被分成許多大小不一的“塊”分配時必須考慮以下情況：n當運行程序要求一塊體積為N的空間時，分配哪一塊比N大的給它；n當運行程序要求一塊體積為N的空間，沒有比N大的塊，但所有空閑塊的總和比N大；n當運行程序要求一塊體積為N的空間，但所有空閑塊的總和也不夠N。堆式動態存儲分配的實現堆式動態存儲分配的實現1.定長塊管理: 初始化時，將堆存儲空間分

15、成長度相等的若干塊，每塊中指定一個鏈域。占用 占用 占用 空閑 空閑 空閑AVAILABLE歸還時，把所歸還的塊插入鏈表。如，插到鏈表頭。占用 空閑 占用 空閑 空閑 空閑AVAILABLE2. 變長塊管理變長塊管理根據需要分配長度不同的存儲塊，初始化時堆存儲空間是一個整塊。初次分配時，按需要分割整塊來分配；歸還時，需要將新歸還的塊與現有空閑塊進行合并，不能合并時，鏈成一個鏈表；再進行分配時，從空閑塊鏈表中找出滿足要求的一塊進行分配。有多個滿足要求的塊時，按以下三種策略進行分配：(1)首次匹配法：(2)最優匹配法：(3)最差匹配法：n(2)適用于請求分配的內存大小范圍較廣的情況；(3)適用于請

16、求分配的內存大小范圍較窄的情況。8.5 臨時變量的存儲分配臨時變量的存儲分配臨時變量是編譯時為暫存中間結果而引進的，對于代碼優化很有好處。都是簡單變量。如果兩個臨時變量名的作用域不相交，則可以共用共用一個存儲單元。因此，對新的臨時變量名分配存儲單元時，只有當它的作用域與所有已分配的臨時變量的作用域沖突時，才分配一個新單元。此時，單元的分配信息包括相應變量名的作用域。例如，用于暫存表達式中間結果的臨時變量，只存在一次定值和一次引用，并且在定值和引用之間不存在分叉轉移。其作用域的確定非常簡單，因而其存儲分配也可以用一種非常簡易的辦法（棧）實現。臨時變量的棧式地址分配：臨時變量的棧式地址分配：賦值語句：X=A*B-C*D+E*F四元式序列：四元式序列： 四元式四元式 臨時變量名臨時變量名 (1)* A B T1 T1 (2)* C D T2 T2 (3)- T1 T2