編譯原理7 運(yùn)行環(huán)境

1、1Ch7 運(yùn)行環(huán)境7.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織問題的提出源程序最終需要運(yùn)行。因此必須了解：與源程序等價(jià)的目標(biāo)程序如何在內(nèi)存中運(yùn)行，為了程序的正確運(yùn)行需要什么樣的支持。不同的源語(yǔ)言結(jié)構(gòu)，所需的運(yùn)行環(huán)境和支持不同。本章僅以最簡(jiǎn)單的、基于過程的、順序執(zhí)行的程序?yàn)榍疤嵊懻摚丛闯绦虻幕窘Y(jié)構(gòu)是順序執(zhí)行的過程，過程與過程之間僅通過子程序調(diào)用的方式進(jìn)行控制流的轉(zhuǎn)移。函數(shù)7.1.1 概述2Ch7 運(yùn)行環(huán)境7.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織過程、活動(dòng)、生存期過程的每一次運(yùn)行稱為一次活動(dòng)(activation)。活動(dòng)是一個(gè)動(dòng)態(tài)的概念，它有有限的生存期(life time)?；顒?dòng)的生存期是指從進(jìn)入活動(dòng)的第一

2、條指令執(zhí)行到離開此活動(dòng)前的最后一條指令執(zhí)行的這段時(shí)間，其中包括調(diào)用其它過程時(shí)其它活動(dòng)的生存期。3Ch7 運(yùn)行環(huán)境7.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織運(yùn)行時(shí)為名字X分配存儲(chǔ)空間S，這一過程稱為綁定 (binding)。X是一個(gè)對(duì)象：* 既可以是數(shù)據(jù)對(duì)象，如變量，與之結(jié)合的是一個(gè)存儲(chǔ)單元；* 也可以是操作對(duì)象，如過程，與之結(jié)合的是可執(zhí)行的代碼。討論僅限于X是一個(gè)數(shù)據(jù)對(duì)象。7.1.2 運(yùn)行環(huán)境與名字的綁定46.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織狀態(tài)(賦值)名字（標(biāo)識(shí)符）存儲(chǔ)位置值runningCh6 運(yùn)行環(huán)境變量與值的兩步映射環(huán)境(綁定)常量名字的映射名字右值Compiler/running變量名字的映射

3、環(huán)境(綁定)5目標(biāo)代碼靜態(tài)數(shù)據(jù)棧固定長(zhǎng)度編譯確定Ch7 運(yùn)行環(huán)境7.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織運(yùn)行時(shí),系統(tǒng)為目標(biāo)程序分配的存儲(chǔ)空間按用途可劃分為下面幾個(gè)部分：7.1.3 運(yùn)行環(huán)境與存儲(chǔ)組織動(dòng)態(tài)數(shù)據(jù)區(qū)堆6動(dòng)態(tài)分配策略存儲(chǔ)分配策略棧式方案堆式方案靜態(tài)存儲(chǔ)分配在編譯時(shí)能夠確定目標(biāo)程序運(yùn)行時(shí)所需的全部數(shù)據(jù)空間的大小，即在編譯時(shí)就可以將程序中的名字關(guān)聯(lián)到存儲(chǔ)單元，確定其存儲(chǔ)位置，這種分配策略稱為靜態(tài)存儲(chǔ)分配。Ch7 運(yùn)行環(huán)境7.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織靜態(tài)分配策略7動(dòng)態(tài)存儲(chǔ)分配在編譯時(shí)不能確定目標(biāo)程序運(yùn)行時(shí)所需的全部數(shù)據(jù)空間的大小，而是在目標(biāo)程序運(yùn)行時(shí)動(dòng)態(tài)確定的。棧式動(dòng)態(tài)存儲(chǔ)分配在內(nèi)存中開辟一

4、個(gè)棧區(qū)，按棧的特性進(jìn)行存儲(chǔ)分配。程序運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)函數(shù)或過程，該函數(shù)所需的存儲(chǔ)空間動(dòng)態(tài)地分配于棧頂，函數(shù)返回時(shí)，釋放所占用的空間。Ch6 運(yùn)行環(huán)境6.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織8堆式動(dòng)態(tài)存儲(chǔ)分配在內(nèi)存中開辟一個(gè)稱為堆的存儲(chǔ)區(qū)，程序運(yùn)行每當(dāng)需要（申請(qǐng)）時(shí)就按照某種分配原則在堆的自由區(qū)(可占用區(qū))中，分配能滿足其需要的存儲(chǔ)空間給它，使用后需要釋放操作，再將不再占用的存儲(chǔ)空間歸還給堆的自由區(qū)。運(yùn)行時(shí)存儲(chǔ)分配的一個(gè)原則是，盡可能對(duì)數(shù)據(jù)對(duì)象進(jìn)行靜態(tài)分配 。Ch6 運(yùn)行環(huán)境6.1 關(guān)于程序運(yùn)行環(huán)境與存儲(chǔ)組織9Ch7 運(yùn)行環(huán)境7.2 靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配在編譯時(shí)能夠確定目標(biāo)程序運(yùn)行時(shí)所需的全部

5、數(shù)據(jù)空間的大小，即在編譯時(shí)就可以將程序中的名字關(guān)聯(lián)到存儲(chǔ)單元，確定其存儲(chǔ)位置，這種分配策略稱為靜態(tài)存儲(chǔ)分配。特點(diǎn)：綁定是1對(duì)1的映射。名字在程序編譯時(shí)與存儲(chǔ)空間結(jié)合，每次過程活動(dòng)時(shí)，它的名字映射到同一存儲(chǔ)單元。程序運(yùn)行時(shí)不再有對(duì)存儲(chǔ)空間的分配。10靜態(tài)分配對(duì)語(yǔ)言的限制(1) 數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置的限制必須在編譯時(shí)知道。(2) 不允許遞歸過程，因?yàn)橐粋€(gè)過程的所有活動(dòng)使用同樣的局部名字結(jié)合。(3) 數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立，因?yàn)闆]有運(yùn)行時(shí)的存儲(chǔ)分配機(jī)制。Ch6 運(yùn)行環(huán)境6.2 靜態(tài)存儲(chǔ)分配調(diào)調(diào)用用方方向向14C 的過程調(diào)用，過程進(jìn)入，數(shù)組空間分配和過程返回的過程調(diào)用，過程進(jìn)入，數(shù)組空間分配

6、和過程返回par Tpar T1 1par Tpar T2 2. . . .par Tpar Tn ncall P, ncall P, n或者或者(i + 3)TOP := addr(T(i + 3)TOP := addr(Ti i) )其中其中:x SP :x SP 表示變址訪問表示變址訪問地址地址 x + SPx + SP15 16177.4 嵌套過程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過程語(yǔ)言的棧式實(shí)現(xiàn)重點(diǎn)重點(diǎn)：嵌套層次的概念和處理方法：嵌套層次的概念和處理方法7.4.1 嵌套層次顯示表嵌套層次顯示表 DISPLAY 和活動(dòng)紀(jì)錄和活動(dòng)紀(jì)錄要求：要求：過程過程 Q 運(yùn)行時(shí)必須知道它的運(yùn)行時(shí)必須知道它的所有所

7、有外層過程的最新活動(dòng)紀(jì)錄的地址外層過程的最新活動(dòng)紀(jì)錄的地址做法：做法：設(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)紀(jì)錄的位置設(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)紀(jì)錄的位置例子：過程例子：過程 R 的外層為的外層為 Q, Q 的外層為主程序的外層為主程序 P, 則則 R 運(yùn)行時(shí)的運(yùn)行時(shí)的DISPLAY 表為：表為： R R 的現(xiàn)行活動(dòng)紀(jì)錄的地址（的現(xiàn)行活動(dòng)紀(jì)錄的地址（SP SP 現(xiàn)行值）現(xiàn)行值） Q Q 的的最新最新活動(dòng)紀(jì)錄的地址活動(dòng)紀(jì)錄的地址 P P 的活動(dòng)紀(jì)錄的地址的活動(dòng)紀(jì)錄的地址18 引入引入 DISPLAY 表以后的活動(dòng)紀(jì)錄表以后的活動(dòng)紀(jì)錄TOPSP19 活動(dòng)紀(jì)錄表：活動(dòng)紀(jì)錄表： ARd + SP2SP1.

8、220建立建立 DISPLAY 的方法的方法DISPLAY 的結(jié)構(gòu)的結(jié)構(gòu)21DISPLAY 的建立方法（從的建立方法（從Q2 調(diào)用調(diào)用 R）進(jìn)入新過程時(shí)進(jìn)入新過程時(shí)1，應(yīng)把它的外層的，應(yīng)把它的外層的 D 表地址作為連接數(shù)據(jù)傳過來(lái)，若進(jìn)表地址作為連接數(shù)據(jù)傳過來(lái)，若進(jìn)R, 應(yīng)把應(yīng)把d SP1.2 傳到傳到 ARR 的全局的全局 D 表表;2,進(jìn)入進(jìn)入 R 時(shí)，根據(jù)時(shí)，根據(jù) SP1.2 從從 Q 的活動(dòng)紀(jì)錄中截取的活動(dòng)紀(jì)錄中截取 d SP1.2 (d + lR) SP1.2 (l 為層數(shù)為層數(shù))， 再添加進(jìn)入再添加進(jìn)入 R 時(shí)新建立的時(shí)新建立的 SP222現(xiàn)行過程中引用了某一外層過程（層數(shù)為現(xiàn)行過程

9、中引用了某一外層過程（層數(shù)為k）獲得）獲得 X 值的方法值的方法當(dāng)過程當(dāng)過程 P1 調(diào)用過程調(diào)用過程 P2 而進(jìn)入了而進(jìn)入了 P2 后，后，P2 建立建立自己的自己的DISPLAY 的方法的方法1，若，若 P2 是一個(gè)是一個(gè)真實(shí)過程，真實(shí)過程，2 種情形種情形P1P2CALL P2P0P2P1CALL P2做法：做法：只需要把只需要把 P1 的的 DISPLAY 地址作為地址作為連接數(shù)據(jù)之一傳給連接數(shù)據(jù)之一傳給 P2, WHY?232, 若若 P2 是形式參數(shù)，連接數(shù)據(jù)包含是形式參數(shù)，連接數(shù)據(jù)包含 3 項(xiàng)項(xiàng)247.4.2 過程調(diào)用，過程進(jìn)入過程調(diào)用，過程進(jìn)入接下來(lái)接下來(lái)25接下來(lái)接下來(lái)P P

10、返回返回267.4.3、靜態(tài)鏈和活動(dòng)記錄、靜態(tài)鏈和活動(dòng)記錄 v靜態(tài)鏈靜態(tài)鏈：指向本過程：指向本過程的直接外層過程的活的直接外層過程的活動(dòng)記錄的起始地址，動(dòng)記錄的起始地址，也稱存取鏈。也稱存取鏈。v動(dòng)態(tài)鏈動(dòng)態(tài)鏈：指向本過程：指向本過程的調(diào)用過程的活動(dòng)記的調(diào)用過程的活動(dòng)記錄的起始地址，也稱錄的起始地址，也稱控制鏈?？刂奇湣?shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元臨時(shí)單元臨時(shí)單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量SP012動(dòng)態(tài)鏈動(dòng)態(tài)鏈(老老SP)TOP 靜態(tài)鏈靜態(tài)鏈27program P;var a, x : integer;procedure Q(b: integer);var i: int

11、eger;procedure R(u: integer; var v: integer);var c, d: integer;begin if u=1 then R(u+1, v).v:=(a+c)*(b-d);.end Rbegin.R(1,x);.end Qprocedure S;var c, i:integer;begina:=1;Q(c);.end Sbegina:=0;S;.end. P主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 R2800返回地址返回地址102a3x4SP TOPq主程序主程序P2900返回地址返回地址102a3x405返回地址返回地址607

12、0(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10SP TOP動(dòng)態(tài)鏈動(dòng)態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P過程過程 S？第第N層過程調(diào)用層過程調(diào)用第第 N+1層過程，如何層過程，如何確定被調(diào)用過程確定被調(diào)用過程(第第 N+1層層)過程的靜態(tài)鏈？過程的靜態(tài)鏈？A:調(diào)用過程調(diào)用過程(第第N層層過程過程)的最新活動(dòng)記錄的最新活動(dòng)記錄的起始地址的起始地址.3000返回地址返回地址102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10SP TOP動(dòng)態(tài)鏈動(dòng)態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q511返回地址返回地址120131(形參個(gè)數(shù)形參個(gè)數(shù))14b(形參形參)15i16？第第N層

13、過程調(diào)用層過程調(diào)用第第 N層過程，如何確層過程，如何確定被調(diào)用過程定被調(diào)用過程(第第 N層層)過程的靜態(tài)鏈？過程的靜態(tài)鏈？A:調(diào)用過程調(diào)用過程(第第N層層過程過程)的靜態(tài)鏈的值。的靜態(tài)鏈的值。3100返回地址返回地址102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈動(dòng)態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R511返回地址返回地址120131(形參個(gè)數(shù)形參個(gè)數(shù))14b(形參形參)15i161117返回地址返回地址1811192(形參個(gè)數(shù)形參個(gè)數(shù))20u(形參形參)21v(形參形參)22c23d24SP TOP3200返回地址返回地址

14、102a3x405返回地址返回地址6070(形參個(gè)數(shù)形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈動(dòng)態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R 過程過程 R511返回地址返回地址120131(形參個(gè)數(shù)形參個(gè)數(shù))14b(形參形參)15i161117返回地址返回地址1811192(形參個(gè)數(shù)形參個(gè)數(shù))20u(形參形參)21v(形參形參)22c23d241725返回地址返回地址2611272(形參個(gè)數(shù)形參個(gè)數(shù))28u(形參形參)29v(形參形參)30c31d32TOPSP 337.5 堆式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序語(yǔ)言提供用戶自由地申請(qǐng)數(shù)據(jù)空如果一個(gè)程序語(yǔ)言提供用戶自由地申

15、請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間的機(jī)制，或者不僅有過程而且有間和退還數(shù)據(jù)空間的機(jī)制，或者不僅有過程而且有進(jìn)程的程序結(jié)構(gòu)，一般用堆式的動(dòng)態(tài)存儲(chǔ)分配方案。進(jìn)程的程序結(jié)構(gòu)，一般用堆式的動(dòng)態(tài)存儲(chǔ)分配方案。如如+中的中的new，delete，PASCAL的的new，等機(jī)，等機(jī)制制 。此時(shí)此時(shí),空間的使用未必服從空間的使用未必服從“先申請(qǐng)后釋放，后先申請(qǐng)后釋放，后申請(qǐng)先釋放申請(qǐng)先釋放”的原則，那么棧式的動(dòng)態(tài)分配方案就的原則，那么棧式的動(dòng)態(tài)分配方案就不適用了。通常使用一種稱為堆式的動(dòng)態(tài)存儲(chǔ)分配不適用了。通常使用一種稱為堆式的動(dòng)態(tài)存儲(chǔ)分配方案。方案。 這種分配方式的存儲(chǔ)管理技術(shù)甚為復(fù)雜，我們這種分配方式的存儲(chǔ)管理技術(shù)

16、甚為復(fù)雜，我們這里舉出這種分配方法必須考慮的幾個(gè)問題。這里舉出這種分配方法必須考慮的幾個(gè)問題。 34堆式的動(dòng)態(tài)存儲(chǔ)分配策略堆式的動(dòng)態(tài)存儲(chǔ)分配策略:當(dāng)運(yùn)行程序要求一塊體積為當(dāng)運(yùn)行程序要求一塊體積為N的空同時(shí)，我們應(yīng)該分配的空同時(shí)，我們應(yīng)該分配哪一塊給它呢？哪一塊給它呢？理論上說(shuō)，應(yīng)從比理論上說(shuō)，應(yīng)從比N稍大一點(diǎn)的一個(gè)空閑塊中取出稍大一點(diǎn)的一個(gè)空閑塊中取出N個(gè)個(gè)單元，以便使大的空閑塊派更大的用場(chǎng)。但這種做法較麻煩。單元，以便使大的空閑塊派更大的用場(chǎng)。但這種做法較麻煩。因此，常常仍采用因此，常常仍采用“先碰上哪塊比先碰上哪塊比N大就從其中分出大就從其中分出N個(gè)單元個(gè)單元”的原則。但不論采用什么原則，

17、整個(gè)大存區(qū)在一定的原則。但不論采用什么原則，整個(gè)大存區(qū)在一定時(shí)間之后必然會(huì)變成零碎不堪。時(shí)間之后必然會(huì)變成零碎不堪?？傆幸粋€(gè)時(shí)候會(huì)出現(xiàn)異樣的情形：運(yùn)行程序要求一塊體總有一個(gè)時(shí)候會(huì)出現(xiàn)異樣的情形：運(yùn)行程序要求一塊體積為積為N的空間，但發(fā)現(xiàn)沒有比的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑大的空閑塊了，然而所有空閑塊的總和卻要比塊的總和卻要比N大得多！出現(xiàn)這種情形時(shí)怎么辦呢？這是大得多！出現(xiàn)這種情形時(shí)怎么辦呢？這是一個(gè)比前面的問題難得多的問題。一個(gè)比前面的問題難得多的問題。解決辦法似乎很簡(jiǎn)單，這就是，把所有空閑塊連接在一解決辦法似乎很簡(jiǎn)單，這就是，把所有空閑塊連接在一起，形成一片可分配的連續(xù)空

18、間。起，形成一片可分配的連續(xù)空間。這里主要問題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的這里主要問題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的全部引用點(diǎn)。全部引用點(diǎn)。 35堆式的動(dòng)態(tài)存儲(chǔ)分配策略堆式的動(dòng)態(tài)存儲(chǔ)分配策略:另外，如果運(yùn)行程序要求一塊體積為另外，如果運(yùn)行程序要求一塊體積為N的空間，但的空間，但所有空閑塊的總和也不夠所有空閑塊的總和也不夠N，那又應(yīng)怎么辦呢？，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做垃圾回收的辦法來(lái)對(duì)付有的管理系統(tǒng)采用一種叫做垃圾回收的辦法來(lái)對(duì)付這種局面。即尋找那些運(yùn)行程序業(yè)己無(wú)用但尚未釋放在這種局面。即尋找那些運(yùn)行程序業(yè)己無(wú)用但尚未釋放在占用塊，或者那些行程序目前很少使用的占用塊

19、，把這占用塊，或者那些行程序目前很少使用的占用塊，把這此占用塊收回來(lái)，重新分配。此占用塊收回來(lái)，重新分配。但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？要使用垃圾回收技術(shù)，除了在語(yǔ)言上要有明確的具要使用垃圾回收技術(shù)，除了在語(yǔ)言上要有明確的具體限制外，還需要有特別的硬件措施，否則回收幾乎不體限制外，還需要有特別的硬件措施，否則回收幾乎不能實(shí)現(xiàn)。能實(shí)現(xiàn)。36堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑：堆式動(dòng)

20、態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑：1）定長(zhǎng)塊管理）定長(zhǎng)塊管理 堆式動(dòng)態(tài)儲(chǔ)分配最簡(jiǎn)單的實(shí)現(xiàn)是按定長(zhǎng)塊進(jìn)行。堆式動(dòng)態(tài)儲(chǔ)分配最簡(jiǎn)單的實(shí)現(xiàn)是按定長(zhǎng)塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長(zhǎng)度相等的若干塊，初始化時(shí)，將堆存儲(chǔ)空間分成長(zhǎng)度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針成一個(gè)鏈表，用指針available指向鏈表中的第一塊。指向鏈表中的第一塊。 分配時(shí)每次都分配指針分配時(shí)每次都分配指針available所指的塊，所指的塊，然后然后available指向相鄰的下一塊。歸還時(shí)，把所歸指向相鄰的下一塊。歸還時(shí)，把所歸還的塊插入鏈表?？紤]插入方便，可以把所歸還的還的塊插入鏈表?？紤]插入方便，可以把所歸還的塊插在塊插在available所指的塊之前，然后所指的塊之前，然后available指指向新歸還的塊。向新歸還的塊。37占用占用占用占用占用占用空閑空閑空閑空閑空閑空閑available(a)占用占用占用占用