目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織概述

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

存儲(chǔ)組織

10.1概述10.2棧式存儲(chǔ)分配的實(shí)現(xiàn)10.3參數(shù)傳遞10.4過程調(diào)用、過程進(jìn)入和過程返回教學(xué)內(nèi)容：教學(xué)方式：

講授式+啟發(fā)式教學(xué)目的：1、介紹目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織方式，包括靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配。2、要求掌握各種存儲(chǔ)組織形式的基本方法。教學(xué)重點(diǎn)：

1、靜態(tài)分配策略和動(dòng)態(tài)分配策略基本思想。

2、嵌套過程語(yǔ)言棧式分配。

3、活動(dòng)記錄、運(yùn)行時(shí)棧的組織。教學(xué)難點(diǎn)：1、嵌套過程語(yǔ)言棧式分配。2、活動(dòng)記錄、運(yùn)行時(shí)棧的組織。教學(xué)時(shí)數(shù)：

2學(xué)時(shí)

10.1概述任務(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ì)通通過說明語(yǔ)語(yǔ)句或隱或或顯規(guī)則而而定義，則則稱這種性性質(zhì)是“靜靜態(tài)”確定定的。動(dòng)態(tài)：如果果名字的性性質(zhì)只有在在程序運(yùn)行行時(shí)才能知知道，則稱稱這種性質(zhì)質(zhì)為“動(dòng)態(tài)態(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;10.2棧式存儲(chǔ)分分配的實(shí)現(xiàn)現(xiàn)1、簡(jiǎn)單的棧棧式存儲(chǔ)分分配的實(shí)現(xiàn)現(xiàn)2、嵌套過程程語(yǔ)言的棧棧式實(shí)現(xiàn)3、分程序結(jié)結(jié)構(gòu)的存儲(chǔ)儲(chǔ)管理1、簡(jiǎn)單的的棧式分配配方案程序結(jié)構(gòu)特特點(diǎn):沒有分程序序結(jié)構(gòu)，過過程定義不不嵌套，過過程可遞歸歸調(diào)用。例:main全局變量的的說明procR……endR;procQ……endQ;主程序執(zhí)行行語(yǔ)句endmain2、嵌套過程程語(yǔ)言的棧棧式

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

數(shù)

組B

數(shù)

組B

e

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)進(jìn)入入分分程程序序B22;10.3參數(shù)數(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)進(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.帶有有過過程程swap的PASCAL程序序傳地地址址（（變變量量參參數(shù)數(shù)））例如如：：過過程程swap(varx,y:integer);swap(a,b）；；（（a,b為調(diào)用用時(shí)時(shí)的的實(shí)參參））調(diào)用用結(jié)結(jié)果果a,b的值值被被改改變變。。傳值值（（值值調(diào)調(diào)用用））特點(diǎn)點(diǎn)是是對(duì)對(duì)形形式式參參數(shù)數(shù)的的任任何何運(yùn)運(yùn)算算不不影影響響實(shí)實(shí)參參的的值值。。例如如：：過過程程swap(x,y:integer);swap(a,b）；；其結(jié)結(jié)果果：：a,b調(diào)用用前前的的值值不不改改變變。。傳值值的實(shí)實(shí)現(xiàn)現(xiàn)1.形式式參參數(shù)數(shù)當(dāng)當(dāng)作作過過程程的的局局部部變變量量處處理理，，即即在在被被調(diào)調(diào)過過程程的的活活動(dòng)動(dòng)記記錄錄中中開開辟辟了了形形參參的的存存儲(chǔ)儲(chǔ)空空間間，，這這些些存存儲(chǔ)儲(chǔ)位位置置即即是是我我們們所所說說的的形形式式單單元元（（用用以以存存放放實(shí)實(shí)參參））。。2.調(diào)用用過過程程計(jì)計(jì)算算實(shí)實(shí)參參的的值值，，并并將將其其放放在在對(duì)對(duì)應(yīng)應(yīng)形形式式單單元元開開辟辟的的空空間間中中。。3.被調(diào)調(diào)用用過過程程執(zhí)執(zhí)行行時(shí)時(shí)，，就就像像使使用用局局部部變變量量一一樣樣使使用用這這些些形形式式單單元元。。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用用swap(a,b)過程程將將不不會(huì)會(huì)影影響響a和b的值值。。其其結(jié)結(jié)果果等等價(jià)價(jià)于于執(zhí)執(zhí)行行下下列列運(yùn)運(yùn)算算：：x:=a；y:=b；temp:=x；x:=y；y:=temp傳地地址址的實(shí)實(shí)現(xiàn)現(xiàn)（call-by-reference)(call-by-address)(call-by-location)把實(shí)實(shí)在在參參數(shù)數(shù)的的地地址址傳傳遞遞給給相相應(yīng)應(yīng)的的形形參參，，即即調(diào)用用過過程程把把一一個(gè)個(gè)指指向向?qū)崒?shí)參參的的存存儲(chǔ)儲(chǔ)地地址址的的指指針針傳傳遞遞給給被被調(diào)調(diào)用用過過程程相相應(yīng)應(yīng)的的形形參參：：1實(shí)在在參參數(shù)數(shù)是是一一個(gè)個(gè)名名字字，，或或具具有有左左值值的的表表達(dá)達(dá)式式----傳遞遞左左值值2實(shí)在在參參數(shù)數(shù)是是無(wú)無(wú)左左值值的的表表達(dá)達(dá)式式----計(jì)算算值值，，放放入入一一存存儲(chǔ)儲(chǔ)單單元元，，傳傳此此存存儲(chǔ)儲(chǔ)單單元元地地址址3目標(biāo)標(biāo)代代碼碼中中，，被被調(diào)調(diào)用用過過程程對(duì)對(duì)形形參參的的引引用用變變成成對(duì)對(duì)傳傳遞遞給給被被調(diào)調(diào)用用過過程程的的指指針針的的間間接接引引用用procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用用swap(i,a[i])其結(jié)結(jié)果果等等價(jià)價(jià)于于執(zhí)執(zhí)行行下下列列運(yùn)運(yùn)算算：：1把把I和a[i]的地地址址分分別別放放到到x和y相應(yīng)應(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)內(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è)個(gè)值值調(diào)調(diào)用用過過程程中中使使用用指指針針的的C程序序在C程序序中中無(wú)無(wú)傳傳地地址址所所以以用用指指針針實(shí)實(shí)現(xiàn)現(xiàn)。。過程程調(diào)調(diào)用用的的四四元元式式序序列列Scallid(<argl