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

1、第10章 目標程序運行時的組織 10.1 概述概述10.2數(shù)據(jù)表示數(shù)據(jù)表示11.10.3目標程序運行時的棧式存儲組織目標程序運行時的棧式存儲組織10.4 參數(shù)傳遞參數(shù)傳遞10.5堆式存儲組織的討論堆式存儲組織的討論概述-代碼生成解決語義gap高級語言支持的概念Type value expressionVariable procedureFunction parameters目標機支持的概念 bits bytes wordsRegistersStack addressRoutine(sub routine)概 述代碼生成前如何安排目標機資源運行時組織的幾個問題運行時組織的幾個問題數(shù)據(jù)表示-如何在

2、目標機中表示每個源語言類型的值表達式求值-如何組織表達式的計算存儲分配-如何組織不同作用域變量的存儲過程實現(xiàn)-如何以例程實現(xiàn)過程，函數(shù)，參數(shù)傳遞概 述任務(wù)：編譯程序?qū)δ繕顺绦蜻\行時的組織（設(shè)任務(wù)：編譯程序?qū)δ繕顺绦蜻\行時的組織（設(shè)計運行環(huán)境和分配存儲）計運行環(huán)境和分配存儲） 如如 通常存儲區(qū)布局通常存儲區(qū)布局可為：可為： 目標代碼區(qū)目標代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū) Stack heap運行環(huán)境和存儲分配設(shè)計分析邏輯階段：在目標代碼生成前，作準備邏輯階段：在目標代碼生成前，作準備實質(zhì)：實質(zhì)： 關(guān)聯(lián)（關(guān)聯(lián)（Binding）將源程序的文本將源程序的文本 程序運行動作的實現(xiàn)程序運行動作的實現(xiàn) 源文件中

3、的名字源文件中的名字N 運行時的存儲運行時的存儲S S在語義學(xué)中，使用術(shù)語在語義學(xué)中，使用術(shù)語environment函數(shù)表示函數(shù)表示env: NS (NS (N到到S S的映射的映射) )靜靜態(tài)態(tài)文文本本中中 運運行行時時動動作作及及為為實實現(xiàn)現(xiàn)其其動動作作的的準準備備 （與與運運行行時時數(shù)數(shù)據(jù)據(jù)對對象象的的表表示示有有關(guān)關(guān)）過過程程定定義義 過過程程名名執(zhí)執(zhí)行行過過程程體體 過過程程體體 控控制制數(shù)數(shù)據(jù)據(jù)對對象象的的分分配配，為為執(zhí)執(zhí)行行過過程程體體使使用用源源文文本本中中同同樣樣的的名名字字 目目標標程程序序中中不不同同的的數(shù)數(shù)據(jù)據(jù)空空間間因因為為一一個個過過程程可可以以是是遞遞歸歸的的，

4、這這時時同同一一個個名名字字在在不不同同的的時時間間可可能能代代表表不不同同的的存存儲儲單單元元決定運行管理復(fù)雜程度的因素決定運行管理復(fù)雜程度的因素源語言本身源語言本身1. 允許的數(shù)據(jù)類型的多少允許的數(shù)據(jù)類型的多少2語言中允許的數(shù)據(jù)項是語言中允許的數(shù)據(jù)項是 靜態(tài)確定靜態(tài)確定 動態(tài)確定動態(tài)確定3程序結(jié)構(gòu)程序結(jié)構(gòu) 決定名字的作用域的規(guī)則和結(jié)構(gòu)決定名字的作用域的規(guī)則和結(jié)構(gòu)A 段結(jié)構(gòu)段結(jié)構(gòu)B 過程定義不嵌套，只允許過程遞歸調(diào)用過程定義不嵌套，只允許過程遞歸調(diào)用C 分程序結(jié)構(gòu)分程序結(jié)構(gòu)分程序嵌套分程序嵌套過程定義嵌套過程定義嵌套 4 4存儲類別的多少存儲類別的多少GlobalStaticLocaldyn

5、amic術(shù) 語u靜態(tài)：如果一個名字的性質(zhì)通過說明語句靜態(tài)：如果一個名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)靜態(tài)”確定的。確定的。u動態(tài)：如果名字的性質(zhì)只有在程序運行時動態(tài)：如果名字的性質(zhì)只有在程序運行時才能知道，則稱這種性質(zhì)為才能知道，則稱這種性質(zhì)為“動態(tài)動態(tài)”確定確定的。的。u例例 procedure A(m,n:integer);u begin real z;u array Bm:n;u beginu u u u end;u end;聲聲明明的的作作用用域域 詞詞法法作作用用域域 動動態(tài)態(tài)作作用用域域例例：（1）program dyn

6、amic(i,0);(2) var r:real(3) procedure show;(4) begin write(r:5:3) end;(5) procedrue small;(6) var r:real;(7) begin r:=0.125; show end;(8) begin(9) r:=0.25;(10) show; small; write/n;(11) show; small; write/n;(12) end.lexical scope0.250 0.2500.250 0.250dynamic scope0.250 0.1250.250 0.125數(shù)據(jù)表示（各種數(shù)據(jù)對象的存儲

7、分配）數(shù)據(jù)對象的屬性 name 名字，名稱 type 類型 location 內(nèi)存地址 value 值 component 成分 數(shù)據(jù)表示（固定長度，直接或間接表示）簡單變量： char: 1 byteintegers: 2 or 4 bytesfloats: 4 to 16 bytesbooleans: 1 bit (but usually 1 byte)指針：unsigned integers一維數(shù)組：一塊連續(xù)的存儲區(qū)多維數(shù)組：一塊連續(xù)的存儲區(qū)，按行存放結(jié)構(gòu)（記錄）：把所有域（field)存放在一塊連續(xù)的存儲區(qū)對象：類的實例變量象結(jié)構(gòu)的域一樣存放在一塊連續(xù)的存儲區(qū)， 但方法（成員函數(shù)）不存

8、在該對象里指令：例例：按按行行 A 是是 10 20 的的二二維維數(shù)數(shù)組組A1, 1A1, 2. . 第第一一行行. .A1, 20A2, 1. . 第第二二行行. . . . .A10, 20 第第十十行行數(shù)組元素的地址計算數(shù)組元素的地址計算設(shè)設(shè) A1，1的地址為的地址為 a，每個元素占一個字，每個元素占一個字Ai，j的地址：的地址： a+（i-1） 20+（j-1）=（a-21）+（20i+j）一般：一般：arrayAl1：u1，l2：u2，ln：un令令 di=ui-li+1元素元素 Ai1，i2，in的地址的地址 D D=a+（i1-l1）d2d3dn+（i2-l2）d3d4dn+（i

9、n-1-l n-1）dn+（in-ln）經(jīng)因子分解后得經(jīng)因子分解后得 D=CONSPART+VARPART其其中中 CONSPART=a-C C=（l1d2+l2）d3+ l3）d4+ l n-1）dn+ ln VARPART=（i1d2+i2）d3+ i3）d4+ i n-1）dn+ in四四元元式式 兩兩組組 VARPART T CONSPARTT1T1 T表表示示數(shù)數(shù)組組元元素素的的地地址址數(shù)數(shù)組組元元素素引引用用： X：=T1 T對對數(shù)數(shù)組組元元素素賦賦值值： T1 T：=Xl 可變可變 (動態(tài)動態(tài))數(shù)組數(shù)組： 若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則稱為

10、可變(動態(tài))數(shù)組。數(shù)組內(nèi)情向量：數(shù)組內(nèi)情向量： 編譯將數(shù)組的有關(guān)信息記錄在一些單元中，稱為數(shù)組的 “內(nèi)內(nèi)情向量情向量”Al 1:u 1,l 2:u 2, ,l ln n : : u un n l1 u1 l2 u2 : : type a（首地址）（首地址） n C目標程序運行時的存儲組織存儲分配策略：存儲分配策略：簡單的棧式分配方案簡單的棧式分配方案 嵌套過程的棧式分配方案嵌套過程的棧式分配方案 分程序結(jié)構(gòu)的存儲分配方案分程序結(jié)構(gòu)的存儲分配方案靜態(tài)存儲分配靜態(tài)存儲分配動態(tài)存儲分配動態(tài)存儲分配棧式棧式堆式堆式l 術(shù)語術(shù)語- -過程活動記錄過程活動記錄AR:為說明方便，假定程序是由過程組成，過程區(qū)

11、分為源文本，為說明方便，假定程序是由過程組成，過程區(qū)分為源文本，運行時稱作過程的激活。運行時稱作過程的激活。一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū)管理，這個區(qū) （塊）叫做一個活動記錄或（塊）叫做一個活動記錄或frame（幀幀）一般這個段要記錄：一般這個段要記錄：l 臨時值，如計算表達式時的中間工作單元。臨時值，如計算表達式時的中間工作單元。l 局部變量局部變量（數(shù)據(jù)）（數(shù)據(jù)）l 保存運行過程前的狀態(tài)保存運行過程前的狀態(tài) （返回地址，寄存器值（返回地址，寄存器值）l 存取鏈存取鏈（可選）（可選） 對于非局部量的引用。對

12、于非局部量的引用。l 控制鏈控制鏈（可選）（可選） 指向調(diào)用者的活動記錄，釋放棧。指向調(diào)用者的活動記錄，釋放棧。l 實參實參（形式單元）（形式單元）l 返回值返回值（對函數(shù)）（對函數(shù)）（有時可使用寄存器存放返回值）（有時可使用寄存器存放返回值） 簡單的棧式分配方案u程序結(jié)構(gòu)特點程序結(jié)構(gòu)特點:過程定義不嵌套，過程可遞歸過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組調(diào)用，含可變數(shù)組; u例例: mainu 全局變量的說明全局變量的說明 proc R end R; proc Q end Q; 主程序執(zhí)行語句主程序執(zhí)行語句 uend mainMain-Q-R Main-Q-Q TOP- R 的活動記錄的活

13、動記錄 Q 的活動記錄的活動記錄 SP- Q 的活動記錄的活動記錄 Q 的活動記錄的活動記錄 主程序全局主程序全局 主程序全局主程序全局 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)TOP- 臨時工作單元臨時工作單元 局部簡單變量局部簡單變量 局部數(shù)組的內(nèi)情向量局部數(shù)組的內(nèi)情向量 保存運保存運 行過程前的狀態(tài)行過程前的狀態(tài)（返回地址，寄存器值）（返回地址，寄存器值） 實參實參（形式單元）和參數(shù)個數(shù)（形式單元）和參數(shù)個數(shù) SP- 控制鏈控制鏈（老（老 SP） TOP R 的數(shù)組區(qū)的數(shù)組區(qū) SP R 的活動記錄的活動記錄 Q 的活動記錄的活動記錄 主程序全局主程序全局 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 嵌套過程語言的棧式分配方案l主要

14、特點主要特點：（語言）一個過程可以引用包圍它的任（語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，一外層過程所定義的標識符（如變量，數(shù)組或過程等）。數(shù)組或過程等）。（實現(xiàn)）一個過程可以引用它的任一外（實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。層過程的最新活動記錄中的某些數(shù)據(jù)。 u關(guān)鍵技術(shù)：解決對非局部量的引用（存關(guān)鍵技術(shù)：解決對非局部量的引用（存?。?。取）。u設(shè)法跟蹤每個外層過程的最新活動記錄設(shè)法跟蹤每個外層過程的最新活動記錄AR的位置。的位置。u跟蹤辦法：跟蹤辦法： 1. 用靜態(tài)鏈（如用靜態(tài)鏈（如PL/0的的SL）。）。 2. 用用DISPLAY表。

15、表。const a=10;const a=10;var var b,c;b,c;procedure p;procedure p; beginbegin c:=b+a; c:=b+a; end; end;beginbegin read(b); read(b); while while b#0b#0 do do begin begin call p; call p; write(2 write(2* *c);c); read(b); read(b); end endend.end.( 0) ( 0) jmpjmp 0 8 0 8 轉(zhuǎn)向轉(zhuǎn)向主程序入口主程序入口( 1) ( 1) jmpjmp 0 2

16、 0 2 轉(zhuǎn)向轉(zhuǎn)向過程過程p p入口入口( 2)( 2) intint 0 3 0 3 過程過程p p入口入口, ,為過程為過程p p開辟空間開辟空間( 3) ( 3) lodlod 1 1 3 3 取變量取變量b b的值到棧頂?shù)闹档綏ｍ? 4) ( 4) lit 0 10 lit 0 10 取常數(shù)取常數(shù)1010到棧頂?shù)綏ｍ? 5) ( 5) opropr 0 2 0 2 次棧頂與棧頂相加次棧頂與棧頂相加( 6) ( 6) stosto 1 1 4 4 棧頂值送變量棧頂值送變量c c中中( 7) ( 7) opropr 0 0 0 0 退棧并返回調(diào)用點退棧并返回調(diào)用點(16)(16)( 8)(

17、 8) intint 0 5 0 5 主程序入口開辟主程序入口開辟5 5個?？臻g個棧空間( 9) ( 9) opropr 0 16 0 16 從命令行讀入值置于棧頂從命令行讀入值置于棧頂(10) (10) stosto 0 3 0 3 將棧頂值存入變量將棧頂值存入變量b b中中(11) (11) lodlod 0 3 0 3 將變量將變量b b的值取至棧頂?shù)闹等≈翖ｍ?12) (12) lit 0 0 lit 0 0 將常數(shù)值將常數(shù)值0 0進棧進棧(13) (13) opropr 0 9 0 9 次棧頂與棧頂是否不等次棧頂與棧頂是否不等(14) (14) jpcjpc 0 24 0 24 等時

18、轉(zhuǎn)等時轉(zhuǎn)(24)(24)（條件不滿足轉(zhuǎn)條件不滿足轉(zhuǎn)）(15) (15) cal 0 2cal 0 2 調(diào)用過程調(diào)用過程p p(16) lit 0 2 (16) lit 0 2 常數(shù)值常數(shù)值2 2進棧進棧(17) (17) lodlod 0 0 4 4 將變量將變量c c的值取至棧頂?shù)闹等≈翖ｍ?18) (18) opropr 0 4 0 4 次棧頂與棧頂相乘次棧頂與棧頂相乘(2(2* *c)c)(19) (19) opropr 0 14 0 14 棧頂值輸出至屏幕棧頂值輸出至屏幕(20) (20) opropr 0 15 0 15 換行換行(21) (21) opropr 0 16 0 16

19、從命令行讀取值到棧頂從命令行讀取值到棧頂(22) (22) stosto 0 0 3 3 棧頂值送變量棧頂值送變量b b中中(23) (23) jmpjmp 0 11 0 11 無條件轉(zhuǎn)到循環(huán)入口無條件轉(zhuǎn)到循環(huán)入口(11)(11)(24) (24) opropr 0 0 0 0 結(jié)束退棧結(jié)束退棧目標代碼解釋執(zhí)行時數(shù)據(jù)棧的布局（運行棧的存儲分配）每個過程的每個過程的ARAR有有3 3個聯(lián)系單元：個聯(lián)系單元：SLSL： 靜態(tài)鏈靜態(tài)鏈，指向，指向定義定義該過程的該過程的直接外過程直接外過程 （或主程序）運行時（或主程序）運行時最新最新數(shù)據(jù)段的基地址數(shù)據(jù)段的基地址。DLDL： 動態(tài)鏈動態(tài)鏈，指向，指向

20、調(diào)用調(diào)用該過程前正在運行過該過程前正在運行過 程的數(shù)據(jù)段基地址。程的數(shù)據(jù)段基地址。RARA： 返回地址返回地址，記錄調(diào)用該過程時，記錄調(diào)用該過程時目標程序目標程序的的斷點斷點，即調(diào)用過程指令的下一條指令的地址，即調(diào)用過程指令的下一條指令的地址。局部變量中間結(jié)果 目標代碼的解釋執(zhí)行 運行棧SuM M調(diào)用過程調(diào)用過程P P RA RA DL DL SL SLb. ttbPM解決對非局部量的引用（存取）用Display表Display表表-嵌套層次顯示表嵌套層次顯示表當前激活過程的層次為當前激活過程的層次為K，它的它的Display表含有表含有K+1個單元，依次存?zhèn)€單元，依次存放著現(xiàn)行層，直接外層放

21、著現(xiàn)行層，直接外層直至最外層的每一過程的最新活動記錄直至最外層的每一過程的最新活動記錄的基地址的基地址例：例：program main(i,0); 程序結(jié)構(gòu)圖程序結(jié)構(gòu)圖 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 P 的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 d

22、1d0displaysptop主程序的主程序的活動記錄活動記錄 d0spdisplaytop（1）（2）用Display表的方案u主程序主程序-P-Q-RR 的的活動記錄活動記錄 Q 的的活動記錄活動記錄 P 的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄Q 的的活動記錄活動記錄 P 的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 displayd2d1d0 d1d0 displaysptoptopsp（3）（4）DISPLAY表的維護和建立 DISPLAY表表d 運行棧運行棧 0 主程活動記錄地址主程活動記錄地址 1 R活動記錄地址活動記錄地址 . 0 老老 SP 1 返回地址返

23、回地址 2 全局全局 DISPLAY地址地址 3 參數(shù)個數(shù)參數(shù)個數(shù) 4形式單元形式單元 . . . d DISPLAY . . . 簡單變量簡單變量 數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量 臨時變量臨時變量 當過程的層次為當過程的層次為n，它的它的 display為為n+1個個值。值。 一個過程被調(diào)用時，一個過程被調(diào)用時，從調(diào)用過程的從調(diào)用過程的DISPLAY表中自下向表中自下向上抄錄上抄錄n個個SP值，再加值，再加上本層的上本層的SP值。值。全局全局DISPLAY地址地址 分分程序結(jié)構(gòu)程序結(jié)構(gòu)Procedure A(m,n); integer m,n; B1:begin real z; array Bm:

24、n; B2:begin real d, e; L3: 2 end; B4:begin array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 分程序結(jié)構(gòu)的存儲分程序結(jié)構(gòu)的存儲分配方案分配方案 處理分程序結(jié)構(gòu)存儲分配方案的一種簡單辦法是，把處理分程序結(jié)構(gòu)存儲分配方案的一種簡單辦法是，把分程序看成分程序看成 “無名無參過無名無參過 程程”，它在哪里定義就在哪里被，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲辦法應(yīng)用到處理分程調(diào)用。因此，可以把處理過程的存儲辦法應(yīng)用到處理分程序中。但這種做法是極為低效的。序中。但這種做法是極為低效的

25、。 一則，每逢進入一則，每逢進入 一個分程序，就照樣建立連接數(shù)據(jù)和一個分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表表,這是不必要的。這是不必要的。 二則二則 ，當從內(nèi)層分程序向外，當從內(nèi)層分程序向外層轉(zhuǎn)移時，可能同時要結(jié)束若干個分程序。層轉(zhuǎn)移時，可能同時要結(jié)束若干個分程序。 按照過程處理辦法，意味著必須一層一層地通過按照過程處理辦法，意味著必須一層一層地通過“返返回回” 來恢復(fù)所要到達的那個分程序的數(shù)據(jù)區(qū)，但不能直接來恢復(fù)所要到達的那個分程序的數(shù)據(jù)區(qū)，但不能直接到達。到達。例如：如果有一個從第例如：如果有一個從第5層分程序轉(zhuǎn)出到達第層分程序轉(zhuǎn)出到達第1層分程序的層分程序的標號標號L，雖然在第雖

26、然在第5層分程序工作時知道層分程序工作時知道L所屬的層數(shù)，我所屬的層數(shù)，我們極易從們極易從DISPLAY中獲得第中獲得第1層分程序的活動記錄基址層分程序的活動記錄基址（SP），），但是怎么知道第但是怎么知道第1層分程序進入時的層分程序進入時的TOP呢？唯一呢？唯一的辦法是從的辦法是從 5,4,3和和2各層順序退出。但這種辦法是很浪費時各層順序退出。但這種辦法是很浪費時間的。間的。 為了解決上述問題，可采取兩種措施。第一為了解決上述問題，可采取兩種措施。第一，對每個過程或分程序都建立有自己的棧，對每個過程或分程序都建立有自己的棧頂指示器頂指示器TOP，代替原來僅有過程的棧頂代替原來僅有過程的棧頂

27、指示器指示器, 每個每個TOP的值保存在各自活動記的值保存在各自活動記錄中。這樣，上述的第二個問題便可解決錄中。這樣，上述的第二個問題便可解決。第二，不把分程序看作。第二，不把分程序看作“無參過程無參過程”，每個分程序享用包圍它的那個最近過程的每個分程序享用包圍它的那個最近過程的DISPLAY。每個分程序都隸屬于某個確定每個分程序都隸屬于某個確定的過程，分程序的層次是相對于它所屬的的過程，分程序的層次是相對于它所屬的那個過程進行編號的。那個過程進行編號的。： 每個過程被當作是每個過程被當作是0層分程序。而過程體分程序（假定層分程序。而過程體分程序（假定是一個分程序）當作是它所管轄的第是一個分程

28、序）當作是它所管轄的第1層分程序。層分程序。這樣，每個過程的活動記錄所含的內(nèi)容有：這樣，每個過程的活動記錄所含的內(nèi)容有：1.過程的過程的TOP值，它指向過程活動記錄的棧頂位置。值，它指向過程活動記錄的棧頂位置。2.連接數(shù)據(jù)，共四項：連接數(shù)據(jù)，共四項： （1)老老SP值；值；（2)返回地址；返回地址； (3)全局全局DISPAY地址；地址；（4)調(diào)用時的棧頂單元地址，老調(diào)用時的棧頂單元地址，老TOP。 3. 參數(shù)個數(shù)和形式單元參數(shù)個數(shù)和形式單元 4. DISPAY表。表。5. 過程所轄的各分程序的局部數(shù)據(jù)單元。過程所轄的各分程序的局部數(shù)據(jù)單元。 對于每個分對于每個分程序來說，它們包括：程序來說，

29、它們包括：（1)分程序的分程序的TOP值。當進入分程序時它含現(xiàn)行棧頂?shù)刂?。當進入分程序時它含現(xiàn)行棧頂?shù)刂罚院?，用來定義棧的新高度（分程序的址，以后，用來定義棧的新高度（分程序的TOP值）；值）；（2)分程序的局部變量，分程序的局部變量， 數(shù)組內(nèi)情向量和臨時工作單元。數(shù)組內(nèi)情向量和臨時工作單元。 變 量 e B5 的 T O P 數(shù) 組 C 的 內(nèi) 情 向 量 變 量 e 和 d B4 的 T O PB2的 TOP 數(shù) 組 B 的 內(nèi) 情 向 量 變 量 zKB1 的 T O PDD I S P L A Y6形 式 單 元 m,n5參 數(shù) 個 數(shù)：24調(diào) 用 時 的 棧 頂 地 址（老 T O

30、 P）3全 局 D I S P L A Y 地 址2返 回 地 址1老 S P0過 程 的 T O P，指 向 活 動 記 錄 之 頂B的 內(nèi) 情 向 量 Z B1的 T O PD I S P L A YD I S P L A Y 形 式 單 元 m , n 2 形 式 單 元 m , n 2連 接 數(shù) 據(jù)連 接 數(shù) 據(jù) A 的 T O PA的 T O P (a) (b)(a) 到 達 標 號 B1處 ; (b)進 入 分 程 序 B1;B Z B1T O 數(shù) 組 B 數(shù) 組 B e dB22的 T O PB 的 內(nèi) 情 向 量B 的 內(nèi) 情 向 量 z zB1 的 T O PB1的 T O

31、PD I S P L A YD I S P L A Y 形式單元 m,n 2 形式單元 m,n 2連 接 數(shù) 據(jù)連接 數(shù) 據(jù)A 的 T O PA 的 T O P (c) (d)(c )數(shù)組 B 分配之后； （d）進入分程序 B22; 數(shù) 組C 數(shù) 組 C 數(shù) 組B 數(shù) 組 B C的 向 量 內(nèi) 情 eB5的T O PC 的 內(nèi) 情 向 量B4的T O PB4的T O PB 的 內(nèi) 情 向 量B的 內(nèi) 情 向 量 z ZB1的T O PB1 的T O PD I S P L A YD I S P L A Y 形式單元 m,n 2 形式單元 m,n 2連接數(shù)據(jù)連 接 數(shù) 據(jù)A的T O PA的T O

32、P (e) (f)(e)進入分程序B4分配數(shù)組C之后； (f)進入分程序B5 。 參數(shù)傳遞參數(shù)傳遞(1)procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5) end; 帶有非局部變量和形參的帶有非局部變量和形參的PASCAL過程過程非局變量非局變量ai和和aj的的值進行交換，值進行交換，i,j為形參（在為形參（在這里是傳值）這里是傳值） (1)program reference(input,output);(2)var a,b:integer;(3)procedure s

33、wap(var x,y:integer);(4) var temp:integer;(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程序程序 u傳地址（變量參數(shù)）傳地址（變量參數(shù)） 例如：過程例如：過程 swap(var x,y:integer); swap(a,b）；（）；（ a,b為為調(diào)用時的調(diào)用時的實參實參 ） 調(diào)用結(jié)果調(diào)用結(jié)果a,b的值

34、被改變。的值被改變。u傳值（值調(diào)用）傳值（值調(diào)用）特點是對形式參數(shù)的任何運算不影響實參的值。特點是對形式參數(shù)的任何運算不影響實參的值。 例如：過程例如：過程 swap(x,y:integer); swap(a,b）；）；其結(jié)果：其結(jié)果： a,b調(diào)用前的值不改變調(diào)用前的值不改變。傳值的實現(xiàn)傳值的實現(xiàn)1.形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程的活形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程的活動記錄中開辟了形參的存儲空間，這些存儲位置即是我動記錄中開辟了形參的存儲空間，這些存儲位置即是我們所說的形式單元（用以存放實參）。們所說的形式單元（用以存放實參）。2.調(diào)用過程計算實參的值，并將其放在對

35、應(yīng)形式單元開辟調(diào)用過程計算實參的值，并將其放在對應(yīng)形式單元開辟的空間中。的空間中。3.被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。式單元。procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 調(diào)用swap(a,b) 過程將不會影響a和b的值。 其結(jié)果等價于執(zhí)行下列運算： x :=a； y :=b； temp :=x； x :=y； y :=temp傳地址的實現(xiàn)傳地址的實現(xiàn)（call- by- reference )(call-

36、by-address)(call-by-location) 把實在參數(shù)的地址傳遞給相應(yīng)的形參，即把實在參數(shù)的地址傳遞給相應(yīng)的形參，即 調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀髡{(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應(yīng)的形參。遞給被調(diào)用過程相應(yīng)的形參。1實在參數(shù)是一個名字，或具有左值的表達式實在參數(shù)是一個名字，或具有左值的表達式-傳遞左值。傳遞左值。2實在參數(shù)是無左值的表達式實在參數(shù)是無左值的表達式-計算值，放入一計算值，放入一存儲單元，傳此存儲單元地址。存儲單元，傳此存儲單元地址。3目標代碼中，被調(diào)用過程對形參的引用變成對目標代碼中，被調(diào)用過程對形參的引用變成對傳遞給被調(diào)用過程

37、的指針的間接引用。傳遞給被調(diào)用過程的指針的間接引用。procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 調(diào)用swap(i,ai) 其結(jié)果等價于執(zhí)行下列運算： 1把 i和ai的地址分別放到x和y相應(yīng)的單元a1,a2 ； 2( temp :=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容； 3 (x :=y;) a1所指單元的內(nèi)容置為a2所指單元值；4( y :=temp) a2所指單元的內(nèi)容置為temp的值。 (1)swap(x,y)(2)int *x,*y;(3) int temp;

38、(4) temp=*x; *x=*y; *y=temp;(5)(6)main( )(7) int a=1,b=2;(8) swap(&a,&b);(9) printf(“a is now %d,b is now %dn”,a,b);(10) 在一個值調(diào)用過程中使用指針的在一個值調(diào)用過程中使用指針的C程序程序在在C程序中無傳地址所以用指針實現(xiàn)。程序中無傳地址所以用指針實現(xiàn)。過程調(diào)用的四元式序列 S call id() ,E Epar T1par T2par Tncall id,n(1)S call id()for 隊列.q的 每一項P do gen(par,-,-,p);n:=n

39、+1; gen(call,-,-,entry(id) (2) 1,E把E.place排在.q 的末端；(3) E 過程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境 傳遞環(huán)境 活動環(huán)境 program param(input,output); procedure b(function h(n:integer):integer);(*) var m:integer; begin m:=3; writeln(h(2) endb; procedure c;(*) var m:integer; function f(n:integer):integr;(&) begin f:=m+n endf; begin

40、m:=0; b(f) end c begin c end. u(1)program param(input,output);u(2)procedure b(function h(n:integer):integer);u(3) begin writeln(h(2) endb;u(4)procedure c;u(5) var m:integer;u(6) function f(n:integer):integr;u(7) begin f:=m+n endf;u(8)begin m := 0; b(f) end c;u(9)beginu(10) cu(11)end 圖10-27 嵌套過程作為參數(shù)傳

41、遞 param c 存取鏈 m b 存取鏈圖 10-28 連同存取鏈一起 傳遞過程實參值結(jié)果傳遞除了未建立真正的別名之外，這個機制得到的結(jié)果與引用傳遞類似：在過程中復(fù)制和使用自變量的值，然后當過程退出時，再將參數(shù)的最終值復(fù)制回自變量的地址。因此，這個方法有時也被稱為復(fù)制進，復(fù)制出，或復(fù)制存儲。值結(jié)果傳遞與引用傳遞的唯一區(qū)別在于別名的表現(xiàn)不同。例如，在以下的代碼中（C語法）：void p (int x, int y)+x;+y;main()int a=1;p(a,a);return 0;在調(diào)用p之后，若使用了引用傳遞，則a的值為3；若使用了值結(jié)果傳遞，則a的值為2。 名字傳遞這是傳遞機制中最復(fù)雜

42、的參數(shù)了。由于名字傳遞的思想是直到在被調(diào)用的程序真正使用了自變量（作為一個參數(shù)）之后才對這個自變量賦值，所以它還稱作延盡賦值（delayed evaluation）。因此，自變量的名稱或是它在調(diào)用點上的結(jié)構(gòu)表示取代了它對應(yīng)的參數(shù)的名字。例如在代碼void p (int x)+x;中，若做了一個如p(ai)的調(diào)用時，其結(jié)果是計算+(ai)。因此，若在p中使用x之前改變i，那么它的結(jié)果就與在引用傳遞或在值結(jié)果傳遞中的不同 int i;int a 10;void p (int x)+i;+x;main ()i=1;a1=1;a2=2;p(ai);return 0;對p的調(diào)用的結(jié)果是將a2設(shè)置為3并保

43、持a1不變。名字傳遞的解釋如下：在調(diào)用點上的自變量的文本被看作是它自己右邊的函數(shù)，生當在被用的過程的代碼中到達相應(yīng)的參數(shù)名時，就要計算它。我們總是在調(diào)用程序的環(huán)境中計算自變，而總是在過程的定義環(huán)境中執(zhí)行過程。建立內(nèi)情向量，分配內(nèi)存的目標代碼（n維可變數(shù)組, type-每個元素占一個字）begin k:=1;n:=1;c:=0; while k=n do begin di:=ui-li+ 1; m:=m*di; c:=c*di+li; 把li,ui和di填進內(nèi)情向量表區(qū)； k:=k+1 end; 申請m個空間, 令首地址為a;把n,c,type ,a填進內(nèi)情 向量表區(qū)end賦值中數(shù)組元素的翻譯A

44、 V:=EV id | id ,E | EV | id , E | id E結(jié)構(gòu)（記錄），抽象數(shù)據(jù)類型對象類實例變量的存儲結(jié)構(gòu)(CIR)class parent | class parent public int a,b,c; | public a,b,c; public void draw() .; | public virtual void draw(); | .class child:public parent | public d,e; | public void sift(); | void draw();堆式動態(tài)存儲分配堆變量堆空間的管理策略減少碎片的技術(shù)空間的釋放C+的堆變量In

45、t *Ptr;Ptr=new int(5)； Int *ptr= new int 10Delete ptrDelete ptr堆變量是可以在程序運行時根據(jù)需要隨時創(chuàng)建或刪除的變量#includeClass MyclassPublic: Myclass(); Myclass(int k,int j); void Set(int,int)m=k;n=j; Myclass();Private: int m,n;Myclass:Myclass() Set(0,0);CoutDefaultendl;Myclass:Myclass(int k,int j) Set(k,j);Cout“m=“mendl;M

46、yclass: Myclass() Cout“Destructor”endl;使用new和delete的示例#includeInt main() Cout“one”endl;Myclass *ptr1=new Myclass;Delete ptr1;Cout“two”endl;Ptr1=new Myclass(5,10);Delete ptr1;Return 0; oneDefaltDestructortwom=5Destructor堆式動態(tài)存儲分配Const int ArraySize=24;/ default sizeClass IntArrayPublic:/operations per

47、formed on arrays IntArray(int sz=ArraySize); IntArray(const IntArray&); IntArray() delete ia; IntArray& operator= (const IntArray&); int& operator (int); int getSize() return size;protected:/internal data representation int size; int * ia; IntArray()函數(shù)的實現(xiàn)，引入新的運算符newIntArray:IntArray

48、（int sz) size= sz;/ allocate an integer array of size/ and set ia to point to itia= new int size;/ initialize arrayfor (int i=0;is. next = memptr = mem;memptr-s. usedsize = 1;memptr-s. freesize = MEMSIZE-1;for (p=memptr;(p-s. next!= memptr) &(p-s. freesize s. next);if (p-s. freesize nunits) return NULL;/* no block big enough */newp = p+p-s. usedsize;newp-s. usedsize= nunits;newp-s. freesize = p-s. freesize-nunits;newp-s.next = p-s. next;p-s. freesize=0;p-s. next= newp;memptr=newp;return (void *)(newp+1);void free (void *ap)Header * bp, *p, *prev;bp= (Header *) ap 1;for (prev= memptr, p=me