1、運行時存儲空間經濟組織概述概述任務：編譯程序對目標程序運行時的數(shù)據(jù)空間的組織任務：編譯程序對目標程序運行時的數(shù)據(jù)空間的組織和管理（設計運行環(huán)境和分配存儲）和管理（設計運行環(huán)境和分配存儲） 如如 通常棧式通常棧式存儲分配布局可為：存儲分配布局可為： 目標代碼區(qū)目標代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū) Stack heap運行環(huán)境和存儲分配運行環(huán)境和存儲分配設計分析設計分析邏輯階段：在目標代碼生成前，作準備邏輯階段：在目標代碼生成前，作準備實質：實質： 關聯(lián)（關聯(lián)（Binding）將源程序的文本將源程序的文本 程序運行動作的實現(xiàn)程序運行動作的實現(xiàn) 源文件中的名字源文件中的名字N 運行時的存儲運行時的存儲S

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

3、間可可能能代代表表不不同同的的存存儲儲單單元元決定存儲管理復雜程度的因素源語言本身決定存儲管理復雜程度的因素源語言本身1. 允許的數(shù)據(jù)類型的多少允許的數(shù)據(jù)類型的多少2語言中允許的數(shù)據(jù)項是語言中允許的數(shù)據(jù)項是 靜態(tài)確定靜態(tài)確定 動態(tài)確定動態(tài)確定3程序結構程序結構 決定名字的作用域的規(guī)則和結構決定名字的作用域的規(guī)則和結構A 段結構段結構B 過程定義不嵌套，只允許過程遞歸調用過程定義不嵌套，只允許過程遞歸調用C 分程序結構分程序結構分程序嵌套分程序嵌套過程定義嵌套過程定義嵌套存儲分配方案策略：存儲分配方案策略： 靜態(tài)存儲分配靜態(tài)存儲分配 動態(tài)存儲分配棧式動態(tài)存儲分配棧式 堆式堆式聲明的作用域聲明的作

4、用域 詞法作用域詞法作用域 動態(tài)作用域動態(tài)作用域例：例：（1）program dynamic(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

5、 scope0.250 0.1250.250 0.125術語術語 靜態(tài)：如果一個名字的性質通過說明語句靜態(tài)：如果一個名字的性質通過說明語句或隱或顯規(guī)則而定義，則稱這種性質是或隱或顯規(guī)則而定義，則稱這種性質是“靜態(tài)靜態(tài)”確定的。確定的。 動態(tài)：如果名字的性質只有在程序運行時動態(tài)：如果名字的性質只有在程序運行時才能知道，則稱這種性質為才能知道，則稱這種性質為“動態(tài)動態(tài)”確定確定的。的。 可變可變 (動態(tài)動態(tài))數(shù)組：數(shù)組： 若一個數(shù)組所需的存儲空間的大小在編若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則譯時就已知道，則稱它為確定數(shù)組，否則稱為可變稱為可變(動態(tài)動態(tài))數(shù)組。數(shù)組

6、。 例例 procedure A(m,n:integer); begin real z; array Bm:n; begin end; end; 數(shù)組內情向量數(shù)組內情向量: 編譯中，將數(shù)組的有關信息記錄在一些單元中，稱為編譯中，將數(shù)組的有關信息記錄在一些單元中，稱為“內“內情向量”，確定數(shù)組，放在符號表中；可變數(shù)組，運行時建立情向量”，確定數(shù)組，放在符號表中；可變數(shù)組，運行時建立相應的內情向量。相應的內情向量。Al 1:u 1,l 2:u 2, ,l ln n : : u un n l1 u1 l2 u2 : : type a（首地址）（首地址） n C 過程活動記錄過程活動記錄 AR:為說明

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

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

9、-Q TOP- R 的活動記錄的活動記錄 Q 的活動記錄的活動記錄 SP- Q 的活動記錄的活動記錄 Q 的活動記錄的活動記錄 主程序全局主程序全局 主程序全局主程序全局 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)TOP- 臨時工作單元臨時工作單元 局部簡單變量局部簡單變量 局部數(shù)組的內情向量局部數(shù)組的內情向量 保存運保存運 行過程前的狀態(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ū)

10、 嵌套過程語言的棧式嵌套過程語言的棧式分配方案分配方案主要特點主要特點： （語言）一個過程可以引用包圍它的任（語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，一外層過程所定義的標識符（如變量，數(shù)組或過程等）。數(shù)組或過程等）。 （實現(xiàn)）一個過程可以引用它的任一外（實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。層過程的最新活動記錄中的某些數(shù)據(jù)。 關鍵技術：解決對非局部量的引用（存關鍵技術：解決對非局部量的引用（存?。Ｈ。?。 設法跟蹤每個外層過程的最新活動記錄設法跟蹤每個外層過程的最新活動記錄AR的位置。的位置。 跟蹤辦法：跟蹤辦法： 1. 用靜態(tài)鏈（如用靜態(tài)

11、鏈（如PL/0的的SL）。）。 2. 用用DISPLAY表。表。例：例：program main(i,0); 程序結構圖程序結構圖 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 的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 d1d0displayspto

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

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

14、 real d, e; L3: 2 end; B4:begin array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 分程序結構的存儲分程序結構的存儲分配方案分配方案 處理分程序結構存儲分配方案的一種簡處理分程序結構存儲分配方案的一種簡單辦法是，把分程序看成單辦法是，把分程序看成 “無參過無參過 程程”，它，它在哪里定義就在哪里被調用。因此，可以把在哪里定義就在哪里被調用。因此，可以把處理過程的存儲辦法應用到處理分程序中。處理過程的存儲辦法應用到處理分程序中。但這種做法是極為低效的。但這種做法是極為低效的。 一則，每逢進入一則，每逢進

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

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

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

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

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

20、I S P L A Y 地 址2返 回 地 址1老 S P0過 程 的 T O P，指 向 活 動 記 錄 之 頂B的 內 情 向 量 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的 內 情 向 量B 的 內 情 向 量 z zB1 的 T O PB1的 T O PD I S P L

21、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的 向 量 內 情 eB5的T O PC 的 內 情 向 量B4的T O PB4的T O PB 的 內 情 向 量B的 內 情 向 量 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 P (e) (f)(e)進入分程序

22、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 swap(var x,y:integ

23、er);(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程序程序 傳地址（變量參數(shù)）傳地址（變量參數(shù)） 例如：過程例如：過程 swap(var x,y:integer); swap(a,b）；（）；（ a,b為調用時的為調用時的實參實參 ） 調用結果調用結果a,b的值被改變。的值被改變。 傳值（值調用）

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

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

26、ll-by-location) 把實在參數(shù)的地址傳遞給相應的形參，即把實在參數(shù)的地址傳遞給相應的形參，即 調用過程把一個指向實參的存儲地址的指針傳遞給調用過程把一個指向實參的存儲地址的指針傳遞給被調用過程相應的形參：被調用過程相應的形參：1實在參數(shù)是一個名字，或具有左值的表達式實在參數(shù)是一個名字，或具有左值的表達式-傳遞傳遞左值左值2實在參數(shù)是無左值的表達式實在參數(shù)是無左值的表達式-計算值，放入一存儲單計算值，放入一存儲單元，傳此存儲單元地址元，傳此存儲單元地址3目標代碼中，被調用過程對形參的引用變成對傳遞給被目標代碼中，被調用過程對形參的引用變成對傳遞給被調用過程的指針的間接引用調用過程的指

27、針的間接引用procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 調用swap(i,ai) 其結果等價于執(zhí)行下列運算： 1把 I和ai的地址分別放到x和y相應的單元a1,a2 2( temp :=x；)temp的內容置為a1所指單元中存的內容 3 (x :=y;) a1所指單元的內容置為a2所指單元值4( y :=temp) a2所指單元的內容置為temp的值 (1)swap(x,y)(2)int *x,*y;(3) int temp;(4) temp=*x; *x=*y; *y=te

28、mp;(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) 在一個值調用過程中使用指針的在一個值調用過程中使用指針的C程序程序在在C程序中無傳地址所以用指針實現(xiàn)。程序中無傳地址所以用指針實現(xiàn)。過程調用的四元式序列過程調用的四元式序列 S call id() ,E Epar T1par T2par Tncall id,n 過程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境 傳遞環(huán)境 活動環(huán)境 program param(input,output); procedur

29、e 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 m:=0; b(f) end c begin c end. (1)program param(input,output); (2)procedure b(function h(n:integer):integer); (3) begin wri

30、teln(h(2) endb; (4)procedure c; (5) var m:integer; (6) function f(n:integer):integr; (7) begin f:=m+n endf; (8)begin m := 0; b(f) end c; (9)begin (10) c (11)end 圖10-27 嵌套過程作為參數(shù)傳遞 param c 存取鏈 m b 存取鏈圖 10-28 連同存取鏈一起 傳遞過程實參各種數(shù)據(jù)對象的存儲分配數(shù)據(jù)對象 name 名字，名稱 type 類型 location 內存地址 value 值 component 成分 例：按行例：按行 A是是 10 20 的二維數(shù)組的二維數(shù)組A1, 1A1, 2. . 第一行第一行. .A1, 20A2, 1. . 第二行第二行. . . . .A10, 20 第十行第十行數(shù)組元素的地址計算數(shù)組元素的地址計算設設 A1，1的地址為的地址為 a