編譯原理第九章

編譯原理電子教案第九章運(yùn)行時(shí)存儲(chǔ)空間組織謝強(qiáng)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)ieqiang@本章的主要內(nèi)容目標(biāo)程序運(yùn)行時(shí)的活動(dòng)運(yùn)行時(shí)存儲(chǔ)器的劃分靜態(tài)存儲(chǔ)分配簡(jiǎn)單棧式存儲(chǔ)分配嵌套過程語言的棧式實(shí)現(xiàn)堆式動(dòng)態(tài)存儲(chǔ)2本章要求

知識(shí)點(diǎn)：有關(guān)源語言中一些問題的討論，存儲(chǔ)組織，運(yùn)行時(shí)刻存儲(chǔ)分配策略，對(duì)非局部名字的訪問，參數(shù)傳遞。深刻理解：活動(dòng)記錄，棧式存儲(chǔ)分配，訪問鏈（存取鏈），display表。熟練掌握：（1）對(duì)于已知過程，設(shè)計(jì)出其活動(dòng)記錄；（2）對(duì)于已知程序，若采用棧式存儲(chǔ)分配，隨著程序的執(zhí)行，畫出相應(yīng)動(dòng)態(tài)棧，訪問鏈（存取鏈）以及display表的變化；3計(jì)算環(huán)境計(jì)算源程序映射運(yùn)行時(shí)的環(huán)境目標(biāo)代碼計(jì)算源程序中的名字（常量，變量）→目標(biāo)機(jī)存儲(chǔ)空間。它受命于源程序的執(zhí)行語義。

源程序由一組過程按某種規(guī)則組成。過程的一次執(zhí)行稱作一次活動(dòng)，在過程的語句序列執(zhí)行之前，過程中訪問的對(duì)象構(gòu)成此過程的運(yùn)行環(huán)境，由運(yùn)行支持程序組織好。編譯程序根據(jù)如何組織運(yùn)行環(huán)境而生成目標(biāo)代碼。

在程序語言中，程序中使用的存儲(chǔ)單元都由標(biāo)志符來表示。它對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序在運(yùn)行時(shí)進(jìn)行分配。

4本章教學(xué)線索1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)1.1過程的活動(dòng)1.2說明的作用域（作用范圍）1.3名字與存儲(chǔ)的綁定1.4參數(shù)傳遞2運(yùn)行時(shí)存儲(chǔ)器的劃分3靜態(tài)存儲(chǔ)分配4簡(jiǎn)單棧式存儲(chǔ)分配5嵌套過程語言的棧式實(shí)現(xiàn)6堆式動(dòng)態(tài)存儲(chǔ)51.1過程的活動(dòng)過程：過程定義是一個(gè)說明，其最簡(jiǎn)單的形式是一個(gè)標(biāo)識(shí)符和一段語句相關(guān)，標(biāo)示符是過程名，語句是過程體。調(diào)用：當(dāng)過程名出現(xiàn)在可執(zhí)行語句里的時(shí)候，稱該過程在這一點(diǎn)被調(diào)用。過程調(diào)用導(dǎo)致過程體的執(zhí)行。過程的活動(dòng)：一個(gè)過程的活動(dòng)指的是該過程的一次執(zhí)行，也就是說，每次執(zhí)行一個(gè)活動(dòng)。活動(dòng)的生存期：指的是從執(zhí)行該過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行該過程時(shí)調(diào)用其它過程花費(fèi)的時(shí)間?；顒?dòng)的生存期或者是嵌套的，或者是不重疊的。過程的遞歸：如果一個(gè)過程在沒有退出當(dāng)前的活動(dòng)時(shí)，又開始其新的活動(dòng)，則這個(gè)過程是遞歸的。（遞歸有直接遞歸和間接遞歸）61.2說明的作用域（作用范圍）說明把名字與名字的屬性信息綁定在一起。說明的作用域是一個(gè)說明起作用的范圍（源程序行文）。一個(gè)名字在源程序行文中可能有幾處說明，語言的作用域規(guī)則規(guī)定了在語句序列中引用的一個(gè)名字時(shí)，該名字是在何處說明的。編譯時(shí)，處理說明語句時(shí)把名字及其屬性信息填寫進(jìn)符號(hào)表（add（id.entry，））；處理引用名字時(shí)，查找這個(gè)名字的屬性信息（lookup（）），符號(hào)表管理程序根據(jù)語言的作用域規(guī)則，使lookup（）返回id的作用域中綁定的屬性信息。71.3名字與存儲(chǔ)的綁定名字與存儲(chǔ)單元的綁定是指把源程序中的數(shù)據(jù)名字映射到目標(biāo)機(jī)存儲(chǔ)單元的過程。引進(jìn)兩個(gè)函數(shù)，environment和state。environment把名字映射到一個(gè)存儲(chǔ)單元上；state把存儲(chǔ)單元映射到那里所存放的值上?？梢哉f，函數(shù)environment把一個(gè)名字映射為一個(gè)L-value（左-值）,而函數(shù)state把一個(gè)L-value（左-值）映射為一個(gè)R-value（右-值）。如圖下圖所示。存儲(chǔ)單元值存儲(chǔ)分配

程序運(yùn)行environmentstateL-valueR-value從名字到值的兩個(gè)階段映射名字

靜態(tài)概念動(dòng)態(tài)對(duì)應(yīng)過程定義過程活動(dòng)名字說明名字的綁定說明的作用域活動(dòng)的生存期81.4參數(shù)傳遞形參與實(shí)參：過程定義中的參數(shù)稱為形參；過程調(diào)用中的參數(shù)稱為實(shí)參。問題：如何把實(shí)在參數(shù)傳遞給形參？函數(shù)的返回值怎樣獲?。繀?shù)傳遞的三種形式：傳地址：把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)；傳值：直接把實(shí)在參數(shù)的值傳遞給形式參數(shù)傳名：換名，少見的方法！特別要注意傳地址與傳值的區(qū)別！9本章教學(xué)線索1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)2運(yùn)行時(shí)存儲(chǔ)器的劃分2.1運(yùn)行時(shí)刻內(nèi)存的劃分2.2活動(dòng)記錄2.3存儲(chǔ)分配策略3靜態(tài)存儲(chǔ)分配4簡(jiǎn)單棧式存儲(chǔ)分配5嵌套過程語言的棧式實(shí)現(xiàn)6堆式動(dòng)態(tài)存儲(chǔ)102.1運(yùn)行時(shí)刻內(nèi)存的劃分運(yùn)行時(shí)刻的存儲(chǔ)空間必須劃分以用來存放：生成的目標(biāo)代碼；數(shù)據(jù)目標(biāo)；用于保存過程活動(dòng)蹤跡的一個(gè)控制棧。存儲(chǔ)空間劃分的各部分：

目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆1.編譯后知道目標(biāo)代碼的大小。2.Pascal主程序中的數(shù)據(jù),c,FORTRAN3.棧:Pascal4.堆:Pascal112.2活動(dòng)記錄把過程的一個(gè)活動(dòng)所需要的信息組織成一塊連續(xù)的存儲(chǔ)單元，稱為活動(dòng)記錄。一個(gè)活動(dòng)所需要的信息的每個(gè)數(shù)據(jù)項(xiàng)有相同的生存期，因此，組織成一個(gè)活動(dòng)記錄是很自然的。對(duì)于Pascal語言來說，運(yùn)行過程中，當(dāng)調(diào)用一個(gè)過程時(shí)，在棧頂構(gòu)筑它的活動(dòng)記錄；當(dāng)這個(gè)過程的活動(dòng)執(zhí)行完后，把它從棧頂彈出。源語言不同，實(shí)現(xiàn)方法不同，組成活動(dòng)記錄的域不同。實(shí)現(xiàn)Pascal語言的活動(dòng)記錄的結(jié)構(gòu)如圖所示。臨時(shí)單元內(nèi)情向量局部向量形式單元靜態(tài)鏈動(dòng)態(tài)鏈返回地址連接數(shù)據(jù)SPTOP12連接數(shù)據(jù)：返回地址動(dòng)態(tài)鏈：指向調(diào)用該過程前的最新活動(dòng)記錄地址的指針。運(yùn)行時(shí)，使運(yùn)行棧上各數(shù)據(jù)區(qū)按動(dòng)態(tài)建立的次序結(jié)成鏈，鏈頭為棧頂起始位置。靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針，用來訪問非局部數(shù)據(jù)。形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元（如存放對(duì)表達(dá)式求值的結(jié)果）132.3存儲(chǔ)分配策略靜態(tài)分配策略：在編譯時(shí)對(duì)所有的數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，并且在運(yùn)行時(shí)始終保持不變。棧式動(dòng)態(tài)分配策略：在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，一旦退出，它所占的空間就予以釋放。堆式動(dòng)態(tài)分配策略：在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶可以對(duì)存儲(chǔ)空間進(jìn)行申請(qǐng)與歸還。14活動(dòng)樹程序執(zhí)行期間的控制流：程序執(zhí)行的控制是順序的；過程的每一次執(zhí)行都是從過程體的開頭開始，并最終把控制返回到緊接著該過程被調(diào)用點(diǎn)的后面。用一顆樹來描繪控制進(jìn)入和離開活動(dòng)的途徑。這樣的樹稱作活動(dòng)樹。在一棵活動(dòng)樹中：每一個(gè)結(jié)點(diǎn)代表一個(gè)過程的活動(dòng)；

根結(jié)點(diǎn)代表主程序的活動(dòng)；

代表a的結(jié)點(diǎn)是b結(jié)點(diǎn)的父結(jié)點(diǎn)當(dāng)且僅當(dāng)控制從活動(dòng)a進(jìn)入活動(dòng)b；結(jié)點(diǎn)a在結(jié)點(diǎn)b的左邊當(dāng)且僅當(dāng)a的生存期發(fā)生在b的生存期之前?？刂茥３绦驁?zhí)行的控制流對(duì)應(yīng)于從根開始，按先根次序遍歷活動(dòng)樹。因此，用一個(gè)棧保存過程活動(dòng)的生存蹤跡，把它稱作控制棧。當(dāng)一個(gè)活動(dòng)開始執(zhí)行時(shí)，把代表這個(gè)活動(dòng)的結(jié)點(diǎn)推進(jìn)棧；當(dāng)這個(gè)活動(dòng)結(jié)束時(shí)，把代表這個(gè)活動(dòng)的結(jié)點(diǎn)從棧中彈出。15srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)控制棧ssrsq(1.9)sq(1.9)p(1,9)sq(1.9)q(1,3)sq(1.9)q(1,3)p(1,3)sq(1.9)q(1,3)q(1,0)sq(1.9)q(1,3)q(2,3)活動(dòng)樹與控制棧

控制棧中的活動(dòng)都是活躍的，當(dāng)前控制進(jìn)入的活動(dòng)在棧頂，從棧頂活動(dòng)到棧底活動(dòng)的活動(dòng)序列是從活動(dòng)樹上當(dāng)前結(jié)點(diǎn)通向根的路徑上的結(jié)點(diǎn)序列：

s,q（1，9），q（l，3），q（2，3），從棧底活動(dòng)到棧頂活動(dòng)的活動(dòng)序列表示了活動(dòng)的生存期的嵌套關(guān)系。結(jié)論：擴(kuò)充控制?？捎脕韺?shí)現(xiàn)如Pascal語言的棧式存儲(chǔ)分配，進(jìn)入一個(gè)活動(dòng)，在棧頂建立這個(gè)活動(dòng)所使用的存儲(chǔ)空間；這個(gè)活動(dòng)結(jié)束，從棧頂彈出其使用的存儲(chǔ)空間。16本章教學(xué)線索1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)2運(yùn)行時(shí)存儲(chǔ)器的劃分3靜態(tài)存儲(chǔ)分配3.1靜態(tài)分配3.2FORTRAN的局部數(shù)據(jù)區(qū)3.3臨時(shí)變量的地址分配4簡(jiǎn)單棧式存儲(chǔ)分配5嵌套過程語言的棧式實(shí)現(xiàn)6堆式動(dòng)態(tài)存儲(chǔ)173.1靜態(tài)分配在編譯時(shí)就能夠確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能夠確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。適于靜態(tài)管理的語言必須滿足的條件：數(shù)組的上下界必須是常數(shù)過程調(diào)用不允許遞歸不允許用戶動(dòng)態(tài)地建立數(shù)據(jù)實(shí)體編譯程序可以確定出現(xiàn)在程序中的數(shù)據(jù)實(shí)體的地址（一般相對(duì)于各數(shù)據(jù)區(qū)基地址的偏移量)。由于過程調(diào)用不允許遞歸，數(shù)據(jù)實(shí)體的存儲(chǔ)地址就和過程相聯(lián)系，過程調(diào)用的活動(dòng)記錄就可以直接安排在目標(biāo)代碼之后，并把各數(shù)據(jù)項(xiàng)的存儲(chǔ)地址填入到相關(guān)的目標(biāo)代碼中，以便在運(yùn)行時(shí)訪問這些數(shù)據(jù)存儲(chǔ)空間。這里，不存在對(duì)存儲(chǔ)區(qū)域的再利用。目標(biāo)代碼運(yùn)行時(shí)不必進(jìn)行運(yùn)行時(shí)的存儲(chǔ)管理。183.2FORTRAN的局部數(shù)據(jù)區(qū)FORTRAN的編譯程序?qū)⒚總€(gè)程序段都定義對(duì)應(yīng)的局部數(shù)據(jù)區(qū)，每個(gè)數(shù)據(jù)區(qū)都有一個(gè)編號(hào)，在地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名將登記上它是屬于哪個(gè)數(shù)據(jù)區(qū)的，以及在該區(qū)中的相對(duì)位置（DA、ADDR）。一般情況下，程序段的局部數(shù)據(jù)區(qū)可以直接安排在該段程序的指令代碼之后，編譯時(shí)統(tǒng)計(jì)每個(gè)數(shù)據(jù)區(qū)的單元數(shù)，對(duì)于各區(qū)的首地址暫時(shí)不分配，在運(yùn)行前再用一個(gè)“裝入程序”（LOADER）把它們連成一個(gè)整體。FORTRAN的局部數(shù)據(jù)區(qū)內(nèi)容：臨時(shí)變量數(shù)組簡(jiǎn)單變量形式單元寄存器保護(hù)區(qū)返回地址稱為：隱參數(shù)返回地址：用來保存調(diào)用此程序段時(shí)的返回地址；寄存器保護(hù)區(qū)：用來保存調(diào)用段留在寄存器中的有關(guān)信息。形式單元：用來存放實(shí)在參數(shù)的地址或值。193.3臨時(shí)變量的地址分配

在三地址代碼－四元式生成中將產(chǎn)生大量的中間變量，在存儲(chǔ)空間的分配中也必須對(duì)這些臨時(shí)變量分配存儲(chǔ)空間。分配策略：如果兩個(gè)臨時(shí)變量名作用域不相交，則它們可以分配在同一單元中。一個(gè)臨時(shí)變量名自它第一次被定值（賦值）的地方起直至它最后一次被引用的地方止，這區(qū)間的程序所能到達(dá)的全體四元式構(gòu)成了它的作用域。令臨時(shí)變量名都分配在局部數(shù)據(jù)區(qū)中，若某一單元已分配給某些臨時(shí)變量名，則把這些名字的作用域（它們必須互不相交信息記錄）作為此單元的分配信息記錄下來。每當(dāng)要對(duì)一個(gè)新臨時(shí)變量名進(jìn)行分配時(shí)，首先求出此名的作用域，然后按序檢查每個(gè)已分配單元，一旦發(fā)現(xiàn)新求出的作用域與某個(gè)單元所記錄的全部作用域均不相交時(shí)就把這個(gè)單元分配給這個(gè)新名，同時(shí)把它的作用域也添加到該單元的分配信息之中。如果新臨時(shí)變量的作用域和所有已分配單元的作用域均有沖突，則就分配給它一個(gè)新的單元，同時(shí)把新名的作用域作為此單元的分配信息。20一般情況下，四元式中的臨時(shí)變量都是一邊生成，馬上使用，一次賦值，一次使用，其作用域類似于配對(duì)使用的括號(hào)。因此，可以用一個(gè)棧來放表達(dá)式計(jì)算過程中的中間結(jié)果。令k為棧的指示器，設(shè)它的初值是局部區(qū)中用來存放臨時(shí)變量值的區(qū)域首地址，每當(dāng)發(fā)現(xiàn)對(duì)一個(gè)新的臨時(shí)變量名Ti定值時(shí)，就用k的現(xiàn)行值作為Ti的地址，然后把k累增1。每當(dāng)引用了某個(gè)臨時(shí)變量名Ti作為操作數(shù)時(shí)（此時(shí)Ti的地址必已分配），就把指示器k的值遞減1。例子：P25421本章教學(xué)線索1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)2運(yùn)行時(shí)存儲(chǔ)器的劃分3靜態(tài)存儲(chǔ)分配4簡(jiǎn)單棧式存儲(chǔ)分配4.1語言要求4.2基于棧的存儲(chǔ)控制4.3同靜態(tài)存儲(chǔ)分配的區(qū)別4.4整體的分配情況4.5C語言的活動(dòng)記錄4.6C的過程調(diào)用、進(jìn)入、數(shù)據(jù)對(duì)象空間分配和過程返回5嵌套過程語言的棧式實(shí)現(xiàn)6堆式動(dòng)態(tài)存儲(chǔ)224簡(jiǎn)單棧式存儲(chǔ)分配基于控制棧的原理：

存儲(chǔ)空間被組織成棧，活動(dòng)記錄的推入和彈出分別對(duì)應(yīng)于活動(dòng)的開始和結(jié)束。與靜態(tài)分配不同的是，在每次活動(dòng)中把局部名字和新的存儲(chǔ)單元綁定，在活動(dòng)結(jié)束時(shí)，活動(dòng)記錄從棧中彈出，因而局部名字的存儲(chǔ)空間也隨之消失。確定活動(dòng)記錄中局部數(shù)據(jù)的地址：假設(shè)sp標(biāo)記一個(gè)活動(dòng)記錄的開始的位置，dx表示x的地址相對(duì)于sp的偏移量。那么，x在過程的目標(biāo)代碼中的地址可寫成dx（sp），在運(yùn)行時(shí)刻，當(dāng)把x的活動(dòng)記錄筑于棧頂時(shí)，寄存器sp被賦于實(shí)際的地址，sp可以是一個(gè)寄存器。23調(diào)用序列和返回序列

通過在目標(biāo)代碼中生成調(diào)用序列和返回序列實(shí)現(xiàn)過程的調(diào)用。激活一個(gè)過程的活動(dòng)是執(zhí)行過程語句的結(jié)果。過程語句：

p(e1，e2，……，en)的目標(biāo)代碼（調(diào)用序列）完成任務(wù)：1）調(diào)用者對(duì)實(shí)在參數(shù)求值，并把它們傳送給被調(diào)用過程的活動(dòng)記錄的參數(shù)域。2）調(diào)用者在被調(diào)用者的活動(dòng)記錄中存放返回地址和老sp之值。之后調(diào)用者把sp之值增加到top的下一個(gè)存儲(chǔ)單元位置（被調(diào)用者的活動(dòng)記錄首地址）。3）被調(diào)用者存放寄存器值和其它狀態(tài)信息。4）被調(diào)用者初始化其局部數(shù)據(jù)并開始執(zhí)行。返回序列，return目標(biāo)代碼完成的任務(wù)是：被調(diào)用者在自己的活動(dòng)記錄的返回值域中放一個(gè)返回值。利用狀態(tài)域中的信息，被調(diào)用者恢復(fù)sp和其它寄存器，并且按返回地址轉(zhuǎn)移到調(diào)用者的代碼之中。調(diào)用者復(fù)制返回值到自己的活動(dòng)記錄中。任務(wù)的劃分，根據(jù)源語言、目標(biāo)機(jī)器和操作系統(tǒng)等具體情況而定。上述任務(wù)，由運(yùn)行支持子程序完成，可視為虛擬機(jī)指令。244.1語言要求過程不允許嵌套，但允許過程遞歸調(diào)用，如C語言。254.2基于棧的存儲(chǔ)控制將存儲(chǔ)組織成一個(gè)棧，過程的活動(dòng)記錄作為一個(gè)元素進(jìn)行出入棧管理。運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程時(shí)，就把它的活動(dòng)記錄入棧，而形成該過程工作時(shí)的數(shù)據(jù)區(qū)，當(dāng)該活動(dòng)結(jié)束時(shí)，再出棧。264.3同靜態(tài)存儲(chǔ)分配的區(qū)別不同的是：每次活動(dòng)過程中，局部名字與新的存儲(chǔ)單元綁定，活動(dòng)結(jié)束后，活動(dòng)記錄從棧中彈出，局部名的存儲(chǔ)空間也隨之消失。注意：1）因而會(huì)出現(xiàn)同一過程的不同活動(dòng)（不同時(shí)期）存儲(chǔ)空間的分配不一樣

2）由于遞歸，過程的活動(dòng)可能有多個(gè)同時(shí)在棧中（活動(dòng)記錄）27

4.4整體的分配情況

R的活動(dòng)記錄Q的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)區(qū)TopSP程序運(yùn)行時(shí)的某一時(shí)刻，表明主過程Main調(diào)用Q，而Q又調(diào)用R。SP：總是指向現(xiàn)行過程活動(dòng)記錄的起點(diǎn)，用于訪問局部數(shù)據(jù)；Top：總是指向（已占用）棧頂單元。284.5C語言的活動(dòng)記錄1）連接數(shù)據(jù)：老SP、返回地址2）參數(shù)個(gè)數(shù)3）形式單元4）過程的局部變量、數(shù)組內(nèi)情向量、臨時(shí)工作單元注意：C語言的非局部變量?jī)H能出現(xiàn)在源程序頭，非局部變量可采用靜態(tài)存儲(chǔ)分配5）局部變量（形參）的訪問： 在編譯時(shí)，對(duì)局部變量和形參都分配了存儲(chǔ)單元，其地址為相對(duì)于活動(dòng)記錄基地址SP的偏移量。則其絕對(duì)地址就為：

絕對(duì)地址=活動(dòng)記錄基地址+相對(duì)地址

臨時(shí)工作單元內(nèi)情向量簡(jiǎn)單變量形式單元參數(shù)個(gè)數(shù)返回地址老SPSPTOP294.6C的過程調(diào)用、進(jìn)入、數(shù)據(jù)對(duì)象空間分配和過程返回1）調(diào)用：將實(shí)參的地址或值傳遞給新的活動(dòng)記錄中的形式單元。 過程調(diào)用的四元式：paramT1paramT2……paramTncallP，n由于形式單元在活動(dòng)記錄中的起始位置是固定的，因此對(duì)于每一個(gè)形式參數(shù)paramTi，可以翻譯為如下指令：（i+3）[TOP]=Ti

（傳參數(shù)值）（i+3）[TOP]=addr（Ti）（傳參數(shù)地址）2）過程進(jìn)入四元式：CALLP，n的翻譯：

1[TOP]=SP（保護(hù)現(xiàn)行的SP，即老SP）

3[TOP]=n（傳遞參數(shù)個(gè)數(shù)）

JSRP（轉(zhuǎn)子指令，轉(zhuǎn)向P的第一條指令）303）數(shù)據(jù)對(duì)象空間分配

SP=TOP+1（定義新的SP）

1[SP]=返回地址（保護(hù)返回地址）

TOP=TOP+L定義新的TOP

（L為過程P的活動(dòng)記錄所需的單元數(shù)，在處理說明語句時(shí)可以計(jì)算出來）4）過程的返回（過程的活動(dòng)記錄出棧，同時(shí)恢復(fù)棧頂活動(dòng)記錄的TOP和SP）如果有返回值（函數(shù)），將返回值傳遞到每個(gè)特定寄存器中。

TOP=SP–1SP=0[SP]x=2[TOP]UJ0[x]（UJ為無條件轉(zhuǎn)移語句，按x中的返回地址實(shí)行變址轉(zhuǎn)移）31本章教學(xué)線索1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)2運(yùn)行時(shí)存儲(chǔ)器的劃分3靜態(tài)存儲(chǔ)分配4簡(jiǎn)單棧式存儲(chǔ)分配5嵌套過程語言的棧式實(shí)現(xiàn)5.1嵌套過程語言非局部名字訪問的實(shí)現(xiàn)5.2參數(shù)傳遞的實(shí)現(xiàn)6堆式動(dòng)態(tài)存儲(chǔ)325嵌套過程語言的棧式實(shí)現(xiàn)語言要求：過程不僅允許遞歸調(diào)用，還允許過程進(jìn)行嵌套定義。存儲(chǔ)分配的實(shí)現(xiàn)：采用棧式存儲(chǔ)分配，對(duì)于運(yùn)行時(shí)的局部名和形參完全可以采用簡(jiǎn)單棧式存儲(chǔ)分配，由于允許過程嵌套定義，因此對(duì)非局部變量的訪問需要單獨(dú)處理，可以采用:靜態(tài)鏈或顯示表（Display）來實(shí)現(xiàn)。嵌套層次：記錄過程在定義時(shí)所在的層數(shù)。約定主程序的層數(shù)為0。如果過程P的直接外層Q的層數(shù)為i，則P的層數(shù)就為i+1。在實(shí)現(xiàn)時(shí)，采用一個(gè)計(jì)數(shù)器，遇到過程定義procBegin時(shí)，計(jì)數(shù)器增加1，遇到過程結(jié)束procend時(shí)，計(jì)數(shù)器減1。將過程的層數(shù)作為過程名的一個(gè)屬性記錄在符號(hào)表中。335.1嵌套過程語言非局部名字訪問的實(shí)現(xiàn)1）靜態(tài)鏈和活動(dòng)記錄在活動(dòng)記錄中增加一個(gè)域，存儲(chǔ)指向直接外層的最新活動(dòng)記錄的地址，這樣形成的鏈稱為靜態(tài)鏈。它表明過程定義時(shí)的嵌套關(guān)系?；顒?dòng)記錄中存儲(chǔ)老SP形成的鏈稱為動(dòng)態(tài)鏈，它表明了過程活動(dòng)時(shí)的調(diào)用關(guān)系?；顒?dòng)記錄的結(jié)構(gòu)：臨時(shí)單元內(nèi)情向量簡(jiǎn)單變量形式單元形參個(gè)數(shù)靜態(tài)鏈返回地址動(dòng)態(tài)鏈（老SP）SPTOP對(duì)于非局部變量的返回可以沿靜態(tài)鏈進(jìn)行訪問。34programP;vara,xinteger;procedureQ(b:integer);vari:integer;procedureR(u:integer,v:integer);varc,d:integer;beginifu=1thenR(u+1,v)v=(a+c)*(b-d);end{R}beginR(1,x);end{Q}procedureS;varc,i:integer;begina=1;Q(c);end{S}begina=0;S;end011224d23c22v（形參）21u（形參）202(形參個(gè)數(shù)）191118返回地址171116i15b(形參）141(形參個(gè)數(shù)）13012返回地址11510i9c80706返回地址504x3a201返回地址00PSQR過程Q調(diào)用R時(shí)活動(dòng)記錄情況352）嵌套層次顯示表和活動(dòng)記錄在進(jìn)入一個(gè)過程后，在建立其活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次表display，該表給出了過程的嵌套關(guān)系，如果該過程的嵌套層次為i，則它的display表就包含i+1個(gè)單元（假設(shè)主過程的層次為0），display本身是一個(gè)棧。由于過程的層數(shù)可以靜態(tài)確定，因此每個(gè)過程的display表的體積在編譯時(shí)可以確定，可以將display表作為活動(dòng)記錄的一部分，置于形式單元的上端。例如：R的外層是Q，Q的外層是P，則R運(yùn)行時(shí)display表的情況：R現(xiàn)行活動(dòng)記錄地址Q的最新活動(dòng)記錄地址P的活動(dòng)記錄地址36對(duì)于非局部變量的絕對(duì)地址就為：

絕對(duì)地址=display[靜態(tài)層次]+相對(duì)地址（非局部變量所在的靜態(tài)層次可以在編譯時(shí)處理說明語句時(shí)確定，可以記錄在符號(hào)表中）在活動(dòng)記錄中，display表的相對(duì)位置d是確定的，因此，在現(xiàn)行過程中引用了某一外層過程（k層）的變量x，可以用以下指令獲取x的值：LDR1，（d+k）[SP]/*獲取x所在的最新活動(dòng)記錄的SP值*/LDR2，x[R1]/*變址取數(shù)，把X的值傳遞給R2*/臨時(shí)單元內(nèi)情向量簡(jiǎn)單變量Display形參參數(shù)個(gè)數(shù)全局display返回地址老SP(動(dòng)態(tài)鏈）SPTOP全局display：連接數(shù)據(jù)，用于記住調(diào)用過程的display表的地址，作為生成本過程display的關(guān)鍵參數(shù)。display根據(jù)全局display所指示的地址，從調(diào)用它的過程中的display表中抄入i個(gè)地址（假設(shè)該過程層數(shù)為i），然后將自己的起始地址放在display表頂。37programP;vara,xinteger;procedureQ(b:integer);vari:integer;procedureR(u:integer,v:integer);varc,d:integer;beginifu=1thenR(u+1,v)v=(a+c)*(b-d);end{R}beginR(1,x);end{Q}procedureS;varc,i:integer;begina=1;Q(c);end{S}begina=0;S;end0112191318017b（形參）161（形參個(gè)數(shù)）159(全局display）14返回地址13512i11c105908072（全局display)6返回地址504x3a201返回地址00displaydisplaydisplayS調(diào)用Q時(shí)PSQ385.2參數(shù)傳遞的實(shí)現(xiàn)ParT，T為數(shù)組根據(jù)不同語言的要求或傳遞數(shù)組T的首地址，或傳送它的內(nèi)情向量地址。ParT，T為過程一般需要傳遞過程T的入口地址和現(xiàn)行的display地址。ParT，T為標(biāo)號(hào)一般需要傳遞標(biāo)號(hào)T的地址和標(biāo)號(hào)定義所在過程的活動(dòng)記錄首地址。ParT，T為形式參數(shù)傳遞形式單元T的內(nèi)容。39本章教學(xué)線索1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)2運(yùn)行時(shí)存儲(chǔ)器的劃分3靜態(tài)存儲(chǔ)分配4簡(jiǎn)單棧式存儲(chǔ)分配5嵌套過程語言的棧式實(shí)現(xiàn)6堆式動(dòng)態(tài)存儲(chǔ)6.1堆式分配的必要性（以C語言為例）6.2

堆式存儲(chǔ)管理的實(shí)現(xiàn)6.3

減少碎片的技術(shù)6.4

空間的釋放406堆式動(dòng)態(tài)存儲(chǔ)對(duì)于允許程序?yàn)樽兞吭谶\(yùn)行時(shí)動(dòng)態(tài)申請(qǐng)和釋放存儲(chǔ)空間的語言，采用堆式分配是最有效的解決方案。堆式分配的基本思想是，為運(yùn)行的程序劃出適當(dāng)大的空間(稱為堆Heap)，每當(dāng)程序申請(qǐng)空間時(shí)，就從堆的空閑區(qū)找出一塊空間分配給程序，每當(dāng)釋放時(shí)則回收。416.1

堆式分配的必要性（以C語言為例）在C中處理鏈表等結(jié)構(gòu)時(shí),常常隨機(jī)地插入或刪除一些結(jié)點(diǎn),利用指針變量和結(jié)構(gòu)類型,可動(dòng)態(tài)地生成新結(jié)點(diǎn)(使用malloc()函數(shù)),或刪除之(使用free()函數(shù)).例如structnode{chardata;structnode*next;}；定義了鏈表的結(jié)點(diǎn)，下面函數(shù)可在表的尾部添加新結(jié)點(diǎn):voidAppend(structnode*head,charch){structnode*p=head;while((p->next)!=NULL)p=p->next;p->next=malloc(sizeof(structnode));p->next->data=ch;p->next->next=NULL;}還可用下面的函數(shù)在表頭刪除一結(jié)點(diǎn):voidDelete(structnode*head){structnode*p=head;if(p!=NULL){head=head->next;free(p);}}426.2

堆式存儲(chǔ)管理的實(shí)現(xiàn)1定長塊管理

堆式動(dòng)態(tài)儲(chǔ)分配最簡(jiǎn)單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針available指向鏈