編譯原理：第9章 運行時的存儲組織

1、第9章 運行時的存儲組織School of Computer Science & Technology Harbin Institute of Technology重點：符號表的內(nèi)容、組織，過程調(diào)用實現(xiàn)， 靜態(tài)存儲分配、動態(tài)存儲分配的基本方法。 難點：參數(shù)傳遞，過程說明語句代碼結(jié)構(gòu)， 過程調(diào)用語句的代碼結(jié)構(gòu)， 過程調(diào)用語句的語法制導(dǎo)定義， 棧式存儲分配。 2022/7/172第9章運行時的存儲組織 9.1 與存儲組織有關(guān)的源語言概念與特征9.2 存儲組織9.3 靜態(tài)存儲分配9.4 棧式存儲分配9.5 棧中非局部數(shù)據(jù)的訪問9.6 堆管理9.7 本章小結(jié)2022/7/1739.1 與存儲組織有關(guān)的

2、源語言概念與特征編譯程序必須準確地實現(xiàn)包含在源程序中的各種抽象概念，如名字、作用域、數(shù)據(jù)類型、操作符、過程、參數(shù)和控制流結(jié)構(gòu)等，這些概念反映了源語言所具有的一些特征，對它們的支持往往會影響運行時的存儲組織和分配策略 給定一個源程序，編譯程序必須根據(jù)源語言的特征(規(guī)定)為源程序中的許多問題做出決策，包括何時、怎樣為名字分配內(nèi)存地址。靜態(tài)策略：在編譯時即可做出決定的策略動態(tài)策略：直到程序執(zhí)行時才能做出決定的策略2022/7/1749.1.1 名字及其綁定 “名字”、“變量”和“標識符” 的區(qū)別與聯(lián)系名字和變量分別表示編譯時的名字和運行時該名字所代表的內(nèi)存位置。 標識符則是一個字符串，用于指示數(shù)據(jù)對

3、象、過程、類或?qū)ο蟮娜肟凇?所有標識符都是名字，但并不是所有的名字都是標識符，名字還可以是表達式。例如，名字x.y可能表示x所代表結(jié)構(gòu)的域y。 同一標識符可以被聲明多次，但每個聲明都引入一個新的變量。即使每個標識符只被聲明一次，局部于某個遞歸過程的標識符在不同的運行時刻也將指向不同的內(nèi)存位置。 2022/7/175名字的綁定從名字到值的兩步映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值賦值改變狀態(tài)，但不改變環(huán)境。 如果環(huán)境將名字x映射到存儲單元s，我們就說x被綁定到s名字內(nèi)存位置(變量)狀態(tài)值環(huán)境2022/7/1769.1.2 聲明的作用域x的聲明的作用域是程序中的這樣一段區(qū)域，在該區(qū)域中，

4、x的引用均指向x的這一聲明。對于某種程序設(shè)計語言，如果只通過考察其程序就可以確定某個聲明的作用域，則稱該語言使用靜態(tài)作用域；否則稱該語言使用動態(tài)作用域。C+、Java和C#等還提供了對作用域的顯式控制，其方法是使用public、private和protected這樣的關(guān)鍵字。聲明的作用域是通過符號表進行管理的，詳見8.4節(jié)的討論。2022/7/1771. 靜態(tài)作用域在具有程序塊結(jié)構(gòu)的語言中，變量聲明的靜態(tài)作用域規(guī)則如下 ：如果名字x的聲明D屬于程序塊B，則D的作用域是B的所有語句，只有滿足如下條件的程序塊B除外：B嵌套在B中(可以是任意的嵌套深度)，且B中具有同一名字x的一個新的聲明。令B1,

5、 B2, , Bk是包圍x的本次引用的所有程序塊，Bk-1是Bk的直接外層程序塊，Bk-2是Bk-1的直接外層程序塊，如此類推。找到使x的某個聲明屬于Bi的最大i，則x的本次引用指向Bi中的這個聲明。換句話說，x的本次引用處在Bi中的這個聲明的作用域中。 2022/7/1781. 靜態(tài)作用域表9.1 圖8.10所示程序中聲明的作用域2022/7/1792. 顯式訪問控制 類和結(jié)構(gòu)為其成員引入了一種新的作用域如果p是某個帶有域(成員)x的類的對象，則p.x中x的引用將指向該類定義中的域x。與程序塊結(jié)構(gòu)類似的是，類D中成員x的聲明的作用域?qū)U展到D的任何子類D，除非D中具有同一名字x的一個局部聲

6、明。2022/7/17102. 顯式訪問控制 通過使用像public、private和protected這樣的關(guān)鍵字，C+或Java類的面向?qū)ο笳Z言提供了一種對超類中成員名字的顯式訪問控制。這些關(guān)鍵字通過限制訪問來支持封裝。因此，私有名的作用域只包含與該類及其友類相關(guān)聯(lián)的方法聲明和定義，保護名只對其子類是可訪問的，而公用名從類的外部也是可以訪問的。 2022/7/17113. 動態(tài)作用域 動態(tài)作用域規(guī)則相對于時間而靜態(tài)作用域規(guī)則相對于空間靜態(tài)作用域規(guī)則要求我們找出某個引用所指向的聲明，條件是該聲明處在包圍該引用的“空間上最近的”單元(程序塊)中。動態(tài)作用域也是要求我們找出某個引用所指向的聲明，

7、但條件是該聲明處在包圍該引用的“時間上最近的”單元(過程活動)中。2022/7/17123. 動態(tài)作用域 “動態(tài)作用域”通常是指下面的策略名字x的引用指向帶有x聲明的最近被調(diào)用的過程中x的這個聲明。例如，過程被當(dāng)做參數(shù)進行傳遞時 2022/7/17139.1.3 過程及其活動 將“過程、函數(shù)和方法”統(tǒng)稱為“過程” 過程定義是一個聲明，它的最簡單形式是把一個標識符和一個語句聯(lián)系起來。該標識符是過程名，而這個語句是過程體。 當(dāng)過程名出現(xiàn)在可執(zhí)行語句中時，稱相應(yīng)的過程在該點被調(diào)用。過程調(diào)用就是執(zhí)行被調(diào)用過程的過程體。注意，過程調(diào)用也可以出現(xiàn)在表達式中。2022/7/17149.1.3 過程及其活動

8、出現(xiàn)在過程定義中的某些標識符具有特殊的意義，稱為該過程的形式參數(shù)，簡稱為形參。調(diào)用過程時，表達式作為實在參數(shù)(或?qū)崊?傳遞給被調(diào)用的過程，以替換出現(xiàn)在過程體中的對應(yīng)形式參數(shù)。9.1.4節(jié)將討論實參和形參的結(jié)合方法。過程體的每次執(zhí)行叫做該過程的一個活動。過程p的一個活動的生存期是從過程體執(zhí)行的第一步到最后一步，包括執(zhí)行被p調(diào)用的過程的時間，以及再由這樣的過程調(diào)用其它過程所花的時間，等等。 2022/7/17159.1.3 過程及其活動 如果a和b是過程的活動，那么它們的生存期或者不交迭，或者嵌套。也就是說，如果在a結(jié)束之前b就開始了，那么b必須在a結(jié)束之前結(jié)束。如果同一個過程的一次新的活動可以在

9、前一次活動結(jié)束前開始，則稱這樣的過程是遞歸的。遞歸過程p也可以間接地調(diào)用自己。如果某個過程是遞歸的，則在某一時刻可能有它的幾個活動同時活躍，這時必須合理組織這些同時活躍著的活動的內(nèi)存空間。 2022/7/17169.1.4 參數(shù)傳遞方式 當(dāng)一個過程調(diào)用另一個過程時，它們之間交換信息的方法通常是通過非局部名字和被調(diào)用過程的參數(shù)來實現(xiàn)的。 傳值傳地址傳值結(jié)果傳名其主要區(qū)別在于實參所代表的究竟是左值、右值還是實參的正文本身 2022/7/17171. 傳值計算實參并將其右值傳遞給被調(diào)用過程 傳值方式可以如下實現(xiàn)：被調(diào)用過程為每個形參開辟一個稱為形式單元的存儲單元，用于存放相應(yīng)實參的值。 調(diào)用過程計算

10、實參，并把右值放入相應(yīng)的形式單元中。 調(diào)用者被調(diào)用者直接使用A實際參數(shù)A形式參數(shù)XA的值單向傳值2022/7/17182. 傳地址調(diào)用過程將實參的地址傳遞給被調(diào)用過程 傳地址方式可以如下實現(xiàn)：如果實參是一個具有左值的名字或表達式，則傳遞該左值本身 如果實參是a+b或2這樣的沒有左值的表達式，則調(diào)用過程首先計算實參的值并將其存入一個新的存儲單元，然后將這個新單元的地址傳遞給被調(diào)用過程 調(diào)用者被調(diào)用者間址訪問A實際參數(shù)A形式參數(shù)XA的地址傳地址2022/7/17193. 傳值結(jié)果傳值結(jié)果就是將傳值和傳地址這兩種方式結(jié)合起來傳值結(jié)果方式可以如下實現(xiàn)：實參的右值和左值同時傳給被調(diào)用過程。在被調(diào)用過程中

11、，像傳值方式那樣使用實參的右值。當(dāng)控制返回調(diào)用過程時，根據(jù)傳遞來的實參的左值，將形參當(dāng)前的值復(fù)制到實參存儲單元。 調(diào)用者被調(diào)用者A實際參數(shù)A形式參數(shù)XA的值傳值/傳地址A的地址2022/7/17204. 傳名用實參表達式對形參進行文字替換。傳名方式可以如下實現(xiàn)：在調(diào)用過程中設(shè)置計算實參左值或右值的形實轉(zhuǎn)換子程序。被調(diào)用過程為每個形參開辟一個存儲單元，用于存放該實參的形實轉(zhuǎn)換子程序的入口地址。被調(diào)過程執(zhí)行時，每當(dāng)要向形參賦值或取該形參的值時，就調(diào)用相應(yīng)于該形參的形實轉(zhuǎn)換子程序，以獲得相應(yīng)的實參地址或值。注意，形實轉(zhuǎn)換子程序的運行環(huán)境是調(diào)用程序。形實轉(zhuǎn)換子程序又稱為換名子程序thunk。2022/

12、7/1721例procedure swap(var x, y: integer);var temp: integer; begin 調(diào)用swap(i, ai) temp := x;temp := i; x := y; i := ai; y := tempai := temp end2022/7/1722子程序P(X,Y,Z);Y:=Y+1; Z:=Z+X傳值：2傳地址：X=T=5,Y=Z=A=2A:=A+1=2+1A:=A+T=3+58傳值結(jié)果：X=T=5,Y=Z=A=2Y:=Y+1=3Z:=Z+X=5+2=7Y A=3Z A=77傳名A:=A+1=3A:=A+A+B=3+3+39主程序A:=

13、2; B:=3;P(A+B, A, A);print A臨時單元: T:A+B=52022/7/1723編譯程序組織存儲空間時必須考慮的問題過程能否遞歸？當(dāng)控制從過程的活動返回時，局部變量的值是否要保留？過程能否訪問非局部變量？過程調(diào)用的參數(shù)傳遞方式？過程能否作為參數(shù)被傳遞？過程能否作為結(jié)果值傳遞？存儲塊能否在程序控制下動態(tài)地分配？存儲塊是否必須顯式地釋放？2022/7/17249.2 存儲組織9.2.1 運行時內(nèi)存的劃分9.2.2 活動記錄9.2.3 局部數(shù)據(jù)的組織9.2.4 全局存儲分配策略2022/7/17259.2.1 運行時內(nèi)存的劃分目標代碼靜態(tài)數(shù)據(jù)棧堆空閑 空間2022/7/172

14、6過程的每個活動所需要的信息用一塊連續(xù)的存儲區(qū)來管理，這塊存儲區(qū)叫做活動記錄 假定語言的特點為:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，過程定義允許/不允許嵌套。采用棧式存儲分配機制活動記錄：運行時，每當(dāng)進入一個過程就有一個相應(yīng)的活動記錄壓入棧頂?；顒佑涗浺话愫羞B接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時工作單元等。9.2.2 活動記錄2022/7/1727對任何局部變量X的引用可表示為變址訪問: dxSPdx:變量X相對于活動記錄起點的地址，在編譯時可確定。參數(shù)個數(shù)返回地址形式單元臨時變量數(shù)組內(nèi)情向量簡單變量SP 012舊SPTOP 每個過程的活動記錄內(nèi)容 非嵌套語言(如C)20

15、22/7/1728 連接數(shù)據(jù) 返回地址 動態(tài)鏈：指向調(diào)用該過程前的最新活動記錄地址的指針。 靜態(tài)鏈：指向靜態(tài)直接外層最新活動記錄地址的指針，用來訪問非局部數(shù)據(jù)。靜態(tài)鏈動態(tài)鏈形式單元臨時變量數(shù)組內(nèi)情向量局部變量SP012返回地址TOP 每個過程的活動記錄內(nèi)容 嵌套語言(如Pascal)2022/7/1729形式單元：存放相應(yīng)的實在參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時工作單元(如存放對表達式求值的結(jié)果)。靜態(tài)鏈動態(tài)鏈形式單元臨時變量數(shù)組內(nèi)情向量局部變量SP 012返回地址TOP 每個過程的活動記錄內(nèi)容2022/7/17309.2.3 局部數(shù)據(jù)的組織字節(jié)是可編址內(nèi)存的最小單位。變量所

16、需的存儲空間可以根據(jù)其類型而靜態(tài)確定。一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。 局部數(shù)據(jù)的地址可以用相對于某個位置的地址來表示。數(shù)據(jù)對象的存儲安排還有對齊的問題。整數(shù)必須放在內(nèi)存中特定的位置，如被2、4、8整除的地址2022/7/17319.2.3 局部數(shù)據(jù)的組織在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的size分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;charc2; long i;double f; double f;a

17、; b;2022/7/17329.2.3 局部數(shù)據(jù)的組織在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的size分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1charc2;8 long i; 4double f;16 double f;8a; b;2022/7/17339.2.3 局部數(shù)據(jù)的組織在X86/Linux機器的結(jié)果和SPARC/Solaris工作站不一樣，是20和16。typedef struct _atypedef struct _bchar c1;0

18、 char c1;0long i;4 char c2; 1charc2;8 long i; 4double f;12 double f;8a; b;2022/7/1734靜態(tài)存儲分配策略(FORTRAN) 如果在編譯時能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時刻為每個數(shù)據(jù)項目確定出在運行時刻的存儲空間中的位置。動態(tài)存儲分配策略(PASCAL) 如果在編譯時不能確定運行時數(shù)據(jù)空間的大小，則必須采用動態(tài)分配方法。允許遞歸過程及動態(tài)申請、釋放內(nèi)存。棧式動態(tài)存儲分配堆式動態(tài)存儲分配9.2.4 全局存儲分配策略 2022/7/17359.3 靜態(tài)存儲分配策略如果在編譯時就能確定一個程序在運行時

19、所需要的存儲空間的大小，則在編譯時就能安排好目標程序運行時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項的地址，存儲空間的這種分配方法稱為靜態(tài)存儲分配。必須滿足如下條件：數(shù)據(jù)對象的長度和它在內(nèi)存中的位置在編譯時必須是已知的；不允許過程的遞歸調(diào)用，因為一個過程的所有活動都是用同樣的局部名字綁定的；數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立，因為沒有運行時的存儲分配機制。2022/7/1736某分段式程序運行時的內(nèi)存劃分2022/7/1737每個數(shù)據(jù)區(qū)有一個編號，地址分配時，在符號表中，對每個數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號及在該區(qū)中的相對位置?？紤]子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND寄

20、存器保護區(qū)返回地址ATB01a2022/7/1738靜態(tài)存儲分配策略順序分配算法（基于調(diào)用圖）按照程序段出現(xiàn)的先后順序逐段分配1/222/153/184/176/105/23程序段 區(qū)域 021 2236 3754 5571 7294 95104共需要105個存儲單元程序段號/所需數(shù)據(jù)空間能用更少的空間么？2022/7/1739分層分配算法允許程序段之間的覆蓋（覆蓋可能性分析）程序段 區(qū)域6095022 4016323402173114162共需要63個存儲單元1/222/153/184/176/105/23思考：如何設(shè)計分配算法？7/802022/7/17409.4 棧式存儲分配策略如果過程

21、允許遞歸某一時刻過程A可能已被自己調(diào)用了若干次，但只有最近一次處于執(zhí)行狀態(tài)。其余各次等待返回被中斷的那次調(diào)用必須保存每次調(diào)用相應(yīng)的數(shù)據(jù)區(qū)內(nèi)容（活動記錄）引入一個運行棧讓過程的每次執(zhí)行和過程的活動記錄相對應(yīng)。每調(diào)用一次過程，就把該過程的活動記錄壓入棧中，返回時彈出。假設(shè)寄存器top標記棧頂，局部名字x的相對地址為dx，則x的地址為top+dx 或 dxtop2022/7/17419.4.1 調(diào)用序列和返回序列 過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復(fù)機器狀態(tài)等過程調(diào)用和返回是通過在目標代碼中生成調(diào)用序列和返回序列來實現(xiàn)的 調(diào)用序列負責(zé)分配活動記錄，并將相關(guān)信息填入活動記錄

22、中 返回序列負責(zé)恢復(fù)機器狀態(tài)，使調(diào)用過程能夠繼續(xù)執(zhí)行 調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中2022/7/17429.4.1 調(diào)用序列和返回序列即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設(shè)計這些序列和活動記錄的一些原則：以活動記錄中間的某個位置作為基地址；長度能較早確定的域放在活動記錄的中間；一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面，以便其長度的改變不會影響數(shù)據(jù)對象相對于中間那些域的位置；用同樣的代碼來執(zhí)行各個活動的狀態(tài)保存和恢復(fù)；把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動記錄的地方。2022/7/17439.4.1 調(diào)用序列和返

23、回序列調(diào)用者和被調(diào)用者之間的任務(wù)劃分2022/7/17449.4.1 調(diào)用序列和返回序列一種可能的調(diào)用序列：調(diào)用者計算實參調(diào)用者把返回地址和sp的舊值存入被調(diào)用者的活動記錄中，然后將sp移過調(diào)用者的局部數(shù)據(jù)域和臨時變量域，以及被調(diào)用者的參數(shù)域和狀態(tài)域被調(diào)用者保存寄存器值和其它機器狀態(tài)信息被調(diào)用者初始化其局部數(shù)據(jù)，并開始執(zhí)行。2022/7/17459.4.1 調(diào)用序列和返回序列一種可能的返回序列： 被調(diào)用者將返回值放入臨近調(diào)用者的活動記錄的地方。利用狀態(tài)域中的信息，被調(diào)用者恢復(fù)sp和其它寄存器，并且按調(diào)用者代碼中的返回地址返回。盡管sp的值減小了，調(diào)用者仍然可以將返回值復(fù)制到自己的活動記錄中，并

24、用它來計算一個表達式。2022/7/17469.4.1 調(diào)用序列和返回序列過程的參數(shù)個數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進棧的代碼被調(diào)用函數(shù)能準確地知道第一個參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個參數(shù)到棧中取第二、第三個參數(shù)等等如C語言的printf2022/7/1747過程調(diào)用的三地址碼:param x1param x2 param xncall p，n9.4.2 C語言的過程調(diào)用和返回 2022/7/17481) 每個param xi(i=1,2,n)可直接翻譯成如下指令:(i+3)top:= xi (傳值)(i+3)top:=addr(xi) (傳地址)2) call

25、 p，n 被翻譯成如下指令:1top:=sp (保護現(xiàn)行sp)3top:=n (傳遞參數(shù)個數(shù))JSR p (轉(zhuǎn)子指令)參數(shù)個數(shù)返回地址內(nèi)情向量局部變量老sp臨時單元對于par和call產(chǎn)生的目標代碼top sp 調(diào)用過程的活動記錄老sp參數(shù)個數(shù)形式單元形式單元2022/7/17493) 進入過程p后，首先應(yīng)執(zhí)行下述指令:sp:=top+1 (定義新的sp)1sp:=返回地址 (保護返回地址)top:=top+L (新top) L：過程P的活動記錄所需單元數(shù)， 在編譯時可確定。 參數(shù)個數(shù)返回地址形式單元內(nèi)情向量局部變量老sp臨時單元TOP 調(diào)用過程的活動記錄返回地址topsp2022/7/175

26、04) 過程返回時，應(yīng)執(zhí)行下列指令:top:=sp-1 (恢復(fù)調(diào)用前top)sp:=0sp (恢復(fù)調(diào)用前SP)X:=2top (把返回地址取到X中)UJ 0X (按X返回) UJ為無條件轉(zhuǎn)移指令， 即按X中的返回地址實行變址轉(zhuǎn)移參數(shù)個數(shù)返回地址形式單元內(nèi)情向量局部變量老sp臨時單元調(diào)用過程的活動記錄topspsptop2022/7/17519.4.3 棧中的可變長數(shù)據(jù)活動記錄的長度在編譯時不能確定的情況局部數(shù)組的大小要等到過程激活時才能確定在活動記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運行時，這些指針指向分配在棧頂?shù)拇鎯臻g2022/7/17529.4.3 棧中的可變長數(shù)據(jù)圖9.13 訪問動態(tài)

27、分配的數(shù)組2022/7/1753棧式存儲分配策略的局限棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持被調(diào)用者的活動比調(diào)用者的活動的生存期更長，此時活動樹不能正確描繪程序的控制流不遵守棧式規(guī)則的有Pascal語言和C語言的動態(tài)變量Java禁止程序員自己釋放空間 2022/7/17549.5 棧中非局部數(shù)據(jù)的訪問本節(jié)內(nèi)容無嵌套過程的靜態(tài)作用域的實現(xiàn)（C語言）包含嵌套過程的靜態(tài)作用域的實現(xiàn)（Pascal語言）動態(tài)作用域的實現(xiàn)（Lisp語言）2022/7/17559.5.1 無過程嵌套的靜態(tài)作用域假定:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如C語言。過程

28、體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒佑涗浿?，可以通過sp指針來訪問無須深入棧中取數(shù)據(jù)，無須訪問鏈過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回C語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況:非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動記錄棧頂?shù)哪莻€活動記錄中外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū) 9.5.1 無過程嵌套的靜態(tài)作用域2022/7/17562022/7/1757 全局數(shù)據(jù)說明main( ) main中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明主

29、程序過程Q 過程RQ的活動記錄主程序活動記錄TOPR的活動記錄SP參數(shù)個數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時單元全局數(shù)據(jù)區(qū)2022/7/17589.5.2 有過程嵌套的靜態(tài)作用域假定語言不僅允許過程的遞歸調(diào)用(和可變數(shù)組)，而且允許過程定義的嵌套，如PASCAL，PL語言。sortreadarrayexchangequicksortpartition2022/7/1759(1) program sort(input, output);(2) var a :array0.10 of integer;(3) x :integer;(4) procedure readarray;(5) va

30、r i :integer;(6) begin a end readarray;(7) procedure exchange(i,j:integer);(8) begin (9) x:= ai; ai:=aj; aj:= x;(10) end exchange ;program sort procedure readarray procedure exchange procedure quicksort function partition 2022/7/1760(11) procedure quicksort(m,n:integer);(12) var k,v:integer;(13) fun

31、ction partition(y,z:integer): integer;(14) var i,j:integer;(15) begin a(16) v(17) exchange(i,j);(18) end partition;(19) begin end quicksort;(20) begin end gram sort procedure readarray procedure exchange procedure quicksort function partition 2022/7/17619.5.2 有過程嵌套的靜態(tài)作用域引入概念：過程嵌套深度sort1reada

32、rray2exchange2quicksort2partition3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度2022/7/17629.5.2 有過程嵌套的靜態(tài)作用域1. 訪問鏈 2022/7/17639.5.2 有過程嵌套的靜態(tài)作用域假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np。如何訪問a的存儲單元？從棧頂?shù)幕顒佑涗涢_始, 追蹤訪問鏈np-na次。到達a的聲明所在過程的活動記錄。訪問鏈的追蹤用間接操作就可完成。2022/7/17649.5.2 有過程嵌套的靜態(tài)作用域過程p對變量a訪問時，a的地址由下面的二元組表示：（np na，a在活動記錄中的偏移

33、）2022/7/17659.5.2 有過程嵌套的靜態(tài)作用域如何建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況x必須在p中進行定義，否則它對于p來說就是不可訪問的被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記錄的訪問鏈2022/7/17669.5.2 有過程嵌套的靜態(tài)作用域如何建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況p和x的嵌套深度分別為1，2，nx 1的外圍過程肯定相同追蹤訪問鏈np nx + 1次，到達了靜態(tài)包圍x和p的且離它們最近的那個過程的最新活動記錄所到達的訪問鏈就是x的活動記錄中的訪問鏈應(yīng)該指向的那個訪問鏈2022/7

34、/17679.5.2 有過程嵌套的靜態(tài)作用域2.過程型參數(shù)的訪問鏈program param(input, output); procedure b(function h(n: integer): integer); begin writeln(h(2) end b;procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin cend.過程作為參數(shù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈從b的訪問鏈難以建立f的訪問鏈激活f

35、c傳遞參數(shù)f時，像調(diào)用f一樣為f建立一個訪問鏈，該訪問鏈同f一起傳遞給b。f被激活時用這個訪問鏈建立f的活動記錄的訪問鏈2022/7/17689.5.2 有過程嵌套的靜態(tài)作用域program param(input, output);（過程作為參數(shù)）procedure b(function h( begin writeln(h(2) end ;procedure c; var m: integer; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin cend.2022/7/17699.5.2

36、 有過程嵌套的靜態(tài)作用域program ret (input, output);（過程作為返回值） var f: function (integer): integer;function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln ( g(2) en

37、d; begin f := a; b(f) end.retabaddm被調(diào)過程addm活動的生存期超出了調(diào)用過程a活動的生存期棧式存儲分配策略失效！活動樹2022/7/17703. Display表Display表是一個指針數(shù)組d，在運行過程中，若當(dāng)前活動的過程的嵌套深度為i，則di中存放當(dāng)前的活動記錄地址，di-1,di-2, ,d1 中依次存放著當(dāng)前活動的過程的直接外層， , 直至最外層（主程序）等每一層過程的最新活動地址。 這樣，嵌套深度為j的變量a存放在由dj所指出的活動記錄中。在運行過程中維持一個Display表實現(xiàn)非局部訪問比存取鏈效率要高。9.5.2 有過程嵌套的靜態(tài)作用域202

38、2/7/1771Display表的維護（過程不作為參數(shù)傳遞）當(dāng)嵌套深度為i的過程的活動記錄壓在棧頂時： (1)在新的活動記錄中保存di的值； (2)置di指向新的活動記錄。 在一個活動結(jié)束前， di置成保存的舊值。用Display表如何訪問非局部量？ 1. Display表是一個數(shù)組，開始地址用通用 寄存器指出； 2. Display表由一組寄存器實現(xiàn)。9.5.2 有過程嵌套的靜態(tài)作用域2022/7/1772一個例子program P;var a, x : integer;procedure Q(b: integer);var i: integer;procedure R(u: integer

39、; 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 過程 R2022/7/1773一、通過靜態(tài)鏈訪問非局部數(shù)據(jù) 靜態(tài)鏈：指向本過程的直接外層過程的活動記錄的起始地址，也稱訪問鏈。動態(tài)鏈：指向本過程的調(diào)用過程的活動記錄的起始地址，也稱控制鏈。參數(shù)個數(shù)返回地址形式單元臨

40、時單元內(nèi)情向量局部變量SP012動態(tài)鏈(老SP)TOP 靜態(tài)鏈2022/7/17740002a3x4SP TOP主程序P1返回地址2022/7/1775002a3x405070(形參個數(shù))8c9i10SP TOP動態(tài)鏈靜態(tài)鏈主程序P過程 S問：第N層過程調(diào)用第 N+1層過程，如何確定被調(diào)用過程(第 N+1層) 的靜態(tài)鏈？答：調(diào)用過程(第N層過程)的最新活動記錄的起始地址.01返回地址6返回地址2022/7/17760002a3x4056070(形參個數(shù))8c9i10SP TOP動態(tài)鏈靜態(tài)鏈主程序P 過程 S 過程 Q5110131(形參個數(shù))14b(形參)15i16問：第N層過程調(diào)用第 N層過

41、程，如何確定被調(diào)用過程(第 N層) 的靜態(tài)鏈？答：調(diào)用過程(第N層過程)的靜態(tài)鏈的值。返回地址12返回地址1返回地址2022/7/177700102a3x4056070(形參個數(shù))8c9i10動態(tài)鏈靜態(tài)鏈主程序P 過程 S 過程 Q 過程 R511120131(形參個數(shù))14b(形參)15i161117返回地址1811192(形參個數(shù))20u(形參)21v(形參)22c23d24SP TOP返回地址返回地址返回地址2022/7/177800102a3x4056070(形參個數(shù))8c9i10動態(tài)鏈靜態(tài)鏈主程序P 過程 S 過程 Q 過程 R 過程 R511120131(形參個數(shù))14b(形參)1

42、5i161117返回地址1811192(形參個數(shù))20u(形參)21v(形參)22c23d241725返回地址2611272(形參個數(shù))28u(形參)29v(形參)30c31d32TOPSP 返回地址返回地址返回地址2022/7/177900返回地址102a3x405返回地址6070(形參個數(shù))8c9i10動態(tài)鏈靜態(tài)鏈主程序P 過程 S 過程 Q 過程 R 過程 Q511返回地址120131(形參個數(shù))14b(形參)15i161117返回地址1811192(形參個數(shù))20u(形參)21v(形參)22c23d24TOPSP 1725返回地址260271(形參個數(shù))28b(形參)29i30問：第N

43、層過程調(diào)用第 N-x層過程，如何確定被調(diào)用過程(第 N-x層)過程的靜態(tài)鏈？答:沿著調(diào)用過程(第N層過程)的靜態(tài)鏈向前走x步到達的活動記錄的靜態(tài)鏈的值。2022/7/1780二、通過Display表訪問非局部數(shù)據(jù)SPn為第n層過程數(shù)據(jù)區(qū)首址9.5.2 有過程嵌套的靜態(tài)作用域SPnSPn-1SP1SP0數(shù)組存儲區(qū)本過程 所轄分 第 臨時工作單元程 一序 層 局部數(shù)組說明存 分儲 程 局部變量區(qū) 序 分程序TOP本過程Display形式單元（m+1個）連 主調(diào)分程序TOP接 全局Display地址數(shù) 返回地址據(jù) 主調(diào)過程SP本過程TOPSP2022/7/1781令過程R的外層為Q，Q的外層為主程序

44、P，則過程R運行時的DISPLAY表內(nèi)容為：2022/7/1782問題：當(dāng)過程P1調(diào)用過程P2而進入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P0P2P1P0P1P22022/7/1783問題：當(dāng)過程P1調(diào)用過程P2而進入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2l2: P1的最新活動記錄的起始地址P0的最新活動記錄的起始地址P1的display表P0的最新活動記錄的起始地址l2: P2的最新活動記錄的起始地址P2的display表從P1的display表中自底而上地取過l2個單元（l2為P2的層數(shù)）再添上進入P2后新建立的SP值就構(gòu)成了P2的display

45、表。2022/7/1784問題：當(dāng)過程P1調(diào)用過程P2而進入P2后，P2應(yīng)如何建立起自己的display表？P0P2P1l2-1: P1的最新活動記錄的起始地址P0的最新活動記錄的起始地址P1的display表P0的最新活動記錄的起始地址P1的最新活動記錄的起始地址P2的display表從P1的display表中自底而上地取過l2個單元（l2為P2的層數(shù)）再添上進入P2后新建立的SP值就構(gòu)成了P2的display表。l2: P2的最新活動記錄的起始地址2022/7/1785問題：當(dāng)過程P1調(diào)用過程P2而進入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P1的最新活動記錄的起始地址

46、P0的最新活動記錄的起始地址P1的display表P0的最新活動記錄的起始地址P2的display表從P1的display表中自底而上地取過l2個單元（l2為P2的層數(shù)）再添上進入P2后新建立的SP值就構(gòu)成了P2的display表。l2: P2的最新活動記錄的起始地址l2: P2的最新活動記錄的起始地址2022/7/1786問題：當(dāng)過程P1調(diào)用過程P2而進入P2后，P2應(yīng)如何建立起自己的display表？答案：從P1的display表中自底而上地取過l2個單元（l2為P2的層數(shù)）再添上進入P2后新建立的SP值就構(gòu)成了P2的display表。把P1的display表地址作為連接數(shù)據(jù)之一(稱為全局

47、display地址)傳送給P2就能夠建立P2的display表。P0P1P2P0P2P1P0P1P22022/7/1787diaplay表在活動記錄中的相對地址d在編譯時能完全確定。假定在現(xiàn)行過程中引用了某層過程(令其層次為k)的X變量，那么，可用下面兩條指令獲得X的地址: LD R1 (d+k)SP LD R2 dxR1嵌套過程語言活動記錄參數(shù)個數(shù)返回地址形式單元臨時單元內(nèi)情向量局部變量SP 012老SPTOP Display 表全局Display3d2022/7/1788一個例子program P;var a, x : integer;procedure Q(b: integer);var

48、 i: integer;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 過程 R2022/7/178900返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序

49、過程 Sc11i12TOPSP 動態(tài)鏈2022/7/179000返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序P過程 S 過程 Qc11i12動態(tài)鏈513返回地址149(全局display)151(形參個數(shù))16b(形參)170181319i20TOPSP 2022/7/179100返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序P過程 S 過程 Q 過程 Rc11i12動態(tài)鏈513返回地址149(全局display)151(形參個數(shù))16b(形參)17018131

50、9i201321返回地址2218(全局display)232(形參個數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP 2022/7/179200返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序P 過程 S 過程 Q 過程 R 過程 Rc11i12動態(tài)鏈513返回地址149(全局display)151(形參個數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP 2132返回

51、地址3327(全局display)342(形參個數(shù))35u(形參)36v(形參)3703813393240c41d422022/7/1793過程調(diào)用、過程進入、過程返回每個par Ti(i=1,2,n)可直接翻譯成如下指令:(i+4)TOP:= Ti (傳值) (i+4)TOP:=addr(Ti ) (傳地址)參數(shù)個數(shù)返回地址形式單元臨時單元內(nèi)情向量局部變量老SPDisplay 表全局DisplayTOPSP 調(diào)用過程的活動記錄形式單元2022/7/1794參數(shù)個數(shù)返回地址形式單元臨時單元內(nèi)情向量局部變量老SPDisplay 表全局Display2. call P，n 被翻譯成:1TOP:=S

52、P (保護現(xiàn)行SP)3TOP:=SP+d (傳送現(xiàn)行display地址)4TOP:=n (傳遞參數(shù)個數(shù))JSR (轉(zhuǎn)子指令)過程調(diào)用、過程進入、過程返回TOPSP 調(diào)用過程的活動記錄老SP全局Display參數(shù)個數(shù)2022/7/17953. 轉(zhuǎn)進過程P后，首先定義新的SP和TOP，保存返回地址。4. 根據(jù)全局display建立現(xiàn)行過程的display：從全局display表中自底向上地取l個單元，在添上進入P后新建立的SP值就構(gòu)成了P的display。參數(shù)個數(shù)返回地址形式單元臨時單元內(nèi)情向量局部變量老SPDisplay 表全局DisplayTOPSP 調(diào)用過程的活動記錄返回地址Display

53、表過程調(diào)用、過程進入、過程返回2022/7/17965. 過程返回時，執(zhí)行下述指令: TOP:=SP-1SP:=0SPX:=2TOPUJ 0X參數(shù)個數(shù)返回地址形式單元臨時單元內(nèi)情向量局部變量老SPDisplay 表全局DisplayTOPSP 調(diào)用過程的活動記錄TOPSP 過程調(diào)用、過程進入、過程返回2022/7/17979.5.3 動態(tài)作用域的實現(xiàn) 從技術(shù)上講，如果作用域策略需要基于程序運行時才能知道的因素，則任何作用域策略都將是動態(tài)的。但“動態(tài)作用域”這個術(shù)語通常是指下面的策略：名字x的引用指向帶有x聲明的最近被調(diào)用的過程中x的這個聲明。 在某種意義上說，動態(tài)作用域規(guī)則相對于時間，而靜態(tài)作

54、用域規(guī)則相對于空間。2022/7/17989.5.3 動態(tài)作用域程序運行時，一個名字a實施其影響，直到含a的聲明的一個過程開始執(zhí)行時暫停，此過程停止時，該影響恢復(fù)。 設(shè)有下面的的調(diào)用序列： A B C P過程P中有對x的非局部引用，沿動態(tài)鏈（紅鏈）查找，最先找到的便是。2022/7/17999.5.3 動態(tài)作用域program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end

55、; begin靜態(tài)作用域 r := 0.25; 0.2500.250 show; small; writeln;0.2500.250 show; small; writeln end.dynamicshowsmallsmallshowshowshow2022/7/171009.5.3 動態(tài)作用域program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin動態(tài)

56、作用域 r := 0.25; 0.2500.125 show; small; writeln;0.2500.125 show; small; writeln end.dynamicshowsmallsmallshowshowshow2022/7/171019.5.3 動態(tài)作用域?qū)崿F(xiàn)動態(tài)作用域的方法深訪問(訪問非局部名字時的開銷大,易于實現(xiàn)過程類參數(shù))用控制鏈搜索運行棧，尋找包含該非局部名字的第一個活動記錄淺訪問(活動開始和結(jié)束時的開銷大)將每個名字的當(dāng)前值保存在靜態(tài)分配的內(nèi)存空間中當(dāng)過程p開始一個新的活動時，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的內(nèi)存單元。n的先前值必須保存在p的活動記錄中，

57、當(dāng)p的活動結(jié)束時再恢復(fù)2022/7/171029.6 堆管理對于允許程序為變量在運行時動態(tài)申請和釋放存儲空間的語言, 采用堆式分配是最有效的解決方案.活動結(jié)束時必須保持局部名字的值。被調(diào)用者的活動比調(diào)用者的活動的生存期長。堆式分配的基本思想是, 為運行的程序劃出適當(dāng)大的空間(稱為堆Heap), 每當(dāng)程序申請空間時, 就從堆的空閑區(qū)找出一塊空間分配給程序, 每當(dāng)釋放時則回收之.內(nèi)存管理器分配和回收堆區(qū)空間的子系統(tǒng) 是應(yīng)用程序和操作系統(tǒng)之間的一個接口 2022/7/171039.6.1 內(nèi)存管理器內(nèi)存管理器的基本任務(wù)空間分配。每當(dāng)程序為某個變量或?qū)ο笊暾堃粔K內(nèi)存空間時，內(nèi)存管理器就產(chǎn)生一塊連續(xù)的具

58、有被請求大小的堆空間。空間回收。內(nèi)存管理器把回收的空間返還到空閑空間的緩沖池中，用于滿足其它的分配請求。2022/7/171049.6.1 內(nèi)存管理器如果下面兩個條件成立的話，內(nèi)存管理將會變得相對簡單一些所有的分配請求都要求相同大小的塊；存儲空間按照某種可以預(yù)見的方式來釋放，如先分配者先釋放。2022/7/171059.6.1 內(nèi)存管理器內(nèi)存管理器的設(shè)計目標空間效率。內(nèi)存管理器應(yīng)該使程序所需堆區(qū)空間的總量達到最小，以便在某個固定大小的虛擬地址空間中運行更大的程序。方法：減少內(nèi)存碎片的數(shù)量。程序效率。內(nèi)存管理器應(yīng)該充分利用內(nèi)存子系統(tǒng)，以便使程序運行得更快。方法：利用程序的“局部性”，即程序在訪問

59、內(nèi)存時具有非隨機性聚集的特性。低開銷。由于存儲分配和回收在很多程序中都是常用的操作，所以內(nèi)存管理器應(yīng)該盡可能地提高這些操作的執(zhí)行效率，也就是說要盡可能地降低它們的開銷。2022/7/171069.6.2 內(nèi)存體系要想做好內(nèi)存管理和編譯器優(yōu)化，首先要充分了解內(nèi)存的工作機理。 內(nèi)存訪問時間的巨大差異來源于硬件技術(shù)的局限。 圖9.21 典型的內(nèi)存體系2022/7/171079.6.3 程序中的局部性 程序的局部性程序中的大部分運行時間都花費在較少的一部分代碼中，而且只是涉及到一小部分數(shù)據(jù)。時間局部性：如果某個程序訪問的內(nèi)存位置有可能在很短的時間內(nèi)被再次訪問空間局部性：如果被訪問過的內(nèi)存位置的鄰近位置

60、有可能在很短的時間內(nèi)被再次訪問2022/7/171089.6.3 程序中的局部性 程序的局部性使得我們可以充分利用圖9.21所示的內(nèi)存層次結(jié)構(gòu)，即將最常用的指令和數(shù)據(jù)放在快而小的內(nèi)存中，而將其余部分放在慢而大的內(nèi)存中，這將顯著降低程序的平均內(nèi)存訪問時間很多程序在對指令和數(shù)據(jù)的訪問方式上既表現(xiàn)出時間局部性，又表現(xiàn)出空間局部性2022/7/171099.6.3 程序中的局部性 雖然將最近使用過的數(shù)據(jù)放在最快的內(nèi)存層中在普通程序中可以發(fā)揮很好的作用，但是在某些數(shù)據(jù)密集型的程序中的作用卻并不明顯，如循環(huán)遍歷大數(shù)組的程序。將最近使用過的指令放在高速緩存中的策略一般都很有效。2022/7/171109.6