第十章目標(biāo)程序運(yùn)行時(shí)的

存儲(chǔ)組織

概述棧式存儲(chǔ)分配的實(shí)現(xiàn)簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)分程序結(jié)構(gòu)的存儲(chǔ)管理參數(shù)傳遞過(guò)程調(diào)用、過(guò)程進(jìn)入和過(guò)程返回概述任務(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 運(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的映射)術(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ù)組。例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;

end;簡(jiǎn)單的棧式分分配方案程序結(jié)構(gòu)特點(diǎn)點(diǎn):過(guò)程定義義不嵌套，過(guò)過(guò)程可遞歸調(diào)調(diào)用，含可變變數(shù)組;例:main全局變量的說(shuō)說(shuō)明procR……endR;procQ……endQ;主程序執(zhí)行語(yǔ)語(yǔ)句endmain嵌套過(guò)程語(yǔ)言言的棧式分分配方案主要特點(diǎn)：（語(yǔ)言）一個(gè)個(gè)過(guò)程可以引引用包圍它的的任一外層過(guò)過(guò)程所定義的的標(biāo)識(shí)符（如如變量，數(shù)組組或過(guò)程等））。（實(shí)現(xiàn)）一個(gè)個(gè)過(guò)程可以引引用它的任一一外層過(guò)程的的最新活動(dòng)記記錄中的某些些數(shù)據(jù)。關(guān)鍵技技術(shù)：：解決決對(duì)非非局部部量的的引用用（存存取））。設(shè)法跟跟蹤每每個(gè)外外層過(guò)過(guò)程的的最新新活動(dòng)動(dòng)記錄錄AR的位位置。。跟蹤辦辦法：：1.用用靜靜態(tài)鏈鏈（如如PL/0的SL））。2.用用DISPLAY表。。用Display表的的方案案(1)主程程序--->(2)P--->(3)Q--->(4)RP的的活動(dòng)記記錄主程序序的活動(dòng)記記錄d[1]d[0]displaysptop主程序序的活動(dòng)記記錄d[0]spdisplaytop（1））（2））用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））DISPLAY表的維維護(hù)和和建立立DISPLAY表d運(yùn)運(yùn)行棧棧0主主程程序活活動(dòng)記記錄地地址1R活活動(dòng)記記錄地地址...當(dāng)過(guò)程程的層層次為為n，，它的的display為n+1個(gè)個(gè)值。。一個(gè)過(guò)過(guò)程被被調(diào)用用時(shí)，，從調(diào)調(diào)用過(guò)過(guò)程的的DISPLAY表表中自自下向向上抄抄錄n個(gè)SP值值，再再加上上本層層的SP值值。全局DISPLAY地址址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é)構(gòu)構(gòu)的存存儲(chǔ)分分配配方案案處理分分程序序結(jié)構(gòu)構(gòu)存儲(chǔ)儲(chǔ)分配配方案案的一一種簡(jiǎn)簡(jiǎn)單辦辦法是是，把把分程程序看看成““無(wú)無(wú)參過(guò)過(guò)程程”，，它在在哪里里定義義就在在哪里里被調(diào)調(diào)用。。因此此，可可以把把處理理過(guò)程程的存存儲(chǔ)辦辦法應(yīng)應(yīng)用到到處理理分程程序中中。但但這種種做法法是極極為低低效的的。一則，，每逢逢進(jìn)入入一一個(gè)分分程序序，就就照樣樣建立立連接接數(shù)據(jù)據(jù)和DISPLAY表,這是是不必必要的的。二二則，，當(dāng)當(dāng)從內(nèi)內(nèi)層分分程序序向外外層轉(zhuǎn)轉(zhuǎn)移時(shí)時(shí)，可可能同同時(shí)要要結(jié)束束若干干個(gè)分分程序序。按照過(guò)過(guò)程處處理辦辦法，，意味味著必必須一一層一一層地地通過(guò)過(guò)“返返回””來(lái)來(lái)恢復(fù)復(fù)所要要到達(dá)達(dá)的那那個(gè)分分程序序的數(shù)數(shù)據(jù)區(qū)區(qū)，但但不能能直接接到達(dá)達(dá)。例如：：如果果有一一個(gè)從從第5層分分程序序轉(zhuǎn)出出到達(dá)達(dá)第1層分分程序序的標(biāo)標(biāo)號(hào)L，雖雖然在在第5層分分程序序工作作時(shí)知知道L所屬屬的層層數(shù)，，我們們極易易從DISPLAY中獲獲得第第1層層分程程序的的活動(dòng)動(dòng)記錄錄基址址（SP）），但但是怎怎么知知道第第1層層分程程序進(jìn)進(jìn)入時(shí)時(shí)的TOP呢？？唯一一的辦辦法是是從5,4,3和和2各各層順順序退退出。。但這這種辦辦法是是很浪浪費(fèi)時(shí)時(shí)間的的。為了解解決上上述問(wèn)問(wèn)題，，可采采取兩兩種措措施。。第一一，對(duì)對(duì)每個(gè)個(gè)過(guò)程程或分分程序序都建建立有有自己己的棧棧頂指指示器器TOP，，代替替原來(lái)來(lái)僅有有過(guò)程程的棧棧頂指指示器器,每每個(gè)個(gè)TOP的的值保保存在在各自自活動(dòng)動(dòng)記錄錄中。。這樣樣，上上述的的第二二個(gè)問(wèn)問(wèn)題便便可解解決。。第二二，不不把分分程序序看作作“無(wú)無(wú)參過(guò)過(guò)程””，每每個(gè)分分程序序享用用包圍圍它的的那個(gè)個(gè)最近近過(guò)程程的DISPLAY。每每個(gè)分分程序序都隸隸屬于于某個(gè)個(gè)確定定的過(guò)過(guò)程，，分程程序的的層次次是相相對(duì)于于它所所屬的的那個(gè)個(gè)過(guò)程程進(jìn)行行編號(hào)號(hào)的。。每個(gè)過(guò)過(guò)程被被當(dāng)作作是0層分分程序序。而而過(guò)程程體分分程序序（假假定是是一個(gè)個(gè)分程程序））當(dāng)作作是它它所管管轄的的第1層分分程序序。這樣，，每個(gè)個(gè)過(guò)程程的活活動(dòng)記記錄所所含的的內(nèi)容容有：：1.過(guò)過(guò)程的的TOP值值，它它指向向過(guò)程程活動(dòng)動(dòng)記錄錄的棧棧頂位位置。。2.連連接數(shù)數(shù)據(jù)，，共四四項(xiàng)：：（1)老SP值值；（2)返回回地址址；(3)全局局DISPAY地址址；（4)調(diào)用用時(shí)的的棧頂頂單元元地址址，老老TOP。。3.參參數(shù)數(shù)個(gè)數(shù)數(shù)和形形式單單元4.DISPAY表。5.過(guò)過(guò)程所所轄的的各分分程序序的局局部數(shù)數(shù)據(jù)單單元。。對(duì)對(duì)于每每個(gè)分分程序序來(lái)說(shuō)說(shuō)，它它們包包括：：（1)分程程序的的TOP值值。當(dāng)當(dāng)進(jìn)入入分程程序時(shí)時(shí)它含含現(xiàn)行行棧頂頂?shù)刂分?，以以后，，用?lái)來(lái)定義義棧的的新高高度（（分程程序的的TOP值值）；；（2)分程程序的的局部部變量量，數(shù)數(shù)組組內(nèi)情情向量量和臨臨時(shí)工工作單單元。。BZB1TO

數(shù)

組B

數(shù)

組Be

dB22的TOPB的

內(nèi)

情

向

量B的

內(nèi)

情

向

量

z

zB1的TOPB1的TOPDISPLAYDISPLAY形式單單元m,n2形式單單元m,n2連接數(shù)據(jù)連接數(shù)據(jù)A的TOPA的TOP∶∶∶∶(c)(d)(c)數(shù)組B分配之之后；；（d）進(jìn)入入分程程序B22;參數(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)進(jìn)行交交換，，i,j為為形參參（在在這里里是傳傳值））(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ò)過(guò)程swap的的PASCAL程序序傳地址址（變變量參參數(shù)））例如：：過(guò)程程swap(varx,y:integer);swap(a,b））；（（a,b為調(diào)用用時(shí)的的實(shí)參））調(diào)用結(jié)結(jié)果a,b的值值被改改變。。傳值（（值調(diào)調(diào)用））特點(diǎn)是是對(duì)形形式參參數(shù)的的任何何運(yùn)算算不影影響實(shí)實(shí)參的的值。。例如：：過(guò)程程swap(x,y:integer);swap(a,b））；其結(jié)果果：a,b調(diào)調(diào)用前前的值值不改改變。。傳值的實(shí)現(xiàn)現(xiàn)1.形形式參參數(shù)當(dāng)當(dāng)作過(guò)過(guò)程的的局部部變量量處理理，即即在被被調(diào)過(guò)過(guò)程的的活動(dòng)動(dòng)記錄錄中開(kāi)開(kāi)辟了了形參參的存存儲(chǔ)空空間，，這些些存儲(chǔ)儲(chǔ)位置置即是是我們們所說(shuō)說(shuō)的形形式單單元（（用以以存放放實(shí)參參）。。2.調(diào)調(diào)用過(guò)過(guò)程計(jì)計(jì)算實(shí)實(shí)參的的值，，并將將其放放在對(duì)對(duì)應(yīng)形形式單單元開(kāi)開(kāi)辟的的空間間中。。3.被被調(diào)用用過(guò)程程執(zhí)行行時(shí)，，就像像使用用局部部變量量一樣樣使用用這些些形式式單元元。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(a,b)過(guò)過(guò)程將將不會(huì)會(huì)影響響a和和b的值。。其其結(jié)果果等價(jià)價(jià)于執(zhí)執(zhí)行下下列運(yùn)運(yùn)算：：x:=a；y:=b；temp:=x；；x:=y；y:=temp傳地址址的實(shí)現(xiàn)現(xiàn)（call-by-reference)(call-by-address)(call-by-location)把實(shí)在在參數(shù)數(shù)的地地址傳傳遞給給相應(yīng)應(yīng)的形形參，，即調(diào)用過(guò)程程把一個(gè)個(gè)指向?qū)崒?shí)參的存存儲(chǔ)地址址的指針針傳遞給給被調(diào)用用過(guò)程相相應(yīng)的形形參：1實(shí)在參參數(shù)是一一個(gè)名字字，或具具有左值值的表達(dá)達(dá)式----傳傳遞左值值2實(shí)在參參數(shù)是無(wú)無(wú)左值的的表達(dá)式式----計(jì)算算值，放放入一存存儲(chǔ)單元元，傳此此存儲(chǔ)單單元地址址3目標(biāo)代代碼中，，被調(diào)用用過(guò)程對(duì)對(duì)形參的的引用變變成對(duì)傳傳遞給被被調(diào)用過(guò)過(guò)程的指指針的間間接引用用procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；；調(diào)用swap(i,a[i])其結(jié)果等等價(jià)于執(zhí)執(zhí)行下列列運(yùn)算：：1把I和a[i]的的地址分分別放到到x和y相應(yīng)的的單元a1,a22(temp:=x；)temp的內(nèi)內(nèi)容置為為a1所所指單元元中存的的內(nèi)容3(x:=y;)a1所指單單元的內(nèi)內(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)}在一個(gè)值值調(diào)用過(guò)過(guò)程中使使用指針針的C程程序在C程序序中無(wú)傳傳地址所所以用指指針實(shí)現(xiàn)現(xiàn)。過(guò)程調(diào)用用的四元元式序列列Scallid(<arglist>)<arglist><arglist>,E<arglist>EparT1parT2parTncallid,n過(guò)程作為為參數(shù)傳傳遞三種環(huán)境境：詞法法環(huán)境傳遞環(huán)境境活動(dòng)環(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嵌嵌套過(guò)程程作為參參數(shù)傳遞遞各種數(shù)據(jù)據(jù)對(duì)象的的存儲(chǔ)分分配數(shù)據(jù)對(duì)象象name名字字，名稱稱type類類型location內(nèi)內(nèi)存地址址value值值component成成分分建立內(nèi)