第8章 存儲(chǔ)空間的分配

1、第八章第八章 運(yùn)行時(shí)的存儲(chǔ)空間組織運(yùn)行時(shí)的存儲(chǔ)空間組織8.1 8.1 概述概述8 8.2 .2 靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配8 8.3 .3 動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配2編譯程序的最終目的是將源程序翻譯成等價(jià)的目標(biāo)程序。因此，除了進(jìn)行詞法、語(yǔ)法、語(yǔ)義分析外，在生成目標(biāo)代碼前，需要把程序靜態(tài)的正文與程序運(yùn)行時(shí)的活動(dòng)聯(lián)系起來(lái)，弄清楚在代碼運(yùn)行時(shí)刻，程序中的各種變量、常量等是如何存放的，如何去訪問(wèn)它們。3編譯程序必須分配目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)空間。這些存儲(chǔ)空間包括：用戶定義的各類變量和常量所需存儲(chǔ)單元；作為保留中間結(jié)果的參數(shù)傳遞用的臨時(shí)工作單元；調(diào)用過(guò)程或函數(shù)時(shí)需要的形式單元；返回地址以及組織輸入/輸出所需

2、的緩沖區(qū)。4從本質(zhì)上看，數(shù)據(jù)對(duì)象的空間分配是將程序中的每個(gè)對(duì)象名字與一個(gè)存儲(chǔ)位置進(jìn)行綁定。目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間組織的基本依據(jù)是程序設(shè)計(jì)語(yǔ)言對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定。如：遞歸調(diào)用的過(guò)程，在運(yùn)行時(shí)，其同一個(gè)局部名字應(yīng)對(duì)應(yīng)不同的運(yùn)行空間位置。5過(guò)程是否允許遞歸？當(dāng)控制從一個(gè)過(guò)程的活動(dòng)返回時(shí)，對(duì)局部如何處理？過(guò)程是否允許引用非局部名？過(guò)程調(diào)用時(shí)如何傳遞參數(shù)；過(guò)程是否可以作為參數(shù)被傳遞和作為結(jié)果被返回？存儲(chǔ)空間可否在程序控制下進(jìn)行動(dòng)態(tài)分配?存儲(chǔ)空間是否必須顯式地釋放？6靜態(tài)存儲(chǔ)分配在編譯階段進(jìn)行的存儲(chǔ)分配。對(duì)程序中的簡(jiǎn)單變量和常量數(shù)組，由于它們所需的存儲(chǔ)單元數(shù)在編譯時(shí)就可以確定，因

3、此在編譯時(shí)就可以給它們分配存儲(chǔ)單元。動(dòng)態(tài)存儲(chǔ)分配在運(yùn)行階段才能確定數(shù)據(jù)的位置及大小的分配方法。7靜態(tài)數(shù)據(jù)區(qū)由靜態(tài)存儲(chǔ)分配產(chǎn)生的數(shù)據(jù)區(qū)。這種數(shù)據(jù)區(qū)在整個(gè)程序運(yùn)行過(guò)程中是固定不變的。動(dòng)態(tài)數(shù)據(jù)區(qū)由動(dòng)態(tài)存儲(chǔ)分配產(chǎn)生的數(shù)據(jù)區(qū)。這種數(shù)據(jù)區(qū)不是固定不變的。隨著相應(yīng)程序單位的調(diào)用和返回，它也會(huì)進(jìn)入和退出。8靜態(tài)存儲(chǔ)分配對(duì)程序設(shè)計(jì)語(yǔ)言的要求:不允許有遞歸調(diào)用；不允許有嵌套的子程序；不允許有可變數(shù)組。FORTRAN語(yǔ)言滿足這些要求。9變量地址= 相對(duì)地址 + 起始地址返回地址返回地址寄存器保護(hù)區(qū)寄存器保護(hù)區(qū)形式單元形式單元簡(jiǎn)單變量簡(jiǎn)單變量數(shù)組數(shù)組臨時(shí)變量臨時(shí)變量10很多高級(jí)語(yǔ)言都支持嵌套分程序、嵌套或遞歸過(guò)程結(jié)構(gòu)

4、及動(dòng)態(tài)數(shù)組，這些需要運(yùn)行時(shí)存儲(chǔ)空間管理機(jī)制。棧式存儲(chǔ)分配方法是適合于這類語(yǔ)言的一種存儲(chǔ)管理方法。棧式存儲(chǔ)分配方法是把整個(gè)程序的存儲(chǔ)空間都安排在一個(gè)棧內(nèi)。11進(jìn)入主程序時(shí)，將主程序定義的各類全程量所需存儲(chǔ)空間分配于棧頂；每當(dāng)調(diào)用一個(gè)子程序（過(guò)程/函數(shù)）時(shí)，就將其所需的存儲(chǔ)空間分配于棧的當(dāng)前棧頂；每當(dāng)從子程序運(yùn)行結(jié)束時(shí)，就從棧中釋放其所占空間；整個(gè)程序執(zhí)行完后，釋放它所占用的全部空間。12棧式存儲(chǔ)分配適合于：層次嵌套結(jié)構(gòu)允許過(guò)程遞歸調(diào)用含可變數(shù)組的程序設(shè)計(jì)語(yǔ)言。13數(shù)據(jù)區(qū)內(nèi)容返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元簡(jiǎn)單變量簡(jiǎn)單變量數(shù)組數(shù)組臨時(shí)變量臨時(shí)變量將這樣一個(gè)數(shù)據(jù)區(qū)稱為將這樣一個(gè)數(shù)據(jù)區(qū)

5、稱為一個(gè)一個(gè)活動(dòng)記錄活動(dòng)記錄。活動(dòng)記錄的大小在編譯活動(dòng)記錄的大小在編譯時(shí)可以靜態(tài)地確定。時(shí)可以靜態(tài)地確定。14活動(dòng)數(shù)據(jù)區(qū)的內(nèi)容與靜態(tài)存儲(chǔ)分配的數(shù)據(jù)區(qū)相同，所不同的是要允許遞歸，則每調(diào)用一次過(guò)程都要生成一個(gè)數(shù)據(jù)區(qū)，每次操作都是在新的數(shù)據(jù)區(qū)上進(jìn)行，遞歸調(diào)用多少次就生成多少個(gè)數(shù)據(jù)區(qū)由于只有在運(yùn)行時(shí)才知道調(diào)用多少次，因此只能在運(yùn)行時(shí)確定分配多少空間。1516Program main; 全局變量 procedure R; end;(R) procedure Q; call R; end;(Q) 主程序; call Q; end.(main)設(shè)在主程序中調(diào)用設(shè)在主程序中調(diào)用Q Q，Q Q又調(diào)用了又調(diào)用了R

6、 R，則棧式，則棧式分配為：分配為：主程序的數(shù)據(jù)區(qū)主程序的數(shù)據(jù)區(qū)Q Q的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)R R的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)每調(diào)用一個(gè)過(guò)程就開辟一每調(diào)用一個(gè)過(guò)程就開辟一個(gè)數(shù)據(jù)區(qū)。當(dāng)某個(gè)過(guò)程執(zhí)個(gè)數(shù)據(jù)區(qū)。當(dāng)某個(gè)過(guò)程執(zhí)行完后，退出此過(guò)程的數(shù)行完后，退出此過(guò)程的數(shù)據(jù)區(qū)，進(jìn)入下一個(gè)過(guò)程的據(jù)區(qū)，進(jìn)入下一個(gè)過(guò)程的數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)。運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過(guò)程就將此過(guò)程的數(shù)據(jù)區(qū)（活動(dòng)記錄）置于棧頂。當(dāng)過(guò)程執(zhí)行完畢后，該過(guò)程所對(duì)應(yīng)的數(shù)據(jù)區(qū)也不復(fù)存在，進(jìn)入到下一個(gè)將要執(zhí)行的過(guò)程的數(shù)據(jù)區(qū)中。因此，有必要用兩個(gè)寄存器來(lái)記下數(shù)據(jù)區(qū)的大小。返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元簡(jiǎn)單變量簡(jiǎn)單變量數(shù)組數(shù)組臨時(shí)變量臨時(shí)變量老老sp(sp(

7、控制鏈控制鏈) )topsp活動(dòng)記錄內(nèi)容活動(dòng)記錄內(nèi)容現(xiàn)行過(guò)程活動(dòng)記錄起點(diǎn)現(xiàn)行過(guò)程活動(dòng)記錄起點(diǎn)17全局變量全局變量Q Q的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)R R的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)Q Q的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)sptoptopsp當(dāng)當(dāng)Q Q退出后，退出后，SPSP應(yīng)指到什應(yīng)指到什么地方不知道（因?yàn)槊吹胤讲恢溃ㄒ驗(yàn)镽 R的的長(zhǎng)度不知），因此在每個(gè)長(zhǎng)度不知），因此在每個(gè)數(shù)據(jù)區(qū)設(shè)一老數(shù)據(jù)區(qū)設(shè)一老SPSP記下上一記下上一過(guò)程的過(guò)程的SPSP值。值。18設(shè)a為數(shù)據(jù)區(qū)中的相對(duì)地址，則asp為相對(duì)地址a+sp的地址；簡(jiǎn)單變量簡(jiǎn)單變量老老sp(sp(控制鏈控制鏈) )sp20則則20sp20sp：將：將2020單元單元的簡(jiǎn)單變量取出來(lái)。的

8、簡(jiǎn)單變量取出來(lái)。19過(guò)程調(diào)用四元式:(par,_,_,T1)(par,_,_,T2)(par,_,_,T3)(call,_,_,p) /地址調(diào)用地址調(diào)用 (i+3)top:=add(T (i+3)top:=add(Ti i) ) /值調(diào)用值調(diào)用 (i+3)top:=T (i+3)top:=Ti i 對(duì)應(yīng)的目標(biāo)動(dòng)作：對(duì)應(yīng)的目標(biāo)動(dòng)作：進(jìn)入進(jìn)入P P前的動(dòng)作：前的動(dòng)作： 1top:=sp;1top:=sp;/保存老保存老spsp3top:=3top:=參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù) 進(jìn)入進(jìn)入P P后，首先應(yīng)定義新的活動(dòng)記錄的后，首先應(yīng)定義新的活動(dòng)記錄的sp,sp,然后保存返回地址并定義新的然后保存返回地址并定義新

9、的toptop值值 sptop老老spsp參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):3:3Add(TAdd(T1 1) )Add(TAdd(T2 2) )Add(TAdd(T3 3) )20sp:=top+1; sp:=top+1; /定義新定義新spsp對(duì)應(yīng)的目標(biāo)動(dòng)作：進(jìn)入對(duì)應(yīng)的目標(biāo)動(dòng)作：進(jìn)入P P后的動(dòng)作：后的動(dòng)作： 過(guò)程過(guò)程P P的活動(dòng)記錄長(zhǎng)的活動(dòng)記錄長(zhǎng)度，在編譯時(shí)可靜度，在編譯時(shí)可靜態(tài)計(jì)算出來(lái)。態(tài)計(jì)算出來(lái)。sptopsptop老老spsp參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):3:3Add(TAdd(T1 1) )Add(TAdd(T2 2) )Add(TAdd(T3 3) )1sp:=1sp:=返回地址返回地址; ;/保存返回地

10、址保存返回地址top:=top+L; top:=top+L; /定義新的定義新的toptop返回地址返回地址21對(duì)應(yīng)的目標(biāo)動(dòng)作：從P返回時(shí)的動(dòng)作: top:=sp-1;sptopsptop返回地址返回地址老老spsp參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):3:3Add(TAdd(T1 1) )Add(TAdd(T2 2) )Add(TAdd(T3 3) )sp:=0sp; sp:=0sp; /老老spsp 無(wú)條件轉(zhuǎn)無(wú)條件轉(zhuǎn)2top 2top /返回地址返回地址22動(dòng)態(tài)存儲(chǔ)分配比靜態(tài)存儲(chǔ)分配省空間。因?yàn)楫?dāng)某一過(guò)程執(zhí)行完后就可以釋放它所占的空間，只有當(dāng)都不釋放空間時(shí)才與靜態(tài)分配所用空間相同。但動(dòng)態(tài)分配省空間所付出的代價(jià)

11、是運(yùn)行時(shí)分配，降低了執(zhí)行效率。23某含遞歸調(diào)用的C語(yǔ)言程序： printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10 +0); /打印余數(shù)在主程序中調(diào)用：printd(-125)2425進(jìn)入子過(guò)程體前： (1+3)top=Ti=n=-125 1top=sp=k /保留老sp 3top=參數(shù)個(gè)數(shù)=1sptopsptop參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1返回地址返回地址形參形參:n=-125:n=-125簡(jiǎn)單變量簡(jiǎn)單變量:i=12:i=12老老spsp：K Kk1轉(zhuǎn)入子過(guò)程體轉(zhuǎn)入子過(guò)程體 s

12、p=top+1 sp=top+1 1sp= 1sp=返回地址返回地址 top=top+L top=top+L 進(jìn)入子過(guò)程體內(nèi)進(jìn)入子過(guò)程體內(nèi)，填簡(jiǎn)單變量，填簡(jiǎn)單變量i i 參數(shù)參數(shù):n=-1250,:n=-1250,先打印先打印-,n=125-,n=125； i=125/10=12!=0 : i=125/10=12!=0 : printd(12)printd(12) printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); 形參形參:n=125:n=12526進(jìn)入子過(guò)程體前

13、： (1+3)top=Ti=n=12 1top=sp=k1 3top=參數(shù)個(gè)數(shù)=1sptop簡(jiǎn)單變量簡(jiǎn)單變量:i=1:i=1轉(zhuǎn)入子過(guò)程體轉(zhuǎn)入子過(guò)程體 sp=top+1 sp=top+1 1sp= 1sp=返回地址返回地址 top=top+L top=top+L 進(jìn)入子過(guò)程體內(nèi)進(jìn)入子過(guò)程體內(nèi), ,填簡(jiǎn)單變量填簡(jiǎn)單變量i i i=12/10=1!=0 : i=12/10=1!=0 : printd(1)printd(1) printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0)

14、; 老老sp:k1sp:k1返回地址返回地址形參形參:n=12:n=12k2參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1k1參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1返回地址返回地址形參形參:n=125:n=125老老sp:Ksp:K簡(jiǎn)單變量簡(jiǎn)單變量:i=12:i=12sptop27 進(jìn)入過(guò)程體內(nèi)：進(jìn)入過(guò)程體內(nèi)： 參數(shù)參數(shù)n=1n=1 i=1/10=0; i=1/10=0; putchar putchar打?。捍蛴。?%10+0=1; printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); sptop簡(jiǎn)單變

15、量簡(jiǎn)單變量:i=1:i=1老老sp:k2sp:k2老老sp:k1sp:k1返回地址返回地址形參形參:n=12:n=12k2參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1k1參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1返回地址返回地址形參形參:n=125:n=125老老sp:Ksp:K簡(jiǎn)單變量簡(jiǎn)單變量:i=12:i=12返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1形參形參:n=1:n=1k3簡(jiǎn)單變量簡(jiǎn)單變量:i=0:i=028返回到第返回到第2 2次調(diào)用處次調(diào)用處( (包括返回?cái)?shù)包括返回?cái)?shù)據(jù)區(qū)據(jù)區(qū)):): n=12, n=12,打?。捍蛴。?2%10+0=2 printd(int n) int i; if(n0) putchar(-); n

16、=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); sptop簡(jiǎn)單變量簡(jiǎn)單變量:i=1:i=1老老sp:k1sp:k1返回地址返回地址形參形參:n=12:n=12k2參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1k1參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1返回地址返回地址形參形參:n=125:n=125老老sp:ksp:k簡(jiǎn)單變量簡(jiǎn)單變量:i=12:i=12老老sp:k2sp:k2返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1形參形參:n=1:n=1k3簡(jiǎn)單變量簡(jiǎn)單變量:i=0:i=0topsp29返回到第返回到第1 1次調(diào)用處次調(diào)用處( (包括返回?cái)?shù)包括返回?cái)?shù)據(jù)區(qū)據(jù)區(qū)):): n=125

17、, n=125, 打?。捍蛴。?25%10+0=5 總的打印結(jié)果為：總的打印結(jié)果為：-125-125 printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); 簡(jiǎn)單變量簡(jiǎn)單變量:i=1:i=1老老sp:k1sp:k1返回地址返回地址形參形參:n=12:n=12k2參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1k1參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1返回地址返回地址形參形參:n=125:n=125老老sp:ksp:k簡(jiǎn)單變量簡(jiǎn)單變量:i=12:i=12topspsptop原來(lái)的活動(dòng)記錄簡(jiǎn)單變量簡(jiǎn)單變量數(shù)組數(shù)

18、組臨時(shí)變量臨時(shí)變量若數(shù)組長(zhǎng)度可若數(shù)組長(zhǎng)度可變，則不能確變，則不能確定活動(dòng)記錄的定活動(dòng)記錄的大小，但要求大小，但要求在編譯時(shí)一定在編譯時(shí)一定要能確定活動(dòng)要能確定活動(dòng)記錄的長(zhǎng)度，記錄的長(zhǎng)度，為此，將活動(dòng)為此，將活動(dòng)記錄改為：記錄改為：簡(jiǎn)單變量簡(jiǎn)單變量數(shù)組數(shù)組臨時(shí)變量臨時(shí)變量數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量新的活動(dòng)記錄新的活動(dòng)記錄活活動(dòng)動(dòng)記記錄錄30對(duì)數(shù)組建立內(nèi)情向量，記錄已知信息。如：數(shù)組起始地址數(shù)組起始地址a a維數(shù)維數(shù)n n數(shù)組常量數(shù)組常量C Cd d1 1d d2 2d dn n數(shù)組起始地址數(shù)組起始地址a a維數(shù)維數(shù)n n數(shù)組常量數(shù)組常量C CL L1 1N N1 1d d1 1L L2 2N N2

19、 2d d2 2L Ln nN Nn nd dn n這樣便于計(jì)算數(shù)組越界這樣便于計(jì)算數(shù)組越界31Void p() int A1.m; int B1.n; P P的活動(dòng)記錄的活動(dòng)記錄數(shù)組數(shù)組B B數(shù)組數(shù)組A Asptop32計(jì)算各維的長(zhǎng)度（或上、下限）調(diào)用數(shù)組空間分配子程序，其參數(shù)為各維的長(zhǎng)度（或上、下限）及內(nèi)情向量的起始地址。33填寫內(nèi)情向量中的信息 （數(shù)組起址:=top+1 )調(diào)整top：top:=top+v v為數(shù)組體積P P的活動(dòng)記錄的活動(dòng)記錄數(shù)組數(shù)組topsptop34例： procedure P procedure Q procedure R end end end這種過(guò)程嵌套結(jié)構(gòu)所

20、附這種過(guò)程嵌套結(jié)構(gòu)所附帶的語(yǔ)義檢查：帶的語(yǔ)義檢查：過(guò)程調(diào)用的合理性過(guò)程調(diào)用的合理性變量使用的合法性變量使用的合法性35由于過(guò)程定義是嵌套的，任一個(gè)過(guò)程都可以引用其外層過(guò)程中定義的變量。因此，子過(guò)程必須要知道其全部外層過(guò)程的最新活動(dòng)記錄的地址。由于允許遞歸調(diào)用和包含可變數(shù)組，因此過(guò)程的活動(dòng)記錄位置往往是變化的，因此應(yīng)跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄的位置。36靜態(tài)鏈指向其直接外層過(guò)程的最新活動(dòng)記錄的基地址。Display表每當(dāng)進(jìn)入一個(gè)子過(guò)程時(shí)，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套的層次顯示表display。37Program P; Var a,x: integer; Procedure Q(b:

21、int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 層次層次0 01 12 21 1變量作用域變量作用域a,xa,xb,ib,iu,vu,vc,dc,dc,ic,i38為了在子過(guò)程的活動(dòng)記錄中引用包圍它的某一外層過(guò)程的數(shù)據(jù)，在子過(guò)

22、程的活動(dòng)記錄中添加靜態(tài)鏈，靜態(tài)鏈指向其直接外層過(guò)程的最新活動(dòng)記錄基地址。返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元靜態(tài)鏈靜態(tài)鏈內(nèi)情向量?jī)?nèi)情向量臨時(shí)變量臨時(shí)變量老老spsp簡(jiǎn)單變量簡(jiǎn)單變量sptop39Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var

23、 c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1靜態(tài)鏈?zhǔn)纠o態(tài)鏈?zhǔn)纠? 1P P調(diào)用調(diào)用S S時(shí)時(shí)返回地址返回地址簡(jiǎn)單變量簡(jiǎn)單變量:a:a簡(jiǎn)單變量簡(jiǎn)單變量: x: x老老sp:0sp:0靜態(tài)鏈靜態(tài)鏈:0:0參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0老老sp:0sp:0返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0簡(jiǎn)單變量簡(jiǎn)單變量:i:i簡(jiǎn)單變量簡(jiǎn)單變量:c:c1 13 34 45 57 78 80 06 62 210109 9P的活的活動(dòng)記錄動(dòng)記錄S的活的活動(dòng)記錄動(dòng)記錄SPTOP40Program P; Var a,x: int

24、eger; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1靜態(tài)鏈?zhǔn)纠o態(tài)鏈?zhǔn)纠? 2過(guò)程過(guò)程S S中中調(diào)用調(diào)用Q Q時(shí)時(shí)返回地址返回地址簡(jiǎn)單變量簡(jiǎn)單變量:a:a簡(jiǎn)單變量簡(jiǎn)單

25、變量: x: x老老sp:0sp:0靜態(tài)鏈靜態(tài)鏈:0:0參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0老老sp:0sp:0返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0簡(jiǎn)單變量簡(jiǎn)單變量:i:i返回地址返回地址靜態(tài)鏈靜態(tài)鏈:0:0簡(jiǎn)單變量簡(jiǎn)單變量:c:c老老sp:5sp:5參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1形參形參:b:b簡(jiǎn)單變量簡(jiǎn)單變量:i:i1 13 34 45 57 78 80 06 62 21010121213139 91111151516161414P的活的活動(dòng)記錄動(dòng)記錄S的活的活動(dòng)記錄動(dòng)記錄Q的活的活動(dòng)記錄動(dòng)記錄SPTOP41Program P; Var a,x: integer; Procedure Q(b:int )

26、 Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1靜態(tài)鏈?zhǔn)纠o態(tài)鏈?zhǔn)纠? 3過(guò)程過(guò)程Q Q中中調(diào)用調(diào)用R R時(shí)時(shí)PSPTOP返回地址返回地址簡(jiǎn)單變量簡(jiǎn)單變量:a:a簡(jiǎn)單變量簡(jiǎn)單變量: x: x老老sp:0sp:0靜

27、態(tài)鏈靜態(tài)鏈:0:0參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0老老sp:0sp:0返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0簡(jiǎn)單變量簡(jiǎn)單變量:i:i返回地址返回地址靜態(tài)鏈靜態(tài)鏈:0:0簡(jiǎn)單變量簡(jiǎn)單變量:c:c老老sp:5sp:5形參形參:b:b參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):1:1簡(jiǎn)單變量簡(jiǎn)單變量:i:i返回地址返回地址靜態(tài)鏈靜態(tài)鏈:11:11老老sp:11sp:11形參形參:u:u參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):2:2形參形參:v:v簡(jiǎn)單變量簡(jiǎn)單變量:c:c簡(jiǎn)單變量簡(jiǎn)單變量:d:d1 13 34 45 57 78 80 06 62 21010121213139 9111115151414161618181919171721212020222

28、223232424SQR42在本過(guò)程的活動(dòng)記錄中添加display表（棧式）用來(lái)存放各外層最新活動(dòng)記錄的基地址。43Program Main; 0 A:integer; procedure R;1 B,C:integer; A:=B+C; end; procedure P;1 procedure Q;2 R; end; Q; end; P;End.topspP PQ QMainMainR RR的的displayQ的的display過(guò)程層次過(guò)程層次Q Q的活動(dòng)記錄起址的活動(dòng)記錄起址MainMain的活動(dòng)記錄起址的活動(dòng)記錄起址P P的活動(dòng)記錄起址的活動(dòng)記錄起址0 01 12 2R R的活動(dòng)記錄起址

29、的活動(dòng)記錄起址MainMain的活動(dòng)記錄起址的活動(dòng)記錄起址0 01 144由于每個(gè)過(guò)程的display表的大小可在編譯階段知道，因此為便于組織存儲(chǔ)區(qū)域和簡(jiǎn)化處理過(guò)程，可把display作為活動(dòng)記錄的一部分放在形式單元的上邊?，F(xiàn)在的活動(dòng)記錄為：返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元displaydisplay內(nèi)情向量?jī)?nèi)情向量臨時(shí)變量臨時(shí)變量老老spsp簡(jiǎn)單變量簡(jiǎn)單變量45全局display: 調(diào)用段display表地址,用來(lái)建 立 被 調(diào) 用 段 的display表：從調(diào)用段P1的display表中自底向上抄錄L2個(gè)單元(L2為被調(diào)用段P2的層數(shù))。返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式

30、單元形式單元新新displaydisplay內(nèi)情向量?jī)?nèi)情向量臨時(shí)變量臨時(shí)變量老老spsp簡(jiǎn)單變量簡(jiǎn)單變量老老displaydisplay地址地址d在編譯時(shí)可確定在編譯時(shí)可確定46當(dāng)P1調(diào)用P2,進(jìn)入P2后,P2如何建立自己的 display表?從P1的display表中自底向上抄錄L2個(gè)單元(L2為P2的層數(shù)),再添加p2自己的sp,就構(gòu)成p2的 display表。47P1P1的的displaydisplay有有 項(xiàng)項(xiàng): :P2P2的的displaydisplay表有表有 項(xiàng)項(xiàng): :P1P1的的displaydisplay有有 項(xiàng)項(xiàng): :P2P2的的displaydisplay表有表有 項(xiàng)項(xiàng):

31、 : P0 P0 -0 -0層層 P2 P2 -1-1層層 P1 P1 -1-1層層 call P2 call P2 (p0,p1)(p0,p1)2 2(p0,p1,p2)(p0,p1,p2)3 3 P0 P0 -0 -0層層 P1 P1 -1-1層層 P2 P2 -2-2層層 call P2 call P2 2 22 2(p0,p1)(p0,p1)(p0,p2)(p0,p2)48 P0 P0 -0 -0層層 P2 P2 -1-1層層 P3 P3 -1-1層層 P1 P1 -2-2層層 call P2 call P2 P1P1的的displaydisplay有有 項(xiàng)項(xiàng): :P2P2的的disp

32、laydisplay表有表有 項(xiàng)項(xiàng): :3 32 2(p0,p3,p1)(p0,p3,p1)(p0,p2)(p0,p2)49(par,_,_,Ti)(par,_,_,Ti)的目標(biāo)動(dòng)作的目標(biāo)動(dòng)作: :(i+4)top:=T(i+4)top:=Ti(Call,_,_P)(Call,_,_P)的目標(biāo)動(dòng)作的目標(biāo)動(dòng)作: :1top:=sp; 1top:=sp; /保存老保存老spsp3top:=sp+d;3top:=sp+d; /現(xiàn)行現(xiàn)行displaydisplay地址地址4top:=n; 4top:=n; /保存參數(shù)個(gè)數(shù)保存參數(shù)個(gè)數(shù)sptop返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元新新disp

33、laydisplay內(nèi)情向量?jī)?nèi)情向量臨時(shí)變量臨時(shí)變量老老spsp簡(jiǎn)單變量簡(jiǎn)單變量老老displaydisplay地址地址50進(jìn)入過(guò)程進(jìn)入過(guò)程P P后的目標(biāo)動(dòng)作后的目標(biāo)動(dòng)作( (確定新確定新spsp、toptop位置位置) ) sp:=top+1; sp:=top+1; top:=top+L; top:=top+L; /L /L：活動(dòng)記錄長(zhǎng)度：活動(dòng)記錄長(zhǎng)度 top:=top+V; top:=top+V; /V/V：數(shù)組體積：數(shù)組體積 建立新的建立新的displaydisplay R:=2sp; R:=2sp; /取出老取出老displaydisplay的地址的地址 dsp:=0R;dsp:=0R

34、; d+1sp:=1R; d+1sp:=1R; (d+i-1)sp:=(i-1)R; (d+i-1)sp:=(i-1)R; (d+i)sp:=sp; (d+i)sp:=sp; /新加入的新加入的displaydisplay項(xiàng)項(xiàng)抄老抄老displaydisplaydsptop返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元新新displaydisplay內(nèi)情向量?jī)?nèi)情向量臨時(shí)變量臨時(shí)變量老老spsp簡(jiǎn)單變量簡(jiǎn)單變量老老displaydisplay地址地址511sp:=1sp:=返回地址返回地址; ;/保存返回地址保存返回地址從過(guò)程返回: top:=sp-1; sp:=0sp; /取老sp 無(wú)條件轉(zhuǎn)

35、2top返回地址返回地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元新新displaydisplay內(nèi)情向量?jī)?nèi)情向量臨時(shí)變量臨時(shí)變量老老spsp簡(jiǎn)單變量簡(jiǎn)單變量老老displaydisplay地址地址52Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: i

36、nteger; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1DisplayDisplay表示例表示例1 1P P調(diào)用調(diào)用S S時(shí)時(shí)P的活的活動(dòng)記錄動(dòng)記錄S的活的活動(dòng)記錄動(dòng)記錄SPTOP返回地址返回地址簡(jiǎn)單變量簡(jiǎn)單變量:a:a簡(jiǎn)單變量簡(jiǎn)單變量: x: x老老sp:0sp:0老老display:2display:2參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù):0:0老老sp:0sp:0返回地址返回地址display:0display:0簡(jiǎn)單變量簡(jiǎn)單變量:i:i簡(jiǎn)單變量簡(jiǎn)單變量:c:c5 50 09 91 13 34 45 57 78 80 06 62 21111

37、10101212display0 0層（主程序）過(guò)程的層（主程序）過(guò)程的displaydisplay只含只含1 1項(xiàng)，項(xiàng)，這一項(xiàng)就是主程序開始工作時(shí)所建立的這一項(xiàng)就是主程序開始工作時(shí)所建立的第第1 1個(gè)個(gè)SPSP值。值。53Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1DisplayDisplay表示例表示例2 2過(guò)程過(guò)程S S中中調(diào)用調(diào)用Q Q時(shí)時(shí)P的活的活動(dòng)記錄動(dòng)記錄S的活的活動(dòng)記錄動(dòng)記錄SPTOPdisplaydisplay返回地址返回地址簡(jiǎn)單變量簡(jiǎn)單變量:a:a簡(jiǎn)單變量簡(jiǎn)