編譯原理：第9章 運行時的存儲組織與管理

1、 2008年3月第9章 運行時的存儲組織與管理 翻譯程序必須分配目標程序運行時所需的存儲空間，這些空間包括：用戶定義的各種類型的變量和常數(shù)所需的存儲單元；作為保留中間結果和參數(shù)傳遞用的臨時工作單元；調(diào)用過程或函數(shù)時所需的連接單元，返回地址以及組織輸入輸出所需要的緩沖區(qū)。本章介紹有關運行時的存儲組織和管理問題。Compiler引進子程序getarea(Addr，Size)和freearea(Addr， size)。第一個子程序稱為分配存儲區(qū)程序，它給調(diào)用它的程序分配以Addr為起址的“連續(xù)”size單元；第二個子程序為釋放存儲區(qū)程序，其功能是釋放從地址Addr開始的“連續(xù)”Size個單元；有些編

2、譯程序只分配存儲區(qū)但并未明顯釋放它，當用戶申請存儲區(qū)而當時又沒有可用的存儲區(qū)時，編譯程序就調(diào)用無用單元收集程序，它釋放當前確已不再使用的一些單元，并調(diào)整存儲空間，將正在用的數(shù)據(jù)移到相連單元，以“騰出”大片相連單元，使其成為可用存儲區(qū). 2008年3月湖北大學數(shù)計學院計科系 2008年3月9.1 數(shù)據(jù)區(qū)和屬性字9.2 基本數(shù)據(jù)類型的存儲分配9.3 數(shù)組的存儲分配9.4 記錄結構的存儲分配9.5 參數(shù)傳遞方式及其實現(xiàn)9.6 棧式存儲分配方法9.7 堆式存儲分配方法9.8 臨時工作單元的存儲分配9.9 小結 2008年3月9.1 數(shù)據(jù)區(qū)和屬性字例：PASCAL主程序中所說明的變量運行時所需要的存儲單

3、元以及主程序運行時所需要的臨時工作單元一起構成了一個數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)是指一片相連的存儲單元。 2008年3月 在編譯時，任何變量運行時存儲單元都可由一對偶（數(shù)據(jù)區(qū)編號，位移）表示。其中，數(shù)據(jù)區(qū)編號是分配給數(shù)據(jù)區(qū)的唯一編號；位移是指該存儲單元相對于該數(shù)據(jù)區(qū)起址的距離（或單元數(shù)）。例如：對于編號為10的數(shù)據(jù)區(qū) 它的第1個存儲單元可表示為（10,0） 第2個存儲單元可表示為（10,1） 第i個存儲單元可表示為（10,i-1） 2008年3月 程序中出現(xiàn)的簡單變量和常量數(shù)組，由于它們所需的存儲單元數(shù)在編譯時就可以確定，所以在編譯時就可以給它們分配存儲單元，這種在編譯階段進行的存儲分配工作稱為靜態(tài)存

4、儲分配，由靜態(tài)存儲分配產(chǎn)生的數(shù)據(jù)區(qū)稱為靜態(tài)數(shù)據(jù)區(qū)。在整個運行過程中，這種數(shù)據(jù)區(qū)是固定不變的。 在運行階段分配的數(shù)據(jù)區(qū)統(tǒng)稱為動態(tài)數(shù)據(jù)區(qū)。在運行時，一個動態(tài)數(shù)據(jù)區(qū)不是固定不變的，隨著相應程序單位的調(diào)用和返回，它也會隨之建立和撤銷數(shù)據(jù)區(qū)。 2008年3月問題：C語言程序引用sizeof函數(shù)時，該函數(shù)的計算是在編譯該程序時完成的，還是在運行該程序時完成的？解答：在C語言中，sizeof函數(shù)的計算是在編譯時進行的，因為每個類型的大小是確定的，不會隨程序的運行而發(fā)生變化，所以完全可以在編譯時計算出來。 2008年3月begin procedure A begin procedure B begin end

5、; procedure C begin end; end; procedure D begin end; end; 若主程序和每個過程都有自己的數(shù)據(jù)區(qū)，那么將所能引用的數(shù)據(jù)區(qū)的起址按照它們建立的先后順序排列起來就構成一個DISPLAY表。例：當執(zhí)行過程C時，DISPLAY表為主程序的數(shù)據(jù)區(qū)起址過程A的數(shù)據(jù)區(qū)起址過程C的數(shù)據(jù)區(qū)起址 2008年3月屬性字 程序中變量的屬性常常不能在編譯階段全部確定出來。為此編譯階段在給變量分配存儲地址的同時，還為它分配一個屬性字，用以記錄該變量在運行時所確定的屬性。 例如動態(tài)數(shù)組，在運行時，一旦知道了存儲空間屬性，就調(diào)用getarea分配存儲空間，并把所分配的存儲

6、空間的起址存放在相應的屬性字中，以后總是通過這個屬性字去訪問相應的數(shù)組元素的地址。 2008年3月9.2 基本數(shù)據(jù)類型的存儲分配基本數(shù)據(jù)類型：整型、實型、布爾型和指示器型。整型變量：通常占用數(shù)據(jù)區(qū)中的一個單元，其值按機器內(nèi)部的標準整數(shù)形式存儲。實型變量：通常占用一個字。布爾型變量：占用一個字，常用零表示“false”值，用非零表示“true”值。指示器型變量：通常占用一個單元。在某些情況下，也把指示器表示成兩個相鄰單元，一個是其屬性字，指明它的類型，另一個單元包含它所真正指向的值。 2008年3月9.3 數(shù)組的存儲分配單塊存儲方式 單塊存儲方式就是把數(shù)據(jù)區(qū)中的一片相連單元分配給數(shù)組的元素，數(shù)組

7、的所有元素則按次序連續(xù)地存儲在這片數(shù)據(jù)區(qū)中。元素的排列次序通常為兩種：按行的次序和按列的次序。兩種存儲方式：單塊存儲、多塊存儲 2008年3月 對array A1.m , 1.n of integer所說明的數(shù)組，如果以按行的次序存儲數(shù)組元素的值，則任一數(shù)組元素Ai , j在數(shù)據(jù)區(qū)中的地址可由下式求得：address(Ai , j)=address(A1,1)+(i-1)*n+(j-1)address(Ai , j)=address(A1,1)-n-1+(i*n+j) 2008年3月 對array A1.m , 1.n of integer所說明的數(shù)組，如果以按行的次序存儲數(shù)組元素的值，則任一

8、數(shù)組元素Ai , j在數(shù)據(jù)區(qū)中的地址可由下式求得：address(Ai , j)=address(A1,1)+(i-1)*n+(j-1)address(Ai , j)=address(A1,1)-n-1+(i*n+j)注：上式中的第一部分是一常數(shù)，僅需計算一次。 2008年3月 設A是下面的說明語句定義的一個n維數(shù)組： array Al1.u1 , l2.u2 , . , ln.un of integer 假設di=ui-li+1 , i=1,2,n，即di為第i對界偶的界差，亦即第i維中不同下標值的個數(shù)，在按行的次序存放方式的前提下，數(shù)組元素Ai1,i2,.,in的地址為： address(

9、Al1,l2,.,ln)+(i1-l1)*d2*d3*dn +(i2-l2)*d3*d4*dn + +(in-1-l n-1)*dn +(in-ln) 2008年3月經(jīng)整理后，得 address(Ai1,i2,.,in)=Conspart+Varpart其中，Conspart= address(Al1,l2,.,ln) -(l1*d2+l2)*d3+l3)*d4+ln-1)*dn+ln) Varpart=(i1*d2+i2)*d3+in-1)*dn+inBegin Varpart:=1 ; j:=1 ; while jn do begin Varpart:=Varpart*dj+1+ij+1

10、; j:=j+1; endendVarpart 2008年3月信息向量與數(shù)組分配程序數(shù)組的信息向量：屬性字l1u1d1l2u2d2lnundnnConsparttypeBaseloc 2008年3月數(shù)組分配程序： begin i:=1 ; Size:=1 ; Conspart:=0; while i n do begin di:=ui-li+1 ; Size:=Size*di ; Conspart:=Conspart*di+li ; 把li , ui , di填入信息向量中; i:=i+1 end 調(diào)用getarea，按Size分配數(shù)據(jù)區(qū)； Baseloc:=該數(shù)據(jù)區(qū)起址； Conspart:

11、=Baseloc-Conspart ; 把n , Conspart , type和Baseloc填入信息向量中 end. 2008年3月多塊存儲方式 多塊存儲方式是對每一行都分配一個單塊數(shù)據(jù)區(qū)，每行的元素按遞增次序存放在這塊數(shù)據(jù)區(qū)中。此外，還設一個指示器表，用以指示這些單塊數(shù)據(jù)區(qū)的開始位置。9.3.3 多塊存儲方式多塊存儲方式 2008年3月9.4 記錄結構的存儲分配記錄結構是由不同類型的數(shù)據(jù)組合起來的一種結構。例如，記載學生信息（名字、學號、年齡）的卡片就可以寫成如下的記錄形式： record name:char-string20; number:integer; age:integer;

12、end存儲分配方式： 將其分量依次連續(xù)存儲在一個數(shù)據(jù)區(qū)中。 2008年3月9.5 參數(shù)傳遞方式及其實現(xiàn) 一個過程或子程序一經(jīng)定義，就可以被調(diào)用。調(diào)用與被調(diào)用者之間的信息交流是通過全局量或經(jīng)由參數(shù)傳遞的方式進行。 參數(shù)傳遞方式： 換名、傳值、傳地址、傳結果以及數(shù)組名用做參數(shù)和過程名用做參數(shù)。 2008年3月?lián)Q名：用過程體的代碼直接替換過程調(diào)用語句，其中的形參被替換為相應的實參。傳值：過程調(diào)用時，將實參的值傳遞給形參。形參值的改變不會引起實參的變化。傳地址：過程調(diào)用時，將實參的地址傳遞給形參。形參值的改變會引起實參的變化。傳結果：過程調(diào)用時，形參用兩個存儲單元分別存放實參的值和地址。調(diào)用完畢，將形

13、參的值按存儲的地址返回給實參。形參：過程定義語句中的參數(shù)。 實參：過程調(diào)用語句中的參數(shù)。 2008年3月9.5.1 換名 是ALGOL 60 特有這是一種用實在參數(shù)的地址計算程序?qū)π问絽?shù)進行原文替換的調(diào)用方式。在調(diào)用者中，對應每一個實行名字調(diào)用的實參都編制一個單獨的程序(稱形實替換程序)，該程序負責計算實參的地址。當調(diào)用時，將此形實替換程序的入口地址傳遞給被調(diào)用者。被調(diào)用者每遇到形參，就按此入口地址調(diào)用形實替換程序，計算實參的地址，并按計算出的地址引用實參。9.5.2 傳值 將實參值送被調(diào)用者的臨時單元，被調(diào)用者使用此臨時單元引用實參數(shù)。 每個形式參數(shù)在數(shù)據(jù)區(qū)中需要一個存放實參值的單元。被調(diào)

14、用者對形參的所有引用都是對存放值的形參單元的引用。 2008年3月9.5.3 傳地址 如果實參是 簡單變量/臨時變量，則將其地址送到被調(diào)用者形參中; 常量，則將其值存放到臨時單元中，將臨時單元的地址送到被調(diào)用者形參中； 表達式，計算出其值并存放在臨時單元中，將臨時單元地址送到被調(diào)用者形參中。 每個形式參數(shù)在數(shù)據(jù)區(qū)中需要一個存放實參地址的單元。被調(diào)用者對形參的所有引用都是對實參的直接引用。 9.5.4 傳結果 實參的值和地址分別被送到被調(diào)用者存放實參值的單元X和存放實參地址的單元Y。 每個形式參數(shù)在數(shù)據(jù)區(qū)中需要一個存放實參值的單元X和一個存放實參地址的單元Y。被調(diào)用者通過X取值使用，調(diào)用結束后，

15、在返回時，按Y地址將結果寫入實參對應的單元。 2008年3月 2008年3月問題：對于下面的程序： procedure P（X , Y , Z）； begin Y:=Y+1 ; Z:=Z+X; end P； begin A:=2 ; B:=3 ; P（A+B , A , A） print A end. 若參數(shù)傳遞的辦法分別為（1）換名（2）傳地址（3）傳結果（4）傳值。 試問：程序執(zhí)行后輸出的A值分別是多少？ 2008年3月9.6 棧式存儲分配方法棧式存儲分配方法：指把整個程序的存儲空間都安排在一個棧內(nèi)。主要思想：進入主程序時，將主程序定義的各類量（全程量）所需存儲空間分配于棧的頂部；每當調(diào)用

16、一個子程序（過程/函數(shù)）時，就將它所需的存儲空間分配于棧的當前頂部；每當一個子程序（過程/函數(shù)）運行結束時，就從棧中釋放它所占空間；整個程序執(zhí)行完后，釋放它所占用的全部空間。 2008年3月 一個過程的活動是指該過程的一次執(zhí)行。即每次執(zhí)行一個過程體，產(chǎn)生該過程體的一個活動。 過程P的一個活動的生存期，指的是從執(zhí)行該過程體第一步操作到最后一步操作之間的操作序列，包括執(zhí)行P時調(diào)用其它過程花費的時間。 在任一時刻，幾個過程可以同時處于正在執(zhí)行的進程中，但只有一個過程是當前正在工作的，這個過程稱為現(xiàn)行過程。其它的過程只是處于等待現(xiàn)行過程的完成和返回。過程的活動與活動記錄活動記錄：為了記錄過程一次活動的

17、數(shù)據(jù)信息而分配的一片連續(xù)的存儲區(qū)域。 2008年3月 在某些程序設計語言中，過程可以嵌套定義或調(diào)用，一個過程可以引用包圍它的任一外層過程所定義的變量或數(shù)組，也就是說，運行時，一個過程Q可能引用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù)。跟蹤外圍過程最新活動記錄地址的方法：靜態(tài)鏈Display表 2008年3月1、靜態(tài)鏈和活動記錄思想：利用一個稱為靜態(tài)鏈的指針，該指針為活動記錄的一個域，指向直接外層過程最新活動記錄的首地址?；顒佑涗浗Y構靜態(tài)鏈：從一個過程的當前活動記錄指向其直接外層過程的最新活動記錄的首地址。動態(tài)鏈：指向調(diào)用該過程前正在運行的過程的最新活動記錄的首地址。動態(tài)鏈（老SP）返回地址

18、靜態(tài)鏈形參個數(shù)形參單元簡單變量信息向量臨時單元SP 2008年3月Program P ; var a , x : integer ; procedure Q (b:integer); var i:integer ; procedure R (u:integer;var v:integer); var c , d:integer; begin if u=1 then R ( u+1 , v) ; v:=(a+c)*(b-d); endR begin R(1 , x); endQ procedure S; var c , i :integer; begin a:=1; Q ( c ) ; endS

19、begin a:=0 ; S ; end.P活動記錄結構臨時單元信息向量簡單變量形參單元形參個數(shù)靜態(tài)鏈返回地址動態(tài)鏈（老SP） 2008年3月2、嵌套層次顯示表( display )和活動記錄思想：利用一張display表，該表為活動記錄的一部分，記錄所有外層過程最新活動記錄的首地址?；顒佑涗浗Y構Display表：該表自頂向下每個單元依次存放著現(xiàn)行層，直接外層，直至最外層（主程序?qū)樱┑让恳粚舆^程最新活動記錄的首地址。全局display：主調(diào)程序的活動記錄中display表的首地址。display動態(tài)鏈（老SP）返回地址全局display形參個數(shù)形參單元簡單變量信息向量臨時單元SP 2008年3

20、月Program P ; var a , x : integer ; procedure Q (b:integer); var i:integer ; procedure R (u:integer;var v:integer); var c , d:integer; begin if u=1 then R ( u+1 , v) ; v:=(a+c)*(b-d); endR begin R(1 , x); endQ procedure S; var c , i :integer; begin a:=1; Q ( c ) ; endSbegin a:=0 ; S ; end.P活動記錄結構臨時單元

21、信息向量簡單變量display形參單元形參個數(shù)全局display返回地址動態(tài)鏈（老SP） 2008年3月9.7 堆式存儲分配方法 基本思想：當一個程序開始執(zhí)行時，有很大一片單元用做空閑存儲區(qū)，當程序開始運行時，可多次調(diào)用getarea分配存儲空間。運行結束，則調(diào)用freearea釋放占用的存儲空間。 多次調(diào)用getarea和freearea之后，原來的存儲區(qū)可能變成如下形式：空閑使用空閑空閑使用空閑使用使用需對空閑區(qū)進行有效管理。首次匹配法、最優(yōu)匹配法、最差匹配法 2008年3月首次匹配法：按序查看空閑區(qū)，選出其中第一個滿足所需容量要求的空閑區(qū)來進行分配。 時間：分配時查表，歸還時不需查表 缺

22、點：容易造成存儲空間浪費最優(yōu)匹配法：選出空閑區(qū)中最接近于（大于或等于）所需容量要求的空閑塊來進行分配。 時間：須將空閑塊由小到大進行排序，分配、歸還時均需查表 缺點：花費時間較多最差匹配法：選出最大的空閑塊來進行分配。 時間：須將空閑塊由大到小進行排序，歸還時均需查表 缺點：可能無法滿足較大的存儲空間要求 2008年3月9.8 臨時工作單元的存儲分配 臨時工作單元也稱為臨時工作變量。其作用域為從該變量開始確定其值到最后一次使用它之間的這段時間間隔。涉及臨時工作變量v的代碼可分為兩大類：1、“ST v”，即對v賦值，從而確定了變量v的作用域的起點；2、“用v”，其中包括“LD v”、“+ v”、

23、“* v”等等。就一個代碼序列中同一個v而言，這種用v指令的最后一條就是v的作用域的終點。 2008年3月例如，對于算術表達式 (a+b)*(c+d)+e*f)*(g-h)一般編譯程序?qū)⑸扇缦履繕舜a：LD a ADD bST T2 LD e MUL f ADD T2ST T1 LD c ADD d MUL T1ST T3 LD g SUB h MUL T3T1的作用域T2的作用域T3的作用域由于T1、T2、T3的作用域互不相交，所以只需一個臨時工作變量T1就夠了。 2008年3月例如，對于算術表達式 (a+b)*(c*d+e*f)一般編譯程序?qū)⑸扇缦履繕舜a：LD aADD bST T1LD cMUL dST T2LD eMUL fADD