編譯原理第九章

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

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

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

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

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

程序運行environmentstateL-valueR-value從名字到值的兩個階段映射名字

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

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

根結(jié)點代表主程序的活動；

代表a的結(jié)點是b結(jié)點的父結(jié)點當(dāng)且僅當(dāng)控制從活動a進入活動b；結(jié)點a在結(jié)點b的左邊當(dāng)且僅當(dāng)a的生存期發(fā)生在b的生存期之前?？刂茥３绦驁?zhí)行的控制流對應(yīng)于從根開始，按先根次序遍歷活動樹。因此，用一個棧保存過程活動的生存蹤跡，把它稱作控制棧。當(dāng)一個活動開始執(zhí)行時，把代表這個活動的結(jié)點推進棧；當(dāng)這個活動結(jié)束時，把代表這個活動的結(jié)點從棧中彈出。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)前結(jié)點通向根的路徑上的結(jié)點序列：

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

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

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

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

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

2）由于遞歸，過程的活動可能有多個同時在棧中（活動記錄）27

4.4整體的分配情況

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

絕對地址=活動記錄基地址+相對地址

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

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

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

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

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

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

1[SP]=返回地址（保護返回地址）

TOP=TOP+L定義新的TOP

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

TOP=SP–1SP=0[SP]x=2[TOP]UJ0[x]（UJ為無條件轉(zhuǎn)移語句，按x中的返回地址實行變址轉(zhuǎn)移）31本章教學(xué)線索1目標(biāo)程序運行時的活動2運行時存儲器的劃分3靜態(tài)存儲分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)5.1嵌套過程語言非局部名字訪問的實現(xiàn)5.2參數(shù)傳遞的實現(xiàn)6堆式動態(tài)存儲325嵌套過程語言的棧式實現(xiàn)語言要求：過程不僅允許遞歸調(diào)用，還允許過程進行嵌套定義。存儲分配的實現(xiàn)：采用棧式存儲分配，對于運行時的局部名和形參完全可以采用簡單棧式存儲分配，由于允許過程嵌套定義，因此對非局部變量的訪問需要單獨處理，可以采用:靜態(tài)鏈或顯示表（Display）來實現(xiàn)。嵌套層次：記錄過程在定義時所在的層數(shù)。約定主程序的層數(shù)為0。如果過程P的直接外層Q的層數(shù)為i，則P的層數(shù)就為i+1。在實現(xiàn)時，采用一個計數(shù)器，遇到過程定義procBegin時，計數(shù)器增加1，遇到過程結(jié)束procend時，計數(shù)器減1。將過程的層數(shù)作為過程名的一個屬性記錄在符號表中。335.1嵌套過程語言非局部名字訪問的實現(xiàn)1）靜態(tài)鏈和活動記錄在活動記錄中增加一個域，存儲指向直接外層的最新活動記錄的地址，這樣形成的鏈稱為靜態(tài)鏈。它表明過程定義時的嵌套關(guān)系?；顒佑涗浿写鎯蟂P形成的鏈稱為動態(tài)鏈，它表明了過程活動時的調(diào)用關(guān)系。活動記錄的結(jié)構(gòu)：臨時單元內(nèi)情向量簡單變量形式單元形參個數(shù)靜態(tài)鏈返回地址動態(tài)鏈（老SP）SPTOP對于非局部變量的返回可以沿靜態(tài)鏈進行訪問。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(形參個數(shù)）191118返回地址171116i15b(形參）141(形參個數(shù)）13012返回地址11510i9c80706返回地址504x3a201返回地址00PSQR過程Q調(diào)用R時活動記錄情況352）嵌套層次顯示表和活動記錄在進入一個過程后，在建立其活動記錄區(qū)的同時建立一張嵌套層次表display，該表給出了過程的嵌套關(guān)系，如果該過程的嵌套層次為i，則它的display表就包含i+1個單元（假設(shè)主過程的層次為0），display本身是一個棧。由于過程的層數(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的值：LDR1，（d+k）[SP]/*獲取x所在的最新活動記錄的SP值*/LDR2，x[R1]/*變址取數(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表頂。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（形參個數(shù)）159(全局display）14返回地址13512i11c105908072（全局display)6返回地址504x3a201返回地址00displaydisplaydisplayS調(diào)用Q時PSQ385.2參數(shù)傳遞的實現(xiàn)ParT，T為數(shù)組根據(jù)不同語言的要求或傳遞數(shù)組T的首地址，或傳送它的內(nèi)情向量地址。ParT，T為過程一般需要傳遞過程T的入口地址和現(xiàn)行的display地址。ParT，T為標(biāo)號一般需要傳遞標(biāo)號T的地址和標(biāo)號定義所在過程的活動記錄首地址。ParT，T為形式參數(shù)傳遞形式單元T的內(nèi)容。39本章教學(xué)線索1目標(biāo)程序運行時的活動2運行時存儲器的劃分3靜態(tài)存儲分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)6堆式動態(tài)存儲6.1堆式分配的必要性（以C語言為例）6.2

堆式存儲管理的實現(xiàn)6.3

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

空間的釋放406堆式動態(tài)存儲對于允許程序為變量在運行時動態(tài)申請和釋放存儲空間的語言，采用堆式分配是最有效的解決方案。堆式分配的基本思想是，為運行的程序劃出適當(dāng)大的空間(稱為堆Heap)，每當(dāng)程序申請空間時，就從堆的空閑區(qū)找出一塊空間分配給程序，每當(dāng)釋放時則回收。416.1

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

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

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