《編譯原理》第9章運行時存儲空間組織

1、整理課件編譯原理第九章第九章 運行時存儲空間組織運行時存儲空間組織整理課件整理課件第九章第九章 運行時存儲空間組織運行時存儲空間組織n目標程序運行時的活動目標程序運行時的活動 n運行時存儲器的劃分運行時存儲器的劃分n靜態(tài)存儲管理靜態(tài)存儲管理n一個簡單棧式存儲分配一個簡單棧式存儲分配n嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)整理課件整理課件第九章第九章 運行時存儲空間組織運行時存儲空間組織9.1 目標程序運行時的活動目標程序運行時的活動 n以以Pascal為例，假定程序由若干個過程組為例，假定程序由若干個過程組成成 過程（過程（procedure）定義定義一個過程的一個過程的活動活動指的是該

2、過程的一次執(zhí)行指的是該過程的一次執(zhí)行 過程過程P一個一個活動的生存期活動的生存期，指的是從執(zhí)行該過程，指的是從執(zhí)行該過程體第一步操作到最后一步操作之間的操作序，體第一步操作到最后一步操作之間的操作序，包括執(zhí)行包括執(zhí)行P時調(diào)用其它過程花費的時間時調(diào)用其它過程花費的時間過程可以是過程可以是遞歸遞歸的的整理課件整理課件（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

3、)（7） end;（8） function partition(y, z:integer):integer;（9） var i:integer;（10） begin .（11） end;program sort procedure readarray function partition procedure quicksort整理課件整理課件（12） procedure quicksort(m, n:integer);（13） var i:integer;（14） begin（15） if (nm) then begin（16） i:=partition(m, n );（17） quickso

4、rt(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 readarray function partition procedure quicksort整理課件整理課件參數(shù)傳遞參數(shù)傳遞n過程是模塊程序設計的主要手段，同時也過程是模塊程序設計的主要手段，同時也是節(jié)省程序代碼和擴充語言的主要途徑。是節(jié)省程序代碼和擴充語言的主要途徑。n過程定義：

5、過程定義：procedure add(x,y:integer; var z:integer) begin z：=x+y; end;n過程調(diào)用過程調(diào)用 add(a,b,c); 整理課件整理課件參數(shù)傳遞方式參數(shù)傳遞方式n傳地址傳地址n得結(jié)果得結(jié)果n傳值傳值n傳名傳名整理課件整理課件參數(shù)傳遞方式參數(shù)傳遞方式一一. . 傳地址傳地址n把實在參數(shù)的地址傳遞給相應的形式參數(shù)把實在參數(shù)的地址傳遞給相應的形式參數(shù)n方法：方法：調(diào)用段預先把實在參數(shù)的調(diào)用段預先把實在參數(shù)的地址地址傳遞到被調(diào)用段傳遞到被調(diào)用段可以拿到的地方可以拿到的地方；程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首

6、先把實在參數(shù)的地址抄進自己相應的形式單元中實在參數(shù)的地址抄進自己相應的形式單元中；過程體對形式參數(shù)的引用域賦值被處理過程體對形式參數(shù)的引用域賦值被處理成成對對形形式單元的間接訪問式單元的間接訪問。nPASCAL的的變量參數(shù)變量參數(shù)方式方式整理課件整理課件procedure swap (var m:integer; var n: integer); var i:integer; begin i:=m; m:=n; n:=i; endq swap(a,b) 把把a,b的地址送到已知單元的地址送到已知單元j1和和j2中中 m:=j1; n:=j2; i:=m; m:= n; n:=i;整理課件整理課

7、件參數(shù)傳遞方式參數(shù)傳遞方式二得結(jié)果二得結(jié)果n傳地址的一種變形傳地址的一種變形n方法：方法：每個形參對應兩個形式單元，第一個形式單元每個形參對應兩個形式單元，第一個形式單元存放存放實參地址實參地址，第二個單元存放，第二個單元存放實參的值實參的值。在過程體中對形式參數(shù)的任何引用或賦值都看在過程體中對形式參數(shù)的任何引用或賦值都看作作對它的第二個單元的直接訪問對它的第二個單元的直接訪問。過程完成返回前把第二個單元的內(nèi)容存放到第過程完成返回前把第二個單元的內(nèi)容存放到第一個單元所指的實參單元中。一個單元所指的實參單元中。n有些有些Fortran采用這種方式；采用這種方式；整理課件整理課件參數(shù)傳遞方式參數(shù)傳

8、遞方式三三傳值傳值n把實在參數(shù)的把實在參數(shù)的值傳遞給相應的形式參數(shù)值傳遞給相應的形式參數(shù)n方法：方法：調(diào)用段預先把實在參數(shù)的的值計算出來并放調(diào)用段預先把實在參數(shù)的的值計算出來并放在被調(diào)用段可以拿到的地方；在被調(diào)用段可以拿到的地方；被調(diào)用段開始工作時，首先把實參的值抄入被調(diào)用段開始工作時，首先把實參的值抄入形式參數(shù)相應的單元；形式參數(shù)相應的單元；被調(diào)用段中，象引用局部數(shù)據(jù)一樣引用形式被調(diào)用段中，象引用局部數(shù)據(jù)一樣引用形式單元。單元。nPASCAL的值參數(shù)的值參數(shù)整理課件整理課件參數(shù)傳遞方式參數(shù)傳遞方式四四傳名傳名n過程調(diào)用的作用相當于把被調(diào)用段的過程過程調(diào)用的作用相當于把被調(diào)用段的過程體抄到調(diào)用

9、出現(xiàn)的地方，但把其中任一出體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應的實參?，F(xiàn)的形式參數(shù)都替換成相應的實參。n方法：方法： 在進入被調(diào)用段之前不對實在參數(shù)預先進行計在進入被調(diào)用段之前不對實在參數(shù)預先進行計值，而是讓過程體中每當使用到相應的形式參值，而是讓過程體中每當使用到相應的形式參數(shù)時才逐次對它實行計值（或計算地址）。因數(shù)時才逐次對它實行計值（或計算地址）。因此，通常把實在參數(shù)處理成一個子程序（稱為此，通常把實在參數(shù)處理成一個子程序（稱為參數(shù)子程序），每當過程體中使用到相應的形參數(shù)子程序），每當過程體中使用到相應的形式參數(shù)時就調(diào)用這個子程序。式參數(shù)時就調(diào)用這個子程序。整理課

10、件整理課件PROGRAM 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 := 5; b := 3; P(a+b,a-b,a,a); write(a);end傳

11、值傳值:傳地址傳地址:得結(jié)果得結(jié)果:傳名傳名:542777整理課件整理課件傳名傳名procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a := 5; b := 3; P(a+b,a-b,a,a); write(a);endBEGIN a := 5; b := 3 a:= a*(a+b) ; a:= a+(a-b) ; write(a);END整理課件整理課件小結(jié) 傳值、傳址、得結(jié)果、傳名整理課件整理課件第九章第九章 運行時存儲空間組織運行時存儲空間組織n目標程序運行時的活動目標程序運行時的活動 n運行時存儲器的劃分運行時存儲器的劃分n靜

12、態(tài)存儲管理靜態(tài)存儲管理n一個簡單棧式存儲分配一個簡單棧式存儲分配n嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)整理課件整理課件編譯程序組織存儲空間須考慮的問題：編譯程序組織存儲空間須考慮的問題：過程是否允許遞歸？過程是否允許遞歸？當控制從一個過程的活動返回時，對局部名當控制從一個過程的活動返回時，對局部名稱的值如何處理？稱的值如何處理？過程是否允許引用非局部名稱？過程是否允許引用非局部名稱？過程調(diào)用時如何傳遞參數(shù)；過程是否可以做過程調(diào)用時如何傳遞參數(shù)；過程是否可以做為參數(shù)被傳遞和做為結(jié)果被返回？為參數(shù)被傳遞和做為結(jié)果被返回？存儲空間可否在程序控制下進行動態(tài)分配？存儲空間可否在程序控制下進行動態(tài)

13、分配？存儲空間是否必須顯式地釋放？存儲空間是否必須顯式地釋放？ 整理課件整理課件9.2 運行時存儲器的劃分運行時存儲器的劃分 n一個一個目標程序運行目標程序運行所需的存儲空間包括所需的存儲空間包括:存放存放目標代碼目標代碼的空間的空間存放存放數(shù)據(jù)項目數(shù)據(jù)項目的空間的空間存放程序運行的存放程序運行的控制或連接數(shù)據(jù)控制或連接數(shù)據(jù)所需單元所需單元(控制控制棧棧)整理課件整理課件n一個程序在運行時刻的內(nèi)存劃分一個程序在運行時刻的內(nèi)存劃分:代碼代碼(Code)靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)(Static Data)棧棧(Stack) 堆堆(Heap) 整理課件整理課件9.2.2 活動記錄活動記錄n活動記錄：活動記錄：

14、為了為了管理過程在一次執(zhí)行中所管理過程在一次執(zhí)行中所需要的信息需要的信息所使用的所使用的一個連續(xù)的存儲塊一個連續(xù)的存儲塊。n假定假定語言的特點語言的特點為為:允許過程遞歸調(diào)用、允允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許許過程含有可變數(shù)組，但過程定義不允許嵌套，如嵌套，如C語言語言。n采用棧式存儲分配機制。采用棧式存儲分配機制。運行時，每當進運行時，每當進入一個過程就有一個相應的活動記錄累筑入一個過程就有一個相應的活動記錄累筑于于棧頂棧頂。此記錄含有。此記錄含有連接數(shù)據(jù)、形式單元、連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時工局部變量、局部數(shù)組的內(nèi)情向量和臨時工作單元作

15、單元等。等。整理課件整理課件對任何對任何局部變量局部變量X的的引用可表示為引用可表示為變址訪變址訪問問: dxSP dx: 變量變量X相對于活相對于活動記錄起點的地址，動記錄起點的地址，在編譯時可確定。在編譯時可確定。參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP 每個過程的每個過程的活動記錄內(nèi)容活動記錄內(nèi)容(非嵌套語言非嵌套語言)整理課件整理課件q連接數(shù)據(jù)連接數(shù)據(jù)返回地址返回地址動態(tài)鏈動態(tài)鏈：指向調(diào)用該：指向調(diào)用該過程前的最新活動記過程前的最新活動記錄地址的指針。錄地址的指針。靜態(tài)鏈：靜態(tài)鏈：指向靜態(tài)直指向靜態(tài)直接外

16、層最新活動記錄接外層最新活動記錄地址的指針，用來訪地址的指針，用來訪問非局部數(shù)據(jù)。問非局部數(shù)據(jù)。靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012返回地址返回地址TOP 每個過程的每個過程的活動記錄內(nèi)容活動記錄內(nèi)容(嵌套語言嵌套語言)整理課件整理課件q形式單元：形式單元：存放相存放相應的實在參數(shù)的地應的實在參數(shù)的地址或值。址或值。q局部數(shù)據(jù)區(qū)局部數(shù)據(jù)區(qū)：局部：局部變量、內(nèi)情向量、變量、內(nèi)情向量、臨時工作單元（如臨時工作單元（如存放對表達式求值存放對表達式求值的結(jié)果）。的結(jié)果）。靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情

17、向量局部變量局部變量SP 012返回地址返回地址TOP 每個過程的活動記錄內(nèi)容每個過程的活動記錄內(nèi)容整理課件整理課件n 靜態(tài)分配策略靜態(tài)分配策略(FORTRAN) 如果在編譯時能確定數(shù)據(jù)空間的大小，則可采用靜如果在編譯時能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時刻為每個數(shù)據(jù)項目確定出在態(tài)分配方法：在編譯時刻為每個數(shù)據(jù)項目確定出在運行時刻的存儲空間中的位置。運行時刻的存儲空間中的位置。n動態(tài)分配策略動態(tài)分配策略(PASCAL) 如果在編譯時不能確定運行時數(shù)據(jù)空間的大小，如果在編譯時不能確定運行時數(shù)據(jù)空間的大小，則必須采用動態(tài)分配方法。允許遞歸過程和動態(tài)申則必須采用動態(tài)分配方法。允許遞歸

18、過程和動態(tài)申請釋放內(nèi)存。請釋放內(nèi)存。棧式動態(tài)分配：允許遞歸棧式動態(tài)分配：允許遞歸堆式動態(tài)分配：允許動態(tài)釋放內(nèi)存堆式動態(tài)分配：允許動態(tài)釋放內(nèi)存9.2.3 9.2.3 存儲分配策略存儲分配策略 整理課件整理課件PROGRAM MAIN integer X，YCOMMON /C/A，B ENDSUBROUTINE SUB1 real X，ZCOMMON /C/A1，B1 END9.3 靜態(tài)存儲管理靜態(tài)存儲管理(FORTRAN)整理課件整理課件9.3 靜態(tài)存儲管理靜態(tài)存儲管理nFORTRAN程序的特點程序的特點：整個程序所需數(shù)據(jù)空間：整個程序所需數(shù)據(jù)空間的總量在編譯時完全確定，每個數(shù)據(jù)名的地址可的總量

19、在編譯時完全確定，每個數(shù)據(jù)名的地址可以靜態(tài)地進行分配。以靜態(tài)地進行分配。n由于每個由于每個FORTRAN 程序段可以獨立編譯，運行程序段可以獨立編譯，運行前由裝入程序把各段連成可運行的整體。前由裝入程序把各段連成可運行的整體。n按按數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)組織存儲組織存儲:每個程序段定義一個每個程序段定義一個局部數(shù)據(jù)區(qū)局部數(shù)據(jù)區(qū)，用來存放程序，用來存放程序段中未出現(xiàn)在段中未出現(xiàn)在COMMON里的局部名的值。里的局部名的值。每個公用塊定義一個每個公用塊定義一個公用數(shù)據(jù)區(qū)公用數(shù)據(jù)區(qū)，用來存放公用，用來存放公用塊里各個名字的值。塊里各個名字的值。整理課件整理課件n每個數(shù)據(jù)區(qū)有一個編號，地址分配時，在每個數(shù)據(jù)區(qū)有

20、一個編號，地址分配時，在符號表中，對每個數(shù)據(jù)名登記其所屬符號表中，對每個數(shù)據(jù)名登記其所屬數(shù)據(jù)數(shù)據(jù)區(qū)編號區(qū)編號及在該區(qū)中的及在該區(qū)中的相對位置相對位置。n每個局部數(shù)據(jù)區(qū)的內(nèi)容及存放次序每個局部數(shù)據(jù)區(qū)的內(nèi)容及存放次序:寄存器保護區(qū)寄存器保護區(qū)返回地址返回地址形式單元形式單元臨時變量臨時變量數(shù)組數(shù)組簡單變量簡單變量01A整理課件整理課件n考慮子程序段：考慮子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND地址地址名字名字NAMENAME性質(zhì)性質(zhì)ATTRIBUTEATTRIBUTEDADAADDRADDRSWAPSWAP子程序，二目子程序，二目A A啞，實變量啞，實

21、變量k ka aB B啞，實變量啞，實變量k ka+2a+2T T實變量實變量k ka+4a+4寄存器保護區(qū)寄存器保護區(qū)返回地址返回地址ATB01aa+2a+4整理課件整理課件第九章第九章 運行時存儲空間組織運行時存儲空間組織n目標程序運行時的活動目標程序運行時的活動 n運行時存儲器的劃分運行時存儲器的劃分n靜態(tài)存儲管理靜態(tài)存儲管理n一個簡單棧式存儲分配一個簡單棧式存儲分配n嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)整理課件整理課件9.4 一個簡單棧式存儲分配一個簡單棧式存儲分配n假定語言的特點為假定語言的特點為:允許過程遞歸調(diào)用、允允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許許

22、過程含有可變數(shù)組，但過程定義不允許嵌套，如嵌套，如C語言語言。n采用采用棧式存儲分配棧式存儲分配機制機制n活動記錄：活動記錄：運行時，每當進入一個過程就運行時，每當進入一個過程就有一個相應的活動記錄累筑于棧頂。此記有一個相應的活動記錄累筑于棧頂。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時工作單元等。局部數(shù)組的內(nèi)情向量和臨時工作單元等。整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程

23、Q 過程過程R全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程R主程序主程序活動記錄活動記錄TOPSP全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程RQ的活動記錄的活動記錄主程序主程序活動記錄活動記錄TOPSP全局數(shù)據(jù)

24、區(qū)全局數(shù)據(jù)區(qū)整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程RQ的活動記錄的活動記錄主程序主程序活動記錄活動記錄TOPR的活動記錄的活動記錄SP參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中

25、的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程RQ的活動記錄的活動記錄主程序主程序活動記錄活動記錄全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)R的活動記錄的活動記錄TOPSPTOPSP整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程RQ的活動記錄的活動記錄主程序主程序活動記錄活動記錄全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)TOPSPTOPSP整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)

26、據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程R主程序主程序活動記錄活動記錄全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)TOPSP整理課件整理課件 全局數(shù)據(jù)說明全局數(shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程Q 過程過程R整理課件整理課件n每個過程的活動記錄內(nèi)容如圖每個過程的活動記錄內(nèi)容如圖:對任何局部變量對任何局部變量X的的引用可表示為變址訪引用可表示為變址訪問問: dxSP dx: 變量變量X相對于活相對于活動記錄起點的地址，動記錄起點

27、的地址，在編譯時可確定。在編譯時可確定。參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP 9.4.1 C的活動記錄的活動記錄 整理課件整理課件n過程調(diào)用的語句過程調(diào)用的語句 P(T1,T2,Tn)n翻譯成四元式序列翻譯成四元式序列:par T1par T2 par Tncall P，n9.4.2 C的過程調(diào)用、過程進入、的過程調(diào)用、過程進入、數(shù)組空間分配和過程返回數(shù)組空間分配和過程返回 整理課件整理課件1) 每個每個par Ti(i=1,2,n)可直接翻譯成如下指令可直接翻譯成如下指令:(i+3)TOP:= Ti (傳值

28、傳值)(i+3)TOP:=addr(Ti) (傳地址傳地址)2) call P，n 被翻譯成被翻譯成:1TOP:=SP (保護現(xiàn)行保護現(xiàn)行SP)3TOP:=n (傳遞參數(shù)個數(shù)傳遞參數(shù)個數(shù))JSR P (轉(zhuǎn)子指令轉(zhuǎn)子指令)參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元對于對于par和和call產(chǎn)生的目標代碼如下產(chǎn)生的目標代碼如下:TOP SP 調(diào)用過程的調(diào)用過程的活動記錄活動記錄形式單元形式單元老老SP參數(shù)個數(shù)參數(shù)個數(shù)整理課件整理課件3) 轉(zhuǎn)進過程轉(zhuǎn)進過程P后，首先應執(zhí)行下述指令后，首先應執(zhí)行下述指令:SP:=TOP+1 (定義新的定義新

29、的SP)1SP:=返回地址返回地址 (保護返回地址保護返回地址)TOP:=TOP+L (新新TOP) L：過程過程P的活動記錄所需單元數(shù)，的活動記錄所需單元數(shù)， 在編譯時可確定。在編譯時可確定。 參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元TOP 調(diào)用過程的活動記錄調(diào)用過程的活動記錄返回地址返回地址TOPSP整理課件整理課件4) 過程返回時，應執(zhí)行下列指令過程返回時，應執(zhí)行下列指令:TOP:=SP-1 (恢復調(diào)用前恢復調(diào)用前TOP)SP:=0SP (恢復調(diào)用前恢復調(diào)用前SP)X:=2TOP (把返回地址把返回地址取到取到X中中)UJ

30、0X (按按X返回返回)參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元調(diào)用過程的活動記錄調(diào)用過程的活動記錄TOPSPSPTOP整理課件整理課件4) 過程返回時，應執(zhí)行下列指令過程返回時，應執(zhí)行下列指令:TOP:=SP-1 (恢復調(diào)用前恢復調(diào)用前TOP)SP:=0SP (恢復調(diào)用前恢復調(diào)用前SP)X:=2TOP (把返回地址把返回地址取到取到X中中)UJ 0X (按按X返回返回)參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元調(diào)用過程的活動記錄調(diào)用過程的活動記錄SPTOP整理課件整理

31、課件小結(jié)小結(jié)n運行時存儲器的劃分運行時存儲器的劃分 活動記錄（像活動記錄（像c等允許遞歸的語言）等允許遞歸的語言） 局部數(shù)據(jù)區(qū)（像局部數(shù)據(jù)區(qū)（像fortran等不含遞歸的語言）等不含遞歸的語言）n一個簡單棧式存儲分配一個簡單棧式存儲分配C的活動記錄的活動記錄C的過程調(diào)用、過程進入、數(shù)組空間分配和過的過程調(diào)用、過程進入、數(shù)組空間分配和過程返回程返回整理課件整理課件第九章第九章 運行時存儲空間組織運行時存儲空間組織n目標程序運行時的活動目標程序運行時的活動 n運行時存儲器的劃分運行時存儲器的劃分n靜態(tài)存儲管理靜態(tài)存儲管理n一個簡單棧式存儲分配一個簡單棧式存儲分配n嵌套過程語言的棧式實現(xiàn)嵌套過程語言

32、的棧式實現(xiàn)整理課件整理課件9.5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)nPASCALn非局部名字的訪問的實現(xiàn)非局部名字的訪問的實現(xiàn)靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄嵌套層次顯示表嵌套層次顯示表displayn過程調(diào)用、過程進入、過程返回過程調(diào)用、過程進入、過程返回整理課件整理課件嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)nPASCALn非局部名字的訪問的實現(xiàn)非局部名字的訪問的實現(xiàn)靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄嵌套層次顯示表嵌套層次顯示表displayn過程調(diào)用、過程進入、過程返回過程調(diào)用、過程進入、過程返回整理課件整理課件9.5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)n假定語言

33、假定語言不僅允許過程的遞歸調(diào)用不僅允許過程的遞歸調(diào)用(和可變和可變數(shù)組數(shù)組)，而且，而且允許過程定義的嵌套允許過程定義的嵌套，如，如PASCAL，PL語言。語言。整理課件整理課件nPASCALPASCAL程序本身可以看成是一個操作系程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。過程可以嵌套和遞歸。一個一個PASCAL過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；執(zhí)行體（由一系列的執(zhí)行語句組成）；end9.5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)整理課件整理課件

34、作用域作用域：一個名字能被使用的區(qū)域范圍：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標識符在不同的過程中代表允許同一個標識符在不同的過程中代表不同的名字。不同的名字。名字作用域規(guī)則名字作用域規(guī)則- 最近嵌套原則最近嵌套原則 n一個在子程序一個在子程序B1中說明的名字中說明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一個內(nèi)層子程序且的一個內(nèi)層子程序且B2中對中對標識符標識符X沒有新的說明，則原來的名字沒有新的說明，則原來的名字X在在B2中仍然有效。中仍然有效。n如果如果B2對對X重新作了說明，那么，重新作了說明，那么，

35、B2對對X的任何引用都是指重新說明過的這個的任何引用都是指重新說明過的這個X。整理課件整理課件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)整理課件整理課件嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)nPASCALn非局部名字的訪問的實現(xiàn)非局部名字的訪問的實現(xiàn)靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄嵌套層次顯示表嵌套層次顯示表displayn過程調(diào)用、過程進入、過

36、程返回過程調(diào)用、過程進入、過程返回整理課件整理課件9.5.1 非局部名字的訪問的實現(xiàn)非局部名字的訪問的實現(xiàn) n主程序的層次為主程序的層次為0；在；在i層中定義的過程，其層中定義的過程，其層次為層次為i+1;(層數(shù)，層數(shù)， 偏移量偏移量)n過程運行時，必須知道過程運行時，必須知道其其所有外層過程的所有外層過程的當前活動記錄的起始地址。當前活動記錄的起始地址。整理課件整理課件 程序程序program P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer; var v: integer);

37、var 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 過程過程 RS的活動記錄的活動記錄主程序主程序P活動記錄活動記錄全局數(shù)據(jù)區(qū)全局數(shù)據(jù)區(qū)Q的活動記錄的活動記錄R的活動記錄的活動記錄R的活動記錄的活動記錄整理課件整理課件嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)nPASCALn非局部

38、名字的訪問的實現(xiàn)非局部名字的訪問的實現(xiàn)靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄嵌套層次顯示表嵌套層次顯示表displayn過程調(diào)用、過程進入、過程返回過程調(diào)用、過程進入、過程返回整理課件整理課件一、靜態(tài)鏈和活動記錄一、靜態(tài)鏈和活動記錄 n靜態(tài)鏈靜態(tài)鏈：指向本過程：指向本過程的的直接外層直接外層過程的活過程的活動記錄的起始地址，動記錄的起始地址，也稱存取鏈。也稱存取鏈。n動態(tài)鏈動態(tài)鏈：指向本過程：指向本過程的的調(diào)用過程調(diào)用過程的活動記的活動記錄的起始地址，也稱錄的起始地址，也稱控制鏈?？刂奇?。參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP012動態(tài)鏈

39、動態(tài)鏈(老老SP)TOP 靜態(tài)鏈靜態(tài)鏈整理課件整理課件 程序程序program 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 Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程

40、序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 R整理課件整理課件00返回地址返回地址102a3x4SP TOPq主程序主程序P參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP012動態(tài)鏈動態(tài)鏈(老老SP)TOP 靜態(tài)鏈靜態(tài)鏈整理課件整理課件00返回地址返回地址102a3x405返回地址返回地址6070(形參個數(shù)形參個數(shù))8c9i10SP TOP動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P過程過程 S參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP012動態(tài)鏈動態(tài)鏈(老老SP)TOP

41、靜態(tài)鏈靜態(tài)鏈整理課件整理課件00返回地址返回地址102a3x405返回地址返回地址6070(形參個數(shù)形參個數(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(形參個數(shù)形參個數(shù))8c9i10SP TOP動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程

42、過程 Q511返回地址返回地址120131(形參個數(shù)形參個數(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(形參個數(shù)形參個數(shù))8c9i10動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R511返回地址返回地址120131(形參個數(shù)形參個數(shù))14b(形參形參)15i161117返回地址返回地址18111

43、92(形參個數(shù)形參個數(shù))20u(形參形參)21v(形參形參)22c23d24SP TOP整理課件整理課件00返回地址返回地址102a3x405返回地址返回地址6070(形參個數(shù)形參個數(shù))8c9i10動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 R511返回地址返回地址120131(形參個數(shù)形參個數(shù))14b(形參形參)15i161117返回地址返回地址1811192(形參個數(shù)形參個數(shù))20u(形參形參)21v(形參形參)22c23d241725返回地址返回地址2611272(形參個數(shù)形參個數(shù))28u(形參形參)29v(形參形參)30c31d32TO

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

45、 N-x層層)過程的靜態(tài)鏈？過程的靜態(tài)鏈？A:沿著調(diào)用過程沿著調(diào)用過程(第第N層過程層過程)的靜態(tài)鏈向的靜態(tài)鏈向前走前走x步到達的活動步到達的活動記錄的靜態(tài)鏈的值。記錄的靜態(tài)鏈的值。整理課件整理課件嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)第第N層過程調(diào)用第層過程調(diào)用第 N+1層：層：P2的靜態(tài)鏈為調(diào)用過程的靜態(tài)鏈為調(diào)用過程P1（第（第N層過程）的最新活動記錄的起層過程）的最新活動記錄的起始地址始地址第第N層過程調(diào)用第層過程調(diào)用第 N層：層：P2的的靜態(tài)鏈為調(diào)用過程靜態(tài)鏈為調(diào)用過程P1（第（第N層層過程）的靜態(tài)鏈的值過程）的靜態(tài)鏈的值第第N層過程調(diào)用第層過程調(diào)用第 N-x層：層：P2的靜態(tài)鏈

46、為沿著調(diào)用過程的靜態(tài)鏈為沿著調(diào)用過程P1的的靜態(tài)鏈向前走靜態(tài)鏈向前走x步到達的活動步到達的活動記錄的靜態(tài)鏈的值。記錄的靜態(tài)鏈的值。P0P2P1P0P1P2P0P1P2整理課件整理課件嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)nPASCALn非局部名字的訪問的實現(xiàn)非局部名字的訪問的實現(xiàn)靜態(tài)鏈和活動記錄靜態(tài)鏈和活動記錄嵌套層次顯示表嵌套層次顯示表displayn過程調(diào)用、過程進入、過程返回過程調(diào)用、過程進入、過程返回整理課件整理課件二、嵌套層次顯示表二、嵌套層次顯示表displayn當進入一個過程后，在建立其活動記錄當進入一個過程后，在建立其活動記錄區(qū)的同時建立一張嵌套層次顯示表區(qū)的同時建立一張

47、嵌套層次顯示表diaplay，把把diaplay表作為活動記錄的表作為活動記錄的一部分。一部分。整理課件整理課件n令過程令過程R的外層為的外層為Q，Q的外層為主程序的外層為主程序為為P，則則過程過程R運行時的運行時的DISPLAY表內(nèi)容表內(nèi)容為：為：2R 的現(xiàn)行活動記錄的現(xiàn)行活動記錄的的地址地址(SP 的現(xiàn)值的現(xiàn)值)1Q 的最新活動記錄的最新活動記錄的地址的地址0P 的活動記錄的活動記錄的地址的地址PRQ整理課件整理課件n問題：問題：當過程當過程P1調(diào)用過程調(diào)用過程P2而進入而進入P2后，后，P2應如何建立起自己的應如何建立起自己的display表？表？P0P1P2P0P2P1P0P1P2整理

48、課件整理課件n問題：問題：當過程當過程P1調(diào)用過程調(diào)用過程P2而進入而進入P2后，后，P2應如何建立起自己的應如何建立起自己的display表？表？P0P1P2l2: P1的最新活動記的最新活動記錄的起始地址錄的起始地址P0的最新活動記的最新活動記錄的起始地址錄的起始地址P1的的display表表P0的最新活動記錄的最新活動記錄的起始地址的起始地址l2: P2的最新活動記的最新活動記錄的起始地址錄的起始地址P2的的display表表從從P1的的display表中自底而上地取過表中自底而上地取過l2個個單元（單元（l2為為P2的層數(shù)）再添上進入的層數(shù)）再添上進入P2后后新建立的新建立的SP值就構(gòu)

49、成了值就構(gòu)成了P2的的display表。表。 0l2-1 l2整理課件整理課件n問題：問題：當過程當過程P1調(diào)用過程調(diào)用過程P2而進入而進入P2后，后，P2應如何建立起自己的應如何建立起自己的display表？表？P0P2P1l2-1: P1的最新活動的最新活動記錄的起始地址記錄的起始地址P0的最新活動記錄的最新活動記錄的起始地址的起始地址P1的的display表表P0的最新活動記錄的最新活動記錄的起始地址的起始地址P1的最新活動記錄的最新活動記錄的起始地址的起始地址P2的的display表表從從P1的的display表中自底而上地取過表中自底而上地取過l2個個單元（單元（l2為為P2的層數(shù)）

50、再添上進入的層數(shù)）再添上進入P2后后新建立的新建立的SP值就構(gòu)成了值就構(gòu)成了P2的的display表。表。l2: P2的最新活動記的最新活動記錄的起始地址錄的起始地址l2-2l2-1整理課件整理課件n問題：問題：當過程當過程P1調(diào)用過程調(diào)用過程P2而進入而進入P2后，后，P2應如何建立起自己的應如何建立起自己的display表？表？P0P1P2P1的最新活動記錄的最新活動記錄的起始地址的起始地址P0的最新活動記錄的最新活動記錄的起始地址的起始地址P1的的display表表P0的最新活動記錄的最新活動記錄的起始地址的起始地址P2的的display表表從從P1的的display表中自底而上地取過表

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

52、SP值就構(gòu)成了值就構(gòu)成了P2的的display表。表。F把把P1的的display表表（全局全局display表表）地址地址作為作為連接數(shù)據(jù)之一傳送給連接數(shù)據(jù)之一傳送給P2就能夠建立就能夠建立P2的的display表。表。P0P1P2P0P2P1P0P1P2整理課件整理課件n全局全局display：調(diào)用過程：調(diào)用過程的的display表地址表地址ndiaplay表在活動記錄表在活動記錄中中的相對地址的相對地址d在編譯時能在編譯時能完全確定。完全確定。n假定在現(xiàn)行過程中引用了假定在現(xiàn)行過程中引用了某層過程某層過程(令其層次為令其層次為k)的的X變量，那么，可用下面變量，那么，可用下面兩條指令獲得

53、兩條指令獲得X的地址的地址: LD R1 (d+k)SP LD R2 dxR1嵌套過程語言活動記錄嵌套過程語言活動記錄參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP Display 表表全局全局Display3d整理課件整理課件program 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+

54、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 過程過程 R整理課件整理課件00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形參個數(shù)形參個數(shù))809510主程序主程序過程過程 Sc11i12TOPSP 動態(tài)鏈動態(tài)鏈參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP Display 表表全局全局Display3d整理課件整理課件00返回地址返回地址10(display)2a3x405返回地址返回地址62(全局全局display)70(形參個數(shù)形參個數(shù))809510主程序主程序P過程過程 S 過程過程 Qc11i12動態(tài)鏈動態(tài)鏈513返回地址返回地址149(全局全局display)151(形參個數(shù)形參個數(shù))16b(形參形