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

Ch8運(yùn)行時(shí)存儲(chǔ)空間組織課件1（1）programsort(input,output)（2）vara:array[0..10]ofinteger;（3）procedurereadarray;（4）vari:integer;（5）begin（6）fori:=1to9doread(a[i])（7）end;（8）functionpartition(y,z:integer):integer;（9）vari:integer;（10）begin......（11）end;programsortprocedurereadarray

functionpartition(yprocedurequicksort（1）programsort(input,output2（12）procedurequicksort(m,n:integer);（13）vari:integer;（14）begin（15）if(n>m)thenbegin（16）i:=partition(m,n);（17）

quicksort(m,i-1);（18）quicksort(i+1,n)（19）end;（20）end;（21）begin（22）a[0]:=-9999;a[10]:=9999;（23）readarray;（24）quicksort(1,9)（25）gramsortprocedurereadarray

functionpartition(yprocedurequicksort（12）procedurequicksort(m,n3參數(shù)傳遞過程是模塊程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和擴(kuò)充語言的主要途徑。過程定義：procedureadd(x,y:integer;varz:integer)beginz：=x+y;end;過程調(diào)用

add(a,b,c);參數(shù)傳遞過程是模塊程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和4參數(shù)傳遞方式一.傳地址把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)方法：調(diào)用段預(yù)先把實(shí)在參數(shù)的地址傳遞到被調(diào)用段可以拿到的地方；程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)在參數(shù)的地址抄進(jìn)自己相應(yīng)的形式單元中；過程體對(duì)形式參數(shù)的引用域賦值被處理成對(duì)形式單元的間接訪問。PASCAL的變量參數(shù)方式參數(shù)傳遞方式一.傳地址5procedureswap(varm:integer;varn:integer);vari:integer;begini:=m;m:=n;n:=i;endswap(a,b)把a(bǔ),b的地址送到已知單元j1和j2中m:=j1;n:=j2;i:=m↑;m↑:=n↑;n↑:=i;procedureswap(varm:integer;6參數(shù)傳遞方式二．得結(jié)果傳地址的一種變形方法：每個(gè)形參對(duì)應(yīng)兩個(gè)形式單元，第一個(gè)形式單元存放實(shí)參地址，第二個(gè)單元存放實(shí)參的值。在過程體中對(duì)形式參數(shù)的任何引用或賦值都看作對(duì)它的第二個(gè)單元的直接訪問。過程完成返回前把第二個(gè)單元的內(nèi)容存放到第一個(gè)單元所指的實(shí)參單元中。有些Fortran采用這種方式；參數(shù)傳遞方式二．得結(jié)果7參數(shù)傳遞方式三．傳值把實(shí)在參數(shù)的值傳遞給相應(yīng)的形式參數(shù)方法：調(diào)用段預(yù)先把實(shí)在參數(shù)的的值計(jì)算出來并放在被調(diào)用段可以拿到的地方；被調(diào)用段開始工作時(shí)，首先把實(shí)參的值抄入形式參數(shù)相應(yīng)的單元；被調(diào)用段中，象引用局部數(shù)據(jù)一樣引用形式單元。PASCAL的值參數(shù)參數(shù)傳遞方式三．傳值8參數(shù)傳遞方式四．傳名過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)參。方法：在進(jìn)入被調(diào)用段的之前不對(duì)實(shí)在參數(shù)預(yù)先進(jìn)行計(jì)值，而是讓過程體中每當(dāng)使用到相應(yīng)的形式參數(shù)時(shí)才逐次對(duì)它實(shí)行計(jì)值（或計(jì)算地址）。因此，通常把實(shí)在參數(shù)處理成一個(gè)子程序（稱為參數(shù)子程序），每當(dāng)過程體中使用到相應(yīng)的形式參數(shù)時(shí)就調(diào)用這個(gè)子程序。參數(shù)傳遞方式四．傳名9PROGRAMEX… varA:integer; PROCEDUREP(B:integer) … varA:integer; BEGIN

A:=0;

B:=B+1;

A:=A+B; END;BEGIN

A:=2;

TA:=0;

A:=A

+1;

TA:=TA+A;write(A);ENDBEGIN

A:=2;

P(A);write(A);ENDPROGRAMEXBEGINBEGIN10例：…procedureP(w,x,y,z);beginy:=y*w;z:=z+x;endbegina:=5;b:=3;P(a+b,a-b,a,a);write(a);end傳值: 傳地址:得結(jié)果:傳名: 542777例：傳值: 511編譯程序?yàn)榱私M織存儲(chǔ)空間，必須考慮下面幾個(gè)問題：過程是否允許遞歸？當(dāng)控制從一個(gè)過程的活動(dòng)返回時(shí)，對(duì)局部名稱的值如何處理？過程是否允許引用非局部名稱？過程調(diào)用時(shí)如何傳遞參數(shù)；過程是否可以做為參數(shù)被傳遞和做為結(jié)果被返回？存儲(chǔ)空間可否在程序控制下進(jìn)行動(dòng)態(tài)分配？存儲(chǔ)空間是否必須顯式地釋放？編譯程序?yàn)榱私M織存儲(chǔ)空間，必須考慮下面幾個(gè)問題：128.2運(yùn)行時(shí)存儲(chǔ)器的劃分

一個(gè)目標(biāo)程序運(yùn)行所需的存儲(chǔ)空間包括:存放目標(biāo)代碼的空間存放數(shù)據(jù)項(xiàng)目的空間存放程序運(yùn)行的控制或連接數(shù)據(jù)所需單元(控制棧)8.2運(yùn)行時(shí)存儲(chǔ)器的劃分一個(gè)目標(biāo)程序運(yùn)行所需的存儲(chǔ)空間13一個(gè)程序在運(yùn)行時(shí)刻的內(nèi)存劃分:代碼(Code)靜態(tài)數(shù)據(jù)(StaticData)棧(Stack)堆(Heap)一個(gè)程序在運(yùn)行時(shí)刻的內(nèi)存劃分:代碼(Code)靜態(tài)數(shù)據(jù)棧(S148.2.2活動(dòng)記錄假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如C語言。采用棧式存儲(chǔ)分配機(jī)制活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動(dòng)記錄累筑于棧頂。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。8.2.2活動(dòng)記錄假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許15對(duì)任何局部變量X的引用可表示為變址訪問:dx[SP]dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012老SPTOP每個(gè)過程的活動(dòng)記錄內(nèi)容(非嵌套語言)對(duì)任何局部變量X的引用可表示為變址訪問:參數(shù)個(gè)數(shù)返回地址形式16連接數(shù)據(jù)返回地址動(dòng)態(tài)鏈：指向調(diào)用該過程前的最新活動(dòng)記錄地址的指針。靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針，用來訪問非局部數(shù)據(jù)。靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)單元內(nèi)情向量局部變量SP012返回地址TOP每個(gè)過程的活動(dòng)記錄內(nèi)容(嵌套語言)連接數(shù)據(jù)靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)單元內(nèi)情向量局部變量SP17形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元（如存放對(duì)表達(dá)式求值的結(jié)果）。靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)單元內(nèi)情向量局部變量SP012返回地址TOP每個(gè)過程的活動(dòng)記錄內(nèi)容形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。靜態(tài)鏈動(dòng)態(tài)鏈形式單元18靜態(tài)分配策略(FORTRAN)如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定出在運(yùn)行時(shí)刻的存儲(chǔ)空間中的位置。動(dòng)態(tài)分配策略(PASCAL)如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，則必須采用動(dòng)態(tài)分配方法。允許遞歸過程和動(dòng)態(tài)申請(qǐng)釋放內(nèi)存。棧式動(dòng)態(tài)分配堆式動(dòng)態(tài)分配8.2.3存儲(chǔ)分配策略

靜態(tài)分配策略(FORTRAN)8.2.3存儲(chǔ)分配策略19PROGRAMMAIN…integerX，YCOMMON/C/A，B…ENDSUBROUTINESUB1…realX，ZCOMMON/C/A1，B1…END8.3 靜態(tài)存儲(chǔ)管理PROGRAMMAIN8.3 靜態(tài)存儲(chǔ)管理208.3 靜態(tài)存儲(chǔ)管理FORTRAN程序的特點(diǎn)：整個(gè)程序所需數(shù)據(jù)空間的總量在編譯時(shí)完全確定，每個(gè)數(shù)據(jù)名的地址可以靜態(tài)地進(jìn)行分配。由于每個(gè)FORTRAN程序段可以獨(dú)立編譯，運(yùn)行前由裝入程序把各段連成可運(yùn)行的整體。通常按數(shù)據(jù)區(qū)組織存儲(chǔ):每個(gè)程序段定義一個(gè)局部數(shù)據(jù)區(qū)，用來存放程序段中未出現(xiàn)在COMMON里的局部名的值。每個(gè)公用塊定義一個(gè)公用數(shù)據(jù)區(qū)，用來存放公用塊里各個(gè)名字的值。8.3 靜態(tài)存儲(chǔ)管理FORTRAN程序的特點(diǎn)：整個(gè)程序所需數(shù)21每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號(hào)及在該區(qū)中的相對(duì)位置。每個(gè)局部數(shù)據(jù)區(qū)的內(nèi)容及存放次序:寄存器保護(hù)區(qū)返回地址形式單元臨時(shí)變量數(shù)組簡(jiǎn)單變量01A每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登22考慮子程序段：SUBROUTINESWAP(A,B)T=AA=BB=TRETURNEND寄存器保護(hù)區(qū)返回地址ATB01a考慮子程序段：寄存器保護(hù)區(qū)返回地址ATB01a238.4 一個(gè)簡(jiǎn)單棧式存儲(chǔ)分配假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如C語言。采用棧式存儲(chǔ)分配機(jī)制活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動(dòng)記錄累筑于棧頂。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。8.4 一個(gè)簡(jiǎn)單棧式存儲(chǔ)分配假定語言的特點(diǎn)為:允許過程遞歸24

全局?jǐn)?shù)據(jù)說明Main(){ Main中的數(shù)據(jù)說明}

voidR(){ R中的數(shù)據(jù)說明}…voidQ(){Q中的數(shù)據(jù)說明}主程序→過程Q→過程RQ的活動(dòng)記錄主程序活動(dòng)記錄TOPR的活動(dòng)記錄SP參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)說明主程序→過程Q→過程RQ的活動(dòng)記錄主程序活動(dòng)25每個(gè)過程的活動(dòng)記錄內(nèi)容如圖:對(duì)任何局部變量X的引用可表示為變址訪問:dx[SP]dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012老SPTOP8.4.1C的活動(dòng)記錄每個(gè)過程的活動(dòng)記錄內(nèi)容如圖:對(duì)任何局部變量X的引用可表示為變26過程調(diào)用的四元式序列: parT1 parT2 … parTn callP，n8.4.2C的過程調(diào)用、過程進(jìn)入、數(shù)組空間分配和過程返回過程調(diào)用的四元式序列:8.4.2C的過程調(diào)用、過程進(jìn)入、271)每個(gè)parTi(i=1,2,…n)可直接翻譯成如下指令: (i+3)[TOP]:=Ti (傳值) (i+3)[TOP]:=addr(Ti)(傳地址)2)callP，n被翻譯成:1[TOP]:=SP(保護(hù)現(xiàn)行SP)3[TOP]:=n(傳遞參數(shù)個(gè)數(shù))JSRP(轉(zhuǎn)子指令)參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元對(duì)于par和call產(chǎn)生的目標(biāo)代碼如下:TOP

SP調(diào)用過程的活動(dòng)記錄形式單元老SP參數(shù)個(gè)數(shù)1)每個(gè)parTi(i=1,2,…n)可直接翻譯成如下指283)轉(zhuǎn)進(jìn)過程P后，首先應(yīng)執(zhí)行下述指令: SP:=TOP+1 (定義新的SP) 1[SP]:=返回地址 (保護(hù)返回地址) TOP:=TOP+L (新TOP)L：過程P的活動(dòng)記錄所需單元數(shù)， 在編譯時(shí)可確定。

參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元TOP調(diào)用過程的活動(dòng)記錄返回地址TOPSP3)轉(zhuǎn)進(jìn)過程P后，首先應(yīng)執(zhí)行下述指令:參數(shù)個(gè)數(shù)返回地址形式294)過程返回時(shí)，應(yīng)執(zhí)行下列指令: TOP:=SP-1 (恢復(fù)調(diào)用前TOP) SP:=0[SP] (恢復(fù)調(diào)用前SP) X:=2[TOP] (把返回地址取到X中) UJ0[X] (按X返回)參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元調(diào)用過程的活動(dòng)記錄TOPSPSPTOP4)過程返回時(shí)，應(yīng)執(zhí)行下列指令:參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)308.5嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回8.5嵌套過程語言的棧式實(shí)現(xiàn)PASCAL31嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL328.5 嵌套過程語言的棧式實(shí)現(xiàn)假定語言不僅允許過程的遞歸調(diào)用(和可變數(shù)組)，而且允許過程定義的嵌套，如PASCAL，PL語言。8.5 嵌套過程語言的棧式實(shí)現(xiàn)假定語言不僅允許過程的遞歸調(diào)33PASCALPASCAL程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個(gè)PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end8.5 嵌套過程語言的棧式實(shí)現(xiàn)PASCAL8.5 嵌套過程語言的棧式實(shí)現(xiàn)34作用域：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。允許同一個(gè)標(biāo)識(shí)符在不同的過程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個(gè)在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個(gè)內(nèi)層子程序且B2中對(duì)標(biāo)識(shí)符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對(duì)X重新作了說明，那么，B2對(duì)X的任何引用都是指重新說明過的這個(gè)X。作用域：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。35programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integr)programmainA(real)B(real)B(bo36嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL378.5.1非局部名字的訪問的實(shí)現(xiàn)

主程序的層次為0；在i層中定義的過程，其層次為i+1;(層數(shù)，偏移量)過程運(yùn)行時(shí)，必須知道其所有外層過程的當(dāng)前活動(dòng)記錄的起始地址。8.5.1非局部名字的訪問的實(shí)現(xiàn)主程序的層次為0；在i38嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL39圖9.15程序programP;vara,x:integer;procedureQ(b:integer); vari:integer; procedureR(u:integer;varv:integer); varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS; varc,i:integer; begin a:=1; Q(c); ...... end{S}begin a:=0; S; ......end.{P}主程序P過程

S過程

Q過程

R過程

R圖9.15程序programP;procedureS;40一、靜態(tài)鏈和活動(dòng)記錄靜態(tài)鏈：指向本過程的直接外層過程的活動(dòng)記錄的起始地址，也稱存取鏈。動(dòng)態(tài)鏈：指向本過程的調(diào)用過程的活動(dòng)記錄的起始地址，也稱控制鏈。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012動(dòng)態(tài)鏈(老SP)TOP靜態(tài)鏈一、靜態(tài)鏈和活動(dòng)記錄參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向4100返回地址102a3x4SPTOP主程序P00返回地址102a3x4SPTOP主程序P4200返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10SPTOP動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S？第N層過程調(diào)用第N+1層過程，如何確定被調(diào)用過程(第N+1層)過程的靜態(tài)鏈？A:調(diào)用過程(第N層過程)的最新活動(dòng)記錄的起始地址.00返回地址102a3x405返回地址6070(形參個(gè)數(shù))84300返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10SPTOP動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q511返回地址120131(形參個(gè)數(shù))14b(形參)15i16？第N層過程調(diào)用第N層過程，如何確定被調(diào)用過程(第N層)過程的靜態(tài)鏈？A:調(diào)用過程(第N層過程)的靜態(tài)鏈的值。00返回地址102a3x405返回地址6070(形參個(gè)數(shù))84400返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q

過程

R511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d24SPTOP00返回地址102a3x405返回地址6070(形參個(gè)數(shù))84500返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q

過程

R

過程

R511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d241725返回地址2611272(形參個(gè)數(shù))28u(形參)29v(形參)30c31d32TOPSP00返回地址102a3x405返回地址6070(形參個(gè)數(shù))84600返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q

過程

R

過程

Q511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d24TOPSP1725返回地址260271(形參個(gè)數(shù))28b(形參)29i30？第N層過程調(diào)用第N-x層過程，如何確定被調(diào)用過程(第N-x層)過程的靜態(tài)鏈？A:沿著調(diào)用過程(第N層過程)的靜態(tài)鏈的向前走x步到達(dá)的活動(dòng)記錄的靜態(tài)鏈的值。00返回地址102a3x405返回地址6070(形參個(gè)數(shù))847嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL48二、嵌套層次顯示表display當(dāng)進(jìn)入一個(gè)過程后，在建立其活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay，把diaplay表作為活動(dòng)記錄的一部分。二、嵌套層次顯示表display49令過程R的外層為Q，Q的外層為主程序?yàn)镻，則過程R運(yùn)行時(shí)的DISPLAY表內(nèi)容為：令過程R的外層為Q，Q的外層為主程序?yàn)镻，則過程R運(yùn)行時(shí)的D50問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P0P2P1P0P1P2問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自51問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2l2:P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址l2:

P2的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自52問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P2P1l2-1:

P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址P1的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。l2:

P2的最新活動(dòng)記錄的起始地址問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自53問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。l2:

P2的最新活動(dòng)記錄的起始地址l2:P2的最新活動(dòng)記錄的起始地址問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自54問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？答案：從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。把P1的display表地址作為連接數(shù)據(jù)之一傳送給P2就能夠建立P2的display表。P0P1P2P0P2P1P0P1P2問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自55diaplay表在活動(dòng)記錄中的相對(duì)地址d在編譯時(shí)能完全確定。假定在現(xiàn)行過程中引用了某層過程(令其層次為k)的X變量，那么，可用下面兩條指令獲得X的地址:LDR1(d+k)[SP]LDR2dx[R1]嵌套過程語言活動(dòng)記錄參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012老SPTOPDisplay表全局Diaplay3d…diaplay表在活動(dòng)記錄中的相對(duì)地址d在編譯時(shí)能完全確定。56圖9.15程序programP;vara,x:integer;procedureQ(b:integer); vari:integer; procedureR(u:integer;varv:integer); varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS; varc,i:integer; begin a:=1; Q(c); ...... end{S}begin a:=0; S; ......end.{P}主程序P過程

S過程

Q過程

R過程

R圖9.15程序programP;procedureS;5700返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序過程

Sc11i12TOPSP動(dòng)態(tài)鏈00返回地址10(display)2a3x405返回地址625800返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序P過程

S

過程

Qc11i12動(dòng)態(tài)鏈513返回地址149(全局display)151(形參個(gè)數(shù))16b(形參)170181319i20TOPSP00返回地址10(display)2a3x405返回地址625900返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序P過程

S

過程

Q

過程

Rc11i12動(dòng)態(tài)鏈513返回地址149(全局display)151(形參個(gè)數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個(gè)數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP00返回地址10(display)2a3x405返回地址626000返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序P過程

S

過程

Q

過程

R

過程

Rc11i12動(dòng)態(tài)鏈513返回地址149(全局display)151(形參個(gè)數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個(gè)數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP2132返回地址3327(全局display)342(形參個(gè)數(shù))35u(形參)36v(形參)3703813393240c41d4200返回地址10(display)2a3x405返回地址6261嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL62參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局Diaplay1.每個(gè)parTi(i=1,2,…n)可直接翻譯成如下指令: (i+4)[TOP]:=Ti

(傳值)(i+4)[TOP]:=addr(Ti) (傳地址)過程調(diào)用、過程進(jìn)入、過程返回TOPSP調(diào)用過程的活動(dòng)記錄……形式單元參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDis63參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局Diaplay2.callP，n被翻譯成:1[TOP]:=SP (保護(hù)現(xiàn)行SP)3[TOP]:=SP+d(傳送現(xiàn)行display地址)4[TOP]:=n (傳遞參數(shù)個(gè)數(shù))JSR (轉(zhuǎn)子指令)過程調(diào)用、過程進(jìn)入、過程返回TOPSP調(diào)用過程的活動(dòng)記錄……老SP全局Diaplay參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDis643.轉(zhuǎn)進(jìn)過程P后，首先定義新的SP和TOP，保存返回地址。4.根據(jù)"全局display"建立現(xiàn)行過程的display：從全局display表中自底向上地取l個(gè)單元，在添上進(jìn)入P后新建立的SP值就構(gòu)成了P的display。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局DiaplayTOPSP調(diào)用過程的活動(dòng)記錄……返回地址Display表3.轉(zhuǎn)進(jìn)過程P后，首先定義新的SP和TOP，保存返回地址。655.過程返回時(shí)，執(zhí)行下述指令: TOP:=SP-1 SP:=0[SP] X:=2[TOP] UJ0[X]參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局DiaplayTOPSP調(diào)用過程的活動(dòng)記錄……TOPSP5.過程返回時(shí)，執(zhí)行下述指令:參數(shù)個(gè)數(shù)返回地址形式單元臨66嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL67三、上面兩種方法的"折中"——PL編譯程序建立一個(gè)總的運(yùn)行時(shí)的diaplay表(而不是每個(gè)過程的活動(dòng)記錄中都有一個(gè))，它記錄正被調(diào)用執(zhí)行的過程及其所有外層過程的活動(dòng)記錄的起始地址。通過這個(gè)diaplay訪問數(shù)據(jù)。在各過程活動(dòng)記錄之間保留一條"靜態(tài)鏈SL"，它主要用于由層次大的過程調(diào)用層次小的過程后返回時(shí)，恢復(fù)調(diào)用前的display內(nèi)容。(這時(shí)，調(diào)用返回后，執(zhí)行一條UDIS指令)三、上面兩種方法的"折中"——PL編譯程序68PL中每個(gè)過程的活動(dòng)記錄結(jié)構(gòu):1)簡(jiǎn)單局部變量2)連接數(shù)據(jù)返回地址RA動(dòng)態(tài)鏈DL，指向過程調(diào)用者的活動(dòng)記錄起始地址靜態(tài)鏈SL,指向過程的直接外層過程活動(dòng)記錄起始地址靜態(tài)鏈指針SL形式單元局部變量數(shù)組SP012返回地址RATOP動(dòng)態(tài)鏈指針DL3PL中每個(gè)過程的活動(dòng)記錄結(jié)構(gòu):靜態(tài)鏈指針SL形式單元局部變量69programP;varx,y:integer;...procedureP1;vari,j:integer;...procedureP11(a,b:integer);...begin...end;begin...callP11(i,j);...end;

procedureP2;vars,t:integer;...procedureP21;begin...end;begin...callP1...end;begin...callP2;...gramP;procedureP2;70012x3y4RA5SL(0)6DL(0)7s8t90152主程序P

過程

P2

過程

P1

過程

P11DisplayP的活動(dòng)記錄P2的活動(dòng)記錄RA10SL(0)11DL(5)12i13j14102P1的活動(dòng)記錄RA15SL(10)16DL(10)17a18b19P11的活動(dòng)記錄153012x3y4RA5SL(0)6DL(0)7s8t9015271012x3y4RA5SL(0)6DL(0)7s8t9RA10SL(0)11DL(5)12i13j14RA15SL(10)16DL(10)17a18b1901102主程序P

過程

P2

過程

P1

過程

P11P的活動(dòng)記錄P2的活動(dòng)記錄P1的活動(dòng)記錄P11的活動(dòng)記錄15352Display012x3y4RA5SL(0)6DL(0)7s8t9RA1072programP;varx,y:integer;...procedureP1;vari,j:integer;...procedureP11(a,b:integer);...begin...end;begin...callP11(i,j);...end;procedureP2;vars,t:integer;...

procedureP21;varu,v:integer;...begin... callP1...end;begin...callP21...end;begin...callP2;...gramP;procedureP21;73012x3y4RA5SL(0)6DL(0)7s8t90152主程序P

過程

P2

過程

P21

過程

P1DisplayP的活動(dòng)記錄P2的活動(dòng)記錄RA10SL(5)11DL(5)12u13v14103P21的活動(dòng)記錄RA15SL(0)16DL(10)17i18j19P1的活動(dòng)記錄152012x3y4RA5SL(0)6DL(0)7s8t9015274謝謝大家！謝謝大家！75Ch8運(yùn)行時(shí)存儲(chǔ)空間組織課件76（1）programsort(input,output)（2）vara:array[0..10]ofinteger;（3）procedurereadarray;（4）vari:integer;（5）begin（6）fori:=1to9doread(a[i])（7）end;（8）functionpartition(y,z:integer):integer;（9）vari:integer;（10）begin......（11）end;programsortprocedurereadarray

functionpartition(yprocedurequicksort（1）programsort(input,output77（12）procedurequicksort(m,n:integer);（13）vari:integer;（14）begin（15）if(n>m)thenbegin（16）i:=partition(m,n);（17）

quicksort(m,i-1);（18）quicksort(i+1,n)（19）end;（20）end;（21）begin（22）a[0]:=-9999;a[10]:=9999;（23）readarray;（24）quicksort(1,9)（25）gramsortprocedurereadarray

functionpartition(yprocedurequicksort（12）procedurequicksort(m,n78參數(shù)傳遞過程是模塊程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和擴(kuò)充語言的主要途徑。過程定義：procedureadd(x,y:integer;varz:integer)beginz：=x+y;end;過程調(diào)用

add(a,b,c);參數(shù)傳遞過程是模塊程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和79參數(shù)傳遞方式一.傳地址把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)方法：調(diào)用段預(yù)先把實(shí)在參數(shù)的地址傳遞到被調(diào)用段可以拿到的地方；程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)在參數(shù)的地址抄進(jìn)自己相應(yīng)的形式單元中；過程體對(duì)形式參數(shù)的引用域賦值被處理成對(duì)形式單元的間接訪問。PASCAL的變量參數(shù)方式參數(shù)傳遞方式一.傳地址80procedureswap(varm:integer;varn:integer);vari:integer;begini:=m;m:=n;n:=i;endswap(a,b)把a(bǔ),b的地址送到已知單元j1和j2中m:=j1;n:=j2;i:=m↑;m↑:=n↑;n↑:=i;procedureswap(varm:integer;81參數(shù)傳遞方式二．得結(jié)果傳地址的一種變形方法：每個(gè)形參對(duì)應(yīng)兩個(gè)形式單元，第一個(gè)形式單元存放實(shí)參地址，第二個(gè)單元存放實(shí)參的值。在過程體中對(duì)形式參數(shù)的任何引用或賦值都看作對(duì)它的第二個(gè)單元的直接訪問。過程完成返回前把第二個(gè)單元的內(nèi)容存放到第一個(gè)單元所指的實(shí)參單元中。有些Fortran采用這種方式；參數(shù)傳遞方式二．得結(jié)果82參數(shù)傳遞方式三．傳值把實(shí)在參數(shù)的值傳遞給相應(yīng)的形式參數(shù)方法：調(diào)用段預(yù)先把實(shí)在參數(shù)的的值計(jì)算出來并放在被調(diào)用段可以拿到的地方；被調(diào)用段開始工作時(shí)，首先把實(shí)參的值抄入形式參數(shù)相應(yīng)的單元；被調(diào)用段中，象引用局部數(shù)據(jù)一樣引用形式單元。PASCAL的值參數(shù)參數(shù)傳遞方式三．傳值83參數(shù)傳遞方式四．傳名過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)參。方法：在進(jìn)入被調(diào)用段的之前不對(duì)實(shí)在參數(shù)預(yù)先進(jìn)行計(jì)值，而是讓過程體中每當(dāng)使用到相應(yīng)的形式參數(shù)時(shí)才逐次對(duì)它實(shí)行計(jì)值（或計(jì)算地址）。因此，通常把實(shí)在參數(shù)處理成一個(gè)子程序（稱為參數(shù)子程序），每當(dāng)過程體中使用到相應(yīng)的形式參數(shù)時(shí)就調(diào)用這個(gè)子程序。參數(shù)傳遞方式四．傳名84PROGRAMEX… varA:integer; PROCEDUREP(B:integer) … varA:integer; BEGIN

A:=0;

B:=B+1;

A:=A+B; END;BEGIN

A:=2;

TA:=0;

A:=A

+1;

TA:=TA+A;write(A);ENDBEGIN

A:=2;

P(A);write(A);ENDPROGRAMEXBEGINBEGIN85例：…procedureP(w,x,y,z);beginy:=y*w;z:=z+x;endbegina:=5;b:=3;P(a+b,a-b,a,a);write(a);end傳值: 傳地址:得結(jié)果:傳名: 542777例：傳值: 586編譯程序?yàn)榱私M織存儲(chǔ)空間，必須考慮下面幾個(gè)問題：過程是否允許遞歸？當(dāng)控制從一個(gè)過程的活動(dòng)返回時(shí)，對(duì)局部名稱的值如何處理？過程是否允許引用非局部名稱？過程調(diào)用時(shí)如何傳遞參數(shù)；過程是否可以做為參數(shù)被傳遞和做為結(jié)果被返回？存儲(chǔ)空間可否在程序控制下進(jìn)行動(dòng)態(tài)分配？存儲(chǔ)空間是否必須顯式地釋放？編譯程序?yàn)榱私M織存儲(chǔ)空間，必須考慮下面幾個(gè)問題：878.2運(yùn)行時(shí)存儲(chǔ)器的劃分

一個(gè)目標(biāo)程序運(yùn)行所需的存儲(chǔ)空間包括:存放目標(biāo)代碼的空間存放數(shù)據(jù)項(xiàng)目的空間存放程序運(yùn)行的控制或連接數(shù)據(jù)所需單元(控制棧)8.2運(yùn)行時(shí)存儲(chǔ)器的劃分一個(gè)目標(biāo)程序運(yùn)行所需的存儲(chǔ)空間88一個(gè)程序在運(yùn)行時(shí)刻的內(nèi)存劃分:代碼(Code)靜態(tài)數(shù)據(jù)(StaticData)棧(Stack)堆(Heap)一個(gè)程序在運(yùn)行時(shí)刻的內(nèi)存劃分:代碼(Code)靜態(tài)數(shù)據(jù)棧(S898.2.2活動(dòng)記錄假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如C語言。采用棧式存儲(chǔ)分配機(jī)制活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動(dòng)記錄累筑于棧頂。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。8.2.2活動(dòng)記錄假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許90對(duì)任何局部變量X的引用可表示為變址訪問:dx[SP]dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012老SPTOP每個(gè)過程的活動(dòng)記錄內(nèi)容(非嵌套語言)對(duì)任何局部變量X的引用可表示為變址訪問:參數(shù)個(gè)數(shù)返回地址形式91連接數(shù)據(jù)返回地址動(dòng)態(tài)鏈：指向調(diào)用該過程前的最新活動(dòng)記錄地址的指針。靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針，用來訪問非局部數(shù)據(jù)。靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)單元內(nèi)情向量局部變量SP012返回地址TOP每個(gè)過程的活動(dòng)記錄內(nèi)容(嵌套語言)連接數(shù)據(jù)靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)單元內(nèi)情向量局部變量SP92形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元（如存放對(duì)表達(dá)式求值的結(jié)果）。靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)單元內(nèi)情向量局部變量SP012返回地址TOP每個(gè)過程的活動(dòng)記錄內(nèi)容形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。靜態(tài)鏈動(dòng)態(tài)鏈形式單元93靜態(tài)分配策略(FORTRAN)如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定出在運(yùn)行時(shí)刻的存儲(chǔ)空間中的位置。動(dòng)態(tài)分配策略(PASCAL)如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，則必須采用動(dòng)態(tài)分配方法。允許遞歸過程和動(dòng)態(tài)申請(qǐng)釋放內(nèi)存。棧式動(dòng)態(tài)分配堆式動(dòng)態(tài)分配8.2.3存儲(chǔ)分配策略

靜態(tài)分配策略(FORTRAN)8.2.3存儲(chǔ)分配策略94PROGRAMMAIN…integerX，YCOMMON/C/A，B…ENDSUBROUTINESUB1…realX，ZCOMMON/C/A1，B1…END8.3 靜態(tài)存儲(chǔ)管理PROGRAMMAIN8.3 靜態(tài)存儲(chǔ)管理958.3 靜態(tài)存儲(chǔ)管理FORTRAN程序的特點(diǎn)：整個(gè)程序所需數(shù)據(jù)空間的總量在編譯時(shí)完全確定，每個(gè)數(shù)據(jù)名的地址可以靜態(tài)地進(jìn)行分配。由于每個(gè)FORTRAN程序段可以獨(dú)立編譯，運(yùn)行前由裝入程序把各段連成可運(yùn)行的整體。通常按數(shù)據(jù)區(qū)組織存儲(chǔ):每個(gè)程序段定義一個(gè)局部數(shù)據(jù)區(qū)，用來存放程序段中未出現(xiàn)在COMMON里的局部名的值。每個(gè)公用塊定義一個(gè)公用數(shù)據(jù)區(qū)，用來存放公用塊里各個(gè)名字的值。8.3 靜態(tài)存儲(chǔ)管理FORTRAN程序的特點(diǎn)：整個(gè)程序所需數(shù)96每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號(hào)及在該區(qū)中的相對(duì)位置。每個(gè)局部數(shù)據(jù)區(qū)的內(nèi)容及存放次序:寄存器保護(hù)區(qū)返回地址形式單元臨時(shí)變量數(shù)組簡(jiǎn)單變量01A每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登97考慮子程序段：SUBROUTINESWAP(A,B)T=AA=BB=TRETURNEND寄存器保護(hù)區(qū)返回地址ATB01a考慮子程序段：寄存器保護(hù)區(qū)返回地址ATB01a988.4 一個(gè)簡(jiǎn)單棧式存儲(chǔ)分配假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如C語言。采用棧式存儲(chǔ)分配機(jī)制活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動(dòng)記錄累筑于棧頂。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。8.4 一個(gè)簡(jiǎn)單棧式存儲(chǔ)分配假定語言的特點(diǎn)為:允許過程遞歸99

全局?jǐn)?shù)據(jù)說明Main(){ Main中的數(shù)據(jù)說明}

voidR(){ R中的數(shù)據(jù)說明}…voidQ(){Q中的數(shù)據(jù)說明}主程序→過程Q→過程RQ的活動(dòng)記錄主程序活動(dòng)記錄TOPR的活動(dòng)記錄SP參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)說明主程序→過程Q→過程RQ的活動(dòng)記錄主程序活動(dòng)100每個(gè)過程的活動(dòng)記錄內(nèi)容如圖:對(duì)任何局部變量X的引用可表示為變址訪問:dx[SP]dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012老SPTOP8.4.1C的活動(dòng)記錄每個(gè)過程的活動(dòng)記錄內(nèi)容如圖:對(duì)任何局部變量X的引用可表示為變101過程調(diào)用的四元式序列: parT1 parT2 … parTn callP，n8.4.2C的過程調(diào)用、過程進(jìn)入、數(shù)組空間分配和過程返回過程調(diào)用的四元式序列:8.4.2C的過程調(diào)用、過程進(jìn)入、1021)每個(gè)parTi(i=1,2,…n)可直接翻譯成如下指令: (i+3)[TOP]:=Ti (傳值) (i+3)[TOP]:=addr(Ti)(傳地址)2)callP，n被翻譯成:1[TOP]:=SP(保護(hù)現(xiàn)行SP)3[TOP]:=n(傳遞參數(shù)個(gè)數(shù))JSRP(轉(zhuǎn)子指令)參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元對(duì)于par和call產(chǎn)生的目標(biāo)代碼如下:TOP

SP調(diào)用過程的活動(dòng)記錄形式單元老SP參數(shù)個(gè)數(shù)1)每個(gè)parTi(i=1,2,…n)可直接翻譯成如下指1033)轉(zhuǎn)進(jìn)過程P后，首先應(yīng)執(zhí)行下述指令: SP:=TOP+1 (定義新的SP) 1[SP]:=返回地址 (保護(hù)返回地址) TOP:=TOP+L (新TOP)L：過程P的活動(dòng)記錄所需單元數(shù)， 在編譯時(shí)可確定。

參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元TOP調(diào)用過程的活動(dòng)記錄返回地址TOPSP3)轉(zhuǎn)進(jìn)過程P后，首先應(yīng)執(zhí)行下述指令:參數(shù)個(gè)數(shù)返回地址形式1044)過程返回時(shí)，應(yīng)執(zhí)行下列指令: TOP:=SP-1 (恢復(fù)調(diào)用前TOP) SP:=0[SP] (恢復(fù)調(diào)用前SP) X:=2[TOP] (把返回地址取到X中) UJ0[X] (按X返回)參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元調(diào)用過程的活動(dòng)記錄TOPSPSPTOP4)過程返回時(shí)，應(yīng)執(zhí)行下列指令:參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)1058.5嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回8.5嵌套過程語言的棧式實(shí)現(xiàn)PASCAL106嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL1078.5 嵌套過程語言的棧式實(shí)現(xiàn)假定語言不僅允許過程的遞歸調(diào)用(和可變數(shù)組)，而且允許過程定義的嵌套，如PASCAL，PL語言。8.5 嵌套過程語言的棧式實(shí)現(xiàn)假定語言不僅允許過程的遞歸調(diào)108PASCALPASCAL程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個(gè)PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end8.5 嵌套過程語言的棧式實(shí)現(xiàn)PASCAL8.5 嵌套過程語言的棧式實(shí)現(xiàn)109作用域：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。允許同一個(gè)標(biāo)識(shí)符在不同的過程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個(gè)在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個(gè)內(nèi)層子程序且B2中對(duì)標(biāo)識(shí)符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對(duì)X重新作了說明，那么，B2對(duì)X的任何引用都是指重新說明過的這個(gè)X。作用域：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。110programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integr)programmainA(real)B(real)B(bo111嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL1128.5.1非局部名字的訪問的實(shí)現(xiàn)

主程序的層次為0；在i層中定義的過程，其層次為i+1;(層數(shù)，偏移量)過程運(yùn)行時(shí)，必須知道其所有外層過程的當(dāng)前活動(dòng)記錄的起始地址。8.5.1非局部名字的訪問的實(shí)現(xiàn)主程序的層次為0；在i113嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL114圖9.15程序programP;vara,x:integer;procedureQ(b:integer); vari:integer; procedureR(u:integer;varv:integer); varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS; varc,i:integer; begin a:=1; Q(c); ...... end{S}begin a:=0; S; ......end.{P}主程序P過程

S過程

Q過程

R過程

R圖9.15程序programP;procedureS;115一、靜態(tài)鏈和活動(dòng)記錄靜態(tài)鏈：指向本過程的直接外層過程的活動(dòng)記錄的起始地址，也稱存取鏈。動(dòng)態(tài)鏈：指向本過程的調(diào)用過程的活動(dòng)記錄的起始地址，也稱控制鏈。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012動(dòng)態(tài)鏈(老SP)TOP靜態(tài)鏈一、靜態(tài)鏈和活動(dòng)記錄參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向11600返回地址102a3x4SPTOP主程序P00返回地址102a3x4SPTOP主程序P11700返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10SPTOP動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S？第N層過程調(diào)用第N+1層過程，如何確定被調(diào)用過程(第N+1層)過程的靜態(tài)鏈？A:調(diào)用過程(第N層過程)的最新活動(dòng)記錄的起始地址.00返回地址102a3x405返回地址6070(形參個(gè)數(shù))811800返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10SPTOP動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q511返回地址120131(形參個(gè)數(shù))14b(形參)15i16？第N層過程調(diào)用第N層過程，如何確定被調(diào)用過程(第N層)過程的靜態(tài)鏈？A:調(diào)用過程(第N層過程)的靜態(tài)鏈的值。00返回地址102a3x405返回地址6070(形參個(gè)數(shù))811900返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q

過程

R511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d24SPTOP00返回地址102a3x405返回地址6070(形參個(gè)數(shù))812000返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q

過程

R

過程

R511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d241725返回地址2611272(形參個(gè)數(shù))28u(形參)29v(形參)30c31d32TOPSP00返回地址102a3x405返回地址6070(形參個(gè)數(shù))812100返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過程

S

過程

Q

過程

R

過程

Q511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d24TOPSP1725返回地址260271(形參個(gè)數(shù))28b(形參)29i30？第N層過程調(diào)用第N-x層過程，如何確定被調(diào)用過程(第N-x層)過程的靜態(tài)鏈？A:沿著調(diào)用過程(第N層過程)的靜態(tài)鏈的向前走x步到達(dá)的活動(dòng)記錄的靜態(tài)鏈的值。00返回地址102a3x405返回地址6070(形參個(gè)數(shù))8122嵌套過程語言的棧式實(shí)現(xiàn)PASCAL非局部名字的訪問的實(shí)現(xiàn)靜態(tài)鏈和活動(dòng)記錄嵌套層次顯示表display過程調(diào)用、過程進(jìn)入、過程返回嵌套過程語言的棧式實(shí)現(xiàn)PASCAL123二、嵌套層次顯示表display當(dāng)進(jìn)入一個(gè)過程后，在建立其活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay，把diaplay表作為活動(dòng)記錄的一部分。二、嵌套層次顯示表display124令過程R的外層為Q，Q的外層為主程序?yàn)镻，則過程R運(yùn)行時(shí)的DISPLAY表內(nèi)容為：令過程R的外層為Q，Q的外層為主程序?yàn)镻，則過程R運(yùn)行時(shí)的D125問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P0P2P1P0P1P2問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自126問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2l2:P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址l2:

P2的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自127問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P2P1l2-1:

P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址P1的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。l2:

P2的最新活動(dòng)記錄的起始地址問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自128問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。l2:

P2的最新活動(dòng)記錄的起始地址l2:P2的最新活動(dòng)記錄的起始地址問題：當(dāng)過程P1調(diào)用過程P2