8-第八章_存儲空間組織-1-2節(jié)

1、CH8 運行時存儲空間組織運行時存儲空間組織編譯程序總框編譯程序總框 符符 號號 表表詞法分析器詞法分析器語法分析器語法分析器語義分析器語義分析器代碼優(yōu)化代碼優(yōu)化出出 錯錯 處處 理理源程序源程序目標程序目標程序單詞符號集單詞符號集語法單位集語法單位集中間代碼程序中間代碼程序中間代碼程序中間代碼程序 目標代碼生成目標代碼生成 存儲空間組織存儲空間組織存儲空間分配策略存儲空間分配策略 1).1).靜態(tài)分配靜態(tài)分配 存儲分配由編譯程序在編譯時進行；存儲分配由編譯程序在編譯時進行； 2).2).動態(tài)分配動態(tài)分配 在編譯時生成相應在編譯時生成相應( (申請空間申請空間) )的目標的目標 程序，在目標程

2、序運行時，執(zhí)行該代碼，程序，在目標程序運行時，執(zhí)行該代碼， 進行存儲分配。進行存儲分配。 （有：棧式存儲分配，堆式存儲分配）（有：棧式存儲分配，堆式存儲分配）影響存儲分配策略的源語言主要特征影響存儲分配策略的源語言主要特征 1). 過程能否遞歸調用；過程能否遞歸調用；Program PP(input,output); var k: integer; Function F(n:integer):integer; begin if n=0 then F:=1 else F:=n*F(n-1); end; begin K:=F(10); end.執(zhí)行順序：執(zhí)行順序： P PPFPF1 1FF2 2

3、每一次調用每一次調用F F，需要一套數(shù)據(jù)區(qū)需要一套數(shù)據(jù)區(qū)影響存儲分配策略的源語言主要特征影響存儲分配策略的源語言主要特征 2).是否有可變數(shù)組（可變數(shù)組的大小創(chuàng)建時決定）；是否有可變數(shù)組（可變數(shù)組的大小創(chuàng)建時決定）；Pascal: Pascal: thepointthepoint : array of integer; : array of integer; setlength(thepoint,5); setlength(thepoint,5); 在在C99C99，實現(xiàn)了，實現(xiàn)了變長數(shù)組：變長數(shù)組：用用( (整型整型) )變量或表達式聲明變量或表達式聲明的數(shù)組。（在的數(shù)組。（在C90C90和

4、和C+C+，方括號內必須是常數(shù)值）。，方括號內必須是常數(shù)值）。例：例：intint f (void) ; f (void) ; intint main(voidmain(void) ) intint size = 4; size = 4; intint asizeasize; / ok in only C99; / ok in only C99 intint bsizebsize* *size; / ok in only C99size; / ok in only C99 intint c f() ; / ok in only C99 c f() ; / ok in only C99影響存儲分

5、配策略的源語言主要特征影響存儲分配策略的源語言主要特征 3). 過程能否訪問非局部且非全局的變量過程能否訪問非局部且非全局的變量 如：如：Pascal語言的過程嵌套聲明語言的過程嵌套聲明, ,內層可以訪問內層可以訪問 外層定義的名字外層定義的名字Program B1(input,output); const a=10; var b,c: integer; procedure B2(x:real); var f,g:real; procedure B3(y:real); const b=5; var j:real; begin j:=f * B3(a)+b; end; B3 begin ; be

6、gin ; end; B2 begin ; end; B1,主程序主程序其中其中： j,bj,b B3 B3 f B2f B2 a B1 a B1影響存儲分配策略的源語言主要特征影響存儲分配策略的源語言主要特征4). 是否有分程序結構（分程序中可以有是否有分程序結構（分程序中可以有變量聲明變量聲明）#include int test=5; void fun1( );void main( ) int test=10; fun1( ); printf(“2-%dn”,test); int test=15; printf(“3-%dn”,test); void fun1( ) printf(“1-%

7、dn”,test); 全局名：全局名：5main定義的定義的局部名：局部名：10分程序分程序定義的定義的局部名：局部名：15影響存儲分配策略的源語言主要特征影響存儲分配策略的源語言主要特征5). 名字的作用域名字的作用域 如，如， C語言的語言的staticstatic，externextern。動態(tài)局部變量（離開函數(shù)，值就消失）動態(tài)局部變量（離開函數(shù)，值就消失）靜態(tài)局部變量（離開函數(shù)，值仍保留）靜態(tài)局部變量（離開函數(shù)，值仍保留） 靜態(tài)全局變量（只限本文件引用）靜態(tài)全局變量（只限本文件引用）全局變量全局變量 （允許其它文件引用）（允許其它文件引用） 影響存儲分配策略的源語言主要特征影響存儲分配

8、策略的源語言主要特征6). 過程調用時如何傳遞參數(shù)；過程調用時如何傳遞參數(shù)； 如：傳值，傳地址，得結果，傳名等。如：傳值，傳地址，得結果，傳名等。7). 哪些實體可以作為參數(shù)和返回值；哪些實體可以作為參數(shù)和返回值； 如：簡單變量，結構變量，標號，過程等，如：簡單變量，結構變量，標號，過程等， 是否可以做為參數(shù)被傳遞和做為結果被返回？是否可以做為參數(shù)被傳遞和做為結果被返回？7). 是否允許動態(tài)的為對象分配存儲空間；是否允許動態(tài)的為對象分配存儲空間； 如：如：C C：mallocmalloc、calloccalloc； pascalpascal：NewNew、GetMemGetMem 8).8).

9、存儲空間是否必須顯式地釋放存儲空間是否必須顯式地釋放 如：如：C C：free free pascalpascal： DisposeDispose、FreeMemFreeMem8.1 目標程序運行時的活動目標程序運行時的活動8.1.1 過程的活動過程的活動1). 1). 過程的活動過程的活動: : 該過程的一次執(zhí)行該過程的一次執(zhí)行( (調用調用) )。2). 2). 過程活動的生存期過程活動的生存期: : 從執(zhí)行過程從執(zhí)行過程 P P 的過程體的第一步操作到最后的過程體的第一步操作到最后 一步操作之間的操作序列；包括執(zhí)行一步操作之間的操作序列；包括執(zhí)行P P時調用時調用 其他過程其他過程 (

10、(如如Q) Q) 花費的時間?；ㄙM的時間。3). 3). 過程遞歸：過程遞歸： 若過程尚未退出當前活動，又開始其新的活動。若過程尚未退出當前活動，又開始其新的活動。 過程遞歸可以是間接達到的。如：過程遞歸可以是間接達到的。如：PQRPPQRPprogram main (input，output)； var A，B ： integer； procedure Q(X: X: integer); begin end; procedureP(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； if Z0 then Q(Z)if Z0 then

11、 Q(Z) else P(X,Y,Z); else P(X,Y,Z); end; begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，A） end. 過過程程定定義義過程調用過程調用1).1).過程的活動過程的活動2).2).過程活動過程活動 的生存期的生存期3).3).過程遞歸過程遞歸8.1.2 參數(shù)傳遞參數(shù)傳遞 過程過程( (函數(shù)函數(shù)) )： 結構化程序設計的主要手段；結構化程序設計的主要手段； 節(jié)省程序代碼和擴充語言能力的主要途徑；節(jié)省程序代碼和擴充語言能力的主要途徑；只要有過程定義，就可以在別的程序單位調用它

12、。只要有過程定義，就可以在別的程序單位調用它。調用者調用者( (程序單位程序單位) )與被調用者與被調用者( (過程過程) ) 之間的信息之間的信息傳遞主要通過傳遞主要通過“全局量全局量”和和“參數(shù)參數(shù)”來完成。來完成。如果把數(shù)據(jù)看成內容物的話，那么裝載數(shù)據(jù)的容器如果把數(shù)據(jù)看成內容物的話，那么裝載數(shù)據(jù)的容器就是變元。就是變元。主程序主程序/ /過程過程調用者調用者被調用者被調用者變元變元過程過程變元變元控制控制數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流: : . .從從調用者調用者的變元的變元 = = 被調用過程被調用過程的變元；的變元； . .被調用過程被調用過程對數(shù)據(jù)進行計算處理；對數(shù)據(jù)進行計算處理； .

13、.過程結束返回時，把數(shù)據(jù)結果過程結束返回時，把數(shù)據(jù)結果 = 調用者調用者的變元；的變元；在完成對過程中代碼段的調用執(zhí)行的同時，在完成對過程中代碼段的調用執(zhí)行的同時，也完成了與過程的數(shù)據(jù)交換也完成了與過程的數(shù)據(jù)交換信息傳遞中，涉及到兩類參數(shù)信息傳遞中，涉及到兩類參數(shù): : 屬于屬于被調用過程被調用過程： 用于表示相應數(shù)據(jù)在過程執(zhí)行當中的含義用于表示相應數(shù)據(jù)在過程執(zhí)行當中的含義 形式參數(shù)（形參，或啞元）形式參數(shù)（形參，或啞元）program main（input,output）；）； var A，B ： integer； procedure P(X X, ,Y Y, ,Z Z: : integer

14、); begin Y:=Y+1 Y:=Y+1； Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P( P(A+BA+B, ,A A, ,A A); ); writeln(A=，A） end. 形式參數(shù)形式參數(shù)信息傳遞中，涉及到兩類參數(shù)信息傳遞中，涉及到兩類參數(shù): : 屬于屬于調用者調用者： 用于裝載調用者對被調過程的輸入用于裝載調用者對被調過程的輸入/ /輸出數(shù)據(jù)；輸出數(shù)據(jù)； 實在參數(shù)實在參數(shù) （實參（實參 ）program main（input,output）；）； var A，B ： integer； procedure P(X X, ,Y

15、 Y, ,Z Z: : integer); begin Y:=Y+1 Y:=Y+1； Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P( P(A+BA+B, ,A A, ,A A); ); writeln(A=，A） end. 實在參數(shù)實在參數(shù)形參與實參之間按照從左到右的順序一一對應。形參與實參之間按照從左到右的順序一一對應。即：處于兩個列表的相同位置的變元，意味著它們即：處于兩個列表的相同位置的變元，意味著它們 是相互關聯(lián)的。是相互關聯(lián)的。 形形- -實對應的主要方式：傳值，傳地址，得結果，傳名實對應的主要方式：傳值，傳地址，得結果，傳名p

16、rogram main（input,output）；）； var A，B ： integer； procedure P(X X, ,Y Y, ,Z Z: : integer); begin Y:=Y+1 Y:=Y+1； Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P( P(A+BA+B, ,A A, ,A A); ); writeln(A=，A） end. 實在參數(shù)實在參數(shù)形式參數(shù)形式參數(shù)傳值調用（傳值調用（Call by value）調用者計算出實在參數(shù)的值，并將其傳送給過程的調用者計算出實在參數(shù)的值，并將其傳送給過程的形式參數(shù)。形式參數(shù)

17、。 調用者計算實參的值，放在過程可以取到的地方；調用者計算實參的值，放在過程可以取到的地方； 過程取出實參的值，放在過程內對應的形式單元中過程取出實參的值，放在過程內對應的形式單元中 ( (過程的活動記錄中開辟的存儲空間過程的活動記錄中開辟的存儲空間) )； 過程執(zhí)行時，像局部名一樣使用這些形式單元。過程執(zhí)行時，像局部名一樣使用這些形式單元。C參數(shù)為普通變量參數(shù)為普通變量void sub (void sub (intint x,intx,int y) y)pascal值參值參procedure procedure P(x,y:integerP(x,y:integer) )program mai

18、n(input，output); var A，B ： integer； procedure P(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，A） end. 主程序主程序子程序子程序T5X 5 A2Y2 3B3Z2 7此種參數(shù)傳遞方法，此種參數(shù)傳遞方法，過程內對參數(shù)的變動過程內對參數(shù)的變動不會影響到不會影響到“調用者調用者”輸出結果：輸出結果：A=2傳地址傳地址 (引用調用引用調用) ( C

19、all-by-address ) 調用者把一個指向實參的存儲地址的指針，傳遞給調用者把一個指向實參的存儲地址的指針，傳遞給過程的形參。過程的形參。 實參是名字：傳遞其地址；實參是名字：傳遞其地址； 實參是表達式：計算表達式值且存放在某一實參是表達式：計算表達式值且存放在某一 存儲單元，將該存儲單元地址傳遞過去。存儲單元，將該存儲單元地址傳遞過去。 過程中對形參的引用和賦值，都變成對傳遞過程中對形參的引用和賦值，都變成對傳遞 來的指針的間接引用訪問。來的指針的間接引用訪問。C C參數(shù)為指針變量參數(shù)為指針變量 void void sub(intsub(int * *sum)sum)數(shù)組作為參數(shù)數(shù)組

20、作為參數(shù)void void Func(intFunc(int arr5) arr5)pascalpascal變參變參procedure procedure P(VarP(Var x,y:integerx,y:integer) ) program main(input，output); var A，B ： integer； procedure P(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，

21、A） end. 主程序主程序T 5A 2 3 8B 3子程序子程序XTTYAAZAA輸出結果：輸出結果：A=8C C語言參數(shù)例語言參數(shù)例# include # include void sub (void sub (intint x,intx,int y,inty,int * *sum)sum) * *sum=sum=x+yx+y;main ( )main ( ) intint x=9,y=10,s=1; x=9,y=10,s=1; sub(x,y,&ssub(x,y,&s);); printf(%dprintf(%d n,sn,s);); 答案答案: 19: 19其中：其中：

22、x,yx,y 傳值傳值 sum sum 傳地址傳地址其中：其中：x x 傳值傳值 y y 傳地址傳地址#include #include intint x,y,zx,y,z; ; void void p(intp(int * *x,intx,int y) y) + +* *x; y- -; z=x; y- -; z=* *x+yx+y; ; printf(%d,%d,%dnprintf(%d,%d,%dn,* *x,y,zx,y,z); ); void main() void main() x=2; y=3; z=4; x=2; y=3; z=4; p(&x,yp(&x,y);

23、); printf(%d,%d,%dn,x,y,zprintf(%d,%d,%dn,x,y,z);); p(&y,xp(&y,x);); printf(%d,%d,%dn,x,y,zprintf(%d,%d,%dn,x,y,z);); 3, 2, 53, 2, 53, 3, 53, 3, 54, 2, 64, 2, 63, 4, 63, 4, 6得結果得結果 ( Call by result ) 或或 復制恢復復制恢復 ( Copy-Restore ) 被調用過程為每個形參設置兩個形式單元；被調用過程為每個形參設置兩個形式單元； 分別存地址、值。分別存地址、值。 調用者把實在參

24、數(shù)的調用者把實在參數(shù)的地址和值地址和值同時傳遞到被調用同時傳遞到被調用 過程中；過程中； 被調用過程直接使用被調用過程直接使用實參的值實參的值； 過程過程返回時，把形參的現(xiàn)行值復制到相應的實在返回時，把形參的現(xiàn)行值復制到相應的實在 參數(shù)的地址中參數(shù)的地址中, ,將計算結果返回給調用者。將計算結果返回給調用者。（ AdaAda，pascalpascal ) )program main(input，output); var A，B ： integer； procedure P(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； end;

25、begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，A） end. 主程序主程序T 5A 2 3 7B 3子程序子程序XTT5 5YAA2 2 3 3ZAA2 2 7 7或或: 主程序主程序T 5A 2 7 3B 3結果：結果：A=7 (左左右右) 或：或：A=3 (右右左左)傳名調用傳名調用 或：換名調用或：換名調用 ( Call-by-Name ) 調用者調用者將實在參數(shù)的名字傳給將實在參數(shù)的名字傳給被調用被調用過程中過程中 相應的形式參數(shù)；相應的形式參數(shù)； 被調用被調用過程的過程體中，所有的形式參數(shù)都過程的過程

26、體中，所有的形式參數(shù)都 用相應實在參數(shù)的名字進行替換；用相應實在參數(shù)的名字進行替換；ALGOL ALGOL 使用的一種參數(shù)傳遞方式使用的一種參數(shù)傳遞方式program main(input,output); var A，B ： integer； procedure P(X,Y,Z:integer); begin Y:=Y+1；Z:=Z+X； end; begin A:=2; B:=3; P(A+B,A,A); writeln(A=，A） end. program main(input,output); var A，B ： integer； procedure P(X,Y,Z:integer);

27、 begin A:=A+1；A:=A+(A+B)； end; begin A:=2; B:=3; P(A+B,A,A); writeln(A=，A） end. 主程序主程序TAB52 3 93輸出結果：輸出結果：A=98.2 8.2 運行時存儲器的劃分運行時存儲器的劃分8.2.1 8.2.1 運行時存儲器的劃分運行時存儲器的劃分一個目標程序運行所需的存儲空間包括一個目標程序運行所需的存儲空間包括: : 存放目標代碼的空間存放目標代碼的空間 存放數(shù)據(jù)項目的空間存放數(shù)據(jù)項目的空間 存放程序運行的控制或連接數(shù)據(jù)所需單元存放程序運行的控制或連接數(shù)據(jù)所需單元 ( (控制?？刂茥? )一個程序在運行時刻的

28、內存劃分一個程序在運行時刻的內存劃分:代碼代碼(Code)靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)(Static Data)棧棧(Stack) 堆堆(Heap) 絕大多數(shù)高級語言，執(zhí)行時不絕大多數(shù)高級語言，執(zhí)行時不能改變代碼，所以在編譯時，能改變代碼，所以在編譯時，所有代碼所有代碼( (包括每個過程的入包括每個過程的入口點口點) )地址都是可計算的。地址都是可計算的。過程過程1 1的代碼的代碼過程過程2 2的代碼的代碼. . . .過程過程n n的代碼的代碼過程過程1 1入口入口過程過程2 2入口入口過程過程n n入口入口代代碼碼區(qū)區(qū)內容內容代碼區(qū)代碼區(qū)大小大小靜態(tài)確定靜態(tài)確定位置位置靜態(tài)確定靜態(tài)確定靜態(tài)數(shù)據(jù)：靜態(tài)數(shù)

29、據(jù)：編譯時就可以確定存儲位置的數(shù)據(jù)。編譯時就可以確定存儲位置的數(shù)據(jù)。如：如：* *) FORTRAN77 ) FORTRAN77 ：所有的數(shù)據(jù)；：所有的數(shù)據(jù)； * *) Pascal ) Pascal ： 全局變量；全局變量； * *) C ) C ： 外部變量，靜態(tài)變量外部變量，靜態(tài)變量；對常量，常數(shù)：對常量，常數(shù)： 編譯時已知其內容，且編譯時已知其內容，且值不變。通常由編譯程值不變。通常由編譯程序直接插入到代碼中，序直接插入到代碼中，不分配數(shù)據(jù)空間。不分配數(shù)據(jù)空間。內容內容 數(shù)據(jù)段數(shù)據(jù)段 靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū)大小大小靜態(tài)確定靜態(tài)確定位置位置靜態(tài)確定靜態(tài)確定目標代碼目標代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)棧

30、棧堆堆棧區(qū)：棧區(qū)：用于用于符合符合后進先出使用風格的數(shù)據(jù)；后進先出使用風格的數(shù)據(jù)； * *) ) 過程運行的控制及連接數(shù)據(jù)；過程運行的控制及連接數(shù)據(jù)； * *) ) 過程的局部變量、形式參數(shù)等；過程的局部變量、形式參數(shù)等；目標代碼目標代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)棧棧堆堆堆區(qū)：堆區(qū)：用于用于不符合不符合后進先出使用風格的數(shù)據(jù)；后進先出使用風格的數(shù)據(jù)； * *) ) 動態(tài)申請地址空間的變量。動態(tài)申請地址空間的變量。 其中：其中：“棧區(qū)棧區(qū)”和和“堆區(qū)堆區(qū)”的大小是隨著程序的運的大小是隨著程序的運行而行而 改變的，因此兩者采用對開式使用。改變的，因此兩者采用對開式使用。8.2.2 8.2.2 活動記錄活動記錄過程在一次活動過程在一次活動( (執(zhí)行執(zhí)行) )中所需要的信息，存放在一片中所需要的信息，存放在一片連續(xù)的存儲區(qū)中，稱為一個活動記錄。過程調用產生連續(xù)的存儲區(qū)中，稱為一個活動記錄。過程調用產生新的活動記錄。新的活動記錄?；顒佑涗浿兄辽賾摯娣艃深愋畔ⅲ夯顒佑涗浿兄辽賾摯娣艃深愋畔ⅲ?1. 1. 控制信息：控制信息： * *）控制活動的正確調用與返回；）控制活動的正確調用與返回；( (如：返回地址如：返回地址) ) * *）控制活動記錄的正確切換；）控制活動記錄的正確切換；( (如：動態(tài)鏈如：動態(tài)鏈) ) 2. 2