編譯原理課件：8-第八章-存儲(chǔ)空間組織-5節(jié)節(jié)選

§8.5嵌套過程語言的棧式存儲(chǔ)分配

（PASCAL語言）

§8.5.1語言特性：⑴.過程允許遞歸調(diào)用；⑵.可變數(shù)組；⑶.過程嵌套定義；

(內(nèi)層過程可引用外層過程定義的名字)層數(shù)：過程定義的嵌套層次；約定：主程序的層數(shù)=0；P中定義:Q,R，若P的層數(shù)=n,則：Q的層數(shù)=n+1；R的層數(shù)=n+1；稱：P是Q，R的直接外層過程，

Q,R是P的內(nèi)層過程

Q,R是同層的過程ProcPProcQProcRProgramP;

vara,x:integer;procedureQ(b:integer);

vari:integer;procedureR(u:integer;varv:integer);

varc,d:integer;begin…ifu=1thenR(u+1,v);v:=(a+c)*(b-d)+i;——L處

……end;{R}begin……R(1,x);……;end;{Q}procedureS;

varc,i:integer;begin…a:=1;Q(c);…end;{S}begina:=0;S;…end;{P,主程序}0層1層2層1層名字的作用域a,xb,iu,v,c,dc,i值參變參L處：P→S→Q→R1→R2數(shù)據(jù)區(qū)TOP→R2←c,dSP→R1Q←b,iSP←a返回pascal子程序的調(diào)用規(guī)定：⑴任何子程序都不能調(diào)用主程序。⑵任何子程序（包括主程序）可調(diào)用自己的直接內(nèi)層子程序，但不能調(diào)用隔層的內(nèi)層子程序。(圖1)⑶子程序可以調(diào)用自己，以及它的任何一層外層子程序（不包括主程序）。（圖2）P1P2CallP2P1調(diào)用P2P2是P1的直接內(nèi)層圖1P2調(diào)用P0P0是P2的外層P0P2P1CallP0圖2pascal子程序的調(diào)用規(guī)定：⑷并列子程序中后說明的可以調(diào)用先說明的，而先說明的不能調(diào)用后說明的（除非采用向前引用）。⑸一個(gè)子程序可以調(diào)用所有與自己的某個(gè)外層子程序并列的子程序（其說明先于這個(gè)外層子程序）。P0P1P2CallP2P1調(diào)用P2

P1、P2并列圖1圖2P0P2P1CallP1P3

P3調(diào)用P1

P1與P3的外層并列§8.5.2非局部名字的訪問的實(shí)現(xiàn)TOP→臨時(shí)單元內(nèi)情向量局部變量形參單元形參個(gè)數(shù)*靜態(tài)鏈\返回地址連接數(shù)據(jù)SP→動(dòng)態(tài)鏈(老SP)/1.實(shí)現(xiàn)方案Ⅰ：靜態(tài)鏈活動(dòng)記錄中，加“靜態(tài)鏈”，指向靜態(tài)直接外層過程的最新活動(dòng)記錄的地址(有多次調(diào)用時(shí),以最后一次為準(zhǔn))。數(shù)據(jù)區(qū)TOP→R2←c,dSP→R1Q←b,iSP←aR2中:v:=(a+c)*(b-d)+i;要訪問b,i(Q)，或a(P),必須知道外層過程的活動(dòng)記錄首址，即：SPQ

，SPP活動(dòng)記錄TOP→臨時(shí)單元內(nèi)情向量局部變量形參單元

主程序P沒有形參個(gè)數(shù)靜態(tài)鏈\返回地址連接數(shù)據(jù)SP→動(dòng)態(tài)鏈(老SP)/PASCAL中，主程序無參數(shù)項(xiàng)，所以主程序的活動(dòng)記錄中沒有形參單元、形參個(gè)數(shù)。P活動(dòng)記錄xL=5a靜態(tài)鏈:0返回地址老SP臨時(shí)單元內(nèi)情向量局部變量形參單元形參個(gè)數(shù)靜態(tài)鏈返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式過程參數(shù)局部名P(主)a,xQbiRu,vc,dSc,i

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}ProcPProcQProcRProcS程序結(jié)構(gòu)Q活動(dòng)記錄i形參單元:bL=6形參個(gè)數(shù):1靜態(tài)鏈:SPP返回地址老SP臨時(shí)單元內(nèi)情向量局部變量形參單元形參個(gè)數(shù)靜態(tài)鏈返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式過程參數(shù)局部名P(主)a,xQbiRu,vc,dSc,i

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}R活動(dòng)記錄dc形參單元:v形參單元:uL=8形參個(gè)數(shù):2靜態(tài)鏈:SPQ返回地址老SP臨時(shí)單元內(nèi)情向量局部變量形參單元形參個(gè)數(shù)靜態(tài)鏈返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式過程參數(shù)局部名P(主)a,xQbiRu,vc,dSc,i

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}臨時(shí)單元內(nèi)情向量局部變量形參單元形參個(gè)數(shù)靜態(tài)鏈返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式過程參數(shù)局部名P(主)a,xQbiRu,vc,dSc,iS活動(dòng)記錄icL=6形參個(gè)數(shù):0靜態(tài)鏈:SPP返回地址老SP

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}P活動(dòng)記錄xa靜態(tài)鏈:0返回地址老SPQ活動(dòng)記錄i形參單元:b形參個(gè)數(shù):1靜態(tài)鏈:SPP返回地址老SPR活動(dòng)記錄dc形參單元:v形參單元:u形參個(gè)數(shù):2靜態(tài)鏈:SPQ返回地址老SPS活動(dòng)記錄ic形參個(gè)數(shù):0靜態(tài)鏈:SPP返回地址老SP

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}過程參數(shù)局部名LPa,x5Qbi6Ru,vc,d8Sc,i6ProcPProcQProcRProcS程序結(jié)構(gòu)過程LP5Q6R8S6老SP：調(diào)用本過程時(shí)，調(diào)用者的SP;(動(dòng)態(tài)鏈)靜態(tài)鏈：本過程直接外層過程的最新SP；—靜態(tài)鏈—?jiǎng)討B(tài)鏈TOP→32R2靜態(tài)鏈=SPQ=11SP→25老SP=SPR1=1724R1靜態(tài)鏈=SPQ=1117老SP=SPQ=1116Q靜態(tài)鏈=SPP=011老SP=SPS=510S靜態(tài)鏈=SPP=05老SP=SPP=04P靜態(tài)鏈=00老SP=0調(diào)用順序：

P→S→Q→R1→R2訪問b(Q):=>SPQ=>4[SPQ]訪問a(P):=>SPQ=>SPP=>3[SPP]缺點(diǎn)：訪問速度慢?！o態(tài)鏈—?jiǎng)討B(tài)鏈TOP→32R2靜態(tài)鏈=SPQ=11SP→25老SP=SPR1=1724R1靜態(tài)鏈=SPQ=1117老SP=SPQ=1116Q靜態(tài)鏈=SPP=011老SP=SPS=510S靜態(tài)鏈=SPP=05老SP=SPP=04P靜態(tài)鏈=00老SP=0ProcPProcQProcRProcS程序結(jié)構(gòu)過程參數(shù)局部名Pa,xQbiRu,vc,dSc,i2.實(shí)現(xiàn)方案Ⅱ：DISPLAY表（嵌套層次顯示表）⑴.引入DISPLAY表設(shè)過程P,層數(shù)nP,D表有：nP+1項(xiàng)第nP

層,最新活動(dòng)記錄的首址=SPP……第1層，最新活動(dòng)記錄的首址SP第0層，最新活動(dòng)記錄的首址SPR的DISPLAY表SPR2SPQ1SPP0ProcPProcQProcRProcS程序結(jié)構(gòu)過程層數(shù)P0Q1R2S1第nP

層,最新活動(dòng)記錄的首址=SPP……第1層，最新活動(dòng)記錄的首址SP第0層，最新活動(dòng)記錄的首址SP調(diào)用順序：P→S→Q→R1→R2數(shù)據(jù)區(qū)R2R1QSPR2D表SPR22SPQ1SPP0ProcPProcQProcRProcS程序結(jié)構(gòu)過程層數(shù)P0Q1R2S1名字地址=DISPLAY[靜態(tài)層數(shù)]+相對(duì)數(shù)訪問b(Q):=>DISPLAY[1]+相對(duì)數(shù)

=相對(duì)數(shù)[SPQ]訪問a(P):=>DISPLAY[0]+相對(duì)數(shù)

=相對(duì)數(shù)[SPP]數(shù)據(jù)區(qū)R2R1QSPR2D表SPR22SPQ1SPP0ProcPProcQProcRProcS過程層數(shù)參數(shù)局部名P0a,xQ1biR2u,vc,dS1c,i調(diào)用順序：P→S→Q→R1→R2⑵.活動(dòng)記錄格式：其中：*為新增項(xiàng)全局DISPLAY：指向調(diào)用者的

DISPLAY表的位置；DISPLAY表：本過程的嵌套層次顯示表；主程序沒有:參數(shù)項(xiàng)，全局DISPLAY。臨時(shí)單元內(nèi)情向量局部變量*DISPLAY表↑形參單元

形參個(gè)數(shù)*全局DISPLAYｄ返回地址↓動(dòng)態(tài)鏈(老SP)連接數(shù)據(jù)∵過程的層數(shù)是靜態(tài)確定的，∴D表的大小是靜態(tài)確定的（=層數(shù)+1）。又∵過程的形參單元的數(shù)目在編譯時(shí)是可以確定的，∴D表的相對(duì)地址d也是靜態(tài)確定的。返回P1PCallPa)子程序可調(diào)用自己的直接內(nèi)層子程序則層數(shù)：nP

=

nP1+1P的D表中，共有nP+1項(xiàng)，∵P的直接外層是P1，∴“P的D表前nP項(xiàng)”與“P1的D表”相同⑶.構(gòu)造DISPLAY表PASCAL的過程調(diào)用，有4種情況：即：DP=DP1+SPP

=DP1前nP項(xiàng)+SPP

=調(diào)用者D表的前nP項(xiàng)+SPP全局DISPLAY:

指向調(diào)用者的

D表的位置P1調(diào)用P

P是P1的直接內(nèi)層b)子程序可以調(diào)用自己，以及它的任何一層外層子程序P的D表中，共有nP+1項(xiàng)，∵P是P2的外層，∴“P的D表前nP項(xiàng)”與“P2的D表前nP項(xiàng)”相同即：DP=DP2前nP項(xiàng)+SPP

=調(diào)用者D表的前nP項(xiàng)+SPP全局DISPLAY:

指向調(diào)用者的

D表的位置

P2調(diào)用P

P是P2的外層PP2P1CallPP0P1PCallPc)并列子程序中后說明的調(diào)用先說明的

層數(shù)：nP=nP1=nP0+1∵P的直接外層是P0，∴P的D表前nP項(xiàng)與P0的D表相同，即：DP=DP0+SPP同理，P1的D表前nP1項(xiàng)與P0的D表相同，即：DP1=DP0+SPP1∴DP=DP0+SPP

=DP1前nP項(xiàng)+SPP=調(diào)用者D表的前nP項(xiàng)+SPP全局DISPLAY：指向調(diào)用者的

D表的位置；P1調(diào)用PP1、P并列d)子程序調(diào)用與自己的某個(gè)外層子程序并列的子程序

P的D表中，共有nP+1項(xiàng)，

其中前nP項(xiàng)與P0的D表相同，即：DP=DP0+SPP又∵P0也是也是P3的直接外層，∴P3的D表的前nP項(xiàng)與P0的D表相同∴DP=DP0+SPP

=DP3前nP項(xiàng)+SPP=調(diào)用者D表的前nP項(xiàng)+SPP全局DISPLAY：指向調(diào)用者的

D表的位置；P0P2PCallPP3P3調(diào)用PP與P3的外層并列若有過程：P，Q，RP調(diào)用Q

，

Q遞歸調(diào)用自己m次，

Q調(diào)用R，則有：

DQ1=DP前nQ項(xiàng)+SPQ1DQ2=DQ1前nQ項(xiàng)+SPQ2=DP前nQ項(xiàng)+SPQ2

…

DQm

=DQm-1前nQ項(xiàng)+SPQm

=DP前nQ項(xiàng)+SPQmDQm+1=DQm前nQ項(xiàng)+SPQm+1=DP前nQ項(xiàng)+SPQm+1DR=DQm+1前nR項(xiàng)+SPR過程層數(shù)D表項(xiàng)數(shù)PnPnP

+1QnQnQ

+1RnRnR

+1臨時(shí)單元內(nèi)情向量局部變量Display表形參單元形參個(gè)數(shù)全局Display返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式過程層數(shù)參數(shù)局部名LP0a,x5Q1biR2u,vc,dS1c,i

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}P活動(dòng)記錄xL=5aSPPD表返回地址老SP主程序沒有

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}iSPQD表SPP形參單元:b形參個(gè)數(shù):1全局Display返回地址老SPL=8過程層數(shù)參數(shù)局部名LP0a,x5Q1bi8R2u,vc,dS1c,iQ活動(dòng)記錄局部變量/內(nèi)情向量/臨時(shí)單元Display表形參個(gè)數(shù)、形參單元全局Display返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式局部變量/內(nèi)情向量/臨時(shí)單元Display表形參個(gè)數(shù)、形參單元全局Display返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}dcSPRD表SPQSPP形參單元:v形參單元:u形參個(gè)數(shù):2全局Display返回地址老SP過程層數(shù)參數(shù)局部名LP0a,x5Q1bi8R2u,vc,d11S1c,iR活動(dòng)記錄局部變量/內(nèi)情向量/臨時(shí)單元Display表形參個(gè)數(shù)、形參單元全局Display返回地址動(dòng)態(tài)鏈(老SP)活動(dòng)記錄格式

ProgramP;

var

a,x:integer;procedureQ(b);

vari:integer;procedureR(u,v);

varc,d:integer;begin…end;{R}begin…end;{Q}procedureS;

varc,i:integer;begin…end;{S}begin…end;{P}icSPSD表SPP形參個(gè)數(shù):0全局Display返回地址老SP過程層數(shù)參數(shù)局部名LP0a,x5Q1bi8R2u,vc,d11S1c,i8S活動(dòng)記錄P活動(dòng)記錄xaSPPD表返回地址老SPL=5Q活動(dòng)記錄iSPQD表SPP形參單元:b形參個(gè)數(shù):1全局DISPLAY返回地址老SPL=8R活動(dòng)記錄dcSPRD表SPQSPP形參單元:v形參單元:u形參個(gè)數(shù):2全局DISPLAY返回地址老SPL=11S活動(dòng)記錄icSPQD表SPP形參個(gè)數(shù):0全局DISPLAY返回地址老SPL=8返回過程層數(shù)參數(shù)局部名LP0a,x5Q1bi8R2u,vc,d11S1c,i8§8.5.3主要處理工作

1.過程調(diào)用(紅色標(biāo)注)中間代碼

parT1…parTnCallP,n(n:參數(shù)個(gè)數(shù))+5形式單元+4參數(shù)個(gè)數(shù)+3全局DISPLAY+2返回地址+1老SPTOP→R1SP→QSP對(duì)：ParTi(i=1～n),(i+4)[TOP]:=Addr[Ti](傳地址)或：(i+4)[TOP]:=Ti(傳值)對(duì)：CallP,n*

1[TOP]:=SP（保護(hù)工作環(huán)境）*4[TOP]:=n(參數(shù)個(gè)數(shù))*3[TOP]:=全局DISPLAY=SP+d*JSRP(轉(zhuǎn)子)P→S→Q→R1→R2返回2.過程進(jìn)入(藍(lán)色標(biāo)注)⑴.建立新工作環(huán)境⑵.保護(hù)返回地址具體工作：*SP:=TOP+1(新SP)*1[SP]=返回地址

*

TOP:=TOP+L(新TOP)

(L：活動(dòng)記錄大小，靜態(tài)確定)*

建立本過程的D表,若層數(shù)=n,

從全局display地址開始，向上n個(gè)單元的內(nèi)容抄錄到現(xiàn)行活動(dòng)記錄的DISPLAY表中，再添上當(dāng)前SP，形成D表。新TOP→…DISPLAY表形式單元參數(shù)個(gè)數(shù)全局DISPLAY+1返回地址新SP→老SPTOP→R1SP→QSP返回3.數(shù)組分配空間⑴對(duì)可變數(shù)組，計(jì)算每維的上限、下限、維長(zhǎng)，填入內(nèi)情向量；⑵將TOP+1填入數(shù)組內(nèi)情向量的a處(起始地址)；⑶設(shè)數(shù)組大小=M，TOP:=TOP+M

；4.引用各種數(shù)據(jù)的方式⑴參數(shù)、局部量、臨時(shí)單元、內(nèi)情向量：設(shè)相對(duì)數(shù)=x，以SP為變址器訪問：x[SP]⑵數(shù)組元素*從內(nèi)情向量查出a，C，維長(zhǎng)等，計(jì)算出相對(duì)數(shù)x；*變址訪問x[a]⑶非局部量：設(shè)：相對(duì)數(shù)=x，

所在層數(shù)=k，

D表的相對(duì)數(shù)=d，（d[SP]：活動(dòng)記錄起始地址）

LDR1,(d+k)[SP](第k層過程的最新活動(dòng)記錄的SP)

LDR2,x[R1](取出值傳送到R2)5.過程返回

（與C相同）中間代碼：

proc過程名過程體

return(m)

endproc過程返回*由return引起*過程結(jié)束自然返回⑴過程返回值存入特定位置⑵恢復(fù)老的工作環(huán)境

TOP:=SP-1SP:=0[SP]⑶按返回地址轉(zhuǎn)移

X:=2[TOP]（返回地址）

UJ0[X]（無條件轉(zhuǎn)移）TOP→…DISPLAY表形式單元參數(shù)個(gè)數(shù)全局DISPLAY+1返回地址SP→老SPTOP→R1SP→QSP過程LP5Q8R11S8示例程序活動(dòng)記錄13TOP→12Si11c105D表9080參數(shù)個(gè)數(shù)72全局Display6返回地址SP→50老SPTOP→4Px3a20D表1返回地址SP→00老SP調(diào)用：

P→S過程調(diào)用過程進(jìn)入返回TOP→20Qi1913D表18017b參數(shù)161參數(shù)個(gè)數(shù)159全局Display14返回地址SP→135老SPTOP→12Si11c105D表9080參數(shù)個(gè)數(shù)72全局Display6返回地址SP→50老SP4P0調(diào)用：

P→S→Q示例程序活動(dòng)記錄返回過程調(diào)用過程進(jìn)入過程LP5Q8R11S8TOP→31R1d30c2921D表281327026v參數(shù)25u參數(shù)242參數(shù)個(gè)數(shù)2318全Display22返回地址SP→2113老SPTOP→20Qi1913D表18017b參數(shù)調(diào)用：

P→S→Q→R116Q1參數(shù)個(gè)數(shù)159全Di