第目標程序運行時的存儲組織演示文稿

第目標程序運行時的存儲組織演示文稿第一頁，共五十九頁。（優(yōu)選）第目標程序運行時的存儲組織第二頁，共五十九頁。運行環(huán)境和存儲分配設計分析邏輯階段：在目標代碼生成前，作準備實質(zhì)：

關聯(lián)（Binding）將源程序的文本程序運行動作的實現(xiàn)源文件中的名字N

運行時的存儲S在語義學中，使用術語environment函數(shù)表示env:N→S(N到S的映射)第三頁，共五十九頁。靜態(tài)文本中

運行時動作及為實現(xiàn)其動作的準備

（與運行時數(shù)據(jù)對象的表示有關）

執(zhí)行過程體控制數(shù)據(jù)對象的分配，為執(zhí)行過程體使用源文本中同樣的名字

目標程序中不同的數(shù)據(jù)空間因為一個過程可以是遞歸的，這時同一個名字在不同的時間可能代表不同的存儲單元過程定義過程名過程體第四頁，共五十九頁。決定存儲管理復雜程度的因素——源語言本身1.允許的數(shù)據(jù)類型的多少

3．程序結(jié)構決定名字的作用域的規(guī)則和結(jié)構A．段結(jié)構B．過程定義不嵌套，只允許過程遞歸調(diào)用C．分程序結(jié)構分程序嵌套過程定義嵌套

2．語言中允許的數(shù)據(jù)項是靜態(tài)確定動態(tài)確定第五頁，共五十九頁。存儲分配方案策略：靜態(tài)存儲分配動態(tài)存儲分配棧式堆式第六頁，共五十九頁。術語靜態(tài)：如果一個名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動態(tài)：如果名字的性質(zhì)只有在程序運行時才能知道，則稱這種性質(zhì)為“動態(tài)”確定的?？勺?動態(tài))數(shù)組：若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則稱為可變(動態(tài))數(shù)組。第七頁，共五十九頁。例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;

end;第八頁，共五十九頁。第九頁，共五十九頁。一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū)（塊）叫做一個活動記錄或frame（幀）過程活動記錄AR（ActiveRecord）:為說明方便，假定程序是由過程組成，過程區(qū)分為源文本，運行時稱作過程的激活。第十頁，共五十九頁。

活動記錄包括：臨時值：如計算表達式時的中間工作單元局部變量：一個過程定義的變量（包括簡單變量和可變數(shù)組的內(nèi)情向量）保存運行過程前的狀態(tài)存取鏈（可選）：對于非局部量的引用控制鏈（可選）：指向調(diào)用者的活動記錄實參（形式單元）返回地址：保存該被調(diào)過程返回后的地址第十一頁，共五十九頁。簡單的棧式分配方案

程序結(jié)構特點:過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組;例:programmain;

全局變量的說明procR;……endR;procQ;……endQ;主程序執(zhí)行語句endmain.第十二頁，共五十九頁。Main---->Q---->RMain--->Q---->Q

TOP----->R的活動記錄

SP------>Q的活動記錄主程序全局數(shù)據(jù)區(qū)SP指向現(xiàn)行過程記錄的起點，TOP指向已占用的棧頂單元。

TOP----->Q的活動記錄

SP------>Q的活動記錄主程序全局數(shù)據(jù)區(qū)第十三頁，共五十九頁。TOP---->臨時工作單元局部簡單變量局部數(shù)組的內(nèi)情向量實參（形式單元）參數(shù)個數(shù)

SP----->控制鏈（老SP）返回地址

TOP----->R的活動記錄

SP------>Q的活動記錄主程序全局數(shù)據(jù)區(qū)R的數(shù)組區(qū)無嵌套定義的過程活動記錄內(nèi)容(含有可變數(shù)組)分配了數(shù)組區(qū)之后的運行棧第十四頁，共五十九頁。嵌套過程語言的棧式分配方案

主要特點：（語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，數(shù)組或過程等）。（實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。第十五頁，共五十九頁。

關鍵技術：解決對非局部量的引用（存?。８欈k法：

1.用靜態(tài)鏈（如PL/0的SL）。

2.用DISPLAY表。設法跟蹤每個外層過程的最新活動記錄AR的位置。第十六頁，共五十九頁。靜態(tài)鏈（存取鏈）和活動記錄在運行棧的數(shù)據(jù)區(qū)（活動記錄）中增加一個靜態(tài)鏈，從一個過程的當前活動記錄指向其直接外層的最新活動記錄。當過程結(jié)束時，利用動態(tài)鏈可以得到調(diào)用前的活動記錄的基地址。第十七頁，共五十九頁。臨時單元內(nèi)情向量簡單變量形參單元形參個數(shù)靜態(tài)鏈返回地址動態(tài)鏈（老sp）含靜態(tài)鏈的活動記錄連接數(shù)據(jù)sptop調(diào)用該過程的過程sp值靜態(tài)定義時直接外層過程的sp值第十八頁，共五十九頁。例：有如下的示意性源程序(假定該語言的過程是無參數(shù)的):PROGRAMmain;VARa,b,c:real;PROGRAMｘ;VARd,e:real;PROGRAMｙ;VARf,g:real;BEGIN…END;{y}PROGRAMz;VARh,i,j:real;BEGIN…y;END;{z}

BEGIN…11:z;…END;{x}BEGIN…x;…END.{main}第十九頁，共五十九頁。并已知在運行時刻，以過程為單位對程序中的變量進行動態(tài)存儲分配，采用靜態(tài)鏈實現(xiàn)非局部名字的訪問。當運行主程序而調(diào)用過程語句“x;”時，試分別給出以下時刻的數(shù)據(jù)存儲棧S的情形。（要求給出各靜態(tài)鏈（SL）和動態(tài)鏈（DL）的值。）已開始而尚未執(zhí)行完畢標號為11的語句。分析：調(diào)用過程的順序：

main(0)x(1)z(2)y(2)第二十頁，共五十九頁。棧頂寄存器T運行棧S[T]調(diào)用語句及當時T值基地址寄存器sp1動態(tài)鏈DLsp=12返回地址RA3靜態(tài)鏈SL4a5b6cT=6;x;7動態(tài)鏈DL=1sp=78返回地址RA9靜態(tài)鏈SL=110d11eT=11;z;第二十一頁，共五十九頁。棧頂寄存器T運行棧S[T]調(diào)用語句及當時T值基地址寄存器sp12動態(tài)鏈DL=7sp=1213返回地址RA14靜態(tài)鏈SL=715h16i17jT=17;y;18動態(tài)鏈DL=12sp=1819返回地址RA20靜態(tài)鏈SL=721f22gT=2223第二十二頁，共五十九頁。第二十三頁，共五十九頁。用display表的方案(0)主程序--->(1)P--->(2)Q--->(1)Rd[0]主程序的活動記錄

spdisplaytop（1）d[1]d[0]display

P的活動記錄主程序的活動記錄

sptop（2）display含義：一個指針數(shù)組d，也可看作一個小棧，自頂向下每個單元依次存放著現(xiàn)行層、直接外層、…直至最外層（0層，即主程序?qū)樱┑让繉舆^程的最新活動記錄的地址。display的構成：從調(diào)用者的display表中取i個（i為被調(diào)用者的靜態(tài)層次數(shù)）單元，再加上被調(diào)用者的數(shù)據(jù)區(qū)首地址即可。第二十四頁，共五十九頁。d[2]d[1]d[0]Q的活動記錄

P的活動記錄主程序的活動記錄

displaysptop（3）

displayd[1]d[0]R的活動記錄Q的活動記錄

P的活動記錄主程序的活動記錄

topsp（4）(0)主程序--->(1)P--->(2)Q--->(1)R全局display全局display:將調(diào)用者的display地址作為被調(diào)用者的全局display.第二十五頁，共五十九頁。臨時單元內(nèi)情向量簡單變量display形參單元形參個數(shù)全局display返回地址動態(tài)鏈（老sp）

當過程的層次為n，它的display為n+1個值。一個過程被調(diào)用時，從調(diào)用過程的display表中自下向上抄錄n個SP值，再加上本層的SP值。全局display地址含display的活動記錄連接數(shù)據(jù)sptop第二十六頁，共五十九頁。例：下面是一個PASCAL程序：programpp;vark:integer;functionf(n:integer):integer;beginifn<0thenf:=1elsef:=n*f(n-1)end;begink:=f(10);end.當?shù)诙危ㄟf歸地）進入f后，整個運行棧的內(nèi)容是什么？第二十七頁，共五十九頁。棧頂寄存器T運行棧S[T]調(diào)用語句及當時T值基地址寄存器SP1動態(tài)鏈DLsp=12返回地址RA30(參數(shù)個數(shù))41(display)5K(簡單變量)T=5;f(10);6動態(tài)鏈DL=1sp=67返回地址RA84(全局display)9110n第二十八頁，共五十九頁。棧頂寄存器T運行棧S[T]調(diào)用語句及當時T值基地址寄存器SP111(display)126(display)T=12;f(9);13動態(tài)鏈DL=6sp=1314返回地址RA1511(全局display)16117n181(display)1913(display)T=1920第二十九頁，共五十九頁。

ProcedureA(m,n);integerm,n;

B1:beginrealz;arrayB[m:n];B2:beginreald,e; L3:2end;B4:beginarrayC[1:m];1B5:beginreale;L6:54end;end;L8:end;第三十頁，共五十九頁。分程序結(jié)構的存儲

分配方案

處理分程序結(jié)構存儲分配方案的一種簡單辦法是，把分程序看成“無參過程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲辦法應用到處理分程序中。但這種做法是極為低效的。一則，每逢進入一個分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表,這是不必要的。二則，當從內(nèi)層分程序向外層轉(zhuǎn)移時，可能同時要結(jié)束若干個分程序。第三十一頁，共五十九頁。

按照過程處理辦法，意味著必須一層一層地通過“返回”來恢復所要到達的那個分程序的數(shù)據(jù)區(qū)，但不能直接到達。例如：如果有一個從第5層分程序轉(zhuǎn)出到達第1層分程序的標號L，雖然在第5層分程序工作時知道L所屬的層數(shù)，我們極易從DISPLAY中獲得第1層分程序的活動記錄基址（SP），但是怎么知道第1層分程序進入時的TOP呢？唯一的辦法是從5,4,3和2各層順序退出。但這種辦法是很浪費時間的。第三十二頁，共五十九頁。

為了解決上述問題，可采取兩種措施。第一，對每個過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器,每個TOP的值保存在各自活動記錄中。這樣，上述的第二個問題便可解決。第二，不把分程序看作“無參過程”，每個分程序享用包圍它的那個最近過程的DISPLAY。每個分程序都隸屬于某個確定的過程，分程序的層次是相對于它所屬的那個過程進行編號的。第三十三頁，共五十九頁。每個過程被當作是0層分程序。而過程體分程序（假定是一個分程序）當作是它所管轄的第1層分程序。這樣，每個過程的活動記錄所含的內(nèi)容有：1.過程的TOP值，它指向過程活動記錄的棧頂位置。2.連接數(shù)據(jù)，共四項：（1)老SP值；（2)返回地址；

(3)全局DISPAY地址；（4)調(diào)用時的棧頂單元地址，老TOP。第三十四頁，共五十九頁。

3.參數(shù)個數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對于每個分程序來說，它們包括：（1)分程序的TOP值。當進入分程序時它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時工作單元。第三十五頁，共五十九頁。第三十六頁，共五十九頁。B

Z

B1T

O第三十七頁，共五十九頁。

數(shù)

組B

數(shù)

組B

e

dB22的TOPB的

內(nèi)

情

向

量B的

內(nèi)

情

向

量

z

zB1的TOPB1的TOPDISPLAYDISPLAY

形式單元

m,n

2

形式單元

m,n

2連

接

數(shù)

據(jù)連接

數(shù)

據(jù)A的TOPA的TOP

∶

∶

∶

∶

(c)(d)(c)數(shù)組B分配之后；

（d）進入分程序B22;第三十八頁，共五十九頁。第三十九頁，共五十九頁。參數(shù)傳遞

傳值傳地址傳名傳結(jié)果第四十頁，共五十九頁。

(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap(varx,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.

帶有過程swap的PASCAL程序第四十一頁，共五十九頁。

傳地址（變量參數(shù)）例如：過程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時的實參）調(diào)用結(jié)果a,b的值被改變。傳值（值調(diào)用）特點是對形式參數(shù)的任何運算不影響實參的值。例如：過程swap(x,y:integer);swap(a,b）；其結(jié)果：a,b調(diào)用前的值不改變。第四十二頁，共五十九頁。傳值的實現(xiàn)(call-by-value)1.形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程的活動記錄中開辟了形參的存儲空間，這些存儲位置即是我們所說的形式單元（用以存放實參）。2.調(diào)用過程計算實參的值，并將其放在對應形式單元開辟的空間中。3.被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。第四十三頁，共五十九頁。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用swap(a,b)過程將不會影響a和b的值。其結(jié)果等價于執(zhí)行下列運算：x:=a；y:=b；temp:=x；x:=y；y:=temp第四十四頁，共五十九頁。傳地址的實現(xiàn)（call-by-reference)(call-by-address)(call-by-location)把實在參數(shù)的地址傳遞給相應的形參，即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應的形參：3、目標代碼中，被調(diào)用過程對形參的引用變成對傳遞給被調(diào)用過程的指針的間接引用2、實在參數(shù)是無左值的表達式----計算值，放入一存儲單元，傳此存儲單元地址1、實在參數(shù)是一個名字，或具有左值的表達式----傳遞左值第四十五頁，共五十九頁。procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用swap(i,a[i])其結(jié)果等價于執(zhí)行下列運算：1、把I和a[i]的地址分別放到x和y相應的單元a1,a22、(temp:=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容3、(x:=y;)a1所指單元的內(nèi)容置為a2所指單元值4、(y:=temp)a2所指單元的內(nèi)容置為temp的值第四十六頁，共五十九頁。

(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)}

在一個值調(diào)用過程中使用指針的C程序在C程序中無傳地址所以用指針實現(xiàn)。第四十七頁，共五十九頁。過程調(diào)用的四元式序列

Scallid(<arglist>)<arglist><arglist>,E<arglist>EparT1parT2parTncallid,n第四十八頁，共五十九頁。過程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境傳遞環(huán)境活動環(huán)境第四十九頁，共五十九頁。

programparam(input,output);procedureb(functionh(n:integer):integer);(*)varm:integer;beginm:=3;writeln(h(2))end;procedurec;(*)varm:integer;functionf(n:integer):integr;(&)beginf:=m+nend{f};beginm:=0;b(f)end{c}begincend.

第五十頁，共五十九頁。(1)programparam(input,output);(2)procedureb(functionh(n:integer):integer);(3)beginwriteln(h(2))end;(4)procedurec;(5)varm:integer;(6)functionf(n:integer):integr;(7)beginf:=m+nend{f};(8)beginm:=0;b(f)end{c};(9)begin(10)c(11)end

圖10-27嵌套過程作為參數(shù)傳遞第五十一頁，共五十九頁。第五十