運(yùn)行時(shí)存儲(chǔ)空間組織

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

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

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

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

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

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

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

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

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

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

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

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

分配方案

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

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

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

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

P的活動(dòng)記錄主程序的活動(dòng)記錄

d[1]d[0]displaysptop主程序的活動(dòng)記錄

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

P的活動(dòng)記錄主程序的活動(dòng)記錄Q的活動(dòng)記錄

P的活動(dòng)記錄主程序的活動(dòng)記錄

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

d[1]d[0]

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

DISPLAY表d運(yùn)行棧

0主程活動(dòng)記錄地址

1R活動(dòng)記錄地址

...

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

當(dāng)過(guò)程的層次為n，它的display為n+1個(gè)值。一個(gè)過(guò)程被調(diào)用時(shí)，從調(diào)用過(guò)程的DISPLAY表中自下向上抄錄n個(gè)SP值，再加上本層的SP值。全局DISPLAY地址第21頁(yè),共53頁(yè)，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頁(yè),共53頁(yè)，2024年2月25日，星期天分程序結(jié)構(gòu)的存儲(chǔ)

分配方案

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

按照過(guò)程處理辦法，意味著必須一層一層地通過(guò)“返回”來(lái)恢復(fù)所要到達(dá)的那個(gè)分程序的數(shù)據(jù)區(qū)，但不能直接到達(dá)。例如：如果有一個(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各層順序退出。但這種辦法是很浪費(fèi)時(shí)間的。第24頁(yè),共53頁(yè)，2024年2月25日，星期天

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

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

3.參數(shù)個(gè)數(shù)和形式單元4.DISPAY表。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í)工作單元。第27頁(yè),共53頁(yè)，2024年2月25日，星期天第28頁(yè),共53頁(yè)，2024年2月25日，星期天B

Z

B1T

O第29頁(yè),共53頁(yè)，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頁(yè),共53頁(yè)，2024年2月25日，星期天第31頁(yè),共53頁(yè)，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過(guò)程非局變量a[i]和a[j]的值進(jìn)行交換，i,j為形參（在這里是傳值）第32頁(yè),共53頁(yè)，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.

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

傳地址（變量參數(shù)）例如：過(guò)程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時(shí)的實(shí)參）調(diào)用結(jié)果a,b的值被改變。傳值（值調(diào)用）特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。例如：過(guò)程swap(x,y:integer);swap(a,b）；其結(jié)果：a,b調(diào)用前的值不改變。第34頁(yè),共53頁(yè)，2024年2月25日，星期天傳值的實(shí)現(xiàn)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í)，就像使用局部變量一樣使用這些形式單元。第35頁(yè),共53頁(yè)，2024年2月25日，星期天procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=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第36頁(yè),共53頁(yè)，2024年2月25日，星期天傳地址的實(shí)現(xiàn)（call-by-reference)(call-by-address)(call-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ò)程的指針的間接引用第37頁(yè),共53頁(yè)，2024年2月25日，星期天procedureswap(x,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,a22(temp:=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容

3(x:=y;)a1所指單元的內(nèi)容置為a2所指單元值4(y:=temp)a2所指單元的內(nèi)容置為temp的值第38頁(yè),共53頁(yè)，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)}

在一個(gè)值調(diào)用過(guò)程中使用指針的C程序在C程序中無(wú)傳地址所以用指針實(shí)現(xiàn)。第39頁(yè),共53頁(yè)，2024年2月25日，星期天過(guò)程調(diào)用的四元式序列

S

callid(<arglist>)<arglist>

<arglist>,E<arglist>

EparT1parT2parTncallid,n第40頁(yè),共53頁(yè)，2024年2月25日，星期天過(guò)程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境傳遞環(huán)境活動(dòng)環(huán)境第41頁(yè),共53頁(yè)，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頁(yè),共53頁(yè)，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嵌套過(guò)程作為參數(shù)傳遞第43頁(yè),共53頁(yè)，2024年2月25日，星期天第44頁(yè),共53頁(yè)，2024年2月25日，星期天各種數(shù)據(jù)對(duì)象的存儲(chǔ)分配數(shù)據(jù)對(duì)象

name名字，名稱

type類型

location內(nèi)存地址

value值

component成分

第45頁(yè),共53頁(yè)，2024年2月25日，星期天第46頁(yè),共53頁(yè)，2024年2月25日，星期天第47頁(yè),共53頁(yè)，2024年2月25日，星期天第48頁(yè),共53頁(yè)，2024年2月25日，星期天建立內(nèi)情向量，問(wèn)配內(nèi)存的目標(biāo)代碼（n維可變數(shù)組,type--每個(gè)元素占一個(gè)字）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