編譯原理 7 運(yùn)行存儲(chǔ)分配學(xué)習(xí)課件

運(yùn)行存儲(chǔ)分配

哈爾濱工業(yè)大學(xué)陳鄞第七章7.1存儲(chǔ)組織7.2靜態(tài)存儲(chǔ)分配7.3棧式存儲(chǔ)分配7.4非局部數(shù)據(jù)的訪問(wèn)7.5堆式存儲(chǔ)分配7.6符號(hào)表提綱編譯器在工作過(guò)程中，必須為源程序中出現(xiàn)的一些數(shù)據(jù)對(duì)象分配運(yùn)行時(shí)的存儲(chǔ)空間對(duì)于那些在編譯時(shí)刻就可以確定大小的數(shù)據(jù)對(duì)象，可以在編譯時(shí)刻就為它們分配存儲(chǔ)空間，這樣的分配策略稱為靜態(tài)存儲(chǔ)分配反之，如果不能在編譯時(shí)完全確定數(shù)據(jù)對(duì)象的大小，就要采用動(dòng)態(tài)存儲(chǔ)分配的策略。即在編譯時(shí)僅產(chǎn)生各種必要的信息，而在運(yùn)行時(shí)刻，再動(dòng)態(tài)的分配數(shù)據(jù)對(duì)象的存儲(chǔ)空間棧式存儲(chǔ)分配堆式存儲(chǔ)分配靜態(tài)和動(dòng)態(tài)分別對(duì)應(yīng)編譯時(shí)刻和運(yùn)行時(shí)刻7.1存儲(chǔ)組織靜態(tài)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)棧(Stack)區(qū)堆

(Heap)區(qū)動(dòng)態(tài)數(shù)據(jù)區(qū)域空閑內(nèi)存運(yùn)行時(shí)內(nèi)存的劃分使用過(guò)程（或函數(shù)、方法）作為用戶自定義動(dòng)作的單元的語(yǔ)言，其編譯器通常以過(guò)程為單位分配存儲(chǔ)空間過(guò)程體的每次執(zhí)行稱為該過(guò)程的一個(gè)活動(dòng)(activation)過(guò)程每執(zhí)行一次，就為它分配一塊連續(xù)存儲(chǔ)區(qū)，用來(lái)管理過(guò)程一次執(zhí)行所需的信息，這塊連續(xù)存儲(chǔ)區(qū)稱為活動(dòng)記錄(activationrecord)活動(dòng)記錄實(shí)參臨時(shí)變量控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)指向調(diào)用者的活動(dòng)記錄用來(lái)訪問(wèn)存放于其它活動(dòng)記錄中的非局部數(shù)據(jù)返回值活動(dòng)記錄的一般形式7.1存儲(chǔ)組織7.2靜態(tài)存儲(chǔ)分配7.3棧式存儲(chǔ)分配7.4非局部數(shù)據(jù)的訪問(wèn)7.5堆式存儲(chǔ)分配7.6符號(hào)表提綱在靜態(tài)存儲(chǔ)分配中，編譯器為每個(gè)過(guò)程確定其活動(dòng)記錄在目標(biāo)程序中的位置這樣，過(guò)程中每個(gè)名字的存儲(chǔ)位置就確定了因此，這些名字的存儲(chǔ)地址可以被編譯到目標(biāo)代碼中過(guò)程每次執(zhí)行時(shí)，它的名字都綁定到同樣的存儲(chǔ)單元7.2靜態(tài)存儲(chǔ)分配適合靜態(tài)存儲(chǔ)分配的語(yǔ)言必須滿足以下條件數(shù)組上下界必須是常數(shù)不允許過(guò)程的遞歸調(diào)用不允許動(dòng)態(tài)建立數(shù)據(jù)實(shí)體滿足這些條件的語(yǔ)言有BASIC和FORTRAN等靜態(tài)存儲(chǔ)分配的限制條件順序分配法層次分配法常用的靜態(tài)存儲(chǔ)分配方法按照程序段出現(xiàn)的先后順序逐段分配存儲(chǔ)空間各過(guò)程的活動(dòng)記錄占用互不相交的存儲(chǔ)空間

1/222/153/184/176/105/23過(guò)程編號(hào)/所需存儲(chǔ)空間

過(guò)程存儲(chǔ)區(qū)域

10~21222~36

337~54

455~71

572~94

695~104共需要105個(gè)存儲(chǔ)單元優(yōu)點(diǎn)：處理上簡(jiǎn)單缺點(diǎn)：對(duì)內(nèi)存空間的使用不夠經(jīng)濟(jì)合理能用更少的空間么？順序分配法通過(guò)對(duì)過(guò)程間的調(diào)用關(guān)系進(jìn)行分析，凡屬無(wú)相互調(diào)用關(guān)系的并列過(guò)程，盡量使其局部數(shù)據(jù)共享存儲(chǔ)空間過(guò)程4(0~16)過(guò)程2(17~31)過(guò)程6(0~9)過(guò)程5(0~22)過(guò)程3(23~40)過(guò)程1(41~62)共需要63個(gè)存儲(chǔ)單元7/80如何分配？層次分配法1/222/153/184/176/105/23過(guò)程編號(hào)/所需存儲(chǔ)空間

B[n][n]：過(guò)程調(diào)用關(guān)系矩陣B[i][j]=1：表示第i個(gè)過(guò)程調(diào)用第j個(gè)過(guò)程B[i][j]=0：表示第i個(gè)過(guò)程不調(diào)用第j個(gè)過(guò)程

Units[n]：過(guò)程所需內(nèi)存量矩陣

123456101100020001013000011400000050000006000000層次分配算法base[i]:第i個(gè)過(guò)程局部數(shù)據(jù)區(qū)的基地址

allocated[i]:第i個(gè)過(guò)程局部數(shù)據(jù)區(qū)是否分配的標(biāo)志

voidMakeFortranBlockAllocated(int

*Units,int*base,intNoOfBlocks){/*

NoOfBlocksindicatinghowmanyblocksthereare

*/inti

,j,k,Sum;int*allocated;/*usedtoindicateiftheblockisallocated*/allocated=(int*)malloc(sizeof(int)*NoOfBlocks);for(i=0;i＜NoOfBlocks;i++)/*Initialarraysbaseandallocated*/{base[i]=0;allocated[i]=0;}for(j=0;j＜NoOfBlocks;j++)for(i=0;i＜NoOfBlocks;i++){Sum=0;for(k=0;k＜NoOfBlocks;k++)Sum+=B[i][k];

/*tocheckoutifblockicallssomeblockwhichhasnotbeenallocated*

/if(!Sum&&!allocated[i])

{/*Sum=0meansblockicallsnoblockwhichhasnotbeenallocated;allocated[i]=0;meansblockiisnotallocated*/allocated[i]=1;printf(′′%d:%d-%d/n′′,i,base[i],base[i]+Units[i]-1);for(k=0;k＜NoOfBlocks;k++)

if(B[k][i])/*b[k][i]!=0maensblockkcallsblocki*/{/*Sinceblockkcallsi,itmustbeallocatedafterblocki.Itmeansthebaseofblockkmustbegreaterthanbaseofblocki*/if(base[k]＜base[i]+Units[i])base[k]=base[i]-Units[i];B[k][i]=0;/*SinceblockinhasbeenallocatedB[k][i]shouldbemodified*/}}}free(allocated);}7.1存儲(chǔ)組織7.2靜態(tài)存儲(chǔ)分配7.3棧式存儲(chǔ)分配7.4非局部數(shù)據(jù)的訪問(wèn)7.5堆式存儲(chǔ)分配7.6符號(hào)表提綱有些語(yǔ)言使用過(guò)程、函數(shù)或方法作為用戶自定義動(dòng)作的單元，幾乎所有針對(duì)這些語(yǔ)言的編譯器都把它們的（至少一部分的）運(yùn)行時(shí)刻存儲(chǔ)以棧的形式進(jìn)行管理，稱為棧式存儲(chǔ)分配當(dāng)一個(gè)過(guò)程被調(diào)用時(shí)，該過(guò)程的活動(dòng)記錄被壓入棧；當(dāng)過(guò)程結(jié)束時(shí)，該活動(dòng)記錄被彈出棧這種安排不僅允許活躍時(shí)段不交疊的多個(gè)過(guò)程調(diào)用之間共享空間，而且允許以如下方式為一個(gè)過(guò)程編譯代碼：它的非局部變量的相對(duì)地址總是固定的，和過(guò)程調(diào)用的序列無(wú)關(guān)7.3棧式存儲(chǔ)分配用來(lái)描述程序運(yùn)行期間控制進(jìn)入和離開各個(gè)活動(dòng)的情況的樹稱為活動(dòng)樹樹中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)活動(dòng)。根結(jié)點(diǎn)是啟動(dòng)程序執(zhí)行的main過(guò)程的活動(dòng)在表示過(guò)程p的某個(gè)活動(dòng)的結(jié)點(diǎn)上，其子結(jié)點(diǎn)對(duì)應(yīng)于被p的這次活動(dòng)調(diào)用的各個(gè)過(guò)程的活動(dòng)。按照這些活動(dòng)被調(diào)用的順序，自左向右地顯示它們。一個(gè)子結(jié)點(diǎn)必須在其右兄弟結(jié)點(diǎn)的活動(dòng)開始之前結(jié)束活動(dòng)樹p(1,3)q(1,0)q(2,3)p(5,9)q(5,5)q(7,9)mq(1,9)rp(1,9)q(1,3)q(5,9)p(2,3)q(2,1)q(3,3)p(7,9)q(7,7)q(9,9)inta[11];

voidreadArray()/*將9個(gè)整數(shù)讀入到a[1],…,a[9]中

*/{inti;…}intpartition(intm,intn){/*選擇一個(gè)分割值v，劃分a[m…n]，使得a[m…p-1]小于v,a[p]=v,a[p+1…n]大于v。返回

p*/…

}voidquicksort(intm,intn){inti;if(n＞m){i=partition(m,n);quicksort(m,i-1);quicksort(i+1,n);}}main(){readArray();a[0]=-9999;a[10]=9999;quicksort(1,9);}每個(gè)活躍的活動(dòng)都有一個(gè)位于控制棧中的活動(dòng)記錄例：一個(gè)快速排序程序的概要mrmainint

a[11]rint

i活動(dòng)樹控制棧mq(1,9)rp(1,9)mainint

a[11]q(1,9)int

ip(1,9)int

i活動(dòng)樹控制棧mq(1,9)rp(1,9)q(1,3)p(1,3)mainint

a[11]q(1,9)int

ip(1,3)int

i活動(dòng)樹控制棧q(1,3)int

imq(1,9)rp(1,9)q(1,3)p(1,3)mainint

a[11]q(1,9)int

i活動(dòng)樹控制棧q(1,3)int

iq(1,0)q(1,0)int

i當(dāng)一個(gè)過(guò)程是遞歸的時(shí)，常常會(huì)有該過(guò)程的多個(gè)活動(dòng)記錄同時(shí)出現(xiàn)在棧中mq(1,9)rp(1,9)q(1,3)p(1,3)mainint

a[11]q(1,9)int

i活動(dòng)樹控制棧q(1,3)int

iq(1,0)q(2,3)int

iq(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)

每個(gè)活躍的活動(dòng)都有一個(gè)位于控制棧中的活動(dòng)記錄

活動(dòng)樹的根的活動(dòng)記錄位于棧底

程序控制所在的活動(dòng)的記錄位于棧頂

棧中全部活動(dòng)記錄的序列對(duì)應(yīng)于在活動(dòng)樹中到達(dá)當(dāng)前控制所在的活動(dòng)結(jié)點(diǎn)的路徑在調(diào)用者和被調(diào)用者之間傳遞的值一般被放在被調(diào)用者的活動(dòng)記錄的開始位置，這樣它們可以盡可能地靠近調(diào)用者的活動(dòng)記錄固定長(zhǎng)度的項(xiàng)被放置在中間位置控制連、訪問(wèn)鏈、機(jī)器狀態(tài)字在早期不知道大小的項(xiàng)被放置在活動(dòng)記錄的尾部棧頂指針寄存器top_sp指向活動(dòng)記錄中局部數(shù)據(jù)開始的位置，以該位置作為基地址被調(diào)用者的活動(dòng)記錄控制鏈訪問(wèn)鏈和機(jī)器狀態(tài)參數(shù)和返回值局部數(shù)據(jù)臨時(shí)數(shù)據(jù)參數(shù)和返回值控制鏈訪問(wèn)鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)...棧top_sp調(diào)用者的活動(dòng)記錄設(shè)計(jì)活動(dòng)記錄的一些原則過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等調(diào)用序列實(shí)現(xiàn)過(guò)程調(diào)用的代碼段。為一個(gè)活動(dòng)記錄在棧中分配空間，并在此記錄的字段中填寫信息返回序列恢復(fù)機(jī)器狀態(tài)，使得調(diào)用過(guò)程能夠在調(diào)用結(jié)束之后繼續(xù)執(zhí)行一個(gè)調(diào)用代碼序列中的代碼通常被分割到調(diào)用過(guò)程（調(diào)用者）和被調(diào)用過(guò)程（被調(diào)用者）中。返回序列也是如此調(diào)用序列和返回序列

調(diào)用者計(jì)算實(shí)際參數(shù)的值

調(diào)用者將返回地址（程序計(jì)數(shù)器的值）放到被調(diào)用者的機(jī)器狀態(tài)字段中。將原來(lái)的top-sp值放到被調(diào)用者的控制鏈中。然后，增加top-sp的值，使其指向被調(diào)用者局部數(shù)據(jù)開始的位置

被調(diào)用者保存寄存器值和其它狀態(tài)信息

被調(diào)用者初始化其局部數(shù)據(jù)并開始執(zhí)行……參數(shù)和返回值控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)和臨時(shí)數(shù)據(jù)參數(shù)和返回值控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)和臨時(shí)數(shù)據(jù)……top_sp被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄調(diào)用序列

被調(diào)用者將返回值放到與參數(shù)相鄰的位置使用機(jī)器狀態(tài)字段中的信息，被調(diào)用者恢復(fù)top-sp和其它寄存器，然后跳轉(zhuǎn)到由調(diào)用者放在機(jī)器狀態(tài)字段中的返回地址盡管top-sp已經(jīng)被減小，但調(diào)用者仍然知道返回值相對(duì)于當(dāng)前top-sp值的位置。因此，調(diào)用者可以使用那個(gè)返回值……參數(shù)和返回值控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)和臨時(shí)數(shù)據(jù)參數(shù)和返回值控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)和臨時(shí)數(shù)據(jù)……top_sp被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄返回序列調(diào)用者填寫被調(diào)用者填寫被調(diào)用者填寫調(diào)用者更新被調(diào)用者恢復(fù)……參數(shù)和返回值控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)和臨時(shí)數(shù)據(jù)參數(shù)和返回值控制鏈訪問(wèn)鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)和臨時(shí)數(shù)據(jù)……top_sp被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄調(diào)用者和被調(diào)用者之間的任務(wù)劃分在現(xiàn)代程序設(shè)計(jì)語(yǔ)言中，在編譯時(shí)刻不能確定大小的對(duì)象將被分配在堆區(qū)。但是，如果它們是過(guò)程的局部對(duì)象，也可以將它們分配在運(yùn)行時(shí)刻棧中。盡量將對(duì)象放置在棧區(qū)的原因：可以避免對(duì)它們的空間進(jìn)行垃圾回收，也就減少了相應(yīng)的開銷只有一個(gè)數(shù)據(jù)對(duì)象局部于某個(gè)過(guò)程，且當(dāng)此過(guò)程結(jié)束時(shí)它變得不可訪問(wèn)，才可以使用棧為這個(gè)對(duì)象分配空間變長(zhǎng)數(shù)據(jù)…控制鏈和保存的機(jī)器狀態(tài)…指向a的指針指向c的指針指向b的指針…數(shù)組a數(shù)組b數(shù)組c控制鏈和保存的機(jī)器狀態(tài)top_sptop被調(diào)用者q的活動(dòng)記錄調(diào)用者p的活動(dòng)記錄q的數(shù)組p的數(shù)組訪問(wèn)動(dòng)態(tài)分配的數(shù)組7.1存儲(chǔ)組織7.2靜態(tài)存儲(chǔ)分配7.3棧式存儲(chǔ)分配7.4非局部數(shù)據(jù)的訪問(wèn)7.5堆式存儲(chǔ)分配7.6符號(hào)表提綱7.4非局部數(shù)據(jù)的訪問(wèn)一個(gè)過(guò)程除了可以使用過(guò)程自身定義的局部數(shù)據(jù)以外，還可以使用過(guò)程外定義的非局部數(shù)據(jù)語(yǔ)言可以分為兩種類型

支持過(guò)程嵌套聲明的語(yǔ)言可以在一個(gè)過(guò)程中聲明另一個(gè)過(guò)程例:Pascal

不支持過(guò)程嵌套聲明的語(yǔ)言不可以在一個(gè)過(guò)程中聲明另一個(gè)過(guò)程例：C例：C語(yǔ)言inta[11];

voidreadArray()/*將9個(gè)整數(shù)讀入到a[1],…,a[9]中

*/{inti;…}intpartition(intm,intn){/*選擇一個(gè)分割值v，劃分a[m…n]，使得a[m…p-1]小于v,a[p]=v,

a[p+1…n]大于v。返回

p*/…

}voidquicksort(intm,intn){inti;if(n＞m){i=partition(m,n);quicksort(m,i-1);quicksort(i+1,n);}}main(){readArray();

a[0]=-9999;

a[10]=9999;quicksort(1,9);}不支持過(guò)程嵌套聲明的語(yǔ)言過(guò)程中使用的非局部數(shù)據(jù)是全局?jǐn)?shù)據(jù)例:Pascal語(yǔ)言支持過(guò)程嵌套聲明的語(yǔ)言program

sort(input,output);

var

a:array[0..10]ofinteger;x:integer;

procedure

readarray;

var

i:integer;

begin…a…end{readarray}；

procedure

exchange(i,j:integer);

begin

x=a[i];a[i]=a[j];a[j]=x;end{exchange}；

procedure

quicksort(m,n:integer);

var

k,v:integer;

function

partition(y,z:integer):integer;

var

i,j:integer;

begin…a…v

…exchange(i,j)…end{partition};

begin…a…v…partition

…quicksort

…end{quicksort}；

begin…a…readarray

…quicksort

…end{sort}；過(guò)程中使用的非局部數(shù)據(jù)不一定都是全局?jǐn)?shù)據(jù)，也可能是其它過(guò)程定義的數(shù)據(jù)例

procedure

A;

var

x:integer; …

procedure

B;

var

x:integer; …

procedure

C;

var

a:real;

begin…x

…end{C};

begin…end{B}；

begin…end{A}；名字x的當(dāng)前出現(xiàn)對(duì)應(yīng)的是哪個(gè)聲明語(yǔ)句？在程序的不同部分可能有同一名字的互相獨(dú)立的聲明x的一個(gè)聲明的作用域(scope)是指程序的一個(gè)區(qū)域，在其中對(duì)x的使用都指向這個(gè)聲明如果僅通過(guò)閱讀程序就可以確定一個(gè)聲明的作用域，那么這個(gè)語(yǔ)言使用的是靜態(tài)作用域。否則，這個(gè)語(yǔ)言使用的是動(dòng)態(tài)作用域包括C及其同類語(yǔ)言在內(nèi)的大多數(shù)語(yǔ)言使用靜態(tài)作用域C語(yǔ)言的作用域規(guī)則是基于程序結(jié)構(gòu)的，聲明的作用域由該聲明在程序中出現(xiàn)的位置隱含地決定稍后出現(xiàn)的語(yǔ)言，如C++、Java和

C#，也通過(guò)諸如public、private和protected等關(guān)鍵字的使用，提供對(duì)作用域的顯式的控制靜態(tài)作用域塊是聲明和語(yǔ)句的一個(gè)組合C使用括號(hào)“{”和“}”來(lái)界定一個(gè)塊另一種為同一目的使用begin和end的方法可以追溯到Algol塊結(jié)構(gòu)語(yǔ)言中聲明的靜態(tài)作用域規(guī)則如果名字x的聲明D屬于塊B，那么D的作用域包括整個(gè)B，但是以任意深度嵌套在B中、重新聲明了x的所有塊B'不在此作用域中例

procedure

A;

varx:integer; …

procedureB;

var

x:integer; …

procedure

C;

var

a:real;

begin…x…end{C};

begin…end{B}；

begin…end{A}；塊結(jié)構(gòu)語(yǔ)言中聲明的靜態(tài)作用域規(guī)則不支持過(guò)程嵌套聲明的語(yǔ)言在C系列語(yǔ)言中，各個(gè)變量要么在某個(gè)函數(shù)內(nèi)定義，要么在所有函數(shù)之外（全局地）定義一個(gè)全局變量v的作用域包含了該變量聲明后出現(xiàn)的所有函數(shù)，但那些存在標(biāo)識(shí)符v的局部定義的地方除外在一個(gè)函數(shù)內(nèi)部聲明的變量的作用域就是這個(gè)函數(shù)，或者如果該函數(shù)具有嵌套的語(yǔ)句塊，這個(gè)變量的作用域可能是該函數(shù)的部分區(qū)域無(wú)過(guò)程嵌套聲明時(shí)的靜態(tài)作用域變量的存儲(chǔ)分配和訪問(wèn)全局變量被分配在靜態(tài)區(qū)，使用靜態(tài)確定的地址訪問(wèn)它們其它變量一定是棧頂活動(dòng)的局部變量。可以通過(guò)運(yùn)行時(shí)刻棧的top_sp指針訪問(wèn)它們無(wú)過(guò)程嵌套聲明時(shí)的數(shù)據(jù)訪問(wèn)根據(jù)塊結(jié)構(gòu)語(yǔ)言的靜態(tài)作用域規(guī)則，只要過(guò)程a的聲明包含過(guò)程b的聲明，過(guò)程b就可以訪問(wèn)過(guò)程a中聲明的對(duì)象program

sort

(input,output);

var

a:array[0..10]ofinteger;x:integer;

procedure

readarray;

var

i:integer;

begin…a…end{readarray}；

procedure

exchange(i,j:integer);

begin

x=a[i];a[i]=a[j];a[j]=x;end{exchange}；

procedure

quicksort(m,

n:integer);

var

k,v:integer;

function

partition(y,z:integer):integer;

var

i,j:integer;

begin…a…v

…exchange(i,

j)…end{partition};

begin…

a

…

v

…partition

…quicksort

…end{quicksort}；

begin…a…readarray

…quicksort

…end{sort}；有過(guò)程嵌套聲明時(shí)的數(shù)據(jù)訪問(wèn)運(yùn)行時(shí)如何訪問(wèn)在過(guò)程外聲明的數(shù)據(jù)？過(guò)程的嵌套深度不內(nèi)嵌在任何其它過(guò)程中的過(guò)程，設(shè)其嵌套深度為1如果一個(gè)過(guò)程p在一個(gè)嵌套深度為i的過(guò)程中定義，則設(shè)定p的嵌套深度為i+1變量的嵌套深度將變量聲明所在過(guò)程的嵌套深度作為該名字的嵌套深度嵌套深度

過(guò)程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3program

sort(input,output);

var

a:array[0..10]ofinteger;x:integer;

procedure

readarray;

var

i:integer;

begin…a…end{readarray}；

procedure

exchange(i,j:integer);

begin

x=a[i];a[i]=a[j];a[j]=x;end{exchange}；

procedure

quicksort(m,n:integer);

var

k,v:integer;

function

partition(y,z:integer):integer;

var

i,j:integer;

begin…a…v

…exchange(i,j)…end{partition};

begin…a…v…partition

…quicksort

…end{quicksort}；

begin…a…readarray

…quicksort

…end{sort}；例靜態(tài)作用域規(guī)則：只要過(guò)程b的聲明嵌套在過(guò)程a的聲明中，過(guò)程b就可以訪問(wèn)過(guò)程a中聲明的對(duì)象可以在相互嵌套的過(guò)程的活動(dòng)記錄之間建立一種稱為訪問(wèn)鏈(Accesslink)的指針，使得內(nèi)嵌的過(guò)程可以訪問(wèn)外層過(guò)程中聲明的對(duì)象如果過(guò)程b在源代碼中直接嵌套在過(guò)程a中(b的嵌套深度比a的嵌套深度多1)，那么b的任何活動(dòng)中的訪問(wèn)鏈都指向最近的a的活動(dòng)訪問(wèn)鏈(AccessLinks)sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(5,9)eeprogram

sort(input,output);

var

a:array[0..10]ofinteger;x:integer;

procedure

readarray;

var

i:integer;

begin…a…end{readarray}；

procedure

exchange(i,j:integer);

begin

x=a[i];a[i]=a[j];a[j]=x;end{exchange}；

procedure

quicksort(m,n:integer);

var

k,v:integer;

function

partition(y,z:integer):integer;

var

i,j:integer;

begin…a…v

…exchange(i,j)…end{partition};

begin…a…v…partition

…quicksort

…end{quicksort}；

begin…a…readarray

…quicksort

…end{sort}；例s活動(dòng)樹sa訪問(wèn)鏈控制棧

過(guò)程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3sr活動(dòng)樹控制棧

過(guò)程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3sa訪問(wèn)鏈ri訪問(wèn)鏈r中的訪問(wèn)鏈指向s的活動(dòng)記錄，這不是因?yàn)閟調(diào)用了r，而是因?yàn)樵诔绦蛑校瑂是r外圍的最靠近r的嵌套函數(shù)sq(1,9)rp(1,9)活動(dòng)樹sa訪問(wèn)鏈控制棧

過(guò)程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3q(1,9)v訪問(wèn)鏈p(1,9)i,j訪問(wèn)鏈ee訪問(wèn)鏈sq(1,9)rp(1,9)q(1,3)p(1,3)活動(dòng)樹

過(guò)程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3sa訪問(wèn)鏈控制棧q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈eee訪問(wèn)鏈假定棧頂?shù)倪^(guò)程b的嵌套深度是nb且b需要訪問(wèn)x，而x是在某個(gè)包圍b的嵌套深度為na的過(guò)程a中定義的一個(gè)元素(na≤nb)?？梢园慈缦路椒ㄕ业絰從位于棧頂?shù)腷的活動(dòng)記錄開始，沿著訪問(wèn)鏈進(jìn)行nb

-na次從一個(gè)活動(dòng)記錄到另一個(gè)活動(dòng)記錄的查找，最終找到a的活動(dòng)記錄。這一定是當(dāng)前出現(xiàn)在棧中離b最近的a的活動(dòng)記錄。這個(gè)活動(dòng)記錄中包括要找的元素xsa訪問(wèn)鏈q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈

過(guò)程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3利用訪問(wèn)鏈訪問(wèn)非局部數(shù)據(jù)的方法建立訪問(wèn)鏈的代碼屬于調(diào)用序列的一部分假設(shè)嵌套深度為nx的過(guò)程x調(diào)用嵌套深度為ny的過(guò)程y

(x→y)nx<ny的情況(外層調(diào)用內(nèi)層)y一定是直接嵌套在x中(例如：s→q,

q→p)，因此，ny=nx+1在調(diào)用代碼序列中增加一個(gè)步驟：(利用控制鏈)在y的訪問(wèn)鏈中放置一個(gè)指向x的活動(dòng)記錄的指針sa訪問(wèn)鏈q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈e訪問(wèn)鏈

過(guò)程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3訪問(wèn)鏈的建立sa訪問(wèn)鏈q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈e訪問(wèn)鏈

過(guò)程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3建立訪問(wèn)鏈的代碼屬于調(diào)用序列的一部分假設(shè)嵌套深度為nx的過(guò)程x調(diào)用嵌套深度為ny的過(guò)程y

(x→y)nx<ny的情況(外層調(diào)用內(nèi)層)nx=ny的情況(本層調(diào)用本層)遞歸調(diào)用(例如：q→q)被調(diào)用者的活動(dòng)記錄的訪問(wèn)鏈與調(diào)用者的活動(dòng)記錄的訪問(wèn)鏈?zhǔn)窍嗤?，可以直接?fù)制訪問(wèn)鏈的建立sa訪問(wèn)鏈q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈e訪問(wèn)鏈

過(guò)程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3建立訪問(wèn)鏈的代碼屬于調(diào)用序列的一部分假設(shè)嵌套深度為nx的過(guò)程x調(diào)用嵌套深度為ny的過(guò)程y

(x→y)nx<ny的情況(外層調(diào)用內(nèi)層)nx=ny的情況(本層調(diào)用本層)nx>ny的情況(內(nèi)層調(diào)用外層，如：p→e)過(guò)程x必定嵌套在某個(gè)過(guò)程z中，而z中直接定義了過(guò)程y從x的活動(dòng)記錄開始，沿著訪問(wèn)鏈經(jīng)過(guò)nx

-ny

+1步就可以找到離棧頂最近的z的活動(dòng)記錄。y的訪問(wèn)鏈必須指向z的這個(gè)活動(dòng)記錄訪問(wèn)鏈的建立7.1存儲(chǔ)組織7.2靜態(tài)存儲(chǔ)分配7.3棧式存儲(chǔ)分配7.4非局部數(shù)據(jù)的訪問(wèn)7.5堆式存儲(chǔ)分配7.6符號(hào)表提綱堆式存儲(chǔ)分配是把連續(xù)存儲(chǔ)區(qū)域分成塊，當(dāng)活動(dòng)記錄或其它對(duì)象需要時(shí)就分配塊的釋放可以按任意次序進(jìn)行，所以經(jīng)過(guò)一段時(shí)間后，對(duì)可能包含交錯(cuò)的正在使用和已經(jīng)釋放的區(qū)域堆式存儲(chǔ)分配鏈頭指針FREEA已占用塊記錄表堆式存儲(chǔ)分配的示意圖申請(qǐng)?jiān)O(shè)當(dāng)前自由塊總長(zhǎng)為M，欲申請(qǐng)長(zhǎng)度為n如果存在若干個(gè)長(zhǎng)度大于或等于n的存儲(chǔ)塊，可按以下策略之一進(jìn)行存儲(chǔ)分配取長(zhǎng)度m滿足需求的第1個(gè)自由塊，將長(zhǎng)度為m-n的剩余部分仍放在自由鏈中取長(zhǎng)度m滿足需求的最小的自由塊取長(zhǎng)度m滿足需求的最大的自由塊如果不存在長(zhǎng)度大于或等于n的存儲(chǔ)塊如果M≥n，將自由塊在堆中進(jìn)行移位和重組（對(duì)各有關(guān)部分都需作相應(yīng)的修改，是一件十分復(fù)雜和困難的工作）如果M<n，則應(yīng)采用更復(fù)雜的策略來(lái)解決堆的管理問(wèn)題申請(qǐng)?jiān)O(shè)當(dāng)前自由塊總長(zhǎng)為M，欲申請(qǐng)長(zhǎng)度為n如果存在若干個(gè)長(zhǎng)度大于或等于n的存儲(chǔ)塊，可按以下策略之一進(jìn)行存儲(chǔ)分配釋放只需將被釋放的存儲(chǔ)塊作為新的自由塊插入自由鏈中，并刪除已占?jí)K記錄表中相應(yīng)的記錄即可申請(qǐng)為實(shí)現(xiàn)堆式存儲(chǔ)管理須完成大量的輔助操作如排序、查表、填表、插入、刪除、……其空間和時(shí)間的開銷較大7.1存儲(chǔ)組織7.2靜態(tài)存儲(chǔ)分配7.3棧式存儲(chǔ)分配7.4非局部數(shù)據(jù)的訪問(wèn)7.5堆式存儲(chǔ)分配7.6符號(hào)表提綱符號(hào)表的組織為每個(gè)作用域（程序塊）建立一個(gè)獨(dú)立的符號(hào)表7.6符號(hào)表program

sort(input,output);

vara:array[0..10]ofinteger;

x:integer;

procedure

readarray;

var

i:integer;

begin

…a…

end;

procedure

exchange(i,j:integer);

begin

x=a[i];a[i]=a[j];a[j]=x;end;

procedure

quicksort(m,n:integer);

var

k,v:integer;

function

partition(y,z:integer):integer;

var

i,j:integer;

begin

…a…v…exchange(i,j)…end;

begin

…a…v…partition…quicksort…quicksort…end

;

begin

…a…readarray…quicksort…end;kint0vint4jint4iint0header48sortreadarraryaarray0xint44readarrayexchangeheader0exchangeheader8quicksortheader8partitionpartitionquicksortheader4

iint0例訪問(wèn)棧中的非局部數(shù)據(jù)kint0vint4jint4iint0header48sortreadarraryaarray0xint44readarrayexchangeheader0exchangeheader8quicksortheader8partitionpartitionquicksortheader4

iint0sa訪問(wèn)鏈q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈實(shí)際上，這種為每個(gè)過(guò)程或作用域建立的符號(hào)表與編譯時(shí)的活動(dòng)記錄是對(duì)應(yīng)的。一個(gè)過(guò)程的非局部名字的信息可以通過(guò)掃描外圍過(guò)程的符號(hào)表而得到符號(hào)表的使用訪問(wèn)棧中的非局部數(shù)據(jù)構(gòu)造訪問(wèn)鏈kint0vint4jint4iint0header48sortreadarraryaarray0xint44readarrayexchangeheader0exchangeheader8quicksortheader8partitionpartitionquicksortheader4

iint0sa訪問(wèn)鏈q(1,9)v訪問(wèn)鏈q(1,3)v訪問(wèn)鏈p(1,3)i,j訪問(wèn)鏈e訪問(wèn)鏈x→y

nx<ny的情況(例：

s→q,

q→p)nx=ny的情況(例：

q→q)nx>ny的情況(例：p→e)符號(hào)表的使用當(dāng)在某一層的聲明語(yǔ)句中識(shí)別出一個(gè)標(biāo)識(shí)符(id的定義性出現(xiàn))時(shí)，以此標(biāo)識(shí)符查相應(yīng)于本層的符號(hào)表如果查到，則報(bào)錯(cuò)并發(fā)出診斷信息“id重復(fù)聲明”否則，在符號(hào)表中加入新登記項(xiàng)，將標(biāo)識(shí)符及有關(guān)信息填入當(dāng)在可執(zhí)行語(yǔ)句部分掃視到標(biāo)識(shí)符時(shí)(id的應(yīng)用性出現(xiàn))首先在該層符號(hào)表中查找該id，如果找不到，則到直接外層符號(hào)表中去查，如此等等，一旦找到，則在表中取出有關(guān)信息并作相應(yīng)處理如果查遍所有外層符號(hào)表均未找到該id，則報(bào)錯(cuò)并發(fā)出診斷信息“id未聲明”標(biāo)識(shí)符的基本處理方法嵌套過(guò)程聲明語(yǔ)句的文法 P

D

D

D

D|procid;D

S|id:T;在允許嵌套過(guò)程聲明的語(yǔ)言中，局部于每個(gè)過(guò)程的名字可以使用第6章介紹的方法分配相對(duì)地址；當(dāng)看到嵌套的過(guò)程p時(shí)，應(yīng)暫時(shí)掛起對(duì)外圍過(guò)程q聲明語(yǔ)句的處理符號(hào)表的建立P

M

D

{addwidth(top(tblptr),top(offset));

pop(tblptr);

pop(offset);}M

{t=mktable(nil);

push(t,tblptr);

push(0,offset);}D

D1

D2Dp

procid;N

D1

S{t=top(tblptr);

addwidth(t,top(offset));

pop(tblptr);

pop(offset);

enterproc(top(tblptr),id.lexeme,t);}Dv

id:T;{enter(top(tblptr),id.lexeme,T.type,top(offset));

top(offset)

=top(offset）+T.width;}N

{t=mktable(top(tblptr));

push(t,tblptr);push(0,offset);}mktable(previous)創(chuàng)建一個(gè)新的符號(hào)表，并返回指向新表的指針。參數(shù)previous指向先前創(chuàng)建的符號(hào)表(外圍過(guò)程的符號(hào)表)enter(table,name,type,offset)在table指向的符號(hào)表中為名字name建立一個(gè)新表項(xiàng)addwidth(table,width)將table指向的符號(hào)表中所有表項(xiàng)的寬度之和width記錄在符號(hào)表的表頭中enterproc(table,name,newtable)在table指向的符號(hào)表中為過(guò)程name建立一條記錄，newtable指向過(guò)程name的符號(hào)表嵌套過(guò)程聲明語(yǔ)句的SDTprogram

sort(input,output);

vara:array[0..10]ofinteger;

x:integer;

procedure

readarray;

var

i:integer;

begin

…a…

end;

procedure

exchange(i,j:integer);

begin

x=a[i];a[i]=a[j];a[j]=x;end;

procedure

quicksort(m,n:integer);

var

k,v:integer;

function

partition(y,z:integer):integer;

var

i,j:integer;

begin

…a…v…exchange(i,j)…end;

begin

…a…v…partition…quicksort…quicksort…end

;

begin

…a…readarray…quicksort…end;program

sort;

vara:int[11];x:int;

proc

readarray;

var

i:int;{…}

proc

exchange;{…}

proc

quicksort;

var

k,v:int;

func

partitin;

var

i,j:int;{…}{…}{…}例headersortP

M

D

{addwidth(top(tblptr),top(offset));

pop(tblptr);pop(offset);}M

{t=mktable(nil);

push(t,tblptr);push(0,offset);}D

D1

D2Dp

procid;N

D1

S{t=top(tblptr);addwidth(t,top(offset));

pop(tblptr);pop(offset);enterproc(top(tblptr),id.lexeme,t);}Dv

id:T;{enter(top(tblptr),id.lexeme,T.type,top(offset));

top(offset)

=top(offset）+T.width;}N

{t=mktable(top(tblptr));push(t,tblptr);push(0,offset);}readarraryheaderprogram

sort;

vara:int[11];x:int;

proc

readarray;

var

i:int;{…}

proc

exchange;{…}

proc

quicksort;

var

k,v:int;

func

partitin;

var

i,j:int;{…}{…}{…}header

niloffsettblptraarray00044xint44480iint044readarray例headersortP

M

D

{addwidth(top(tblptr),top(offset));

pop(tblptr);pop(offset);}M

{t=mktable(nil);

push(t,tblptr);push(0,offset);}D

D1

D2Dp

procid;N

D1

S{t=top(tblptr);addwidth(t,top(offset));

pop(tblptr);pop(offset);enterproc(top(tblptr),id.lexeme,t);}Dv

id:T;{enter(top(tblptr),id.lexeme,T.type,top(offset));

top(offset)

=top(offset）+T.width;}N

{t=mktable(top(tblptr));push(t,tblptr);push(0,offset);}readarraryheaderprogram

sort;

vara:int[11];x:int;

proc

readarray;

var

i:int;{…}

proc

exchange;{…}

proc

quicksort;

var

k,v:int;

func

partitin;

var

i,j:int;{…}{…}{…}header

niloffsettblptraarray00040xint4448iint04readarrayexchangeheader00exchange例headersortP

M

D

{addwidth(top(tblptr),top(offset));

pop(tblptr);pop(offset);}M

{t=mktable(nil);

push(t,tblptr);push(0,offset);}D

D1

D2Dp

procid;N

D1

S{t=top(tblptr);addwidth(t,top(offset));

pop(tblptr);pop(offset);enterproc(top(tblptr),id.lexeme,t);}Dv

id:T;{enter(top(tblptr),id.lexeme,T.type,top(offset));

top(offset)

=top(offset）+T.width;}N

{t=mktable(top(tblptr));push(t,tblptr);push(0,offset);}readarraryheaderprogram

sort;

vara:int[11];x:int;

proc

readarray;

var

i:int;{…}

proc

exchange;{…}

proc

quicksort;

var

k,v:int;

func

partitin;

var

i,j:int;{…}{…}{…}header

niloffsettblptraarray00040xint4448iint04readarrayexchangeheader0exchangeheaderquicksort0k