運(yùn)行時(shí)空間管理-變量訪問環(huán)境

變量環(huán)境堆區(qū)空間棧區(qū)空間靜態(tài)區(qū)空間目標(biāo)代碼空間庫代碼空間最大地址最小地址臨時(shí)變量區(qū)局部變量區(qū)形參區(qū)變量

環(huán)境活動(dòng)記錄大小寄存器狀態(tài)過程層數(shù)返回值返回地址動(dòng)態(tài)鏈指針sp過程活動(dòng)記錄top調(diào)用鏈、動(dòng)態(tài)鏈調(diào)用鏈：過程名序列若M是主程序名，則（M）是一個(gè)調(diào)用鏈；若(M,…,R)是調(diào)用鏈，且在R中有S的調(diào)用，則（

M,…,R,S）也是調(diào)用鏈。記為：CallChain(S)=(M,…,R,S)動(dòng)態(tài)鏈：如果有調(diào)用鏈CallChain(S)=(M,…,R,S)，則它對(duì)應(yīng)的動(dòng)態(tài)鏈為：

DynamicChain=[AR(M),…,AR(R),AR(S)]活躍活動(dòng)記錄(LAR)LiveAR（LAR）:一個(gè)過程S在動(dòng)態(tài)鏈中可有多個(gè)AR，但其中只有

AR(S

)是可

的，稱此AR(S)為S的活躍活動(dòng)記錄，并記為LiveAR(S)，簡寫為LAR（S）?；钴S活動(dòng)記錄(LAR)例：假設(shè)有當(dāng)前調(diào)用鏈?zhǔn)牵∕,P1,P2,Q1,

R1,R2,R3

)則當(dāng)前動(dòng)態(tài)AR鏈為[AR(M),AR(P1),AR(P2),AR(Q),AR(R1),AR(R2),AR(R3)]活躍活動(dòng)記錄LAR為：LAR(M

)

=

AR(M)LAR(Q

)

=AR(Q1)LAR(

P

)=AR(P2)LAR(

R)

=AR(R3)鏈和變量

環(huán)境過程鏈(DeclaChain):過程名序列（M）是過程鏈，M是主程序名；若(M,…,P)是過程

鏈，且P中有過程Q的

，則(M,…,P,Q)也是過程聲明鏈；記為：DeclaChain(Q)=(M,…,P,Q)當(dāng)前變量

環(huán)境VarVisitEnv:若DeclaChain(Q)=

[M,…,P,Q]則VarVisitEnv(LAR(Q))=[LAR(M),…,LAR(P),LAR(Q)]例子鏈，假設(shè)有當(dāng)前調(diào)用鏈?zhǔn)抢海∕,P,Q,R)為R的（M,P1,P2,Q1,R1,R2,R3

)則當(dāng)前動(dòng)態(tài)鏈為：[AR(M),AR(P1),AR(P2),AR(Q1),AR(R1),AR(R2),AR(R3)]R的當(dāng)前變量

環(huán)境:VarVisitEnv(LAR(R)

=[AR(M),AR(P2),AR(Q1),AR(R3)]非局部變量的實(shí)現(xiàn):環(huán)境:假設(shè)Q的變量VarVisitEnv（LAR（Q））=[LAR（M）,…，LAR（P），LAR（Q）]，在Q中有變量XQ，YM，ZP，它們分別定義在過程Q、M和P中，則它們的存儲(chǔ)單元地址可表示如下（其中<LAR（Q）>表示LAR（Q）的始地址，其它類似）：addr(

XQ

)=

<LAR（Q）>

+

OffsetXaddr(

YM

）=

<LAR（M）>

+

OffsetYaddr

(

ZP

）=<LAR（P）>

+

Offsez結(jié)論:

對(duì)于每個(gè)AR，只要知道了它的變量

環(huán)境VarVisitEnv（AR），即可實(shí)現(xiàn)包括非局部變量在內(nèi)的所有變量的

?！?/p>

…BeginPEndPROC

Q;Begin…end…

…PROC

P;BeginQEndPROC

P;…

…PROC

QBegin

End…

…Begin

Q

EndPROC

Q;…

…PROC

P;Begin

QEndBegin

End情況1：況3 P調(diào)用Q P層數(shù)(N

1)小于Q層數(shù)(N)D情ee情況4：P調(diào)用Q,P層數(shù)大于Q層數(shù)(N).D

DeclaChain(Q)=(M，P1,P2,…,PN-1,

Q)DeclaChain(P)=

(M，P1,

P2,…,PN-1,Q，…，P)如何計(jì)算當(dāng)前過程的變量環(huán)境情況4情況3情況2情況1PROC

P;如何計(jì)算當(dāng)前過程的變量環(huán)境定理：設(shè)[AR(M),…,AR(P),AR(Q)]DynamicChain(Q),且Q的層數(shù)為N，則有：VarVisitEnv(AR(Q))=VarVisitEnv(AR(P))N

AR(Q)結(jié)論：變量

環(huán)境可由先行過程的變量

環(huán)境求得.變量

環(huán)境的實(shí)現(xiàn)方法Display表方法全局表法局部表法

靜態(tài)鏈方法局部Display表方法

對(duì)于每個(gè)AR求出其變量

環(huán)境，并把它以地址表的形式(Display表）保存在AR中。因?yàn)槊總€(gè)AR都自帶Display表，稱這種方法為局部化Display表方法。

如果層數(shù)為N的過程P的變量

環(huán)境為：VarVisitEnv(AR(P))=[AR0,…,ARn],ari表示ARi的始地址，則[ar0,…,arn]是AR(P)的Display表.Display表的求法NewAR.Display=CurrentAR.Display的前N項(xiàng)newsp動(dòng)態(tài)鏈指針…

…Display表…

…newsp動(dòng)態(tài)鏈指針…

…Display表…

…sp[ar0,ar1,…,arN-1,…][ar0,ar1,…,arN-1,newsp]例：有過程M,Q,R,S，其中l(wèi)evel(M)=0;level(Q)=1;level(R)=1;level(S)=2，各AR的Display表分別如下：Z單元ar0ar1newspX單元Y單元AR(M)

AR(Q)

AR(R)AR(S)ar1ar2ar0spDisplay表Off-DisplaXs=sp+offx;Yq=sp+initoff[Ly]+offy;局部Display表時(shí)變量的對(duì)一個(gè)變量X(L,off)，地址為：當(dāng)L=CurrentAR.level時(shí)：addr(X)=sp+off否則:addr(X)=CurrentAR.Display[L]+off即[sp+D+L]+off靜態(tài)鏈的方法問題的提出例：假設(shè)有調(diào)用鏈(M,G,H,R,S),并且有Level(M)=0,

Level(G)=1,

Level(H)=2,Level(R)=3,Level(S)=3則相應(yīng)動(dòng)態(tài)鏈的基本結(jié)構(gòu)應(yīng)如下：[

AR0(M),

AR1(G),

AR2(H),

AR3(R),

AR4(S)

]如果用局部Display表方法，則Display表情況如下：AR0(M).Display=[ar0

]AR1(G).Display=[ar0,ar1

]AR2(H).Display=[ar0,ar1

,

ar2]AR3(R).Display=[ar0,ar1,

ar2,ar3]AR4(S).Display=[ar0,ar1,ar2,ar4]靜態(tài)鏈的方法原Display表部分變成一個(gè)單元，稱為靜態(tài)鏈單元，存放靜態(tài)鏈指針。靜態(tài)鏈指針的確定：若k=CurrentAR.level+1-NewAR.level，則

NewAR.StaticChainPointer=Indir(sp,k)

其中Indir(sp,k)表示sp的k次間接內(nèi)容。nilnilspAR0(M)

AR1(G)

AR3(R)AR2(H)AR4(S)ar1ar2ar3ar4AR0(M).DisplayAR1(G).DisplayAR2(H).DisplayAR3(R).DisplayAR4(S).Display=[

ar0

]=[

ar0,

ar1

]=[

ar0,

ar1

,

ar2

]=[

ar0,

ar1,

ar2,

ar3]=[

ar0,

ar1,

ar2,ar4]Level(M)=0,

Level(G)=1,

Level(H)=2,Level(R)=3,Level(S)=3ar0虛線為靜態(tài)鏈指針實(shí)線為動(dòng)態(tài)鏈指針使用靜態(tài)鏈時(shí)變量的變量X(L,off)的地址：若L=CurrentAR.Level,則addr(X)=sp+off若L=CurrentAR.Level+1-k,則addr(X)=

Indir(sp,k)+

off全局Display表

每個(gè)程序設(shè)置一個(gè)總的Display表，其長度為最大嵌套層數(shù)（最長

鏈的長度），其中Display[i]存放第i層

AR的指針,用D[i]表示。該方法的理論依據(jù)：在程序的任何一點(diǎn)，相同層數(shù)的過程

只能有一個(gè)有效。在AR中設(shè)置一個(gè)Resume單元，用來臨時(shí)保存某D[i]全局Display表當(dāng)層數(shù)為j的過程Q被調(diào)用時(shí)：將舊的D[j]的內(nèi)容保存到NewAR(Q)中：NewAR(Q).ResumeAddr

=

D[j];改寫D[j]的內(nèi)容：D[j]=NewAR(Q)的地址；當(dāng)退出Q時(shí)：恢復(fù)原來D[j]的內(nèi)容：D[j]

=

CurrentAR.ResumeAddr局部變量X(L,off,indir/dir)的X的地址：addr(X)=

D[L]+off例P{Q{R}R{S{R}S}Q}設(shè)P為0層有如下調(diào)用鏈：PQRSR210P210QP210R(Q)QP210SR(Q)QP210R(R)SR(Q)QPAR(T)過程P

過程Q

過程R

過程S

過程T全局Displayproc

P;（設(shè)P層數(shù)為1）proc

Q;（Q層數(shù)為2）begin

R

endproc

R;（R層數(shù)為2）proc

S;（S層數(shù)為3）begin

T

endproc

T;(T層數(shù)為3)begin

X(1,off

)…xY(2,offy)

…Z(3,offz)…endbegin

S

endbegin

Q

end……arQAR(P)arparRAR(Q)arSAR(R)arT←spAR(S)arPSaarrTD(3)D(2)D(1)D(0)arRQ………Z(…3…,…of…f…z)……ars動(dòng)態(tài)鏈（控制鏈）指針…………動(dòng)態(tài)鏈（控制鏈）指針………Y(…2…,…of…f…y)……arQ動(dòng)態(tài)鏈（控制鏈）指針…………動(dòng)態(tài)鏈（控制鏈）指針……X…(…1…,o…f…f…x)……AR(R)AR(S)AR(T)主程序P

過程Q

過程

R

過程

S

過程T全局Displayproc

P;（設(shè)P層數(shù)為1）proc

Q;Q層數(shù)為2begin

R

endproc

R;R層數(shù)為2proc

S;S層數(shù)為3begin

T

endproc

T;T層數(shù)為3begin

…

endbegin

S

endbegin

Q

end表……AR(P)arparQarRAR(Q)arSarTarParTSD(3)D(2)D(1)D(0)arRQ……………a…r…………s動(dòng)態(tài)鏈（控制鏈）指針…………動(dòng)態(tài)鏈（控制鏈）指針……………ar……………動(dòng)態(tài)鏈（控Q制鏈）指針…………動(dòng)態(tài)鏈（控制鏈）指針…………總結(jié)Display表方法是用表結(jié)構(gòu)表示變量

環(huán)境。局部Display表的產(chǎn)生需要花時(shí)間，但返回時(shí)不需要為恢復(fù)變量

環(huán)境做任何事情。對(duì)于全局Display