編譯原理 7 運行存儲分配學習課件

運行存儲分配

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

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

1/222/153/184/176/105/23過程編號/所需存儲空間

過程存儲區(qū)域

10~21222~36

337~54

455~71

572~94

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

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

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

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

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

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存儲組織7.2靜態(tài)存儲分配7.3棧式存儲分配7.4非局部數(shù)據(jù)的訪問7.5堆式存儲分配7.6符號表提綱有些語言使用過程、函數(shù)或方法作為用戶自定義動作的單元，幾乎所有針對這些語言的編譯器都把它們的（至少一部分的）運行時刻存儲以棧的形式進行管理，稱為棧式存儲分配當一個過程被調(diào)用時，該過程的活動記錄被壓入棧；當過程結(jié)束時，該活動記錄被彈出棧這種安排不僅允許活躍時段不交疊的多個過程調(diào)用之間共享空間，而且允許以如下方式為一個過程編譯代碼：它的非局部變量的相對地址總是固定的，和過程調(diào)用的序列無關7.3棧式存儲分配用來描述程序運行期間控制進入和離開各個活動的情況的樹稱為活動樹樹中的每個結(jié)點對應于一個活動。根結(jié)點是啟動程序執(zhí)行的main過程的活動在表示過程p的某個活動的結(jié)點上，其子結(jié)點對應于被p的這次活動調(diào)用的各個過程的活動。按照這些活動被調(diào)用的順序，自左向右地顯示它們。一個子結(jié)點必須在其右兄弟結(jié)點的活動開始之前結(jié)束活動樹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個整數(shù)讀入到a[1],…,a[9]中

*/{inti;…}intpartition(intm,intn){/*選擇一個分割值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);}每個活躍的活動都有一個位于控制棧中的活動記錄例：一個快速排序程序的概要mrmainint

a[11]rint

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

a[11]q(1,9)int

ip(1,9)int

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

a[11]q(1,9)int

ip(1,3)int

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

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

a[11]q(1,9)int

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

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

i當一個過程是遞歸的時，常常會有該過程的多個活動記錄同時出現(xiàn)在棧中mq(1,9)rp(1,9)q(1,3)p(1,3)mainint

a[11]q(1,9)int

i活動樹控制棧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)

每個活躍的活動都有一個位于控制棧中的活動記錄

活動樹的根的活動記錄位于棧底

程序控制所在的活動的記錄位于棧頂

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

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

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

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

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

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

支持過程嵌套聲明的語言可以在一個過程中聲明另一個過程例:Pascal

不支持過程嵌套聲明的語言不可以在一個過程中聲明另一個過程例：C例：C語言inta[11];

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

*/{inti;…}intpartition(intm,intn){/*選擇一個分割值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);}不支持過程嵌套聲明的語言過程中使用的非局部數(shù)據(jù)是全局數(shù)據(jù)例:Pascal語言支持過程嵌套聲明的語言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}；過程中使用的非局部數(shù)據(jù)不一定都是全局數(shù)據(jù)，也可能是其它過程定義的數(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的當前出現(xiàn)對應的是哪個聲明語句？在程序的不同部分可能有同一名字的互相獨立的聲明x的一個聲明的作用域(scope)是指程序的一個區(qū)域，在其中對x的使用都指向這個聲明如果僅通過閱讀程序就可以確定一個聲明的作用域，那么這個語言使用的是靜態(tài)作用域。否則，這個語言使用的是動態(tài)作用域包括C及其同類語言在內(nèi)的大多數(shù)語言使用靜態(tài)作用域C語言的作用域規(guī)則是基于程序結(jié)構(gòu)的，聲明的作用域由該聲明在程序中出現(xiàn)的位置隱含地決定稍后出現(xiàn)的語言，如C++、Java和

C#，也通過諸如public、private和protected等關鍵字的使用，提供對作用域的顯式的控制靜態(tài)作用域塊是聲明和語句的一個組合C使用括號“{”和“}”來界定一個塊另一種為同一目的使用begin和end的方法可以追溯到Algol塊結(jié)構(gòu)語言中聲明的靜態(tài)作用域規(guī)則如果名字x的聲明D屬于塊B，那么D的作用域包括整個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)語言中聲明的靜態(tài)作用域規(guī)則不支持過程嵌套聲明的語言在C系列語言中，各個變量要么在某個函數(shù)內(nèi)定義，要么在所有函數(shù)之外（全局地）定義一個全局變量v的作用域包含了該變量聲明后出現(xiàn)的所有函數(shù)，但那些存在標識符v的局部定義的地方除外在一個函數(shù)內(nèi)部聲明的變量的作用域就是這個函數(shù)，或者如果該函數(shù)具有嵌套的語句塊，這個變量的作用域可能是該函數(shù)的部分區(qū)域無過程嵌套聲明時的靜態(tài)作用域變量的存儲分配和訪問全局變量被分配在靜態(tài)區(qū)，使用靜態(tài)確定的地址訪問它們其它變量一定是棧頂活動的局部變量?？梢酝ㄟ^運行時刻棧的top_sp指針訪問它們無過程嵌套聲明時的數(shù)據(jù)訪問根據(jù)塊結(jié)構(gòu)語言的靜態(tài)作用域規(guī)則，只要過程a的聲明包含過程b的聲明，過程b就可以訪問過程a中聲明的對象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}；有過程嵌套聲明時的數(shù)據(jù)訪問運行時如何訪問在過程外聲明的數(shù)據(jù)？過程的嵌套深度不內(nèi)嵌在任何其它過程中的過程，設其嵌套深度為1如果一個過程p在一個嵌套深度為i的過程中定義，則設定p的嵌套深度為i+1變量的嵌套深度將變量聲明所在過程的嵌套深度作為該名字的嵌套深度嵌套深度

過程 嵌套深度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ī)則：只要過程b的聲明嵌套在過程a的聲明中，過程b就可以訪問過程a中聲明的對象可以在相互嵌套的過程的活動記錄之間建立一種稱為訪問鏈(Accesslink)的指針，使得內(nèi)嵌的過程可以訪問外層過程中聲明的對象如果過程b在源代碼中直接嵌套在過程a中(b的嵌套深度比a的嵌套深度多1)，那么b的任何活動中的訪問鏈都指向最近的a的活動訪問鏈(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活動樹sa訪問鏈控制棧

過程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3sr活動樹控制棧

過程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3sa訪問鏈ri訪問鏈r中的訪問鏈指向s的活動記錄，這不是因為s調(diào)用了r，而是因為在程序中，s是r外圍的最靠近r的嵌套函數(shù)sq(1,9)rp(1,9)活動樹sa訪問鏈控制棧

過程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

partition 3q(1,9)v訪問鏈p(1,9)i,j訪問鏈ee訪問鏈sq(1,9)rp(1,9)q(1,3)p(1,3)活動樹

過程 嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

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

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

過程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

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

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

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

過程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

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

過程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

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

(x→y)nx<ny的情況(外層調(diào)用內(nèi)層)nx=ny的情況(本層調(diào)用本層)遞歸調(diào)用(例如：q→q)被調(diào)用者的活動記錄的訪問鏈與調(diào)用者的活動記錄的訪問鏈是相同的，可以直接復制訪問鏈的建立sa訪問鏈q(1,9)v訪問鏈q(1,3)v訪問鏈p(1,3)i,j訪問鏈e訪問鏈

過程嵌套深度sort 1

readarray 2

exchange 2

quicksort 2

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

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

-ny

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

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

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

nx<ny的情況(例：

s→q,

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

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

D

D

D

D|procid;D

S|id:T;在允許嵌套過程聲明的語言中，局部于每個過程的名字可以使用第6章介紹的方法分配相對地址；當看到嵌套的過程p時，應暫時掛起對外圍過程q聲明語句的處理符號表的建立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)建一個新的符號表，并返回指向新表的指針。參數(shù)previous指向先前創(chuàng)建的符號表(外圍過程的符號表)enter(table,name,type,offset)在table指向的符號表中為名字name建立一個新表項addwidth(table,width)將table指向的符號表中所有表項的寬度之和width記錄在符號表的表頭中enterproc(table,name,newtable)在table指向的符號表中為過程name建立一條記錄，newtable指向過程name的符號表嵌套過程聲明語句的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