第7章-運(yùn)行時(shí)存儲空間組織

1、第九章 運(yùn)行時(shí)存儲空 間組織內(nèi)容線索n目標(biāo)程序運(yùn)行時(shí)的活動目標(biāo)程序運(yùn)行時(shí)的活動n運(yùn)行時(shí)存儲器的劃分運(yùn)行時(shí)存儲器的劃分 n靜態(tài)存儲分配靜態(tài)存儲分配n簡單的棧式存儲分配簡單的棧式存儲分配n嵌套過程語言的棧式實(shí)現(xiàn)嵌套過程語言的棧式實(shí)現(xiàn)過程的活動n過程定義：過程名過程體過程定義：過程名過程體n過程調(diào)用：過程名出現(xiàn)在可執(zhí)行語句中。過程調(diào)用：過程名出現(xiàn)在可執(zhí)行語句中。n過程的活動：過程的一次執(zhí)行。過程的活動：過程的一次執(zhí)行。n活動的生存期：執(zhí)行過程體第一步操作到活動的生存期：執(zhí)行過程體第一步操作到最后一步操作之間的操作序列，包括該過最后一步操作之間的操作序列，包括該過程調(diào)用其它過程花費(fèi)的時(shí)間。程調(diào)用其它過

2、程花費(fèi)的時(shí)間。（1） program sort(input, output)（2） var a: array0.10 of integer;（3） procedure readarray;（4） var i: integer;（5） begin（6） for i:=1 to 9 do read(ai)（7） end;（8） function partition(y, z:integer):integer;（9） var i:integer;（10） begin .（11） end;program sort procedure readarray function partition(y pro

3、cedure quicksort（12） procedure quicksort(m, n:integer);（13） var i:integer;（14） begin（15） if (nm) then begin（16） i:=partition(m, n );（17） quicksort(m, i-1 );（18） quicksort(i+1, n )（19） end;（20） end;（21） begin（22） a0:=-9999; a10:=9999;（23） readarray;（24） quicksort(1, 9 )（25） gram sort procedure

4、 readarray function partition(y procedure quicksort過程的活動n每次控制從過程每次控制從過程P進(jìn)入過程進(jìn)入過程Q后，如果沒有錯(cuò)誤，最后都后，如果沒有錯(cuò)誤，最后都返回到過程返回到過程P。對于非遞歸的兩個(gè)過程，如果對于非遞歸的兩個(gè)過程，如果a和和b都是過程的活動，那么它們的都是過程的活動，那么它們的生存期或者是生存期或者是不重疊不重疊的，或者是的，或者是嵌套嵌套的。的。n如果一個(gè)過程是遞歸的，那么在某一時(shí)刻可能有這個(gè)過程如果一個(gè)過程是遞歸的，那么在某一時(shí)刻可能有這個(gè)過程的幾個(gè)活動活躍著。的幾個(gè)活動活躍著。n編譯程序組織存儲空間時(shí)，要考慮激活一個(gè)過程

5、的新活動編譯程序組織存儲空間時(shí)，要考慮激活一個(gè)過程的新活動時(shí)或從過程的活動返回時(shí)，對局部名的處理，及是否允許時(shí)或從過程的活動返回時(shí)，對局部名的處理，及是否允許靜態(tài)或動態(tài)存儲分配等。靜態(tài)或動態(tài)存儲分配等。過程調(diào)用n過程（函數(shù)）是結(jié)構(gòu)化程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)過程（函數(shù)）是結(jié)構(gòu)化程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和擴(kuò)充語言能力的主要途徑。省程序代碼和擴(kuò)充語言能力的主要途徑。n過程定義：過程定義： procedure add(x,y:integer; var z:integer) begin z：=x+y; end;n過程調(diào)用過程調(diào)用 add(a,b,c); 參數(shù)傳遞n調(diào)用和被調(diào)用過程之

6、間的信息是通過調(diào)用和被調(diào)用過程之間的信息是通過參數(shù)參數(shù)（或全局量）來傳遞的。稱之為（或全局量）來傳遞的。稱之為形式參數(shù)形式參數(shù)與與實(shí)在參數(shù)實(shí)在參數(shù)。傳地址傳地址得結(jié)果得結(jié)果傳值傳值傳名傳名傳地址n把把實(shí)在參數(shù)的地址實(shí)在參數(shù)的地址傳遞給相應(yīng)的傳遞給相應(yīng)的形式參數(shù)形式參數(shù)，形式，形式參數(shù)在過程段有相應(yīng)的形式單元存放相應(yīng)的實(shí)在參數(shù)在過程段有相應(yīng)的形式單元存放相應(yīng)的實(shí)在參數(shù)的地址。參數(shù)的地址。n方法：方法：調(diào)用段預(yù)先把實(shí)在參數(shù)的地址傳遞到被調(diào)用段可以拿調(diào)用段預(yù)先把實(shí)在參數(shù)的地址傳遞到被調(diào)用段可以拿到的地方到的地方；程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)在參程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)

7、在參數(shù)的地址抄進(jìn)自己相應(yīng)的形式單元中數(shù)的地址抄進(jìn)自己相應(yīng)的形式單元中；過程體對形式參數(shù)的引用過程體對形式參數(shù)的引用或賦值被處理成或賦值被處理成對形式單元對形式單元的間接訪問。的間接訪問。例例. 對如下程序?qū)θ缦鲁绦?procedure P(x,y,z) begin y:=y+1; z:=z+x; end program M(input, output) begin A:=2;B:=3; P(A+B,A,A); print A;end傳地址方式下的程序輸出傳地址方式下的程序輸出結(jié)果。結(jié)果。5TA實(shí)參單元實(shí)參單元形參單元形參單元xzy3B 2 3 8結(jié)果輸出結(jié)果輸出A=8procedure swa

8、p (var m:integer; var n: integer); var i:integer; begin i:=m; m:=n; n:=i; endnswap(a,b)把把a(bǔ),b的地址送到已知單元的地址送到已知單元j1和和j2中中m:=j1;n:=j2;i:=m;m:= n;n:=i;得結(jié)果n傳地址的一種變形傳地址的一種變形，但不等價(jià)但不等價(jià)n方法：方法：每個(gè)形參對應(yīng)每個(gè)形參對應(yīng)兩個(gè)形式單元兩個(gè)形式單元，第一個(gè)形式單元存放實(shí)，第一個(gè)形式單元存放實(shí)參地址，第二個(gè)單元存放實(shí)參的值參地址，第二個(gè)單元存放實(shí)參的值。在過程體中對形式參數(shù)的任何引用或賦值都看作對它在過程體中對形式參數(shù)的任何引用或賦值

9、都看作對它的第二個(gè)單元的直接訪問的第二個(gè)單元的直接訪問。過程完成返回前把第二個(gè)單元的內(nèi)容存放到第一個(gè)單過程完成返回前把第二個(gè)單元的內(nèi)容存放到第一個(gè)單元所指的實(shí)參單元中元所指的實(shí)參單元中。例：對如下程序例：對如下程序 procedure P(x,y,z) begin y:=y+1; z:=z+x; end program M(input, output) begin A:=2;B:=3; P(A+B,A,A); print A;end得結(jié)果方式下的程序輸出結(jié)果。得結(jié)果方式下的程序輸出結(jié)果。實(shí)參單元實(shí)參單元形參單元形參單元53TABxyz 5 2 2 3 7 2 7結(jié)果輸出結(jié)果輸出A=7傳值n把實(shí)

10、在參數(shù)的把實(shí)在參數(shù)的值值傳遞給相應(yīng)的形式參數(shù)傳遞給相應(yīng)的形式參數(shù)n方法：方法：調(diào)用段預(yù)先把實(shí)在參數(shù)的的值計(jì)算出來并放在被調(diào)用調(diào)用段預(yù)先把實(shí)在參數(shù)的的值計(jì)算出來并放在被調(diào)用段可以拿到的地方段可以拿到的地方；被調(diào)用段開始工作時(shí)，首先把實(shí)參的值抄入形式參數(shù)被調(diào)用段開始工作時(shí)，首先把實(shí)參的值抄入形式參數(shù)相應(yīng)的單元相應(yīng)的單元；被調(diào)用段中，象引用局部數(shù)據(jù)一樣引用形式單元被調(diào)用段中，象引用局部數(shù)據(jù)一樣引用形式單元。例例. 對如下程序?qū)θ缦鲁绦?procedure P(x,y,z) begin y:=y+1; z:=z+x; end program M(input, output) begin A:=2;B:

11、=3; P(A+B,A,A); print A;end傳值方式下的程序輸出結(jié)果。傳值方式下的程序輸出結(jié)果。實(shí)參單元實(shí)參單元523AB形參單元形參單元Txyz 5 2 2 3 7結(jié)果輸出結(jié)果輸出A=2傳名n過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)參。參。n方法：方法： 在進(jìn)入被調(diào)用段的之前不對實(shí)在參數(shù)預(yù)先進(jìn)行計(jì)值，而是讓過程在進(jìn)入被調(diào)用段的之前不對實(shí)在參數(shù)預(yù)先進(jìn)行計(jì)值，而是讓過程體中每當(dāng)使用到相應(yīng)的形式參數(shù)時(shí)才逐次對它實(shí)行計(jì)值（或計(jì)算體中

12、每當(dāng)使用到相應(yīng)的形式參數(shù)時(shí)才逐次對它實(shí)行計(jì)值（或計(jì)算地址）。因此，通常把實(shí)在參數(shù)處理成一個(gè)子程序（稱為參數(shù)子地址）。因此，通常把實(shí)在參數(shù)處理成一個(gè)子程序（稱為參數(shù)子程序），每當(dāng)過程體中使用到相應(yīng)的形式參數(shù)時(shí)就調(diào)用這個(gè)子程程序），每當(dāng)過程體中使用到相應(yīng)的形式參數(shù)時(shí)就調(diào)用這個(gè)子程序。序。例：對如下程序例：對如下程序 procedure P(x,y,z) begin y:=y+1; z:=z+x; end program M(input, output) begin A:=2;B:=3; P(A+B,A,A); print A;end傳名方式下的程序輸出結(jié)果。傳名方式下的程序輸出結(jié)果。主程序替換為：

13、主程序替換為： beginA:=2；B=3；A:=A+1;A:=A+A+B;print A； end結(jié)果輸出結(jié)果輸出A=9PROGRAM EX var A:integer;PROCEDURE P(B:integer)var A: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);END例例. .procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a :=

14、 5; b := 3; P(a+b,a-b,a,a); write(a);end傳值傳值:傳地址傳地址:得結(jié)果得結(jié)果:傳名傳名:542777小結(jié)n編譯程序?yàn)榱私M織存儲空間，必須考慮下面幾個(gè)編譯程序?yàn)榱私M織存儲空間，必須考慮下面幾個(gè)問題：問題：過程是否允許遞歸？過程是否允許遞歸？當(dāng)控制從一個(gè)過程的活動返回時(shí)，對局部名稱的值如當(dāng)控制從一個(gè)過程的活動返回時(shí)，對局部名稱的值如何處理？何處理？過程是否允許引用非局部名稱？過程是否允許引用非局部名稱？過程調(diào)用時(shí)如何傳遞參數(shù)；過程是否可以做為參數(shù)被過程調(diào)用時(shí)如何傳遞參數(shù)；過程是否可以做為參數(shù)被傳遞和做為結(jié)果被返回？傳遞和做為結(jié)果被返回？存儲空間可否在程序控制

15、下進(jìn)行動態(tài)分配？存儲空間可否在程序控制下進(jìn)行動態(tài)分配？存儲空間是否必須顯式地釋放？存儲空間是否必須顯式地釋放？內(nèi)容線索目標(biāo)程序運(yùn)行時(shí)的活動目標(biāo)程序運(yùn)行時(shí)的活動n運(yùn)行時(shí)存儲器的劃分運(yùn)行時(shí)存儲器的劃分 n靜態(tài)存儲分配靜態(tài)存儲分配n簡單的棧式存儲分配簡單的棧式存儲分配n嵌套過程語言的棧式實(shí)現(xiàn)嵌套過程語言的棧式實(shí)現(xiàn)存儲空間需求n一個(gè)目標(biāo)程序運(yùn)行所需的存儲空間包括一個(gè)目標(biāo)程序運(yùn)行所需的存儲空間包括:存放目標(biāo)代碼的空間存放目標(biāo)代碼的空間存放數(shù)據(jù)項(xiàng)目的空間存放數(shù)據(jù)項(xiàng)目的空間存放程序運(yùn)行的控制或連接數(shù)據(jù)所需單元（控存放程序運(yùn)行的控制或連接數(shù)據(jù)所需單元（控制棧）制棧）n一個(gè)程序在運(yùn)行時(shí)刻的內(nèi)存劃分一個(gè)程序在運(yùn)行

16、時(shí)刻的內(nèi)存劃分:代碼代碼(Code)靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)(Static Data)棧棧(Stack) 堆堆(Heap) 存放動態(tài)數(shù)據(jù)存放動態(tài)數(shù)據(jù)過程活過程活動數(shù)據(jù)動數(shù)據(jù)活動記錄n活動記錄：為了管理一個(gè)過程活動所需的活動記錄：為了管理一個(gè)過程活動所需的信息，使用一個(gè)連續(xù)的存儲塊存放這些信信息，使用一個(gè)連續(xù)的存儲塊存放這些信息，這個(gè)連續(xù)存儲塊稱為息，這個(gè)連續(xù)存儲塊稱為活動記錄活動記錄。n運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動記錄累筑于棧頂。此記錄含有連接的活動記錄累筑于棧頂。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)

17、情向量和臨時(shí)工作單元等。內(nèi)情向量和臨時(shí)工作單元等。n連接數(shù)據(jù)連接數(shù)據(jù)返回地址返回地址動態(tài)鏈：指向調(diào)用該動態(tài)鏈：指向調(diào)用該過程前的最新活動記過程前的最新活動記錄地址的指針。錄地址的指針。靜態(tài)鏈：指向靜態(tài)直靜態(tài)鏈：指向靜態(tài)直接外層最新活動記錄接外層最新活動記錄地址的指針，用來訪地址的指針，用來訪問非局部數(shù)據(jù)。問非局部數(shù)據(jù)。靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012返回地址返回地址TOP 活動記錄內(nèi)容活動記錄內(nèi)容n形式單元：存放相應(yīng)的形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。實(shí)在參數(shù)的地址或值。n局部數(shù)據(jù)區(qū)：局部變量、局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情

18、向量、臨時(shí)工作單內(nèi)情向量、臨時(shí)工作單元（如存放對表達(dá)式求元（如存放對表達(dá)式求值的結(jié)果）。值的結(jié)果）。靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012返回地址返回地址TOP 活動記錄內(nèi)容活動記錄內(nèi)容對任何局部變量對任何局部變量X的引用的引用可表示為變址訪問可表示為變址訪問: dxSP dx: 變量變量X相對于活動記相對于活動記錄起點(diǎn)的地址，在編譯錄起點(diǎn)的地址，在編譯時(shí)可確定。時(shí)可確定。靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012返回地址返回地址TOP 活動記錄內(nèi)容活動記錄內(nèi)容存儲分配策略存

19、儲分配策略n靜態(tài)分配策略靜態(tài)分配策略(FORTRAN)： 如果在編譯時(shí)能確定數(shù)據(jù)空如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法。間的大小，則可采用靜態(tài)分配方法。在編譯時(shí)刻為每個(gè)數(shù)在編譯時(shí)刻為每個(gè)數(shù)據(jù)對象分配固定的存儲單元，且在運(yùn)行時(shí)始終保持不變據(jù)對象分配固定的存儲單元，且在運(yùn)行時(shí)始終保持不變。n動態(tài)分配策略動態(tài)分配策略(PASCAL) ：如果在編譯時(shí)不能確定運(yùn)行時(shí)：如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，則必須采用動態(tài)分配方法。數(shù)據(jù)空間的大小，則必須采用動態(tài)分配方法。允許遞歸過允許遞歸過程和動態(tài)申請釋放內(nèi)存程和動態(tài)申請釋放內(nèi)存。棧式動態(tài)分配棧式動態(tài)分配堆式動態(tài)分配堆式動態(tài)分配內(nèi)容線

20、索目標(biāo)程序運(yùn)行時(shí)的活動目標(biāo)程序運(yùn)行時(shí)的活動運(yùn)行時(shí)存儲器的劃分運(yùn)行時(shí)存儲器的劃分 n靜態(tài)存儲分配靜態(tài)存儲分配n簡單的棧式存儲分配簡單的棧式存儲分配n嵌套過程語言的棧式實(shí)現(xiàn)嵌套過程語言的棧式實(shí)現(xiàn)FORTRAN的存儲分配nFORTRAN語言特點(diǎn)語言特點(diǎn) 不允許遞歸過程；不允許遞歸過程； 不允許可變數(shù)組；不允許可變數(shù)組； 每個(gè)數(shù)據(jù)所需空間是常數(shù)；每個(gè)數(shù)據(jù)所需空間是常數(shù)； 數(shù)據(jù)名性質(zhì)確定；數(shù)據(jù)名性質(zhì)確定；n整個(gè)程序所需空間在編譯時(shí)可確定整個(gè)程序所需空間在編譯時(shí)可確定, 可采用靜態(tài)分配策略可采用靜態(tài)分配策略n 難點(diǎn)難點(diǎn): COMMAN 語句的處理語句的處理 EQUIVALENCE 語句的處理語句的處理存儲

21、結(jié)構(gòu)n數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 局部區(qū)局部區(qū): 每個(gè)程序段一個(gè)每個(gè)程序段一個(gè), （編號（編號128) 存放公用塊中變量的值。存放公用塊中變量的值。n存儲映象存儲映象:描述數(shù)據(jù)區(qū)中名字與描述數(shù)據(jù)區(qū)中名字與地址的對應(yīng)關(guān)系。地址的對應(yīng)關(guān)系。在符號表中，對每個(gè)數(shù)據(jù)名登記其在符號表中，對每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號及在該區(qū)中的相對所屬數(shù)據(jù)區(qū)編號及在該區(qū)中的相對位置。位置。 目標(biāo)程序區(qū)目標(biāo)程序區(qū)表表 區(qū)區(qū)局部區(qū)局部區(qū)1局部區(qū)局部區(qū)2. . .公用區(qū)公用區(qū)1公用區(qū)公用區(qū)2數(shù)數(shù)據(jù)據(jù)區(qū)區(qū). . .局部數(shù)據(jù)區(qū)的內(nèi)容及存放次序局部數(shù)據(jù)區(qū)的內(nèi)容及存放次序寄存器保護(hù)區(qū)寄存器保護(hù)區(qū)返回地址返回地址形式單元形式單元臨時(shí)變量臨時(shí)變量數(shù)

22、組數(shù)組簡單變量簡單變量01A保存調(diào)用此程序段保存調(diào)用此程序段時(shí)的返回地址時(shí)的返回地址保存調(diào)用段留在寄保存調(diào)用段留在寄存器中的有關(guān)信息存器中的有關(guān)信息形式單元是和形式形式單元是和形式參數(shù)（啞元）相對參數(shù)（啞元）相對應(yīng)的，旨在存放實(shí)應(yīng)的，旨在存放實(shí)在參數(shù)的地址或值在參數(shù)的地址或值n考慮子程序段：考慮子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND地地址址名名字字N NA AM ME E性性質(zhì)質(zhì)A AT TT TR RI IB BU UT TE ED DA A A AD DD DR RS SW WA AP P子子程程序序，二二目目A A啞啞，實(shí)實(shí)變變量量k ka

23、 aB B啞啞，實(shí)實(shí)變變量量k ka a+ +2 2T T實(shí)實(shí)變變量量k ka a+ +4 4寄存器保護(hù)區(qū)寄存器保護(hù)區(qū)返回地址返回地址ATB01a臨時(shí)變量的地址分配n特點(diǎn)特點(diǎn): 放中間結(jié)果放中間結(jié)果, 定值一次定值一次, 引用一次引用一次n方法方法: 用棧實(shí)現(xiàn)作用域的層次嵌套用棧實(shí)現(xiàn)作用域的層次嵌套例例. X := A*B - C * D + E * F 四元式四元式 ( *, A, B, T1 ) ( *, C, D, T2 ) ( - , T1, T2, T3 ) ( *, E, F, T4 ) ( +, T3, T4, T5 ) (:=, T5, _ , X )臨時(shí)變量的地址分配 四元式

24、四元式( *, A, B, T1 ) ( *, C, D, T2 )( - , T1, T2, T3 )( *, E, F, T4 )( +, T3, T4, T5 )(:=, T5, _ , X )臨時(shí)變量名臨時(shí)變量名 地址地址 T1 a T2 a+1 T3 a T4 a+1 T5 a代真后的四元式代真后的四元式 ( *, A, B, $a ) ( *, C, D, $(a+1) )( - , $a, $(a+1), $a)( *, E, F, $(a+1) )( +, $a, $(a+1), $a)(:=, $a, _ , X )內(nèi)容線索目標(biāo)程序運(yùn)行時(shí)的活動目標(biāo)程序運(yùn)行時(shí)的活動運(yùn)行時(shí)存儲器

25、的劃分運(yùn)行時(shí)存儲器的劃分 靜態(tài)存儲分配靜態(tài)存儲分配n簡單的棧式存儲分配簡單的棧式存儲分配n嵌套過程語言的棧式實(shí)現(xiàn)嵌套過程語言的棧式實(shí)現(xiàn)簡單程序語言nC語言特點(diǎn)語言特點(diǎn)沒有分程序結(jié)構(gòu)，過沒有分程序結(jié)構(gòu)，過程定義不允許嵌套程定義不允許嵌套允許過程的遞歸調(diào)用。允許過程的遞歸調(diào)用。C語言的程序結(jié)構(gòu)語言的程序結(jié)構(gòu) 全局?jǐn)?shù)據(jù)說明全局?jǐn)?shù)據(jù)說明;main( ) main中數(shù)據(jù)說明；中數(shù)據(jù)說明； void R( ); R 中數(shù)據(jù)說明；中數(shù)據(jù)說明；. . . void Q( ); Q 中數(shù)據(jù)說明；中數(shù)據(jù)說明；. . . 存儲組織n非局部數(shù)據(jù)靜非局部數(shù)據(jù)靜態(tài)分配于棧底。態(tài)分配于棧底。n局部數(shù)據(jù)分配局部數(shù)據(jù)分配于活動

26、記錄。于活動記錄。n棧式棧式: 每調(diào)用每調(diào)用一個(gè)過程將其一個(gè)過程將其活動記錄分配活動記錄分配于棧頂，退出于棧頂，退出一個(gè)過程釋放一個(gè)過程釋放該空間。該空間。主程序過程Q 過程RQ的活動記錄的活動記錄主程序主程序活動記錄活動記錄TOPR的活動記錄的活動記錄SP參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時(shí)單元臨時(shí)單元全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)區(qū)對任何局部變量對任何局部變量X的的引用可表示為變址訪引用可表示為變址訪問問: dxSP dx: 變量變量X相對于活相對于活動記錄起點(diǎn)的地址，動記錄起點(diǎn)的地址，在編譯時(shí)可確定。在編譯時(shí)可確定。參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回

27、地址形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP C的活動記錄C過程調(diào)用n過程調(diào)用的四元式序列過程調(diào)用的四元式序列:par T1par T2 par Tncall P，n參數(shù)傳遞參數(shù)傳遞過程名過程名形參數(shù)目形參數(shù)目1) 每個(gè)每個(gè)par Ti(i=1,2,n)可直接翻譯成如下指令可直接翻譯成如下指令:(i+3)TOP:= Ti (傳值傳值)(i+3)TOP:=addr(Ti) (傳地址傳地址)2) call P，n 被翻譯成被翻譯成: 1TOP:=SP (保護(hù)現(xiàn)行保護(hù)現(xiàn)行SP) 3TOP:=n (傳遞參數(shù)個(gè)數(shù)傳遞參數(shù)個(gè)數(shù)) JSR P (轉(zhuǎn)子指令轉(zhuǎn)子

28、指令)參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時(shí)單元臨時(shí)單元TOP SP 調(diào)用過程的調(diào)用過程的活動記錄活動記錄形式單元形式單元老老SP參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)C過程調(diào)用的翻譯過程3) 轉(zhuǎn)進(jìn)過程轉(zhuǎn)進(jìn)過程P后，首先應(yīng)執(zhí)行后，首先應(yīng)執(zhí)行下述指令下述指令:SP:=TOP+1 (定義新的定義新的SP)1SP:=返回地址返回地址 (保護(hù)返回地址保護(hù)返回地址)TOP:=TOP+L (新新TOP) L：過程過程P的活動記錄所需單元的活動記錄所需單元數(shù)，在編譯時(shí)可確定。數(shù)，在編譯時(shí)可確定。參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老

29、老SP臨時(shí)單元臨時(shí)單元TOP 調(diào)用過程的活動記錄調(diào)用過程的活動記錄返回地址返回地址TOPSP4) 過程返回時(shí)，應(yīng)執(zhí)行下列指令過程返回時(shí)，應(yīng)執(zhí)行下列指令:TOP:=SP-1 (恢復(fù)調(diào)用前恢復(fù)調(diào)用前TOP)SP:=0SP (恢復(fù)調(diào)用前恢復(fù)調(diào)用前SP)X:=2TOP (把返回地址把返回地址取到取到X中中)UJ 0X (按按X返回返回)參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時(shí)單元臨時(shí)單元調(diào)用過程的活動記錄調(diào)用過程的活動記錄TOPSPSPTOP內(nèi)容線索目標(biāo)程序運(yùn)行時(shí)的活動目標(biāo)程序運(yùn)行時(shí)的活動運(yùn)行時(shí)存儲器的劃分運(yùn)行時(shí)存儲器的劃分 n靜態(tài)存儲分配靜態(tài)存儲分

30、配n簡單的棧式存儲分配簡單的棧式存儲分配n嵌套過程語言的棧式實(shí)現(xiàn)嵌套過程語言的棧式實(shí)現(xiàn)Pascal語言n語言特點(diǎn)語言特點(diǎn)過程嵌套定義過程嵌套定義 過程遞歸調(diào)用過程遞歸調(diào)用n一個(gè)一個(gè)PASCAL過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；執(zhí)行體（由一系列的執(zhí)行語句組成）；endPascal過程調(diào)用規(guī)則（1）任何子程序都不能調(diào)用主程序，主程序可直接調(diào)用所有第）任何子程序都不能調(diào)用主程序，主程序可直接調(diào)用所有第1層的子層的子程序。程序。（2）任何子程序（包括主程序）可直接調(diào)用自己的直接內(nèi)層子程序，）任何子

31、程序（包括主程序）可直接調(diào)用自己的直接內(nèi)層子程序，但不能直接調(diào)用隔層的內(nèi)層子程序。但不能直接調(diào)用隔層的內(nèi)層子程序。（3）內(nèi)層子程序可以直接調(diào)用自己及它的任何一層外層子程序（不包）內(nèi)層子程序可以直接調(diào)用自己及它的任何一層外層子程序（不包括主程序）。括主程序）。（4）并列子程序中后說明的可以調(diào)用先說明的，而先說明的不能調(diào)用）并列子程序中后說明的可以調(diào)用先說明的，而先說明的不能調(diào)用后說明的（除非采用向前引用的方式）。后說明的（除非采用向前引用的方式）。（5）一個(gè)子程序可以調(diào)用所有與自己的某個(gè)外層子程序并列，且其說）一個(gè)子程序可以調(diào)用所有與自己的某個(gè)外層子程序并列，且其說明先于這個(gè)外層子程序的子程序。

32、明先于這個(gè)外層子程序的子程序。（6）Pascal語言允許子程序自己調(diào)用自己，這種調(diào)用方式稱為遞歸調(diào)語言允許子程序自己調(diào)用自己，這種調(diào)用方式稱為遞歸調(diào)用用 program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integr)非局部名字的訪問的實(shí)現(xiàn)非局部名字的訪問的實(shí)現(xiàn) n主程序的層次為主程序的層次為0；在；在i層中定義的過程，其層中定義的過程，其層次為層次為i+1;(層數(shù)，層數(shù)，

33、 偏移量偏移量)n過程運(yùn)行時(shí)，必須知道過程運(yùn)行時(shí)，必須知道其其所有外層過程的所有外層過程的當(dāng)前活動記錄的起始地址。當(dāng)前活動記錄的起始地址。靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄嵌套層次顯示表嵌套層次顯示表displayprogram P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer; var v: integer);var c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Q

34、procedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 Rn靜態(tài)鏈靜態(tài)鏈：指向本過程：指向本過程的的直接外層過程直接外層過程的活的活動記錄的起始地址，動記錄的起始地址，也稱存取鏈。也稱存取鏈。n動態(tài)鏈動態(tài)鏈：指向本過程：指向本過程的的調(diào)用過程調(diào)用過程的活動記的活動記錄的起始地址，也稱錄的起始地址，也稱控制鏈?？刂奇?。參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP012動態(tài)鏈動態(tài)鏈(老老SP)T

35、OP 靜態(tài)鏈靜態(tài)鏈靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄00返回地址返回地址102a3x4SP TOPq主程序主程序P00返回地址返回地址102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10SP TOP動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P過程過程 S？第第N層過程調(diào)用層過程調(diào)用第第 N+1層過程，如何層過程，如何確定被調(diào)用過程確定被調(diào)用過程(第第 N+1層層)過程的靜態(tài)鏈？過程的靜態(tài)鏈？A:調(diào)用過程調(diào)用過程(第第N層層過程過程)的最新活動記錄的最新活動記錄的起始地址的起始地址.00返回地址返回地址102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10SP

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

37、參形參)15i161117返回地址返回地址1811192(形參個(gè)數(shù)形參個(gè)數(shù))20u(形參形參)21v(形參形參)22c23d24SP TOP00返回地址返回地址102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 R511返回地址返回地址120131(形參個(gè)數(shù)形參個(gè)數(shù))14b(形參形參)15i161117返回地址返回地址1811192(形參個(gè)數(shù)形參個(gè)數(shù))20u(形參形參)21v(形參形參)22c23d241725返回地址返回地址2611272(形參個(gè)數(shù)形參個(gè)數(shù))28u(形參形參)2

38、9v(形參形參)30c31d32TOPSP 00返回地址返回地址102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 Q511返回地址返回地址120131(形參個(gè)數(shù)形參個(gè)數(shù))14b(形參形參)15i161117返回地址返回地址1811192(形參個(gè)數(shù)形參個(gè)數(shù))20u(形參形參)21v(形參形參)22c23d24TOPSP 1725返回地址返回地址260271(形參個(gè)數(shù)形參個(gè)數(shù))28b(形參形參)29i30？第第N層過程調(diào)用層過程調(diào)用第第 N-x層過程，如何層過程，如何確定被調(diào)用過程

39、確定被調(diào)用過程(第第 N-x層層)過程的靜態(tài)鏈？過程的靜態(tài)鏈？A:沿著調(diào)用過程沿著調(diào)用過程(第第N層過程層過程)的靜態(tài)鏈的的靜態(tài)鏈的向前走向前走x步到達(dá)的活步到達(dá)的活動記錄的靜態(tài)鏈的值。動記錄的靜態(tài)鏈的值。嵌套層次顯示表嵌套層次顯示表displayn當(dāng)進(jìn)入一個(gè)過程后，在建立其活動記錄區(qū)的同時(shí)建立一張當(dāng)進(jìn)入一個(gè)過程后，在建立其活動記錄區(qū)的同時(shí)建立一張嵌套層次顯示表嵌套層次顯示表diaplay，把把diaplay表作為活動記錄的一表作為活動記錄的一部分。部分。n令過程令過程R的外層為的外層為Q，Q的外層為主程序?yàn)榈耐鈱訛橹鞒绦驗(yàn)镻，則過程，則過程R運(yùn)運(yùn)行時(shí)的行時(shí)的DISPLAY表內(nèi)容為：表內(nèi)容為：

40、2R 的現(xiàn)行活動記錄的現(xiàn)行活動記錄的的地址地址(SP 的現(xiàn)值的現(xiàn)值)1Q 的最新活動記錄的最新活動記錄的地址的地址0P 的活動記錄的活動記錄的地址的地址n問題：問題：當(dāng)過程當(dāng)過程P1調(diào)用過程調(diào)用過程P2而進(jìn)入而進(jìn)入P2后，后，P2應(yīng)如何建立起自己的應(yīng)如何建立起自己的display表？表？P0P1P2P0P2P1P0P1P2n問題：問題：當(dāng)過程當(dāng)過程P1調(diào)用過程調(diào)用過程P2而進(jìn)入而進(jìn)入P2后，后，P2應(yīng)如何建立起自己的應(yīng)如何建立起自己的display表？表？P0P1P2l2: P1的最新活動記的最新活動記錄的起始地址錄的起始地址P0的最新活動記的最新活動記錄的起始地址錄的起始地址P1的的disp

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

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

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

44、，P2應(yīng)如何建立起自己的應(yīng)如何建立起自己的display表？表？答案：從答案：從P1的的display表中自底而上地取過表中自底而上地取過l2個(gè)單元（個(gè)單元（l2為為P2的層數(shù)）再添上進(jìn)入的層數(shù)）再添上進(jìn)入P2后后新建立的新建立的SP值就構(gòu)成了值就構(gòu)成了P2的的display表。表。F把把P1的的display表地址作為連接數(shù)據(jù)之一傳表地址作為連接數(shù)據(jù)之一傳送給送給P2就能夠建立就能夠建立P2的的display表。表。P0P1P2P0P2P1P0P1P2嵌套過程語言活動記錄ndiaplay表在活動記表在活動記錄錄中中的相對地址的相對地址d在在編譯時(shí)能完全確定。編譯時(shí)能完全確定。n假定在現(xiàn)行過程

45、中引假定在現(xiàn)行過程中引用了某層過程用了某層過程(令其層令其層次為次為k)的的X變量，那變量，那么，可用下面兩條指么，可用下面兩條指令獲得令獲得X的地址的地址: LD R1 (d+k)SP LD R2 dxR1參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP Display 表表全局全局Diaplay3dprogram P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer; var v: integer);var

46、 c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 R00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形參個(gè)數(shù)形參個(gè)數(shù))809510主程序主程序過程過程 Sc11i12TOPSP 動態(tài)鏈動態(tài)鏈display00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形參個(gè)數(shù)形參個(gè)數(shù))809510主程序主程序P過程過程 S 過程過程 Qc11i12動態(tài)鏈動態(tài)鏈513返回地址返回地址149(全局全局display)151(形參個(gè)數(shù)形參個(gè)數(shù))16b(形參形參)170