編譯原理運(yùn)行時(shí)存儲(chǔ)空間組織

編譯原理運(yùn)行時(shí)存儲(chǔ)空間組織第一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五6.1靜態(tài)存儲(chǔ)分配如果在編譯時(shí)就能夠確定一個(gè)程序在運(yùn)行時(shí)所需的存儲(chǔ)空間大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址，存儲(chǔ)空間的這種分配方法叫做靜態(tài)分配。第二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五對(duì)FORTRAN語(yǔ)言來(lái)說(shuō)，其特點(diǎn)是不允許過(guò)程有遞歸性，每個(gè)數(shù)據(jù)名所需的存儲(chǔ)空間大小都是常量(即不允許含可變體積的數(shù)據(jù)，如可變數(shù)組)，并且所有數(shù)據(jù)名的性質(zhì)是完全確定的(不允許出現(xiàn)在運(yùn)行時(shí)再動(dòng)態(tài)確定其性質(zhì)的名字這種情況)。這些特點(diǎn)確保整個(gè)程序所需數(shù)據(jù)空間的總量在編譯時(shí)是完全確定的，從而每個(gè)數(shù)據(jù)名的地址就可靜態(tài)地進(jìn)行分配。靜態(tài)存儲(chǔ)分配是一種最簡(jiǎn)單的存儲(chǔ)管理。一般而言，適于靜態(tài)存儲(chǔ)分配的語(yǔ)言必須滿足以下條件：第三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五(1)數(shù)組的上下界必須是常數(shù)；(2)過(guò)程調(diào)用不允許遞歸；(3)不允許采用動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)(即在程序運(yùn)行過(guò)程中申請(qǐng)和釋放的數(shù)據(jù)結(jié)構(gòu))。第四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五滿足這些條件的語(yǔ)言除了FORTRAN之外，還有BASIC等語(yǔ)言。在這些語(yǔ)言中，編譯程序可以完全確定程序中數(shù)據(jù)項(xiàng)所在的地址(通常為相對(duì)于各數(shù)據(jù)區(qū)起始地址的位移量)。由于過(guò)程調(diào)用不允許遞歸，因此數(shù)據(jù)項(xiàng)的存儲(chǔ)地址就與過(guò)程相聯(lián)系。過(guò)程調(diào)用所使用的局部數(shù)據(jù)區(qū)可以直接安排在過(guò)程的目標(biāo)代碼之后，并把各數(shù)據(jù)項(xiàng)的存儲(chǔ)地址填入相關(guān)的目標(biāo)代碼中，以便在過(guò)程運(yùn)行時(shí)訪問(wèn)這個(gè)局部數(shù)據(jù)區(qū)。在此，不存在對(duì)存儲(chǔ)區(qū)的再利用問(wèn)題；目標(biāo)程序執(zhí)行時(shí)不必進(jìn)行運(yùn)行時(shí)的存儲(chǔ)空間管理，過(guò)程的進(jìn)入和退出變得極為簡(jiǎn)單。第五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

FORTRAN語(yǔ)言的靜態(tài)存儲(chǔ)管理特點(diǎn)是FORTRAN程序中的各程序段均可獨(dú)立地進(jìn)行編譯。在編譯過(guò)程中，給程序中的變量或數(shù)組分配存儲(chǔ)單元的一般做法是：為每一個(gè)變量(或數(shù)組)確定一個(gè)有序的整數(shù)對(duì)；其中，第一個(gè)整數(shù)用來(lái)指示數(shù)據(jù)區(qū)(局部數(shù)據(jù)區(qū)或公用區(qū))的編號(hào)，第二個(gè)整數(shù)則用來(lái)指明該變量(或數(shù)組)所對(duì)應(yīng)的存儲(chǔ)起始單元相對(duì)于其所在數(shù)據(jù)區(qū)起點(diǎn)的位移(即相對(duì)于數(shù)據(jù)區(qū)起點(diǎn)的地址)；并將這一對(duì)整數(shù)填入符號(hào)表相應(yīng)登記項(xiàng)的信息欄中。至于各數(shù)據(jù)區(qū)的起始地址在編譯時(shí)可暫不確定，待各程序段全部編譯完成之后，再由連接裝配程序最終確定，并將各程序段的目標(biāo)代碼組裝成一個(gè)完整的目標(biāo)程序。第六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五一個(gè)FORTRAN程序段的局部數(shù)據(jù)區(qū)可由圖6–1所示的項(xiàng)目組成。其中，隱參數(shù)是指過(guò)程調(diào)用時(shí)的連接信息(不在源程序中明顯出現(xiàn))，如調(diào)用時(shí)的返回地址、調(diào)用時(shí)寄存器的保護(hù)等；形式單元用來(lái)存放過(guò)程調(diào)用時(shí)形參與實(shí)參結(jié)合的實(shí)參地址或值。第七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–1一個(gè)FORTRAN程序段的局部數(shù)據(jù)區(qū)第八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五6.2簡(jiǎn)單的棧式存儲(chǔ)分配我們首先考慮一種簡(jiǎn)單程序語(yǔ)言的實(shí)現(xiàn)，這種語(yǔ)言沒(méi)有分程序結(jié)構(gòu)，過(guò)程定義不允許嵌套，但允許過(guò)程的遞歸調(diào)用，允許過(guò)程含有可變數(shù)組。例如，C語(yǔ)言除不允許含有可變數(shù)組外，就是這樣一種語(yǔ)言。C語(yǔ)言的程序結(jié)構(gòu)如下：第九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五全局?jǐn)?shù)據(jù)說(shuō)明main(?){main中的數(shù)據(jù)說(shuō)明}voidR(?){R中的數(shù)據(jù)說(shuō)明}第十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五voidQ(){Q中的數(shù)據(jù)說(shuō)明}第十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五例如，下面計(jì)算n！的C語(yǔ)言程序就是一個(gè)遞歸調(diào)用的程序，它的執(zhí)行過(guò)程可以用棧來(lái)實(shí)現(xiàn)。#include“stdio.h”longfactorial(intn){if(n>1)return(n*factorial(n?1));elsereturn(1);}第十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五main(?){intnum;do{scanf(“%d”,&num);if(num>=0&&num<15)printf(“%d\n”,factorial(num));elseprintf(“error!\n”);}while(num>=0);}第十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.2.1棧式存儲(chǔ)分配與活動(dòng)記錄使用棧式存儲(chǔ)分配法意味著程序運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過(guò)程(或函數(shù))就有一個(gè)相應(yīng)的活動(dòng)記錄累筑于棧頂，此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等；在進(jìn)入過(guò)程和執(zhí)行過(guò)程的可執(zhí)行語(yǔ)句之前，再把局部數(shù)組所需空間累筑于棧頂，從而形成過(guò)程工作時(shí)的完整數(shù)據(jù)區(qū)。第十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五注意，每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可以靜態(tài)地確定。但由于允許含有可變數(shù)組，所以數(shù)組的大小只有在運(yùn)行時(shí)才能知道。因數(shù)組區(qū)的大小不能預(yù)先獲知，為了擴(kuò)充方便，所以只能將數(shù)組區(qū)累筑于活動(dòng)記錄之上的當(dāng)前棧頂。當(dāng)一個(gè)過(guò)程工作完畢返回時(shí)，它在棧頂?shù)臄?shù)據(jù)區(qū)(包括活動(dòng)記錄和數(shù)組區(qū))也隨即不復(fù)存在。第十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五對(duì)C語(yǔ)言來(lái)說(shuō)，由于其不含可變數(shù)組，因而它的活動(dòng)記錄本身包含了局部數(shù)組的空間。圖6–2和圖6–3分別給出了C語(yǔ)言和含可變數(shù)組的某簡(jiǎn)單語(yǔ)言程序運(yùn)行時(shí)的數(shù)據(jù)空間結(jié)構(gòu)，即顯示了主程序在調(diào)用了過(guò)程Q，Q又調(diào)用了過(guò)程R，且在R投入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)。

SP指示器總是指向執(zhí)行過(guò)程活動(dòng)記錄的起點(diǎn)，而TOP指示器則始終指向(已占用)棧頂單元。當(dāng)進(jìn)入一個(gè)過(guò)程時(shí)，TOP指向?yàn)榇诉^(guò)程創(chuàng)建的活動(dòng)記錄的頂端；在分配數(shù)組區(qū)之后(如果有的話)，TOP又改為指向數(shù)組區(qū)(從而是該過(guò)程整個(gè)數(shù)據(jù)區(qū))的頂端。第十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–2C語(yǔ)言程序的存儲(chǔ)組織第十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–3含可變數(shù)組程序的存儲(chǔ)組織第十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

C的活動(dòng)記錄含有以下幾個(gè)區(qū)段(如圖6–4所示)：

(1)連接數(shù)據(jù)(兩項(xiàng))：老SP值(即前一活動(dòng)記錄的起始地址)和返回地址；

(2)參數(shù)個(gè)數(shù)；

(3)形式單元(存放實(shí)在參數(shù)的值或地址)；

(4)過(guò)程的局部變量(簡(jiǎn)單變量)、數(shù)組的內(nèi)情向量和臨時(shí)工作單元。第十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–4C過(guò)程的活動(dòng)記錄第二十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

C語(yǔ)言不允許過(guò)程(函數(shù))嵌套，也即不允許一個(gè)過(guò)程的定義出現(xiàn)在另一個(gè)過(guò)程的定義之內(nèi)。因此，C語(yǔ)言的非局部變量?jī)H能出現(xiàn)在源程序頭，非局部變量可采用靜態(tài)存儲(chǔ)分配并在編譯時(shí)確定它們的地址。由圖6–4可知，過(guò)程的每一局部變量或形參在活動(dòng)記錄中的位置都是確定的；也就是說(shuō)，這些變量或形參所分配的存儲(chǔ)單元其地址都是相對(duì)于活動(dòng)記錄的基址SP的。因此，變量和形參運(yùn)行時(shí)在棧上的絕對(duì)地址是：絕對(duì)地址=活動(dòng)記錄基址(SP)+相對(duì)地址第二十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五于是，對(duì)當(dāng)前正在執(zhí)行(即活動(dòng))的過(guò)程，其任何局部變量或形參X的引用均可表示為變址訪問(wèn)X[SP]。此處X代表X相對(duì)于活動(dòng)記錄基址的偏移量，這個(gè)偏移量(即相對(duì)數(shù))在編譯時(shí)可完全確定下來(lái)。過(guò)程的局部數(shù)組的內(nèi)情向量的相對(duì)地址在編譯時(shí)也同樣可完全確定下來(lái)，一旦數(shù)據(jù)空間在過(guò)程里獲得分配后，對(duì)數(shù)組元素的引用也就容易用變址的方式進(jìn)行訪問(wèn)。第二十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.2.2過(guò)程的執(zhí)行1．過(guò)程調(diào)用過(guò)程調(diào)用的四元式序列為：

parT1parT2

parTncallP,n第二十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五由于此時(shí)TOP是指向被調(diào)用過(guò)程P之前的棧頂，而P的形式單元和活動(dòng)記錄起點(diǎn)之間的距離是確定的(等于3，參見(jiàn)圖6–4)，因而由調(diào)用者過(guò)程給將要調(diào)用的過(guò)程P的活動(dòng)記錄(正在形成中)的形式單元傳遞實(shí)參值或?qū)崊⒌刂?，即每個(gè)parTi(i=1,2,…,n)可直接翻譯成如下指令：

(i+3)[TOP]=Ti

/*傳遞參數(shù)值*/

或(i+3)[TOP]=addr[Ti] /*傳遞參數(shù)地址*/第二十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五而四元式callP,n則翻譯成：

1[TOP]=SP/*保護(hù)現(xiàn)行SP*/3[TOP]=n /*傳遞參數(shù)個(gè)數(shù)*/JSRP /*轉(zhuǎn)子指令，轉(zhuǎn)向P過(guò)程的第一條指令*/過(guò)程P調(diào)用之前，先構(gòu)造出P的活動(dòng)記錄部分內(nèi)容，見(jiàn)圖6–5所示。第二十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–5過(guò)程P調(diào)用前先構(gòu)造P的活動(dòng)記錄部分內(nèi)容第二十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

2．過(guò)程進(jìn)入轉(zhuǎn)入過(guò)程P后，首先要做的工作是定義新活動(dòng)記錄的SP，保護(hù)返回地址和定義新活動(dòng)記錄的TOP值，即執(zhí)行下述指令：

SP=TOP+1/*定義新SP*/1[SP]=返回地址/*保護(hù)返回地址*/TOP=TOP+L/*定義新TOP*/

其中，L是過(guò)程P的活動(dòng)記錄所需的單元數(shù)，這個(gè)數(shù)在編譯時(shí)可靜態(tài)地計(jì)算出來(lái)。第二十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五對(duì)含可變數(shù)組(非C語(yǔ)言)的情況來(lái)說(shuō)，因?yàn)檫^(guò)程可含可變數(shù)組且所有數(shù)組都分配在活動(dòng)記錄的頂上，所以緊接上述指令之后應(yīng)是對(duì)數(shù)組進(jìn)行存儲(chǔ)分配的指令(如果含有局部數(shù)組)，這些指令是在翻譯數(shù)組說(shuō)明時(shí)產(chǎn)生的。對(duì)每個(gè)數(shù)組說(shuō)明，相應(yīng)的目標(biāo)指令組將做以下幾件工作：

(1)計(jì)算各維的上、下限；

(2)調(diào)用數(shù)組空間分配子程序，其參數(shù)是各維的上、下限和內(nèi)情向量單元首地址。第二十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五數(shù)組空間分配子程序計(jì)算并填好內(nèi)情向量的所有信息，然后在TOP所指的位置之上留出數(shù)組所需的空間，并將TOP調(diào)整為指向數(shù)組區(qū)的頂端。?進(jìn)入過(guò)程P后所做的工作如圖6–6所示。此后，在過(guò)程段執(zhí)行語(yǔ)句的工作過(guò)程中，凡引用形式參數(shù)、局部變量或數(shù)組元素都將以SP為基址進(jìn)行相對(duì)訪問(wèn)。第二十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–6進(jìn)入過(guò)程P后所做的工作示意第三十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

3．過(guò)程返回

C語(yǔ)言以及其它一些相似的語(yǔ)言含有return(E)形式的返回語(yǔ)句，其中E為表達(dá)式。假定E值已計(jì)算出來(lái)并存放在某臨時(shí)單元T中，則此時(shí)即可將T值傳送到某個(gè)特定的寄存器中(調(diào)用過(guò)程將從這個(gè)特定的寄存器中獲得被調(diào)用過(guò)程P的結(jié)果)。剩下的工作就是恢復(fù)SP和TOP為進(jìn)入過(guò)程P之前的原值(即指向調(diào)用過(guò)程的活動(dòng)記錄及工作空間)，并按返回地址實(shí)行無(wú)條件轉(zhuǎn)移，即執(zhí)行下述指令序列：第三十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

TOP=SP–1 /*恢復(fù)調(diào)用過(guò)程的TOP值*/SP=0[SP] /*恢復(fù)調(diào)用過(guò)程的SP值*/X=2[TOP] /*將返回地址送X*/UJ0[X] /*無(wú)條件轉(zhuǎn)移，即按X的地址返回到調(diào)用過(guò)程*/

一個(gè)過(guò)程也可通過(guò)它的end語(yǔ)句(對(duì)C語(yǔ)言則是該過(guò)程(函數(shù))體結(jié)束時(shí)的“}”)自動(dòng)返回。如果此過(guò)程是一個(gè)函數(shù)過(guò)程，則按上述辦法傳遞結(jié)果值，否則僅直接執(zhí)行上述返回指令序列。過(guò)程P的返回示意如圖6–7所示。第三十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–7過(guò)程P的返回示意第三十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五6.3嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)在簡(jiǎn)單程序語(yǔ)言實(shí)現(xiàn)中是允許過(guò)程的遞歸調(diào)用的，并且過(guò)程中可含有可變數(shù)組。現(xiàn)在，我們?cè)偌由弦环N功能，即允許過(guò)程的嵌套性。從結(jié)構(gòu)上看，PASCAL就是這樣的一種語(yǔ)言；但由于PASCAL含有“文件”和“動(dòng)態(tài)變量”，因此，它的存儲(chǔ)分配不能簡(jiǎn)單地用棧式方法來(lái)實(shí)現(xiàn)。采用PASCAL的一個(gè)子集，例如去掉“文件”和“動(dòng)態(tài)變量”這種數(shù)據(jù)類型，那就可以用我們下面將要討論的方法實(shí)現(xiàn)存儲(chǔ)分配。第三十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.3.1嵌套層次顯示表(DISPLAY)和活動(dòng)記錄在討論中，常常要用到過(guò)程定義的“嵌套層次”(簡(jiǎn)稱層數(shù))這個(gè)概念。我們始終假定主程序的層數(shù)為0，因此主程序稱為第0層過(guò)程。如果過(guò)程Q是在層數(shù)為i的過(guò)程P內(nèi)定義的，并且P是包圍Q的最小過(guò)程，則Q的層數(shù)就為i+1。當(dāng)編譯程序處理過(guò)程說(shuō)明時(shí)，過(guò)程的層數(shù)將作為過(guò)程名的一個(gè)重要屬性登記在符號(hào)表中。第三十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五由于過(guò)程定義是嵌套的，因而一個(gè)過(guò)程可以引用包圍它的任一外層過(guò)程所定義的變量或數(shù)組。也就是說(shuō)，運(yùn)行時(shí)，一個(gè)過(guò)程Q可能引用它的任一外層過(guò)程P的最新活動(dòng)記錄中的某些數(shù)據(jù)。因此，過(guò)程Q運(yùn)行時(shí)必須知道它的所有外層的最新活動(dòng)記錄的地址。由于允許遞歸和可變數(shù)組的存在，過(guò)程的活動(dòng)記錄位置(即使是相對(duì)位置)也往往是變遷的，因而必須設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄的位置。第三十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五一種常用的跟蹤每個(gè)外層過(guò)程最新活動(dòng)記錄位置的有效辦法是，每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表DISPLAY。假定現(xiàn)在進(jìn)入的過(guò)程層數(shù)為i，則它的DISPLAY表含有i+1個(gè)單元。此表本身是一個(gè)小棧，自頂而下每個(gè)單元依次存放著現(xiàn)行層、直接外層……直至最外層(第0層，即主程序?qū)?的每一層的最新活動(dòng)記錄的起始地址。例如，令過(guò)程R的外層為Q，Q的外層為主程序P，則過(guò)程R運(yùn)行時(shí)的DISPLAY表內(nèi)容如表6.1所示。第三十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五表6.1DISPLAY表2R的現(xiàn)行活動(dòng)記錄的始址(SP的現(xiàn)行值)1Q的最新活動(dòng)記錄的始址0P的活動(dòng)記錄的始址第三十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五由于過(guò)程的層數(shù)可靜態(tài)確定，因此每個(gè)過(guò)程的DISPLAY表的體積在編譯時(shí)即可知道。為了便于組織存儲(chǔ)區(qū)和簡(jiǎn)化處理手續(xù)，我們把DISPLAY作為活動(dòng)記錄的一部分置于形式單元的上端，如圖6–8所示。第三十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五由于每個(gè)過(guò)程的形式單元數(shù)目在編譯時(shí)是知道的，因此DISPLAY的相對(duì)地址d(相對(duì)于活動(dòng)記錄的起點(diǎn))在編譯時(shí)也是完全確定的。被調(diào)用過(guò)程為了建立自己的DISPLAY，就必須知道它的直接外層過(guò)程的DISPLAY，這意味著必須把直接外層的DISPLAY地址作為連接數(shù)據(jù)之一(稱為“全局DISPLAY地址”)傳送給被調(diào)用過(guò)程。于是，此時(shí)的連接數(shù)據(jù)包含老SP值、返回地址和全局DISPLAY地址這三項(xiàng)內(nèi)容。整個(gè)活動(dòng)記錄的結(jié)構(gòu)如圖6–8所示。第四十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–8活動(dòng)記錄結(jié)構(gòu)第四十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.3.2嵌套過(guò)程的執(zhí)行

1．過(guò)程調(diào)用過(guò)程調(diào)用所做的工作與簡(jiǎn)單棧式存儲(chǔ)分配大體相同，只是增加了一個(gè)連接數(shù)據(jù)，所以每個(gè)parTi

相應(yīng)的指令應(yīng)改為：

(i+4)[TOP]=Ti

或者(i+4)[TOP]=addr[Ti]第四十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

callP,n所對(duì)應(yīng)的指令應(yīng)為：

1[TOP]=SP /*保護(hù)現(xiàn)行SP*/3[TOP]=SP+d /*將直接外層的DISPLAY始址作為P的全局DISPLAY地址*/4[TOP]=n /*傳遞參數(shù)個(gè)數(shù)*/JSRP /*轉(zhuǎn)向P的第一條指令*/第四十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

2．過(guò)程進(jìn)入轉(zhuǎn)入過(guò)程P后，首先執(zhí)行和簡(jiǎn)單棧式存儲(chǔ)分配相同的指令：

SP=TOP+1 /*定義新的SP*/1[SP]=返回地址 /*保護(hù)返回地址*/TOP=TOP+L /*定義新的TOP*/

其次，應(yīng)按第三項(xiàng)連接數(shù)據(jù)所提供的全局DISPLAY地址，自底而上地抄錄k個(gè)單元內(nèi)容(k為P的層次)，最后再添上新的SP值形成現(xiàn)行過(guò)程P的DISPLAY(共k+1個(gè)單元)。其過(guò)程如圖6–9所示。第四十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–9過(guò)程P進(jìn)入示意第四十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

3．過(guò)程返回當(dāng)過(guò)程P工作完畢要返回到調(diào)用段時(shí)，若return語(yǔ)句含有返回值或P是函數(shù)過(guò)程，則把已算好的值傳送到某個(gè)特定的寄存器，然后執(zhí)行：

TOP=SP?1 /*恢復(fù)調(diào)用過(guò)程的TOP值*/SP=0[SP] /*恢復(fù)調(diào)用過(guò)程的SP值*/X=2[TOP] /*將返回地址送X*/UJ0[X] /*無(wú)條件轉(zhuǎn)移，返回*/

過(guò)程返回執(zhí)行的指令與簡(jiǎn)單棧式存儲(chǔ)分配的過(guò)程返回完全一樣。第四十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.3.3訪問(wèn)非局部名的另一種實(shí)現(xiàn)方法在允許嵌套的過(guò)程中，一個(gè)過(guò)程可以引用包圍它的任一外層過(guò)程所定義的變量或數(shù)組；也即在運(yùn)行時(shí)，一個(gè)過(guò)程Q可能引用它的任一外層過(guò)程P的最新活動(dòng)記錄中的某些數(shù)據(jù)(這些數(shù)據(jù)視為過(guò)程Q的非局部量)。為了在活動(dòng)記錄中查找非局部名字所對(duì)應(yīng)的存儲(chǔ)空間，過(guò)程Q運(yùn)行時(shí)必須知道它的所有外層過(guò)程的最新活動(dòng)記錄的地址。因?yàn)檫^(guò)程活動(dòng)記錄的位置(即使是相對(duì)位置)往往也因過(guò)程的遞歸而變遷，所以必須設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄的位置。第四十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五跟蹤的一種有效辦法是采用嵌套層次顯示表DISPLAY，其優(yōu)點(diǎn)是訪問(wèn)非局部量的速度較快。在此，我們介紹另一種訪問(wèn)非局部名的方法——存取鏈(也稱靜態(tài)鏈)方法。存取鏈方法引入一個(gè)稱為存取鏈的指針，該指針作為活動(dòng)記錄的一項(xiàng)指向直接外層的最新活動(dòng)記錄的地址，這就意味著在運(yùn)行時(shí)棧中的每個(gè)數(shù)據(jù)區(qū)(活動(dòng)記錄)之間又拉出一條鏈，這個(gè)鏈稱為存取鏈。注意，運(yùn)行時(shí)棧中數(shù)據(jù)區(qū)之間原先就存在一條鏈，即每個(gè)活動(dòng)記第四十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五錄中所保存的老SP值這一項(xiàng)，它是指向調(diào)用該過(guò)程(子過(guò)程)的那個(gè)過(guò)程(父過(guò)程)的最新活動(dòng)記錄的起點(diǎn)，由此向前形成了一條SP鏈。為了區(qū)別于存取鏈，稱SP鏈為控制鏈(也稱動(dòng)態(tài)鏈)，它記錄了在運(yùn)行中過(guò)程之間相互調(diào)用的關(guān)系。注意，控制鏈?zhǔn)莿?dòng)態(tài)的，而存取鏈?zhǔn)庆o態(tài)的?？刂奇溣涗浟水?dāng)前時(shí)刻程序中各過(guò)程相互調(diào)用的情況；而存取鏈則始終記錄著程序靜態(tài)定義時(shí)該過(guò)程所有的直接外層(嵌套過(guò)程規(guī)定，內(nèi)層過(guò)程只允許調(diào)用其靜態(tài)定義時(shí)的外層過(guò)程說(shuō)明的變量和數(shù)組)；因此，存取鏈指出了一個(gè)過(guò)程的當(dāng)前活動(dòng)記錄指向其直接定義的外層過(guò)程直至最外層的最新活動(dòng)記錄的起點(diǎn)。具有存取鏈的活動(dòng)記錄結(jié)構(gòu)如圖6–10所示。假定過(guò)程的嵌套關(guān)系如下：第四十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五第五十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–10具有存取鏈的活動(dòng)記錄結(jié)構(gòu)第五十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五程序中每個(gè)過(guò)程的靜態(tài)結(jié)構(gòu)(嵌套層次)是確定的，如嵌套深度為2的過(guò)程R引用了非局部量a和b，其嵌套深度分別為0和1。從R的活動(dòng)記錄開(kāi)始，分別沿著2???0?=?2和2?1=1個(gè)存取鏈向前查找，則可找到包含這兩個(gè)非局部量的活動(dòng)記錄。上述過(guò)程P調(diào)用S以及S調(diào)用Q運(yùn)行時(shí)棧的變化過(guò)程如圖6–11(a)、(b)所示。第五十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五由圖6–11可以看出，指針SP總是指向當(dāng)前正在執(zhí)行過(guò)程的活動(dòng)記錄起點(diǎn)，控制鏈(老SP)則指向調(diào)用運(yùn)行過(guò)程的父過(guò)程的活動(dòng)記錄起點(diǎn)。因此，當(dāng)運(yùn)行過(guò)程調(diào)用結(jié)束返回時(shí)，利用控制鏈老SP值可以得到調(diào)用前原父過(guò)程活動(dòng)記錄的起點(diǎn)。從程序的靜態(tài)結(jié)構(gòu)來(lái)看，P是S和Q的靜態(tài)直接外層，所以，S和Q活動(dòng)記錄中的存取鏈均指向其直接外層P的活動(dòng)記錄起點(diǎn)。第五十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–11過(guò)程調(diào)用時(shí)運(yùn)行棧的變化第五十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五例6.1

某程序的結(jié)構(gòu)如圖6–12所示，其中A、B、C為過(guò)程名，請(qǐng)分別畫出過(guò)程C調(diào)用A前后的棧頂活動(dòng)記錄。第五十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–12例6.1的程序結(jié)構(gòu)示意第五十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

[解答]過(guò)程C調(diào)用A前后的棧頂活動(dòng)記錄示意如圖6–13所示。由圖6–13可知，當(dāng)過(guò)程C執(zhí)行時(shí)，它可使用主程序、A、B和C過(guò)程所說(shuō)明的變量，且其外層嵌套的過(guò)程活動(dòng)記錄始址由DISPLAY表指出。當(dāng)C調(diào)用A而使過(guò)程A執(zhí)行時(shí)，我們看到此時(shí)的DISPLAY表已變?yōu)閮身?xiàng)，即主程序和A過(guò)程自身；也即此時(shí)A只可使用主程序和A過(guò)程所說(shuō)明的變量。第五十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–13例6.1的運(yùn)行棧與活動(dòng)記錄示意第五十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五例6.2

在下面的PASCAL程序中，已經(jīng)第二次(遞歸地)進(jìn)入了f，請(qǐng)給出第三次進(jìn)入f后的運(yùn)行棧及DISPLAY的示意圖

PROGRAMtest(input,output);VARK:integer;FUNCTIONf(n:integer):integer;BEGINIFn<=0THENf:=1第五十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–14例6.2的運(yùn)行棧及DISPLAY示意圖第六十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

[解答]第三次進(jìn)入f后的運(yùn)行棧及DISPLAY的示意圖如圖6–14所示。由于靜態(tài)嵌套層次只有兩層，故每一次遞歸調(diào)用產(chǎn)生的DISPLAY表只有兩項(xiàng)，一項(xiàng)是test的SP(即0)，另一項(xiàng)是當(dāng)前活動(dòng)記錄的SPi(i=1,2,3)。第六十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五6.4堆式動(dòng)態(tài)存儲(chǔ)分配

6.4.1堆式存儲(chǔ)的概念如果一種程序語(yǔ)言允許數(shù)據(jù)對(duì)象能夠自由地分配和釋放，或者不僅有過(guò)程而且有進(jìn)程(process)這樣的程序結(jié)構(gòu)，那么由于空間的使用不一定遵循“先申請(qǐng)后釋放”的原則，則棧式存儲(chǔ)分配就不適用了。在這種情況下，通常使用一種稱之為堆的動(dòng)態(tài)存儲(chǔ)分配方案。假定程序運(yùn)行時(shí)有一個(gè)大的存儲(chǔ)空間，需要時(shí)就從這個(gè)空間中借用一塊，不用時(shí)再退還給它。第六十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五由于借、還的時(shí)間先后不一，因而經(jīng)過(guò)一段時(shí)間的運(yùn)行后，這個(gè)大空間就必然被分割成如圖6–15所示的許多小塊，這些塊有些正在使用，有些則是空閑的(未被使用)。第六十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–15堆式存儲(chǔ)分配示意第六十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五對(duì)于堆式存儲(chǔ)分配來(lái)說(shuō)，需要解決兩個(gè)問(wèn)題：一是堆空間的分配，即當(dāng)運(yùn)行程序需要一塊空間時(shí)應(yīng)分配哪一塊給它；另一個(gè)問(wèn)題是分配空間的回收，由于返回堆的不用空間是按任意次序進(jìn)行的，所以需要研究專門的回收分配策略。在許多語(yǔ)言中都有顯式的堆空間分配和回收語(yǔ)句或函數(shù)，如PASCAL語(yǔ)言中的new和dispose、C語(yǔ)言中的alloc和free以及C++語(yǔ)言中的new和delete。第六十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.4.2堆式存儲(chǔ)管理的方法由于堆式分配方式和存儲(chǔ)管理技術(shù)較為復(fù)雜，并且有效的堆管理是數(shù)據(jù)結(jié)構(gòu)課程研究的問(wèn)題，故我們只對(duì)堆式分配方式作簡(jiǎn)單的討論。當(dāng)運(yùn)行程序要求一塊體積為N的存儲(chǔ)空間時(shí)應(yīng)如何分配？從理論上講，這時(shí)應(yīng)從比N稍大一些的空閑塊中取出N個(gè)單元予以分配，這種做法的目的是保持較大的空閑塊以備將來(lái)之需。但這種方法實(shí)現(xiàn)起來(lái)難度較大，實(shí)際中采用的辦法是：掃描空閑塊鏈并在首次遇到的比N大的空閑塊中取出N個(gè)單元進(jìn)行分配。第六十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五如果找不到一塊比N大的空閑塊，但所有空閑塊的總和卻比N大，這時(shí)就需要用某種方法使這些空閑塊拼接在一起，形成一個(gè)可分配的連續(xù)空間。如果所有空閑塊的總和都不及N大，則需要采用更復(fù)雜的辦法，如廢品回收技術(shù)(即尋找那些運(yùn)行程序已不使用但仍未釋放的存儲(chǔ)塊或運(yùn)行程序目前很少使用的存儲(chǔ)塊)，把這些存儲(chǔ)塊回收后再重新分配?？梢圆捎枚喾N策略進(jìn)行堆式動(dòng)態(tài)存儲(chǔ)管理。在此，我們介紹一種使用可利用空間表進(jìn)行動(dòng)態(tài)分配的方法?？衫每臻g表是指將所有空閑塊用一張表記錄下來(lái)，表的結(jié)構(gòu)可以是目錄表，也可以是鏈表，其結(jié)構(gòu)分別如圖6–16(b)、(c)所示。第六十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五圖6–16內(nèi)存狀態(tài)和可利用空間表第六十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五使用可利用空間表進(jìn)行動(dòng)態(tài)存儲(chǔ)分配的方法又可分為如下兩種：

(1)定長(zhǎng)塊的管理。最簡(jiǎn)單的堆式存儲(chǔ)管理方法是采用定長(zhǎng)塊的管理方法，即將堆存儲(chǔ)空間在初始化時(shí)就劃分成大小相同的若干塊，將各個(gè)塊通過(guò)鏈表鏈接起來(lái)形成一個(gè)單向線性鏈表。由于各塊大小相同，故分配時(shí)無(wú)需查找，只需將頭指針?biāo)傅牡谝粔K分配給用戶即可，然后頭指針指向下一塊。同樣，當(dāng)回收時(shí)，系統(tǒng)將待回收的存儲(chǔ)塊插入到表頭即完成了該塊的回收。第六十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

(2)變長(zhǎng)塊的管理。變長(zhǎng)塊管理方法是一種常用的堆式存儲(chǔ)管理方法，它可以根據(jù)實(shí)際需要來(lái)分配長(zhǎng)度不同的空閑塊；對(duì)空閑塊的管理則可以采用圖6–16(c)中的鏈表形式。系統(tǒng)開(kāi)始時(shí)，存儲(chǔ)空間是一完整空間，可利用空間表中只有一個(gè)大小為整個(gè)存儲(chǔ)空間的空閑塊。當(dāng)系統(tǒng)運(yùn)行一段時(shí)間后，隨著分配和回收的進(jìn)行，可利用空間表中空閑塊的大小和個(gè)數(shù)也隨之改變。由于可利用空間表中的空閑塊大小不同，因而存在著如何進(jìn)行空閑塊分配的問(wèn)題。若可利用空間表存在多個(gè)大于所要求空間的空閑塊，可采取以下三種方法之一進(jìn)行存儲(chǔ)分配：第七十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

(1)首次滿足法。從表頭開(kāi)始查找可利用空間表，將找到的第一個(gè)滿足需要的空閑塊或空閑塊的一部分分配出去(當(dāng)空閑塊略大于所要求的空間時(shí)，則整塊分配出去)，而其余部分仍作為一個(gè)空閑塊留在表中。

(2)最優(yōu)滿足法。系統(tǒng)掃描整個(gè)可利用空間表，從中找出一塊不小于要求的最小空閑塊予以分配。為了避免每次分配都要掃描整個(gè)表，通常將空閑塊按由小到大的順序進(jìn)行排列。這樣，所找到的第一個(gè)大于或等于所需空間的空閑塊即為所求，無(wú)須再掃描整個(gè)表。第七十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

(3)最差滿足法。系統(tǒng)將可利用空間表中最大的空閑塊予以分配(當(dāng)然也要求其不小于所需空間的大小)，這種方法應(yīng)使空閑塊按由大到小的順序排列，此時(shí)表頭的空閑塊即為所求。最優(yōu)滿足法和最差滿足法在回收時(shí)都需將待回收的空閑塊插入到鏈表中適當(dāng)?shù)奈恢蒙先?。第七十二?yè)，共九十四頁(yè)，編輯于2023年，星期五以上三種方法各有所長(zhǎng)。一般來(lái)說(shuō)，最優(yōu)滿足法適用于請(qǐng)求分配的內(nèi)存大小范圍較廣的系統(tǒng)；最差滿足法適用于請(qǐng)求分配的內(nèi)存大小范圍較窄的系統(tǒng)；而首次滿足法則適用于事先無(wú)法獲知請(qǐng)求分配和回收情況的系統(tǒng)。從時(shí)間上來(lái)看，最優(yōu)滿足法無(wú)論分配與回收都需要查表，故最費(fèi)時(shí)間；最差滿足法分配時(shí)無(wú)需查表，但回收時(shí)卻需查表并根據(jù)回收空閑塊的大小確定其在表中應(yīng)插入的位置；而首次滿足法在分配時(shí)需要查表，回收時(shí)直接插入到表頭即可。第七十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五對(duì)于已分配的存儲(chǔ)塊，可以采用不同的回收策略。有的程序語(yǔ)言干脆不做回收工作，直到內(nèi)存空間用完為止；如果當(dāng)空間用完后還有分配存儲(chǔ)塊的請(qǐng)求，就停止程序的運(yùn)行。這樣做的缺點(diǎn)是浪費(fèi)空間，但如果系統(tǒng)具有海量虛存或堆中的多數(shù)數(shù)據(jù)是一分配就一直使用的情形，則這種方法也是可行的。如果程序語(yǔ)言有顯式的分配命令，那么就可用顯式的回收命令(如C語(yǔ)言中的free)來(lái)回收不用的空間。第七十四頁(yè)，共九十四頁(yè)，編輯于2023年，星期五*6.5參數(shù)傳遞補(bǔ)遺定義和調(diào)用過(guò)程是程序語(yǔ)言的主要特征之一。過(guò)程是模塊程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和擴(kuò)充語(yǔ)言能力的主要途徑。PASCAL語(yǔ)言的設(shè)計(jì)者N.Wirth曾經(jīng)說(shuō)過(guò)：“在程序設(shè)計(jì)技巧中，過(guò)程是很少幾種基本工具中的一種，掌握了這種工具，就能對(duì)程序員工作的質(zhì)量和風(fēng)格產(chǎn)生決定性的影響”。第七十五頁(yè)，共九十四頁(yè)，編輯于2023年，星期五一個(gè)過(guò)程一旦定義后，就可以在別的地方調(diào)用它。調(diào)用與被調(diào)用(過(guò)程)兩者之間的信息往來(lái)通過(guò)全局量或參數(shù)傳遞。例如，下面的C語(yǔ)言程序：

#include“stdio.h”voidshowme(inta,intb,intc){printf(“a=%d,b=%d,c=%d\n”,a,b,c);第七十六頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

}main(?){intx=10,y=20,z=30;showme(z,y,x);}

就是一個(gè)含函數(shù)調(diào)用的程序。其中a、b、c稱為形式參數(shù)(簡(jiǎn)稱形參)，而函數(shù)調(diào)用語(yǔ)句：showme(z,y,x)第七十七頁(yè)，共九十四頁(yè)，編輯于2023年，星期五中的z、y、x則稱為實(shí)在參數(shù)(簡(jiǎn)稱實(shí)參)。實(shí)參甚至也可以是一個(gè)較復(fù)雜的表達(dá)式而不僅僅只是一個(gè)變量。實(shí)參和對(duì)應(yīng)的形參在性質(zhì)上應(yīng)相容不悖。

第七十八頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

6.5.1參數(shù)傳遞的方法形式參數(shù)提供了參數(shù)替換的手段，在過(guò)程調(diào)用時(shí)可以使用不同的數(shù)據(jù)作為實(shí)在參數(shù)來(lái)替換形式參數(shù)，從而實(shí)現(xiàn)了同一個(gè)過(guò)程可以對(duì)不同的實(shí)在參數(shù)進(jìn)行相同操作的功能。那么，如何把實(shí)在參數(shù)傳遞給相應(yīng)的形式參數(shù)呢？程序語(yǔ)言中參數(shù)傳遞的方式主要有傳值(callbyvalue)、傳地址(callbyreference)和傳名(callbyname)三種。第七十九頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

1．傳值傳值是最簡(jiǎn)單的參數(shù)傳遞方法。所謂傳值，就是計(jì)算出實(shí)在參數(shù)的值然后把它傳給被調(diào)用過(guò)程相對(duì)應(yīng)的形式參數(shù)，具體過(guò)程如下：

(1)把形式參數(shù)當(dāng)作過(guò)程的局部變量處理，即在被調(diào)用過(guò)程的活動(dòng)記錄中開(kāi)辟形式參數(shù)的存儲(chǔ)空間(即形式單元)。

(2)調(diào)用過(guò)程計(jì)算出實(shí)在參數(shù)的值，并將該值放入為形式單元開(kāi)辟的空間中。第八十頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

(3)被調(diào)用過(guò)程執(zhí)行時(shí)就像使用局部變量一樣使用這些形式單元。傳值的一個(gè)重要特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算都不影響調(diào)用過(guò)程的活動(dòng)記錄中實(shí)在參數(shù)的值，即參數(shù)傳遞后實(shí)在參數(shù)與對(duì)應(yīng)的形式參數(shù)不再發(fā)生聯(lián)系了。第八十一頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

2．傳地址所謂傳地址，是指把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)所對(duì)應(yīng)的形式單元。如果實(shí)在參數(shù)是一個(gè)變量(包括下標(biāo)變量)，則直接將該變量的地址傳給相應(yīng)的形式單元；如果實(shí)在參數(shù)是常數(shù)或表達(dá)式，則先計(jì)算其值并存放在某一臨時(shí)單元中，然后將這個(gè)臨時(shí)單元的地址傳給相應(yīng)的形式單元。被調(diào)用過(guò)程執(zhí)行時(shí)，對(duì)形式參數(shù)的任何引用或賦值都被處理成對(duì)形式單元的間接訪問(wèn)，即按形式單元中存放的地址轉(zhuǎn)到調(diào)用過(guò)程的活動(dòng)記錄中去訪問(wèn)實(shí)在參數(shù)。第八十二頁(yè)，共九十四頁(yè)，編輯于2023年，星期五對(duì)形式參數(shù)的任何運(yùn)算實(shí)際上都是對(duì)實(shí)在參數(shù)的運(yùn)算，而形式參數(shù)只不過(guò)起到輔助查找到實(shí)在參數(shù)的指針的作用。因此，當(dāng)被調(diào)用過(guò)程工作完畢返回時(shí)，形式單元所指的實(shí)在參數(shù)單元就保留了運(yùn)算的結(jié)果。第八十三頁(yè)，共九十四頁(yè)，編輯于2023年，星期五

3．傳名傳名是高級(jí)語(yǔ)言ALGOL60所定義的一種特殊的參數(shù)傳遞方式，其傳遞參數(shù)的方法如下：

(1)過(guò)程調(diào)用的作用相當(dāng)于把被調(diào)用過(guò)程的過(guò)程體復(fù)制到調(diào)用處(替換調(diào)用語(yǔ)句)，并將過(guò)程體中所有出現(xiàn)的形式參數(shù)