第10章目標程序運行時的存儲組織

1、第第1010章章 目標程序運行時的組織目標程序運行時的組織 教學要求：本章介紹目標程序運行時的教學要求：本章介紹目標程序運行時的存儲組織方式，包括靜態(tài)存儲分配和動存儲組織方式，包括靜態(tài)存儲分配和動態(tài)存儲分配。態(tài)存儲分配。 要求掌握各種存儲組織形要求掌握各種存儲組織形式的基本方法。式的基本方法。 教學重點：靜態(tài)分配策略和動態(tài)分配策教學重點：靜態(tài)分配策略和動態(tài)分配策略的基本思想，嵌套過程語言棧式分配，略的基本思想，嵌套過程語言棧式分配，活動記錄、運行時棧的組織?；顒佑涗?、運行時棧的組織。 10.1 10.1 概述概述 從邏輯上看，代碼生成前，編譯程序必須從邏輯上看，代碼生成前，編譯程序必須進行目標

2、程序運行環(huán)境的設計和數據空間進行目標程序運行環(huán)境的設計和數據空間的分配的分配 數據空間包括：用戶定義的各種類型的數數據空間包括：用戶定義的各種類型的數據對象（變量和常量）所需的存儲空間，據對象（變量和常量）所需的存儲空間，作為保留中間結果和傳遞參數的臨時工作作為保留中間結果和傳遞參數的臨時工作單元，調用過程時所需的連接單元，組織單元，調用過程時所需的連接單元，組織輸入輸入/ /輸出所需的緩沖區(qū)。輸出所需的緩沖區(qū)。存儲管理復雜度取決于源語言本身，具體包括：存儲管理復雜度取決于源語言本身，具體包括：允許的數據類型的多少允許的數據類型的多少? ?語言中允許的數據項是語言中允許的數據項是: : 靜態(tài)確

3、定靜態(tài)確定? ?動態(tài)確定動態(tài)確定? ?程序決定名字的作用域的規(guī)則和結構程序決定名字的作用域的規(guī)則和結構段結構段結構? ?過程定義不嵌套過程定義不嵌套? ?只允許過程遞歸調用只允許過程遞歸調用? ?分程序結構分程序結構: : 分程序嵌套分程序嵌套? ?過程定義嵌套過程定義嵌套? ? 目標代碼區(qū)目標代碼區(qū) 靜態(tài)數據區(qū)靜態(tài)數據區(qū) Stack heap目標代碼區(qū)用以存放目標代碼，這是目標代碼區(qū)用以存放目標代碼，這是固定長度的，即編譯時能確定的。固定長度的，即編譯時能確定的。靜態(tài)數據區(qū)用以存放編譯時能確定所靜態(tài)數據區(qū)用以存放編譯時能確定所占用空間的數據。占用空間的數據。堆堆/棧用于存放可變數據以及管理過

4、棧用于存放可變數據以及管理過程活動的控制信息。程活動的控制信息。三種數據區(qū)對應著下述三種不同的分配策略三種數據區(qū)對應著下述三種不同的分配策略在編譯時能確定在編譯時能確定目標程序運行中所需的全部數據空間的大目標程序運行中所需的全部數據空間的大小，編譯時安排好目標程序運行時的全部小，編譯時安排好目標程序運行時的全部數據空間，確定每個數據對象的存儲位置數據空間，確定每個數據對象的存儲位置對任何局部變量對任何局部變量X X的引的引用可表示為變址訪問用可表示為變址訪問: : dxSP dxSP dx: dx: 變量變量X X相對于活相對于活動記錄起點的地址，動記錄起點的地址，在編譯時可確定。在編譯時可確

5、定。SP 012TOP 每個過程的活動記錄內容每個過程的活動記錄內容( (非嵌套語言非嵌套語言) )臨時單臨時單元元內情向內情向量量局部變局部變量量形式單形式單元元參數個參數個數數動態(tài)鏈動態(tài)鏈返回地返回地址址q連接數據連接數據返回地址返回地址動態(tài)鏈：指向調用該動態(tài)鏈：指向調用該過程的最新活動記錄過程的最新活動記錄地址的指針。地址的指針。靜態(tài)鏈：指向直接外靜態(tài)鏈：指向直接外層最新活動記錄地址層最新活動記錄地址的指針，用來訪問非的指針，用來訪問非局部數據。局部數據。SP 012TOP 每個過程的活動記錄內容每個過程的活動記錄內容( (嵌套語言嵌套語言) )臨時單臨時單元元內情向內情向量量局部變局部

6、變量量形式單形式單元元靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈返回地返回地址址q形式單元：存放相形式單元：存放相應的實參的地址或應的實參的地址或值。值。q局部數據區(qū)：局部局部數據區(qū)：局部變量、內情向量、變量、內情向量、臨時工作單元（如臨時工作單元（如存放對表達式求值存放對表達式求值的結果）。的結果）。SP 012TOP 每個過程的活動記錄內容每個過程的活動記錄內容臨時單元臨時單元內情向量內情向量局部變量局部變量形式單元形式單元靜態(tài)鏈靜態(tài)鏈動態(tài)鏈動態(tài)鏈返回地址返回地址 1 1、 call P call P 被翻譯成被翻譯成: :11TOP:=SP (TOP:=SP (保護現行保護現行SP)SP)JSR P (J

7、SR P (轉子指令轉子指令) )參數個數參數個數返回地址返回地址形式單元形式單元內情向量內情向量局部變量局部變量老老SP臨時單元臨時單元活動記錄的填寫活動記錄的填寫TOP SP 調用過程的調用過程的活動記錄活動記錄老老SP2 2、轉進過程、轉進過程P P后，首先應執(zhí)行下述指令后，首先應執(zhí)行下述指令: :SP:=TOP+1 (SP:=TOP+1 (定義新的定義新的SP)SP)1SP:=1SP:=返回地址返回地址 ( (保護返回地址保護返回地址) )TOP:=TOP+L (TOP:=TOP+L (新新TOP)TOP) L L：過程過程P P的活動記錄所需單元數，的活動記錄所需單元數， 在編譯時可

8、確定。在編譯時可確定。 參數個數參數個數返回地址返回地址形式單元形式單元內情向量內情向量局部變量局部變量老老SP臨時單元臨時單元TOP 調用過程的活動記錄調用過程的活動記錄返回地址返回地址TOPSP3 3、 過程返回時，應執(zhí)行下列指令過程返回時，應執(zhí)行下列指令: :TOP:=SP-1 (TOP:=SP-1 (恢復調用前恢復調用前TOP)TOP)X:=2TOP (X:=2TOP (把返回地址取到把返回地址取到X X中中) ) SP:=0SP (SP:=0SP (恢復調用前恢復調用前SP)SP)UJ X (UJ X (按按X X返回返回) )參數個數參數個數返回地址返回地址形式單元形式單元內情向量

9、內情向量局部變量局部變量老老SP臨時單元臨時單元調用過程的活動記錄調用過程的活動記錄TOPSPSPTOP 例例:Main( ) Main中的數據說明中的數據說明 proc R( ) R中的數據說明中的數據說明 proc Q( ) Q中的數據說明中的數據說明 主程序主程序過程過程Q 過程過程RQ的活動記錄的活動記錄TOPR的活動記錄的活動記錄SP主程序活動記錄主程序活動記錄全局數據區(qū)全局數據區(qū) R R的數組區(qū)的數組區(qū) R R的活動記錄的活動記錄 Q Q的活動記錄的活動記錄 主程序全局主程序全局 數據區(qū)數據區(qū)分配了數組區(qū)之后的運行棧分配了數組區(qū)之后的運行棧TOPSP PASCALPASCALPAS

10、CALPASCAL程序本身可以看成是一個操作程序本身可以看成是一個操作系統(tǒng)所調用的過程，過程可以嵌套和系統(tǒng)所調用的過程，過程可以嵌套和遞歸。遞歸。一個一個PASCALPASCAL過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；beginbegin執(zhí)行體（由一系列的執(zhí)行語句組成）；執(zhí)行體（由一系列的執(zhí)行語句組成）；endend作用域作用域：一個名字能被使用的區(qū)域范圍：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標識符在不同的過程中代表允許同一個標識符在不同的過程中代表不同的名字。不同的名字。名字作用域規(guī)則名字作用

11、域規(guī)則- 最近嵌套原則最近嵌套原則 一個在子程序一個在子程序B1B1中說明的名字中說明的名字X X只在只在B1B1中有效（局部于中有效（局部于B1B1）；）； 如果如果B2B2是是B1B1的一個內層子程序且的一個內層子程序且B2B2中中對標識符對標識符X X沒有新的說明，則原來的沒有新的說明，則原來的名字名字X X在在B2B2中仍然有效。如果中仍然有效。如果B2B2對對X X重重新作了說明，那么，新作了說明，那么，B2B2對對X X的任何引的任何引用都是指重新說明過的這個用都是指重新說明過的這個X X。program main var A, B : real; procedure P1 var

12、 B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integr) 非局部名字的訪問的實現非局部名字的訪問的實現 主程序的層次為主程序的層次為0 0；在；在i i層中定義的過程，層中定義的過程，其層次為其層次為i+1;i+1; 過程運行時，必須知道其所有外層過程的過程運行時，必須知道其所有外層過程的當前活動記錄的起始地址。當前活動記錄的起始地址。main p1 p2 p3 p4 main過過程程定定義義的的嵌嵌套套執(zhí)執(zhí)行行順順序序p2p4p3p3mainmain活動

13、記活動記錄錄P3P3活動記錄活動記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動動態(tài)鏈態(tài)鏈) )P3P3活動記錄活動記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動動態(tài)鏈態(tài)鏈) )P4P4活動記錄活動記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動動態(tài)鏈態(tài)鏈) )P2P2活動記錄活動記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動動態(tài)鏈態(tài)鏈) )program P; var x,y: integer; . procedure P1; var i,j:integer; . procedure P11(a,b:integer); . begin .

14、end; begin . call P11(i,j); . end; procedure P2; var s,t:integer; . procedure P21; begin . end; begin . call P1 . end; begin . call P2; . end.012x3y4RA567s8t9152主程序主程序P過程過程 P2過程過程 P1過程過程 P11DisplayP的的活動活動記錄記錄P2的的活動活動記錄記錄RA101112i13j142P1的的活動活動記錄記錄RA151617a18b19P11的活的活動記動記錄錄3例：例：program main(i,0); 程序

15、結構圖程序結構圖 proc R(c,d); R end /*R*/ proc P (a); 主主 proc Q (b); P Q call R R(x,y); end /*Q*/ call Q Q(z); call P end /*P*/ call R P（W）；）； R（U，V）；）； end /*main*/用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R主程序的主程序的活動記錄活動記錄 d0spdisplaytop（1） P P的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 d1d0displaysptop（2）用用Display表的方案表的方案(

16、1)主程序主程序-(2)P-(3)Q-(4)RQ Q的的活動記錄活動記錄 P P的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 displayd2d1d0sptop（3）R R的的活動記錄活動記錄 Q Q的的活動記錄活動記錄 P P的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 d1d0 displaytopsp（4） d DISPLAY d DISPLAY 4 4 形式單元形式單元 3 3 參數個數參數個數 2 2 全局全局DISPLAYDISPLAY地址地址 1 1 返回地址返回地址 0 0 老老SPSP堆：堆：通常是一片連續(xù)的足夠大的存儲區(qū)，當需要通常是一片連續(xù)的足夠大的存儲

17、區(qū)，當需要時，就從堆中分配一小塊存儲區(qū)；用完就及時退時，就從堆中分配一小塊存儲區(qū)；用完就及時退還給堆。還給堆。注：注：在高級語言中有些數據存儲空間的請求與釋在高級語言中有些數據存儲空間的請求與釋放不再遵循后進先出的原則，而且是全局性的。放不再遵循后進先出的原則，而且是全局性的。為此，需要讓運行程序持有一塊專用的全局存儲為此，需要讓運行程序持有一塊專用的全局存儲空間來滿足這些數據的存儲要求。這種存儲空間空間來滿足這些數據的存儲要求。這種存儲空間就是堆。就是堆。 10.4 10.4 參數傳遞參數傳遞(1)procedure exchangel(i,j:integer);(1)procedure e

18、xchangel(i,j:integer);(2) var x:integer;(2) var x:integer;(3) begin;(3) begin;(4) x:=ai; ai:=aj; aj:=x(4) x:=ai; ai:=aj; aj:=x(5) end;(5) end; 帶有非局部變量和形參的帶有非局部變量和形參的PASCALPASCAL過程過程非局變量非局變量aiai和和ajaj的值進行交換，的值進行交換，i,ji,j為為形參形參傳值的實現傳值的實現 1.1.形式參數當作過程的局部變量處理，形式參數當作過程的局部變量處理，即在被調過程的活動記錄中開辟了形參即在被調過程的活動記錄

19、中開辟了形參的存儲空間，這些存儲位置即是我們所的存儲空間，這些存儲位置即是我們所說的形式單元（用以存放實參）。說的形式單元（用以存放實參）。 2.2.調用過程計算實參的值，并將其放在調用過程計算實參的值，并將其放在對應形式單元開辟的空間中。對應形式單元開辟的空間中。 3.3.被調用過程執(zhí)行時，就像使用局部變被調用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。量一樣使用這些形式單元。 (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y:integer);(4) var temp:int

20、eger;(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=,a);writeln(b=,b)(14)end. 帶有過程帶有過程swap的的PASCAL程序程序傳地址的實現傳地址的實現 把實在參數的地址傳遞給相應的形參，即把實在參數的地址傳遞給相應的形參，即調用過程把一個指向實參的存儲地址的指針調用過程把一個指向實參的存儲地址的指針傳遞給被調用過程相應的形參：傳遞給被調用過程相應的形參：1.1.實在參數是一個名字，或具有左值的表達式實在

21、參數是一個名字，或具有左值的表達式-傳遞左值傳遞左值2.2.實在參數是無左值的表達式實在參數是無左值的表達式-計算值，放計算值，放入一存儲單元，傳此存儲單元地址入一存儲單元，傳此存儲單元地址3.3.目標代碼中，被調用過程對形參的引用變成目標代碼中，被調用過程對形參的引用變成對傳遞給被調用過程的指針的間接引用對傳遞給被調用過程的指針的間接引用 (1)swap(x,y)(1)swap(x,y)(2)int (2)int * *x,x,* *y;y;(3) int temp;(3) int temp;(4)temp=(4)temp=* *x; x; * *x=x=* *y; y; * *y=temp

22、;y=temp;(5) (5) (6)main( )(6)main( )(7) int a=1,b=2;(7) int a=1,b=2;(8) swap(&a,&b);(8) swap(&a,&b);(9) printf(“a is now %d,b is now (9) printf(“a is now %d,b is now %dn”,a,b);%dn”,a,b); 在一個值調用過程中使用指針的在一個值調用過程中使用指針的C C程序程序, ,在在C C程序中無傳地址所以用指針實現。程序中無傳地址所以用指針實現。 (1)program param(input,output); (2)procedure b(function h(n:in