【正文】 heap 運行環(huán)境和存儲分配 設(shè)計分析 邏輯階段：在目標(biāo)代碼生成前，作準(zhǔn)備 實質(zhì)： 關(guān)聯(lián)（ Binding） 將源程序的文本 ? 程序運行動作的實現(xiàn) 源文件中的名字 N ? 運行時的存儲 S 在語義學(xué)中，使用術(shù)語 environment函數(shù)表示 env: N→S (N 到 S的映射 ) 靜態(tài)文本中 運行時動作及為實現(xiàn)其動作的準(zhǔn)備 （與運行時數(shù)據(jù)對象的表示有關(guān)）過程定義 過程名 執(zhí)行過程體 過程體 控制數(shù)據(jù)對象的分配，為執(zhí)行過程體使用源文本中同樣的名字 目標(biāo)程序中不同的數(shù)據(jù)空間因為一個過程可以是遞歸的，這時同一個名字在不同的時間可能代表不同的存儲單元決定運行管理復(fù)雜程度的因素 —— 源語言本身 1. 允許的數(shù)據(jù)類型的多少 2 ．語言中允許的數(shù)據(jù)項是 靜態(tài)確定 動態(tài)確定 3 ．程序結(jié)構(gòu) 決定名字的作用域的規(guī)則和結(jié)構(gòu) A ． 段結(jié)構(gòu) B ． 過程定義不嵌套，只允許過程遞歸調(diào)用 C ． 分程序結(jié)構(gòu) 分程序嵌套 過程定義嵌套 4存儲類別的多少 Global Static Local dynamic 術(shù) 語 ?靜態(tài)：如果一個名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。 ?動態(tài)：如果名字的性質(zhì)只有在程序運行時才能知道，則稱這種性質(zhì)為“動態(tài)”確定的。 ? begin real z。 ? begin ? ? ? end。(2) v a r r :r eal(3) procedur e show。(5) procedru e sma ll。(7) be g in r := 5 。(8) begin(9) r := 。 sma ll 。(11 ) show。 wri te /n 。 數(shù)組內(nèi)情向量： 編譯將數(shù)組的有關(guān)信息記錄在一些單元中，稱為數(shù)組的 “內(nèi) 情向量” A[l 1 :u 1 ,l 2 :u 2 , , l n : u n ] l 1 u 1 l 2 u 2 : : type a （首地址） n C 目標(biāo)程序運行時的存儲組織 存儲分配策略： 簡單的棧式分配方案 嵌套過程的棧式分配方案 分程序結(jié)構(gòu)的存儲分配方案 靜態(tài)存儲分配 動態(tài)存儲分配 —— 棧式 堆式 l 術(shù)語 過程活動記錄 AR : 為說明方便，假定程序是由過程組成，過程區(qū)分為源文本， 運行時稱作過程的激活。 l 局部變量 （數(shù)據(jù)） l 保存運行過程前的狀態(tài) （返回地址，寄存器值 ?? ） l 存取鏈 （可選） 對于非局部量的引用。 l 實參 （形式單元） l 返回值 （對函數(shù)） （有時可使用寄存器存放返回值） 簡單的棧式分配方案 ?程序結(jié)構(gòu)特點 :過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組 。 ? proc Q ? …… ? end Q。 ?（實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。 ?設(shè)法跟蹤每個外層過程的最新活動記錄AR的位置。 2. 用 DISPLAY表。 var b,c。 begin c:=b+a。 begin read(b)。 write(2*c)。 end end. ( 0) jmp 0 8 轉(zhuǎn)向 主程序入口 ( 1) jmp 0 2 轉(zhuǎn)向 過程 p入口 ( 2) int 0 3 過程 p入口 ,為過程 p開辟空間 ( 3) lod 1 3 取變量 b的值到棧頂 ( 4) lit 0 10 取常數(shù) 10到棧頂 ( 5) opr 0 2 次棧頂與棧頂相加 ( 6) sto 1 4 棧頂值送變量 c中 ( 7) opr 0 0 退棧并返回調(diào)用點 (16) ( 8) int 0 5 主程序入口開辟 5個?？臻g ( 9) opr 0 16 從命令行讀入值置于棧頂 (10) sto 0 3 將棧頂值存入變量 b中 (11) lod 0 3 將變量 b的值取至棧頂 (12) lit 0 0 將常數(shù)值 0進(jìn)棧 (13) opr 0 9 次棧頂與棧頂是否不等 (14) jpc 0 24 等時轉(zhuǎn) (24)（ 條件不滿足轉(zhuǎn) ） (15) cal 0 2 調(diào)用過程 p (16) lit 0 2 常數(shù)值 2進(jìn)棧 (17) lod 0 4 將變量 c的值取至棧頂 (18) opr 0 4 次棧頂與棧頂相乘 (2*c) (19) opr 0 14 棧頂值輸出至屏幕 (20) opr 0 15 換行 (21) opr 0 16 從命令行讀取值到棧頂 (22) sto 0 3 棧頂值送變量 b中 (23) jmp 0 11 無條件轉(zhuǎn)到循環(huán)入口 (11) (24) opr 0 0 結(jié)束退棧 目標(biāo)代碼解釋執(zhí)行時數(shù)據(jù)棧的布局（運行棧的存儲分配） 每個過程的 AR有 3個聯(lián)系單元： – SL： 靜態(tài)鏈 ，指向 定義 該過程的 直接外過程 （或主程序）運行時 最新 數(shù)據(jù)段的基地址 。 – RA： 返回地址 ，記錄調(diào)用該過程時 目標(biāo)程序的 斷點 ，即調(diào)用過程指令的下一條指令的地址。 程序結(jié)構(gòu)圖 ?? proc R( c , d)。 主 ?? p roc Q (b)。 end /* Q*/ call Q ?? Q(z)。 ? 一個過程被調(diào)用時，從調(diào)用過程的DISPLAY表中自下向上抄錄 n個 SP值，再加上本層的 SP值。 integer m,n。 array B[m:n]。 L3: 2 end。 1 B5:begin real e。 end。 分程序結(jié)構(gòu)的存儲 分配方案 處理分程序結(jié)構(gòu)存儲分配方案的一種簡單辦法是，把分程序看成 “無名無參過 程”，它在哪里定義就在哪里被調(diào)用。但這種做法是極為低效的。 二則 ，當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時，可能同時要結(jié)束若干個分程序。 例如：如果有一個從第 5層分程序轉(zhuǎn)出到達(dá)第 1層分程序的標(biāo)號 L，雖然在第 5層分程序工作時知道 L所屬的層數(shù)，我們極易從 DISPLAY中獲得第 1層分程序的活動記錄基址（ SP），但是怎么知道第 1層分程序進(jìn)入時的 TOP呢？唯一的辦法是從 5,4,3和 2各層順序退出。 為了解決上述問題，可采取兩種措施。這樣，上述的第二個問題便可解決。每個分程序都隸屬于某個確定的過程，分程序的層次是相對于它所屬的那個過程進(jìn)行編號的。而過程體分程序（假定是一個分程序）當(dāng)作是它所管轄的第 1層分程序。 ，共四項： （ 1)老 SP值； （ 2)返回地址； (3)全局 DISPAY地址； （ 4)調(diào)用時的棧頂單元地址，老 TOP。 5. 過程所轄的各分程序的局部數(shù)據(jù)單元。當(dāng)進(jìn)入分程序時它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程序的 TOP值）； （ 2)分程序的局部變量， 數(shù)組內(nèi)情向量和臨時工作單元。 ( b) 進(jìn) 入 分 程 序 B1。 數(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 Z B1的 T O PB1 的 T O P D 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 ) 進(jìn)入分程序 B4分配數(shù)組 C 之后； ( f ) 進(jìn)入分程序 B5 。 (2) var x:integer。 (4) x:=a[i]。 a[j]:=x (5) end。 (2)var a,b:integer。 (4) var temp:integer。 (7) x:=y。 (10)begin (11) a:=1。 (12) swap(a,b)。writeln(‘ b=‘ ,b) (14)end. 帶有過程 swap的 PASCAL程序 ?傳地址（變量參數(shù)） 例如：過程 swap(var x,y:integer)。 ?傳值（值調(diào)用） 特點是對形式參數(shù)的任何運算不影響實參的值。 swap(a,b）； 其結(jié)果： a,b調(diào)用前的值不改變。 ，并將其放在對應(yīng)形式單元開辟的空間中。 procedure swap( x,y:integer)。 begin temp:=x。 其結(jié)果等價于執(zhí)行下列運算： x :=a； y :=b； temp :=x； x :=y； y :=temp 傳地址的實現(xiàn) （ call by reference )(callbyaddress)(callbylocation) 把實在參數(shù)的地址傳遞給相應(yīng)的形參，即 調(diào)用過程把一