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

1、1Ch7 運行環(huán)境7.1 關(guān)于程序運行環(huán)境與存儲組織問題的提出源程序最終需要運行。因此必須了解：與源程序等價的目標(biāo)程序如何在內(nèi)存中運行，為了程序的正確運行需要什么樣的支持。不同的源語言結(jié)構(gòu)，所需的運行環(huán)境和支持不同。本章僅以最簡單的、基于過程的、順序執(zhí)行的程序為前提討論，即源程序的基本結(jié)構(gòu)是順序執(zhí)行的過程，過程與過程之間僅通過子程序調(diào)用的方式進(jìn)行控制流的轉(zhuǎn)移。函數(shù)7.1.1 概述2Ch7 運行環(huán)境7.1 關(guān)于程序運行環(huán)境與存儲組織過程、活動、生存期過程的每一次運行稱為一次活動(activation)?；顒邮且粋€動態(tài)的概念，它有有限的生存期(life time)?；顒拥纳嫫谑侵笍倪M(jìn)入活動的第一

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

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

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

5、數(shù)據(jù)空間的大小，即在編譯時就可以將程序中的名字關(guān)聯(lián)到存儲單元，確定其存儲位置，這種分配策略稱為靜態(tài)存儲分配。特點：綁定是1對1的映射。名字在程序編譯時與存儲空間結(jié)合，每次過程活動時，它的名字映射到同一存儲單元。程序運行時不再有對存儲空間的分配。10靜態(tài)分配對語言的限制(1) 數(shù)據(jù)對象的長度和它在內(nèi)存中的位置的限制必須在編譯時知道。(2) 不允許遞歸過程，因為一個過程的所有活動使用同樣的局部名字結(jié)合。(3) 數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立，因為沒有運行時的存儲分配機(jī)制。Ch6 運行環(huán)境6.2 靜態(tài)存儲分配調(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 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)重點重點：嵌套層次的概念和處理方法：嵌套層次的概念和處理方法7.4.1 嵌套層次顯示表嵌套層次顯示表 DISPLAY 和活動紀(jì)錄和活動紀(jì)錄要求：要求：過程過程 Q 運行時必須知道它的運行時必須知道它的所有所

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

8、220建立建立 DISPLAY 的方法的方法DISPLAY 的結(jié)構(gòu)的結(jié)構(gòu)21DISPLAY 的建立方法（從的建立方法（從Q2 調(diào)用調(diào)用 R）進(jìn)入新過程時進(jìn)入新過程時1，應(yīng)把它的外層的，應(yīng)把它的外層的 D 表地址作為連接數(shù)據(jù)傳過來，若進(jìn)表地址作為連接數(shù)據(jù)傳過來，若進(jìn)R, 應(yīng)把應(yīng)把d SP1.2 傳到傳到 ARR 的全局的全局 D 表表;2,進(jìn)入進(jìn)入 R 時，根據(jù)時，根據(jù) SP1.2 從從 Q 的活動紀(jì)錄中截取的活動紀(jì)錄中截取 d SP1.2 (d + lR) SP1.2 (l 為層數(shù)為層數(shù))， 再添加進(jìn)入再添加進(jìn)入 R 時新建立的時新建立的 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 是一個是一個真實過程，真實過程，2 種情形種情形P1P2CALL P2P0P2P1CALL P2做法：做法：只需要把只需要把 P1 的的 DISPLAY 地址作為地址作為連接數(shù)據(jù)之一傳給連接數(shù)據(jù)之一傳給 P2, WHY?232, 若若 P2 是形式參數(shù)，連接數(shù)據(jù)包含是形式參數(shù)，連接數(shù)據(jù)包含 3 項項247.4.2 過程調(diào)用，過程進(jìn)入過程調(diào)用，過程進(jìn)入接下來接下來25接下來接下來P P

10、返回返回267.4.3、靜態(tài)鏈和活動記錄、靜態(tài)鏈和活動記錄 v靜態(tài)鏈靜態(tài)鏈：指向本過程：指向本過程的直接外層過程的活的直接外層過程的活動記錄的起始地址，動記錄的起始地址，也稱存取鏈。也稱存取鏈。v動態(tài)鏈動態(tài)鏈：指向本過程：指向本過程的調(diào)用過程的活動記的調(diào)用過程的活動記錄的起始地址，也稱錄的起始地址，也稱控制鏈?？刂奇?。參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP012動態(tài)鏈動態(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(形參個數(shù)形參個數(shù))8c9i10SP TOP動態(tài)鏈動態(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層層過程過程)的最新活動記錄的最新活動記錄的起始地址的起始地址.3000返回地址返回地址102a3x405返回地址返回地址6070(形參個數(shù)形參個數(shù))8c9i10SP TOP動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q511返回地址返回地址120131(形參個數(shù)形參個數(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(形參個數(shù)形參個數(shù))8c9i10動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈q主程序主程序P 過程過程 S 過程過程 Q 過程過程 R511返回地址返回地址120131(形參個數(shù)形參個數(shù))14b(形參形參)15i161117返回地址返回地址1811192(形參個數(shù)形參個數(shù))20u(形參形參)21v(形參形參)22c23d24SP TOP3200返回地址返回地址

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

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

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

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

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

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

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