編譯原理第九章

1、編譯原理電子教案第九章第九章 運行時存儲空間組織運行時存儲空間組織謝強謝強計算機科學與技術(shù)學院計算機科學與技術(shù)學院上一頁下一頁本章的主要內(nèi)容本章的主要內(nèi)容n目標程序運行時的活動n運行時存儲器的劃分n靜態(tài)存儲分配n簡單棧式存儲分配n嵌套過程語言的棧式實現(xiàn)n堆式動態(tài)存儲2上一頁下一頁本章要求本章要求 知識點知識點：有關(guān)源語言中一些問題的討論，存儲組織，運行時刻存儲分配策略，對非局部名字的訪問，參數(shù)傳遞。 深刻理解：深刻理解：活動記錄，棧式存儲分配，訪問鏈（存取鏈），display表。 熟練掌握：熟練掌握： （1）對于已知過程，設(shè)計出其活動記錄； （2）對于已知程序，若采用棧式存儲分配，隨著程序的執(zhí)

2、行，畫出相應動態(tài)棧，訪問鏈（存取鏈）以及display表的變化； 3上一頁下一頁計算環(huán)境計算源程序映射運行時的環(huán)境目標代碼計算源程序中的名字（常量，變量）目標機存儲空間。它受命于源程序的執(zhí)行語義。 源程序由一組過程按某種規(guī)則組成。過程的一次執(zhí)行稱作一次活動活動，在過程的語句序列執(zhí)行之前，過程中訪問的對象構(gòu)成此過程的運行環(huán)境，由運行支持程序組織好。編譯程序根據(jù)如何組織運行環(huán)境而生成目標代碼。 在程序語言中，程序中使用的存儲單元都由標志符來表示。它對應的內(nèi)存地址都是由編譯程序在編譯時或由其生成的目標程序在運行時進行分配。 4上一頁下一頁本章教學線索本章教學線索1 目標程序運行時的活動目標程序運行時

3、的活動 1.1 過程的活動 1.2 說明的作用域（作用范圍） 1.3 名字與存儲的綁定 1.4 參數(shù)傳遞2 運行時存儲器的劃分運行時存儲器的劃分3 靜態(tài)存儲分配靜態(tài)存儲分配4 簡單棧式存儲分配簡單棧式存儲分配5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)6 堆式動態(tài)存儲堆式動態(tài)存儲5上一頁下一頁1.1 過程的活動過程的活動過程過程：過程定義是一個說明，其最簡單的形式是一個標識符和一段語句相關(guān)，標示符是過程名，語句是過程體。調(diào)用調(diào)用：當過程名出現(xiàn)在可執(zhí)行語句里的時候，稱該過程在這一點被調(diào)用。過程調(diào)用導致過程體的執(zhí)行。過程的活動過程的活動：一個過程的活動指的是該過程的一次執(zhí)行，也就是說，每次執(zhí)行

4、一個活動?；顒拥纳嫫诨顒拥纳嫫冢褐傅氖菑膱?zhí)行該過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行該過程時調(diào)用其它過程花費的時間?；顒拥纳嫫诨蛘呤乔短椎?，或者是不重疊的。過程的遞歸過程的遞歸：如果一個過程在沒有退出當前的活動時，又開始其新的活動，則這個過程是遞歸的。（遞歸有直接遞歸和間接遞歸）6上一頁下一頁1.2 說明的作用域（作用范圍）說明的作用域（作用范圍） 說明把名字與名字的屬性信息綁定在一起。 說明的作用域是一個說明起作用的范圍（源程序行文）。一個名字在源程序行文中可能有幾處說明，語言的作用域規(guī)則規(guī)定了在語句序列中引用的一個名字時，該名字是在何處說明的。 編譯時，處理說明語句時把

5、名字及其屬性信息填寫進符號表（add（id.entry，）； 處理引用名字時，查找這個名字的屬性信息（lookup（），符號表管理程序根據(jù)語言的作用域規(guī)則，使 lookup（）返回id的作作用域中綁定的屬性信息。7上一頁下一頁1.3 名字與存儲的綁定名字與存儲的綁定名字與存儲單元的綁定是指把源程序中的數(shù)據(jù)名字映射到目標機存儲單元的過程。引進兩個函數(shù)，environment和state。environment把名字映射到一個存儲單元上；state把存儲單元映射到那里所存放的值上。可以說，函數(shù)environment把一個名字映射為一個L-value（左-值

6、）,而函數(shù)state把一個L-value（左-值）映射為一個R-value（右-值）。如圖下圖所示。 存儲單元值存儲分配 程序運行environmentstateL-valueR-value從名字到值的兩個階段映射名字 靜態(tài)概念動態(tài)對應過程定義過程活動名字說明名字的綁定說明的作用域活動的生存期8上一頁下一頁1.4 參數(shù)傳遞參數(shù)傳遞形參與實參形參與實參：過程定義中的參數(shù)稱為形參；過程調(diào)用中的參數(shù)稱為實參。問題：如何把實在參數(shù)傳遞給形參？函數(shù)的返回值怎樣獲取？參數(shù)傳遞的三種形式： 傳地址：把實在參數(shù)的地址傳遞給相應的形式參數(shù)； 傳值：直接把實在參數(shù)的值傳遞給形式參數(shù) 傳名：換名，少見的方法！特別要

7、注意傳地址與傳值的區(qū)別！9上一頁下一頁本章教學線索本章教學線索1 目標程序運行時的活動目標程序運行時的活動2 運行時存儲器的劃分運行時存儲器的劃分 2.1 運行時刻內(nèi)存的劃分 2.2 活動記錄 2.3 存儲分配策略3 靜態(tài)存儲分配靜態(tài)存儲分配4 簡單棧式存儲分配簡單棧式存儲分配5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)6 堆式動態(tài)存儲堆式動態(tài)存儲10上一頁下一頁2.1 運行時刻內(nèi)存的劃分運行時刻內(nèi)存的劃分運行時刻的存儲空間必須劃分以用來存放：1.生成的目標代碼；2.數(shù)據(jù)目標；3.用于保存過程活動蹤跡的一個控制棧。 存儲空間劃分的各部分： 目標代碼靜態(tài)數(shù)據(jù)棧堆1.編譯后知道目標代碼的大小。

8、2 . P a s c a l 主 程 序 中 的 數(shù)據(jù),c,FORTRAN3. 棧:Pascal4. 堆:Pascal11上一頁下一頁2.2 活動記錄活動記錄 把過程的一個活動所需要的信息組織成一塊連續(xù)的存儲單元，稱為活動記錄活動記錄。 一個活動所需要的信息的每個數(shù)據(jù)項有相同的生存期，因此，組織成一個活動記錄是很自然的。 對于Pascal語言來說，運行過程中，當調(diào)用一個過程時，在棧頂構(gòu)筑它的活動記錄；當這個過程的活動執(zhí)行完后，把它從棧頂彈出。源語言不同，實現(xiàn)方法不同，組成活動記錄的域不同。實現(xiàn)Pascal語言的活動記錄的結(jié)構(gòu)如圖所示。臨時單元內(nèi)情向量局部向量形式單元靜態(tài)鏈動態(tài)鏈返回地址連接數(shù)

9、據(jù)SPTOP12上一頁下一頁 連接數(shù)據(jù)：返回地址動態(tài)鏈：指向調(diào)用該過程前的最新活動記錄地址的指針。運行時，使運行棧上各數(shù)據(jù)區(qū)按動態(tài)建立的次序結(jié)成鏈，鏈頭為棧頂起始位置。靜態(tài)鏈：指向靜態(tài)直接外層最新活動記錄地址的指針，用來訪問非局部數(shù)據(jù)。 形式單元：存放相應的實在參數(shù)的地址或值。 局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時工作單元（如存放對表達式求值的結(jié)果）13上一頁下一頁2.3 存儲分配策略存儲分配策略靜態(tài)分配策略靜態(tài)分配策略：在編譯時對所有的數(shù)據(jù)對象分配固定的存儲單元，并且在運行時始終保持不變。棧式動態(tài)分配策略棧式動態(tài)分配策略：在運行時把存儲器作為一個棧進行管理，運行時，每當調(diào)用一個過程，它所需要

10、的存儲空間就動態(tài)地分配于棧頂，一旦退出，它所占的空間就予以釋放。堆式動態(tài)分配策略堆式動態(tài)分配策略：在運行時把存儲器組織成堆結(jié)構(gòu)，以便用戶可以對存儲空間進行申請與歸還。14上一頁下一頁活動樹活動樹程序執(zhí)行期間的控制流： 程序執(zhí)行的控制是順序的； 過程的每一次執(zhí)行都是從過程體的開頭開始，并最終把控制返回到緊接著該過程被調(diào)用點的后面。 用一顆樹來描繪控制進入和離開活動的途徑。這樣的樹稱作活動樹。在一棵活動樹中： 每一個結(jié)點代表一個過程的活動； 根結(jié)點代表主程序的活動； 代表a的結(jié)點是b結(jié)點的父結(jié)點當且僅當控制從活動a進入活動b； 結(jié)點a在結(jié)點b的左邊當且僅當a的生存期發(fā)生在b的生存期之前?？刂茥？刂?/p>

11、棧 程序執(zhí)行的控制流對應于從根開始，按先根次序遍歷活動樹。因此，用一個棧保存過程活動的生存蹤跡，把它稱作控制棧。當一個活動開始執(zhí)行時，把代表這個活動的結(jié)點推進棧；當這個活動結(jié)束時，把代表這個活動的結(jié)點從棧中彈出。15上一頁下一頁srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)控制棧ss rs q(1.9)s q(1.9) p(1,9)s q(1.9) q(1,3)s q(1.9) q(1,3) p(1,3)s q(1.9) q(1,3) q(1,0)s q(1.9) q(1,3) q(2,3)活動樹與控制棧 控制棧中的活動都是活躍的，當前控制進入的活動在棧頂，從棧頂

12、活動到棧底活動的活動序列是從活動樹上當前結(jié)點通向根的路徑上的結(jié)點序列： s,q（1，9），q（l，3），q（2，3），從棧底活動到棧頂活動的活動序列表示了活動的生存期的嵌套關(guān)系。結(jié)論：擴充控制?？捎脕韺崿F(xiàn)如Pascal語言的棧式存儲分配，進入一個活動，在棧頂建立這個活動所使用的存儲空間；這個活動結(jié)束，從棧頂彈出其使用的存儲空間。16上一頁下一頁本章教學線索本章教學線索1 目標程序運行時的活動目標程序運行時的活動2 運行時存儲器的劃分運行時存儲器的劃分3 靜態(tài)存儲分配靜態(tài)存儲分配 3.1 靜態(tài)分配 3.2 FORTRAN的局部數(shù)據(jù)區(qū) 3.3 臨時變量的地址分配4 簡單棧式存儲分配簡單棧式存儲分配

13、5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)6 堆式動態(tài)存儲堆式動態(tài)存儲17上一頁下一頁3.1 靜態(tài)分配靜態(tài)分配在編譯時就能夠確定一個程序在運行時所需要的存儲空間的大小，則在編譯時就能夠安排好目標程序運行時的全部數(shù)據(jù)空間，并能夠確定每個數(shù)據(jù)項的單元地址。適于靜態(tài)管理的語言必須滿足的條件：1. 數(shù)組的上下界必須是常數(shù)2. 過程調(diào)用不允許遞歸3. 不允許用戶動態(tài)地建立數(shù)據(jù)實體編譯程序可以確定出現(xiàn)在程序中的數(shù)據(jù)實體的地址（一般相對于各數(shù)據(jù)區(qū)基地址的偏移量)。由于過程調(diào)用不允許遞歸，數(shù)據(jù)實體的存儲地址就和過程相聯(lián)系，過程調(diào)用的活動記錄就可以直接安排在目標代碼之后，并把各數(shù)據(jù)項的存儲地址填入到相關(guān)的

14、目標代碼中，以便在運行時訪問這些數(shù)據(jù)存儲空間。這里，不存在對存儲區(qū)域的再利用。目標代碼運行時不必進行運行時的存儲管理。18上一頁下一頁3.2 FORTRANFORTRAN的局部數(shù)據(jù)區(qū)的局部數(shù)據(jù)區(qū) FORTRAN的編譯程序?qū)⒚總€程序段都定義對應的局部數(shù)據(jù)區(qū)，每個數(shù)據(jù)區(qū)都數(shù)據(jù)區(qū)都有一個編號有一個編號，在地址分配時，在符號表中，對每個數(shù)據(jù)名將登記上它是屬于哪個在地址分配時，在符號表中，對每個數(shù)據(jù)名將登記上它是屬于哪個數(shù)據(jù)區(qū)的，以及在該區(qū)中的相對位置（數(shù)據(jù)區(qū)的，以及在該區(qū)中的相對位置（DA、ADDR）。）。 一般情況下，程序段的局部數(shù)據(jù)區(qū)可以直接安排在該段程序的指令代碼之后，編譯時統(tǒng)計每個數(shù)據(jù)區(qū)的單元

15、數(shù)，對于各區(qū)的首地址暫時不分配，在運行前再用一個“裝入程序”（LOADER）把它們連成一個整體。FORTRAN的局部數(shù)據(jù)區(qū)內(nèi)容：臨時變量數(shù)組簡單變量形式單元寄存器保護區(qū)返回地址稱為：隱參數(shù)返回地址：用來保存調(diào)用此程序段時的返回地址；寄存器保護區(qū)：用來保存調(diào)用段留在寄存器中的有關(guān)信息。形式單元：用來存放實在參數(shù)的地址或值。19上一頁下一頁3.3 臨時變量的地址分配臨時變量的地址分配 在三地址代碼四元式生成中將產(chǎn)生大量的中間變量，在存儲空間的分配中也必須對這些臨時變量分配存儲空間。分配策略：分配策略：如果兩個臨時變量名作用域不相交，則它們可以分配在同一單元中。一個臨時變量名自它第一次被定值（賦值）

16、的地方起直至它最后一次被引用的地方止，這區(qū)間的程序所能到達的全體四元式構(gòu)成了它的作用域。 令臨時變量名都分配在局部數(shù)據(jù)區(qū)中，若某一單元已分配給某些臨時變量名，則把這些名字的作用域（它們必須互不相交信息記錄）作為此單元的分配信息記錄下來。每當要對一個新臨時變量名進行分配時，首先求出此名的作用域，然后按序檢查每個已分配單元，一旦發(fā)現(xiàn)新求出的作用域與某個單元所記錄的全部作用域均不相交時就把這個單元分配給這個新名，同時把它的作用域也添加到該單元的分配信息之中。如果新臨時變量的作用域和所有已分配單元的作用域均有沖突，則就分配給它一個新的單元，同時把新名的作用域作為此單元的分配信息。 20上一頁下一頁 一

17、般情況下，四元式中的臨時變量都是一邊生成，馬上使用，一次賦值，一次使用，其作用域類似于配對使用的括號。因此，可以用一個棧來放表達式計算過程中的中間結(jié)果。令k為棧的指示器，設(shè)它的初值是局部區(qū)中用來存放臨時變量值的區(qū)域首地址，每當發(fā)現(xiàn)對一個新的臨時變量名Ti定值時，就用k的現(xiàn)行值作為Ti的地址，然后把k累增1。每當引用了某個臨時變量名Ti作為操作數(shù)時（此時Ti的地址必已分配），就把指示器k的值遞減1。例子：P254 21上一頁下一頁本章教學線索本章教學線索1 目標程序運行時的活動目標程序運行時的活動2 運行時存儲器的劃分運行時存儲器的劃分3 靜態(tài)存儲分配靜態(tài)存儲分配4 簡單棧式存儲分配簡單棧式存儲

18、分配 4.1 語言要求 4.2 基于棧的存儲控制 4.3 同靜態(tài)存儲分配的區(qū)別 4.4 整體的分配情況 4.5 C語言的活動記錄 4.6 C的過程調(diào)用、進入、數(shù)據(jù)對象空間分配和過程返回5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)6 堆式動態(tài)存儲堆式動態(tài)存儲22上一頁下一頁4 簡單棧式存儲分配簡單棧式存儲分配 基于控制棧的原理： 存儲空間被組織成棧，活動記錄的推入和彈出分別對應于活動的開始和結(jié)束。 與靜態(tài)分配不同的是，在每次活動中把局部名字和新的存儲單元綁定，在活動結(jié)束時，活動記錄從棧中彈出，因而局部名字的存儲空間也隨之消失。 確定活動記錄中局部數(shù)據(jù)的地址：假設(shè)sp標記一個活動記錄的開始的位

19、置，dx表示x的地址相對于sp的偏移量。那么，x在過程的目標代碼中的地址可寫成dx（sp），在運行時刻，當把x的活動記錄筑于棧頂時，寄存器sp被賦于實際的地址，sp可以是一個寄存器。23上一頁下一頁調(diào)用序列和返回序列調(diào)用序列和返回序列通過在目標代碼中生成調(diào)用序列和返回序列實現(xiàn)過程的調(diào)用。激活一個過程的活動是執(zhí)行過程語句的結(jié)果。過程語句： p(e1，e2，en)的目標代碼（調(diào)用序列）完成任務：1）調(diào)用者對實在參數(shù)求值，并把它們傳送給被調(diào)用過程的活動記錄的參數(shù)域。2）調(diào)用者在被調(diào)用者的活動記錄中存放返回地址和老sp之值。之后調(diào)用者把sp之值增加到top的下一個存儲單元位置（被調(diào)用者的活動記錄首地址

20、）。3）被調(diào)用者存放寄存器值和其它狀態(tài)信息。4）被調(diào)用者初始化其局部數(shù)據(jù)并開始執(zhí)行。返回序列，return目標代碼完成的任務是：1.被調(diào)用者在自己的活動記錄的返回值域中放一個返回值。2.利用狀態(tài)域中的信息，被調(diào)用者恢復sp和其它寄存器，并且按返回地址轉(zhuǎn)移到調(diào)用者的代碼之中。3.調(diào)用者復制返回值到自己的活動記錄中。 任務的劃分，根據(jù)源語言、目標機器和操作系統(tǒng)等具體情況而定。上述任務，由運行支持子程序完成，可視為虛擬機指令。24上一頁下一頁4.1 語言要求語言要求 過程不允許嵌套，但允許過程遞歸調(diào)用，如C語言。25上一頁下一頁4.2 基于棧的存儲控制基于棧的存儲控制 將存儲組織成一個棧，過程的活動

21、記錄作為一個元素進行出入棧管理。運行時，每當進入一個過程時，就把它的活動記錄入棧，而形成該過程工作時的數(shù)據(jù)區(qū)，當該活動結(jié)束時，再出棧。26上一頁下一頁4.3 同靜態(tài)存儲分配的區(qū)別同靜態(tài)存儲分配的區(qū)別 不同的是：每次活動過程中，局部名字與新的存儲單元綁定，活動結(jié)束后，活動記錄從棧中彈出，局部名的存儲空間也隨之消失。注意：1）因而會出現(xiàn)同一過程的不同活動（不同時期）存儲空間的分配不一樣 2）由于遞歸，過程的活動可能有多個同時在棧中（活動記錄）27上一頁下一頁4.4 整體的分配情況整體的分配情況 R的活動記錄Q的活動記錄Main的活動記錄全局數(shù)據(jù)區(qū)TopSP程序運行時的某一時刻，表明主過程Main調(diào)

22、用Q，而Q又調(diào)用R。SP：總是指向現(xiàn)行過程活動記錄的起點，用于訪問局部數(shù)據(jù)；Top：總是指向（已占用）棧頂單元。28上一頁下一頁4.5 C C語言的活動記錄語言的活動記錄1）連接數(shù)據(jù)：老SP、返回地址2）參數(shù)個數(shù)3）形式單元4）過程的局部變量、數(shù)組內(nèi)情向量、臨時工作單元 注意：C語言的非局部變量僅能出現(xiàn)在源程序頭，非局部 變量可采用靜態(tài)存儲分配5）局部變量（形參）的訪問：在編譯時，對局部變量和形參都分配了存儲單元，其地址為相對于活動記錄基地址SP的偏移量。則其絕對地址就為： 絕對地址 = 活動記錄基地址 + 相對地址 臨時工作單元內(nèi)情向量簡單變量形式單元參數(shù)個數(shù)返回地址老SPSPTOP29上一

23、頁下一頁4.6 C C的過程調(diào)用、進入、數(shù)據(jù)對象空的過程調(diào)用、進入、數(shù)據(jù)對象空間分配和過程返回間分配和過程返回1）調(diào)用：將實參的地址或值傳遞給新的活動記錄中的形式單元。過程調(diào)用的四元式： param T1 param T2 param Tn call P，n 由于形式單元在活動記錄中的起始位置是固定的，因此對于每一個形式參數(shù)param Ti，可以翻譯為如下指令：（i+3）TOP = Ti （傳參數(shù)值）（i+3）TOP = addr（Ti） （傳參數(shù)地址）2）過程進入 四元式：CALL P，n 的翻譯： 1TOP = SP （保護現(xiàn)行的SP，即老SP） 3TOP = n （傳遞參數(shù)個數(shù)） JSR

24、 P （轉(zhuǎn)子指令，轉(zhuǎn)向P的第一條指令）30上一頁下一頁3）數(shù)據(jù)對象空間分配 SP = TOP + 1 （定義新的SP） 1SP = 返回地址 （保護返回地址） TOP = TOP + L 定義新的TOP （L為過程P的活動記錄所需的單元數(shù)，在處理說明語句時可以計算出來）4）過程的返回（過程的活動記錄出棧，同時恢復棧頂活動記錄的TOP和SP） 如果有返回值（函數(shù)），將返回值傳遞到每個特定寄存器中。 TOP = SP 1 SP = 0SP x = 2TOP UJ 0 x （UJ為無條件轉(zhuǎn)移語句，按x中的返回地址實行變址轉(zhuǎn)移）31上一頁下一頁本章教學線索本章教學線索1 目標程序運行時的活動目標程序運

25、行時的活動2 運行時存儲器的劃分運行時存儲器的劃分3 靜態(tài)存儲分配靜態(tài)存儲分配4 簡單棧式存儲分配簡單棧式存儲分配5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn) 5.1 嵌套過程語言非局部名字訪問的實現(xiàn) 5.2 參數(shù)傳遞的實現(xiàn)6 堆式動態(tài)存儲堆式動態(tài)存儲32上一頁下一頁5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn) 語言要求：過程不僅允許遞歸調(diào)用，還允許過程進行嵌套定義。 存儲分配的實現(xiàn)：采用棧式存儲分配，對于運行時的局部名和形參完全可以采用簡單棧式存儲分配，由于允許過程嵌套定義，因此對非局部變量的訪問需要單獨處理，可以采用:靜態(tài)鏈或顯示表（Display）來實現(xiàn)。 嵌套層次：記錄過程在定

26、義時所在的層數(shù)。約定主程序的層數(shù)為0。如果過程P的直接外層Q的層數(shù)為i，則P的層數(shù)就為i+1。在實現(xiàn)時，采用一個計數(shù)器，遇到過程定義proc Begin時，計數(shù)器增加1，遇到過程結(jié)束proc end時，計數(shù)器減1。將過程的層數(shù)作為過程名的一個屬性記錄在符號表中。33上一頁下一頁5.1 嵌套過程語言非局部名字訪問的實現(xiàn)嵌套過程語言非局部名字訪問的實現(xiàn)1）靜態(tài)鏈和活動記錄 在活動記錄中增加一個域，存儲指向直接外層的最新活動記錄的地址，這樣形成的鏈稱為靜態(tài)鏈。它表明過程定義時的嵌套關(guān)系。 活動記錄中存儲老SP形成的鏈稱為動態(tài)鏈，它表明了過程活動時的調(diào)用關(guān)系?；顒佑涗浀慕Y(jié)構(gòu)：臨時單元內(nèi)情向量簡單變量形

27、式單元形參個數(shù)靜態(tài)鏈返回地址動態(tài)鏈（老SP）SPTOP對于非局部變量的返回可以沿靜態(tài)鏈進行訪問。 34上一頁下一頁program P; var a,x integer; procedure Q(b:integer); var i:integer; procedure R(u:integer,v:integer); var c,d:integer; begin if u = 1 then R(u+1,v) v=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c, i:integer ; begin a = 1; Q(c); endS

28、begina=0;S;end011224d23c22v（形參）（形參）21u（形參）（形參）202(形參個數(shù)）形參個數(shù)）191118返回地址返回地址171116i15b(形參）形參）141(形參個數(shù)）形參個數(shù)）13012返回地址返回地址11510i9c80706返回地址返回地址504x3a201返回地址返回地址00PSQR過程Q調(diào)用R時活動記錄情況35上一頁下一頁2）嵌套層次顯示表和活動記錄 在進入一個過程后，在建立其活動記錄區(qū)的同時建立一張嵌套層次表display，該表給出了過程的嵌套關(guān)系，如果該過程的嵌套層次為i，則它的display表就包含i+1個單元（假設(shè)主過程的層次為0），displ

29、ay本身是一個棧。 由于過程的層數(shù)可以靜態(tài)確定，因此每個過程的display表的體積在編譯時可以確定，可以將display表作為活動記錄的一部分，置于形式單元的上端。例如：R的外層是Q，Q的外層是P，則R運行時display表的情況：R現(xiàn)行活動記錄地址Q的最新活動記錄地址P的活動記錄地址36上一頁下一頁對于非局部變量的絕對地址就為： 絕對地址 = display靜態(tài)層次 + 相對地址（非局部變量所在的靜態(tài)層次可以在編譯時處理說明語句時確定，可以記錄在符號表中）在活動記錄中，display表的相對位置d是確定的，因此，在現(xiàn)行過程中引用了某一外層過程（k層）的變量x，可以用以下指令獲取x的值：LD

30、 R1，（d+k）SP /*獲取x所在的最新活動記錄的SP值*/LD R2，xR1 /*變址取數(shù)，把X的值傳遞給R2*/臨時單元內(nèi)情向量簡單變量Display形參參數(shù)個數(shù)全局display返回地址老SP(動態(tài)鏈）SPTOP全局display：連接數(shù)據(jù)，用于記住調(diào)用過程的display表的地址，作為生成本過程display的關(guān)鍵參數(shù)。display根據(jù)全局display所指示的地址，從調(diào)用它的過程中的display表中抄入i個地址（假設(shè)該過程層數(shù)為i），然后將自己的起始地址放在display表頂。37上一頁下一頁program P; var a,x integer; procedure Q(b:

31、integer); var i:integer; procedure R(u:integer,v:integer); var c,d:integer; begin if u = 1 then R(u+1,v) v=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c, i:integer ; begin a = 1; Q(c); endSbegina=0;S;end0112191318017b（形參）（形參）161（形參個數(shù)）（形參個數(shù)）159(全局全局display）14返回地址返回地址13512i11c105908072（全局（

32、全局display)6返回地址返回地址504x3a201返回地址返回地址00displaydisplaydisplayS調(diào)用Q時PSQ38上一頁下一頁5.2 參數(shù)傳遞的實現(xiàn)參數(shù)傳遞的實現(xiàn) Par T，T為數(shù)組 根據(jù)不同語言的要求或傳遞數(shù)組T的首地址，或傳送它的內(nèi)情向量地址。 Par T，T為過程 一般需要傳遞過程T的入口地址和現(xiàn)行的display地址。 Par T，T為標號 一般需要傳遞標號T的地址和標號定義所在過程的活動記錄首地址。 Par T，T為形式參數(shù) 傳遞形式單元T的內(nèi)容。39上一頁下一頁本章教學線索本章教學線索1 目標程序運行時的活動目標程序運行時的活動2 運行時存儲器的劃分運行時

33、存儲器的劃分3 靜態(tài)存儲分配靜態(tài)存儲分配4 簡單棧式存儲分配簡單棧式存儲分配5 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)6 堆式動態(tài)存儲堆式動態(tài)存儲 6.1 堆式分配的必要性（以C語言為例） 6.2 堆式存儲管理的實現(xiàn) 6.3 減少碎片的技術(shù) 6.4 空間的釋放40上一頁下一頁6 堆式動態(tài)存儲堆式動態(tài)存儲 對于允許程序為變量在運行時動態(tài)申請和釋放存儲空間的語言，采用堆式分配是最有效的解決方案。 堆式分配的基本思想是，為運行的程序劃出適當大的空間(稱為堆Heap)，每當程序申請空間時，就從堆的空閑區(qū)找出一塊空間分配給程序，每當釋放時則回收。41上一頁下一頁6.1 堆式分配的必要性（以堆式分配

34、的必要性（以C C語言為例）語言為例）在C中處理鏈表等結(jié)構(gòu)時,常常隨機地插入或刪除一些結(jié)點,利用指針變量和結(jié)構(gòu)類型,可動態(tài)地生成新結(jié)點(使用malloc()函數(shù)), 或刪除之(使用free()函數(shù)).例如 struct node char data; struct node *next; ；定義了鏈表的結(jié)點，下面函數(shù)可在表的尾部添加新結(jié)點: void Append(struct node *head,char ch) struct node *p=head; while( (p-next) != NULL ) p=p-next ; p-next=malloc(sizeof(struct nod

35、e) ; p-next-data=ch ; p-next-next=NULL ;還可用下面的函數(shù)在表頭刪除一結(jié)點:void Delete(struct node *head) struct node *p=head; if(p != NULL) head =head-next; free(p); 42上一頁下一頁6.2 堆式存儲管理的實現(xiàn)堆式存儲管理的實現(xiàn)1 定長塊管理定長塊管理 堆式動態(tài)儲分配最簡單的實現(xiàn)是按定長塊進行。初 始化時，將堆存儲空間分成長度相等的若干塊，每塊 中指定一個鏈域，按照鄰塊的順序把所有塊鏈成一個 鏈表，用指針available指向鏈表中的第一塊。 分配時每次都分配指針available所指的塊，然后a