第10章目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織RUN-TimeOrganizationCompilerphase—Beforewritingacodegenerator,wemustdecidehowtomarshaltheresourcesofthetargetmachine(instructions,storage,andsystemsoftware)inordertoimplementthesourcelanguage.Thisiscalledrun-timeorganization概述代碼生成前如何安排目標(biāo)機(jī)資源運(yùn)行時(shí)存儲(chǔ)組織的幾個(gè)問(wèn)題：數(shù)據(jù)表示—如何在目標(biāo)機(jī)中表示每個(gè)源語(yǔ)言類型的值表達(dá)式求值—如何組織表達(dá)式的計(jì)算存儲(chǔ)分配—如何組織不同作用域變量的存儲(chǔ)過(guò)程實(shí)現(xiàn)—如何以例程實(shí)現(xiàn)過(guò)程，函數(shù)，參數(shù)傳遞Thekeyissues

inrun-timeorganizationDatarepresentation:Howshouldwerepresentthevaluesofeachsource-languagetypeinthetargetmachine?Expressionevaluation:Howshouldweorganizetheevaluationofexpressions,takingcareofintermediateresults?Thekeyissues

inrun-timeorganizationStorageallocation:Howshouldweorganizestorageforvariables,takingintoaccountthedifferentlifetimesofglobal,localandheapvariables?Routines:Howshouldweimplementprocedures,functions,andparameters,intermsoflow-levelroutines?Thekeyissues

inrun-timeorganizationRun-timeorganizationforobject-orientedlanguages:Howshouldwerepresentobjectsandmethods?概述任務(wù)：編譯程序?qū)δ繕?biāo)程序運(yùn)行時(shí)的組織—設(shè)計(jì)運(yùn)行環(huán)境和分配存儲(chǔ)存儲(chǔ)區(qū)布局—典型劃分：

目標(biāo)代碼區(qū)code

靜態(tài)數(shù)據(jù)區(qū)

Staticdata Stack

heap 數(shù)據(jù)表示固定長(zhǎng)度，直接或間接表示簡(jiǎn)單變量：char:1byteintegers:2or4bytesfloats:4to16bytesbooleans:1bit(butusually1byte)指針：unsignedintegers數(shù)據(jù)表示一維數(shù)組：一塊連續(xù)的存儲(chǔ)區(qū)多維數(shù)組：一塊連續(xù)的存儲(chǔ)區(qū)，按行存放結(jié)構(gòu)(記錄)：把所有域(field)存放在一塊連續(xù)的存儲(chǔ)區(qū)對(duì)象：類的實(shí)例變量象結(jié)構(gòu)的域一樣存放在一塊連續(xù)的存儲(chǔ)區(qū)，但方法(成員函數(shù))不存在該對(duì)象里二維數(shù)組存儲(chǔ)的例第一行第二行第十行A[0,0]A[0,1].A[0,19]A[1,0].....A[9,19]按行存儲(chǔ)的1020的二維數(shù)組A10.1數(shù)據(jù)空間的

三種不同使用方法和管理方法存儲(chǔ)分配策略：靜態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配—棧式堆式簡(jiǎn)單的棧式分配方案嵌套過(guò)程的棧式分配方案分程序結(jié)構(gòu)的存儲(chǔ)分配方案各種數(shù)據(jù)對(duì)象的存儲(chǔ)分配數(shù)據(jù)對(duì)象的屬性

name名字，名稱

type類型

location內(nèi)存地址

value值

component成分Storageclassesglobal:existthroughoutlifetimeofentireprogramandcanbereferencedanywhere.static:existthroughoutlifetimeofentireprogrambutcanonlybereferencedinthefunction(ormodule)inwhichtheyaredeclared.Storageclasseslocal:(alsocalledautomatic)existonlyforthedurationofacalltotheroutineinwhichtheyaredeclared;anewvariableiscreatedeachtimetheroutineisentered(anddestroyedonexit).dynamic:variablesthatarecreatedduringprogramexecution;usuallyrepresentedbyanaddressheldinavariableofoneoftheaboveclasses.10.1.1靜態(tài)存儲(chǔ)分配靜態(tài)：如果一個(gè)名字的性質(zhì)通過(guò)說(shuō)明語(yǔ)句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。在編譯時(shí)能確定：目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，分配運(yùn)行時(shí)的數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的位置，則稱這種分配策略為靜態(tài)存儲(chǔ)分配。10.1.2動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)：如果名字的性質(zhì)只有在程序運(yùn)行時(shí)才能知道，則稱這種性質(zhì)為“動(dòng)態(tài)”確定的。遞歸過(guò)程、可變數(shù)組、用戶自由申請(qǐng)和釋放存儲(chǔ)空間，需要?jiǎng)討B(tài)存儲(chǔ)管理技術(shù)所需的數(shù)據(jù)空間在程序運(yùn)行時(shí)動(dòng)態(tài)地確定有兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式(stack)和堆式(heap)10.1.3棧式動(dòng)態(tài)存儲(chǔ)分配將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧在調(diào)用一個(gè)過(guò)程時(shí)，將所需的數(shù)據(jù)空間分配在棧頂，過(guò)程調(diào)用結(jié)束時(shí)釋放這部分空間。過(guò)程所需空間：局部變量、參數(shù)單元、臨時(shí)變量管理過(guò)程的記錄信息—中斷信息當(dāng)控制從過(guò)程調(diào)用返回時(shí)，根據(jù)棧中記錄的信息，恢復(fù)中斷前的狀態(tài)。10.1.4堆式動(dòng)態(tài)存儲(chǔ)分配在C語(yǔ)言動(dòng)態(tài)地生成和釋放結(jié)點(diǎn)等操作，需要使用堆式動(dòng)態(tài)存儲(chǔ)分配。

(malloc、calloc、free函數(shù))需求：一個(gè)程序語(yǔ)言允許用戶自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間，或者不僅有過(guò)程而且有進(jìn)程(process)的程序結(jié)構(gòu)，操作：堆提供兩個(gè)操作—分配和釋放操作情況：碎片問(wèn)題10.2棧式存儲(chǔ)分配的實(shí)現(xiàn)運(yùn)行時(shí)每當(dāng)進(jìn)入一個(gè)過(guò)程，就在棧頂為該過(guò)程分配所需的數(shù)據(jù)空間當(dāng)一個(gè)過(guò)程工作完畢返回時(shí)，釋放其在棧頂?shù)臄?shù)據(jù)空間過(guò)程的活動(dòng)記錄AR(ActivationRecord)是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過(guò)程的一次執(zhí)行所需要的信息。過(guò)程的活動(dòng)記錄臨時(shí)工作單元局部變量機(jī)器狀態(tài)信息存取鏈控制鏈實(shí)參返回地址存取鏈：用以存取在其它過(guò)程活動(dòng)記錄中的非局部變量控制鏈：指向調(diào)用該過(guò)程的過(guò)程的活動(dòng)記錄。10.2.1簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)簡(jiǎn)單程序結(jié)構(gòu)：無(wú)分程序結(jié)構(gòu)、過(guò)程定義不嵌套、過(guò)程可遞歸調(diào)用。例:main

全局變量的說(shuō)明

procR……endR;procQ……endQ;

主程序執(zhí)行語(yǔ)句

endmain簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)

Main---->Q---->RMain--->Q---->QTOP------>R的活動(dòng)記錄Q的活動(dòng)記錄

SP------>Q的活動(dòng)記錄Q的活動(dòng)記錄主程序全局主程序全局?jǐn)?shù)據(jù)區(qū)數(shù)據(jù)區(qū)SP總是指向現(xiàn)行過(guò)程活動(dòng)記錄的起點(diǎn)TOP始終指向已占用的棧頂單元TOP---->臨時(shí)工作單元局部簡(jiǎn)單變量局部數(shù)組的內(nèi)情向量保存運(yùn)行過(guò)程前的狀態(tài)(返回地址，寄存器值……)

實(shí)參（形式單元）參數(shù)個(gè)數(shù)返回地址

SP----->控制鏈（老SP）

無(wú)嵌套定義的過(guò)程活動(dòng)記錄內(nèi)容分配了數(shù)組區(qū)的運(yùn)行棧TOPR的數(shù)組區(qū)

R的活動(dòng)記錄SPQ的活動(dòng)記錄主程序全局?jǐn)?shù)據(jù)區(qū)10.2.2嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)主要特點(diǎn)：一個(gè)過(guò)程可以引用包圍它的任一外層過(guò)程所定義的標(biāo)識(shí)符(如變量，數(shù)組或過(guò)程等)。一個(gè)過(guò)程可以引用它的任一外層過(guò)程的最新活動(dòng)記錄中的某些數(shù)據(jù)。

關(guān)鍵技術(shù)：解決對(duì)非局部量的引用(存取)。設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄AR的位置。跟蹤辦法：

1.使用過(guò)程活動(dòng)記錄的存取鏈(靜態(tài)鏈)。

2.每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display。嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)10.2.3分程序結(jié)構(gòu)的存儲(chǔ)管理處理分程序結(jié)構(gòu)存儲(chǔ)分配方案的一種簡(jiǎn)單辦法是，把分程序看成“無(wú)名無(wú)參過(guò)程”，在定義處被調(diào)用。因此，可以把處理過(guò)程的存儲(chǔ)辦法應(yīng)用到處理分程序中。10.2.3分程序結(jié)構(gòu)的存儲(chǔ)管理1.每逢進(jìn)入一個(gè)分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表。2.當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時(shí)，可能同時(shí)要結(jié)束若干個(gè)分程序。按照過(guò)程處理辦法，必須一層一層地通過(guò)“返回”來(lái)恢復(fù)所要到達(dá)的那個(gè)分程序的數(shù)據(jù)區(qū)。

例如：如果有一個(gè)從第5層分程序轉(zhuǎn)出到達(dá)第1層分程序的標(biāo)號(hào)L，雖然在第5層分程序工作時(shí)知道L所屬的層數(shù)，我們極易從DISPLAY中獲得第1層分程序的活動(dòng)記錄基址(SP)，但是若要知道第1層分程序進(jìn)入時(shí)的TOP，唯一的辦法是從5,4,3和2各層順序退出。分程序結(jié)構(gòu)的存儲(chǔ)管理

為了解決上述問(wèn)題，可采取兩種措施。第一，對(duì)每個(gè)過(guò)程或分程序都建立有自己的棧頂指示器TOP，代替原來(lái)僅有過(guò)程的棧頂指示器,每個(gè)TOP的值保存在各自活動(dòng)記錄中。這樣，上述的第二個(gè)問(wèn)題便可解決。分程序結(jié)構(gòu)的存儲(chǔ)管理

第二，不把分程序看作“無(wú)參過(guò)程”，每個(gè)分程序享用包圍它的那個(gè)最近過(guò)程的DISPLAY。每個(gè)分程序都隸屬于某個(gè)確定的過(guò)程，分程序的層次是相對(duì)于它所屬的那個(gè)過(guò)程進(jìn)行編號(hào)的。分程序結(jié)構(gòu)的存儲(chǔ)管理：

每個(gè)過(guò)程被當(dāng)作是0層分程序。而過(guò)程體分程序(假定是一個(gè)分程序)當(dāng)作是它所管轄的第1層分程序。這樣，每個(gè)過(guò)程的活動(dòng)記錄所含的內(nèi)容有：1.過(guò)程的TOP值，它指向過(guò)程活動(dòng)記錄的棧頂位置。分程序結(jié)構(gòu)的存儲(chǔ)管理：2.連接數(shù)據(jù)，共四項(xiàng)：(1)老SP值；(2)返回地址；(3)全局DISPAY地址；(4)調(diào)用時(shí)的棧頂單元地址，老TOP。3.參數(shù)個(gè)數(shù)和形式單元4.DISPAY表。分程序結(jié)構(gòu)的存儲(chǔ)管理

5.過(guò)程所轄的各分程序的局部數(shù)據(jù)單元。對(duì)于每個(gè)分程序來(lái)說(shuō)，它們包括：（1)分程序的TOP值。當(dāng)進(jìn)入分程序時(shí)它含現(xiàn)行棧頂?shù)刂?，以后，用?lái)定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時(shí)工作單元。分程序結(jié)構(gòu)的存儲(chǔ)管理

參數(shù)的傳遞有多種途徑：傳值、傳地址、傳名、宏擴(kuò)展等。賦值語(yǔ)句：a[i]=a[j]，a[j]表示一個(gè)值，a[i]表示一個(gè)存儲(chǔ)位置。左值(l-value)：表達(dá)式代表的存儲(chǔ)右值(r-value)：該存儲(chǔ)位置中含有的值參數(shù)傳遞的方法基于實(shí)在參數(shù)是表達(dá)右值、左值。C語(yǔ)言數(shù)組名字表示地址。10.3參數(shù)傳遞

傳地址(變量參數(shù))例如：過(guò)程swap(varx,y:integer);swap(a,b)；(a，b為調(diào)用時(shí)的實(shí)參)

調(diào)用結(jié)果a，b的值被改變。C語(yǔ)言：函數(shù)swap(int*x,int*y)

使用指針做函數(shù)參數(shù)，實(shí)參為變量的地址。10.3參數(shù)傳遞

傳值(值調(diào)用)特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。例如：過(guò)程swap(x,y:integer);swap(a,b)；

其結(jié)果：a，b調(diào)用前的值不改變。C語(yǔ)言函數(shù)：函數(shù)swap(intx,inty)

使用變量做函數(shù)參數(shù)，實(shí)參為變量，傳遞的是值。參數(shù)傳遞10.3.1傳值1.形式參數(shù)當(dāng)作過(guò)程的局部變量處理，即在被調(diào)用過(guò)程的活動(dòng)記錄中開(kāi)辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說(shuō)的形式單元(用以存放實(shí)參)。2.調(diào)用過(guò)程計(jì)算實(shí)參的值，并將其右值放在對(duì)應(yīng)形式單元開(kāi)辟的空間中。3.被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。procedureswap(x,y:integer);

vartemp:integer;begintemp:=x;x:=yy:=tempend；調(diào)用swap(a,b)過(guò)程將不會(huì)影響a和b的值。其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：

x:=a；y:=b；

temp:=x；x:=y；y:=temp傳值的實(shí)現(xiàn)

(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap(x,y:integer);(4)vartemp:integer;(5)begin(6)temp:=x;(7)x:=y;(8)y:=temp(9)end;(10)begin(11)a:=1;b:=2;(12)swap(a,b);(13)writeln(‘a(chǎn)=‘,a);writeln(‘b=‘,b)(14)end.帶有過(guò)程swap的PASCAL程序10.3.2傳地址call-by-referencecall-by-addresscall-by-location把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過(guò)程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針傳遞給被調(diào)用過(guò)程相應(yīng)的形參：傳地址1.實(shí)在參數(shù)是一個(gè)名字，或具有左值的表達(dá)式—傳遞左值。2.實(shí)在參數(shù)是無(wú)左值的表達(dá)式—計(jì)算值，放入一存儲(chǔ)單元，傳遞此存儲(chǔ)單元地址。3.目標(biāo)代碼中，被調(diào)用過(guò)程對(duì)形參的引用變成對(duì)傳遞給被調(diào)用過(guò)程的指針的間接引用。procedureswap(varx,y:integer);

vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(i,a[i])其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：1.把i和a[i]的地址分別放到x和y相應(yīng)的單元a1,a2傳地址的實(shí)現(xiàn)2.(temp:=x;)temp的內(nèi)容置為a1所指單元中存的內(nèi)容3.(x:=y;)a1所指單元的內(nèi)容置為a2所指單元值4.(y:=temp)a2所指單元的內(nèi)容置為temp的值傳地址的實(shí)現(xiàn)

(1)swap(x,y)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)}(6)main()(7){inta=1,b=2;(8)swap(&a,&b);(9)printf(“aisnow%d,bisnow%d\n”,a,b);(10)}傳地址的實(shí)現(xiàn)在一個(gè)值調(diào)用過(guò)程中使用指針的C程序10.3.3過(guò)程參數(shù)過(guò)程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境傳遞環(huán)境活動(dòng)環(huán)境(1)programparam(input,output);(2)procedureb(fun