運(yùn)行時存儲空間組織

運(yùn)行時存儲空間組織概述

任務(wù)：編譯程序?qū)δ繕?biāo)程序運(yùn)行時的數(shù)據(jù)空間的組織和管理（設(shè)計運(yùn)行環(huán)境和分配存儲）如通常棧式存儲分配布局可為：

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

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

Stackheap 第2頁,共53頁，2024年2月25日，星期天運(yùn)行環(huán)境和存儲分配

設(shè)計分析邏輯階段：在目標(biāo)代碼生成前，作準(zhǔn)備實(shí)質(zhì)：

關(guān)聯(lián)（Binding）將源程序的文本

程序運(yùn)行動作的實(shí)現(xiàn)源文件中的名字N

運(yùn)行時的存儲S在語義學(xué)中，使用術(shù)語environment函數(shù)表示env:N→S(N到S的映射)第3頁,共53頁，2024年2月25日，星期天第4頁,共53頁，2024年2月25日，星期天第5頁,共53頁，2024年2月25日，星期天第6頁,共53頁，2024年2月25日，星期天第7頁,共53頁，2024年2月25日，星期天術(shù)語靜態(tài)：如果一個名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動態(tài)：如果名字的性質(zhì)只有在程序運(yùn)行時才能知道，則稱這種性質(zhì)為“動態(tài)”確定的?？勺?動態(tài))數(shù)組：若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則稱為可變(動態(tài))數(shù)組。第8頁,共53頁，2024年2月25日，星期天例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;

end;第9頁,共53頁，2024年2月25日，星期天第10頁,共53頁，2024年2月25日，星期天第11頁,共53頁，2024年2月25日，星期天簡單的棧式分配方案

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

全局變量的說明procR……endR;procQ……endQ;主程序執(zhí)行語句endmain第12頁,共53頁，2024年2月25日，星期天第13頁,共53頁，2024年2月25日，星期天第14頁,共53頁，2024年2月25日，星期天嵌套過程語言的棧式

分配方案

主要特點(diǎn)：（語言）一個過程可以引用包圍它的任一外層過程所定義的標(biāo)識符（如變量，數(shù)組或過程等）。（實(shí)現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。第15頁,共53頁，2024年2月25日，星期天

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

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

2.用DISPLAY表。第16頁,共53頁，2024年2月25日，星期天第17頁,共53頁，2024年2月25日，星期天用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R

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

d[1]d[0]displaysptop主程序的活動記錄

d[0]spdisplaytop（1）（2）第18頁,共53頁，2024年2月25日，星期天用Display表的方案主程序--->P--->Q--->RR的活動記錄Q的活動記錄

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

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

displayd[2]d[1]d[0]

d[1]d[0]

displaysptoptopsp（3）（4）第19頁,共53頁，2024年2月25日，星期天DISPLAY表的維護(hù)和建立

DISPLAY表d運(yùn)行棧

0主程活動記錄地址

1R活動記錄地址

...

第20頁,共53頁，2024年2月25日，星期天

當(dāng)過程的層次為n，它的display為n+1個值。一個過程被調(diào)用時，從調(diào)用過程的DISPLAY表中自下向上抄錄n個SP值，再加上本層的SP值。全局DISPLAY地址第21頁,共53頁，2024年2月25日，星期天

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;第22頁,共53頁，2024年2月25日，星期天分程序結(jié)構(gòu)的存儲

分配方案

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

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

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

(3)全局DISPAY地址；（4)調(diào)用時的棧頂單元地址，老TOP。第26頁,共53頁，2024年2月25日，星期天

3.參數(shù)個數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對于每個分程序來說，它們包括：（1)分程序的TOP值。當(dāng)進(jìn)入分程序時它含現(xiàn)行棧頂?shù)刂罚院?，用來定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時工作單元。第27頁,共53頁，2024年2月25日，星期天第28頁,共53頁，2024年2月25日，星期天B

Z

B1T

O第29頁,共53頁，2024年2月25日，星期天

數(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）進(jìn)入分程序B22;第30頁,共53頁，2024年2月25日，星期天第31頁,共53頁，2024年2月25日，星期天參數(shù)傳遞

(1)procedureexchangel(i,j:integer);(2)varx:integer;(3)begin;(4)x:=a[i];a[i]:=a[j];a[j]:=x(5)end;

帶有非局部變量和形參的PASCAL過程非局變量a[i]和a[j]的值進(jìn)行交換，i,j為形參（在這里是傳值）第32頁,共53頁，2024年2月25日，星期天

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

帶有過程swap的PASCAL程序第33頁,共53頁，2024年2月25日，星期天

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

調(diào)用swap(a,b)過程將不會影響a和b的值。其結(jié)果等價于執(zhí)行下列運(yùn)算：

x:=a；

y:=b；

temp:=x；

x:=y；

y:=temp第36頁,共53頁，2024年2月25日，星期天傳地址的實(shí)現(xiàn)（call-by-reference)(call-by-address)(call-by-location)

把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應(yīng)的形參：1實(shí)在參數(shù)是一個名字，或具有左值的表達(dá)式----傳遞左值2實(shí)在參數(shù)是無左值的表達(dá)式----計算值，放入一存儲單元，傳此存儲單元地址3目標(biāo)代碼中，被調(diào)用過程對形參的引用變成對傳遞給被調(diào)用過程的指針的間接引用第37頁,共53頁，2024年2月25日，星期天procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用swap(i,a[i])其結(jié)果等價于執(zhí)行下列運(yùn)算：

1把I和a[i]的地址分別放到x和y相應(yīng)的單元a1,a22(temp:=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容

3(x:=y;)a1所指單元的內(nèi)容置為a2所指單元值4(y:=temp)a2所指單元的內(nèi)容置為temp的值第38頁,共53頁，2024年2月25日，星期天

(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程序中無傳地址所以用指針實(shí)現(xiàn)。第39頁,共53頁，2024年2月25日，星期天過程調(diào)用的四元式序列

S

callid(<arglist>)<arglist>

<arglist>,E<arglist>

EparT1parT2parTncallid,n第40頁,共53頁，2024年2月25日，星期天過程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境傳遞環(huán)境活動環(huán)境第41頁,共53頁，2024年2月25日，星期天

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.

第42頁,共53頁，2024年2月25日，星期天(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ù)傳遞第43頁,共53頁，2024年2月25日，星期天第44頁,共53頁，2024年2月25日，星期天各種數(shù)據(jù)對象的存儲分配數(shù)據(jù)對象

name名字，名稱

type類型

location內(nèi)存地址

value值

component成分

第45頁,共53頁，2024年2月25日，星期天第46頁,共53頁，2024年2月25日，星期天第47頁,共53頁，2024年2月25日，星期天第48頁,共53頁，2024年2月25日，星期天建立內(nèi)情向量，問配內(nèi)存的目標(biāo)代碼（n維可變數(shù)組,type--每個元素占一個字）begink:=1;n:=1;c:=0;whilek<=ndobegindi:=ui-li+1;m:=m*di;c:=c*di+li;

把li,ui和di填進(jìn)內(nèi)情向量表區(qū)；

k:=k+1