研究生院第七章

第七章 運(yùn)行環(huán)境源語(yǔ)言問(wèn)題存儲(chǔ)組織存儲(chǔ)分配策略訪問(wèn)非局部名字參數(shù)傳遞靜態(tài)和動(dòng)態(tài)靜態(tài)和動(dòng)態(tài)的聯(lián)系名字和數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象的動(dòng)態(tài)表示名字的作用域數(shù)據(jù)對(duì)象的存儲(chǔ)分配過(guò)程和活動(dòng)參數(shù)處理運(yùn)行時(shí)支撐程序包源語(yǔ)言問(wèn)題（1）過(guò)程及其執(zhí)行過(guò)程定義：是一個(gè)聲明，最簡(jiǎn)單形式是把一個(gè)標(biāo)識(shí)符和一個(gè)語(yǔ)句聯(lián)系起來(lái)該標(biāo)識(shí)符稱為過(guò)程名語(yǔ)句是過(guò)程體函數(shù)：返回值的過(guò)程過(guò)程調(diào)用過(guò)程名出現(xiàn)在可執(zhí)行語(yǔ)句中時(shí)，則稱這個(gè)過(guò)程在這點(diǎn)被調(diào)用調(diào)用者、被調(diào)用者和調(diào)用點(diǎn)參數(shù)形式參數(shù)：與局部變量有不同實(shí)在參數(shù)：在調(diào)用點(diǎn)，將其傳遞給被調(diào)用的過(guò)程源語(yǔ)言問(wèn)題（2）

programsort(input,output); vara:array[0..10]ofinteger; procedurereadarray; vari:integer; begin fori:=1to9read(a[i]) end; functionpartition(m,n:integer); vari,j,x,v:integer; begin …. end; procedurequicksort(m,n:integer); vari:integer; begin if(n>m)thenbegin i:=partiton(m,n);quicksort(m,i–1);quicksort(i+1,n); end end; begin a[0]:=-9999;a[10]:=9999;readarray;quicksort(1,9) end.源語(yǔ)言問(wèn)題（3）過(guò)程的執(zhí)行的表示：活動(dòng)樹(shù)控制流的假設(shè)控制流是連續(xù)的過(guò)程的每次執(zhí)行都從過(guò)程體的起點(diǎn)開(kāi)始，最后控制返回到直接跟隨本次調(diào)用點(diǎn)的位置過(guò)程間的控制流可以用樹(shù)表示（調(diào)用樹(shù)）活動(dòng)：過(guò)程體的一次執(zhí)行活動(dòng)的生存期：過(guò)程體執(zhí)行的第一步和最后一步之間的步序列包括直接或間接被這個(gè)過(guò)程調(diào)用的其它過(guò)程的時(shí)間過(guò)程的活動(dòng)的生存期要么是不重疊的，要么是嵌套的遞歸：如果一個(gè)過(guò)程的前一個(gè)活動(dòng)結(jié)束前，它的一個(gè)新的活動(dòng)又開(kāi)始遞歸的兩種緣起源語(yǔ)言問(wèn)題（4）活動(dòng)樹(shù)描述控制進(jìn)入和離開(kāi)活動(dòng)：每個(gè)結(jié)點(diǎn)代表過(guò)程的一個(gè)活動(dòng)根結(jié)點(diǎn)代表主程序的活動(dòng)結(jié)點(diǎn)a是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入ba結(jié)點(diǎn)處于b結(jié)點(diǎn)的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期結(jié)點(diǎn)和活動(dòng)是一一對(duì)應(yīng)的源語(yǔ)言問(wèn)題（5）幻燈片4中程序的活動(dòng)樹(shù)源語(yǔ)言問(wèn)題（6）控制?？刂茥Ｓ糜诒４婊钴S著的過(guò)程棧的內(nèi)容表示活動(dòng)樹(shù)上到根結(jié)點(diǎn)的一條路徑源語(yǔ)言問(wèn)題（7）名字與數(shù)據(jù)對(duì)象聲明的作用域區(qū)分同名程序聲明：最接近的嵌套規(guī)則

inta,b; int*p; intfoo(inta) { intb,c; char*p; p=malloc(sizeof(char)); b=foo(1);… }作用域：一個(gè)聲明起作用的程序部分稱為該聲明的作用域局部和非局部：過(guò)程中名字的出現(xiàn)，如果是在該過(guò)程的一個(gè)聲明的作用域內(nèi)，則這個(gè)出現(xiàn)稱為局部于該過(guò)程源語(yǔ)言問(wèn)題（8）名字的結(jié)合程序中聲明的名字和動(dòng)態(tài)數(shù)據(jù)對(duì)象的關(guān)系數(shù)據(jù)對(duì)象是保存值的存儲(chǔ)單元一個(gè)名字可能代表不同的數(shù)據(jù)對(duì)象環(huán)境：表示將名字映射到存儲(chǔ)單元（即名字的左值）的函數(shù)狀態(tài)：表示將存儲(chǔ)單元映射到它所保存的值（即名字的右值）的函數(shù)賦值操作只改變狀態(tài)，但不改變環(huán)境結(jié)合：如果環(huán)境把存儲(chǔ)單元s聯(lián)系到名字x，則稱x結(jié)合到s，這個(gè)聯(lián)系本身稱為x的結(jié)合 靜態(tài)概念 動(dòng)態(tài)概念過(guò)程的定義 過(guò)程的活動(dòng)名字的聲明 名字的結(jié)合聲明的作用域 結(jié)合的生存期源語(yǔ)言問(wèn)題（9）名字結(jié)合要考慮的問(wèn)題過(guò)程是否遞歸當(dāng)控制從過(guò)程的活動(dòng)返回時(shí)，局部名字的值是否要保留過(guò)程能否引用非局部的名字過(guò)程調(diào)用時(shí)參數(shù)是如何傳遞的過(guò)程是否可以作為參數(shù)被傳遞過(guò)程能否作為結(jié)果值返回存儲(chǔ)區(qū)能否在程序控制下動(dòng)態(tài)地分配存儲(chǔ)區(qū)是否必須顯式地釋放存儲(chǔ)組織（1）運(yùn)行時(shí)內(nèi)存的劃分程序運(yùn)行時(shí)如何使用內(nèi)存：目標(biāo)代碼的存放目標(biāo)代碼可以存放在靜態(tài)確定的區(qū)域，其長(zhǎng)度在編譯時(shí)即可確定數(shù)據(jù)對(duì)象可靜態(tài)分配的數(shù)據(jù)對(duì)象，其地址可以編譯到目標(biāo)代碼中動(dòng)態(tài)分配控制棧：記錄過(guò)程活動(dòng)堆：可以存放動(dòng)態(tài)分配的數(shù)據(jù)等，但開(kāi)銷要比棧大存儲(chǔ)組織（2）活動(dòng)記錄定義：過(guò)程的一次執(zhí)行所需要的信息用一塊連續(xù)的存儲(chǔ)區(qū)來(lái)管理，這塊存儲(chǔ)區(qū)叫做活動(dòng)記錄或幀一般的活動(dòng)記錄結(jié)構(gòu)如右圖，但不是所有的語(yǔ)言或編譯器都是如此寄存器的使用活動(dòng)記錄的操作：過(guò)程被調(diào)用時(shí)入棧過(guò)程返回時(shí)出棧存儲(chǔ)組織（3）活動(dòng)記錄的各個(gè)域的作用臨時(shí)數(shù)據(jù)域：臨時(shí)變量的存儲(chǔ)等局部數(shù)據(jù)域：局部于過(guò)程執(zhí)行的數(shù)據(jù)機(jī)器狀態(tài)：保存過(guò)程調(diào)用前的機(jī)器狀態(tài)信息返回地址可選的訪問(wèn)鏈：用于非局部數(shù)據(jù)的訪問(wèn)可選的控制鏈：指向調(diào)用者的活動(dòng)記錄實(shí)在參數(shù)域：參數(shù)個(gè)數(shù)較少時(shí)，可以考慮用寄存器傳遞，效率高；參數(shù)多時(shí)用用這個(gè)域傳遞返回值域：用于存放被調(diào)用過(guò)程返回給調(diào)用過(guò)程的值，也可以用寄存器返回（效率高，但形式受限制）存儲(chǔ)組織（4）過(guò)程調(diào)用時(shí)，每個(gè)域的長(zhǎng)度都可以確定，大部分域的長(zhǎng)度可以在編譯時(shí)刻確定運(yùn)行框架安排的設(shè)計(jì)這個(gè)框架的設(shè)計(jì)要考慮指令集體系結(jié)構(gòu)（ISA）特性和要編譯的程序語(yǔ)言本身的特點(diǎn)有些系統(tǒng)提供商為他們的體系結(jié)構(gòu)提供一種標(biāo)準(zhǔn)的運(yùn)行框架安排，使得可以實(shí)現(xiàn)不同的語(yǔ)言編寫的函數(shù)間的調(diào)用這個(gè)運(yùn)行框架的設(shè)計(jì)通常在運(yùn)行時(shí)支撐系統(tǒng)要考慮存儲(chǔ)組織（5）編譯時(shí)的局部數(shù)據(jù)安排名字所需的存儲(chǔ)空間的大小可以由它的類型確定基本數(shù)據(jù)對(duì)象（字符、整數(shù)或?qū)崝?shù)）可以用幾個(gè)連續(xù)的字節(jié)保存聚合類型（記錄、數(shù)組等）一塊足夠大的空間存放所有成分連續(xù)的字節(jié)區(qū)局部數(shù)據(jù)域在編譯過(guò)程中的聲明時(shí)安排長(zhǎng)度可變的數(shù)據(jù)不保存在這個(gè)區(qū)域數(shù)據(jù)對(duì)象的相對(duì)地址（偏移）是數(shù)據(jù)對(duì)象地址相對(duì)于特定點(diǎn)（例如活動(dòng)記錄的開(kāi)始點(diǎn)）的地址差數(shù)據(jù)對(duì)齊：數(shù)據(jù)對(duì)象的存儲(chǔ)安排受目標(biāo)機(jī)器尋址限制的影響如10個(gè)字符的數(shù)組可以被編譯器分配12個(gè)字節(jié)不用的2個(gè)字節(jié)稱為襯墊空白區(qū)存儲(chǔ)組織（6）兩個(gè)C編譯器的數(shù)據(jù)布局形式：存儲(chǔ)分配策略（1）靜態(tài)分配名字的結(jié)合：編譯時(shí)實(shí)現(xiàn)，不需要運(yùn)行時(shí)支撐程序名字和存儲(chǔ)的結(jié)合是固定的允許名字的值在過(guò)程停止活動(dòng)后保持根據(jù)名字的類型，編譯器可以在靜態(tài)時(shí)刻確定該名字所需的存儲(chǔ)空間，效率局限：數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中位置的限制必須在編譯時(shí)知道不允許遞歸過(guò)程不允許有動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)在FORTRAN77中，靜態(tài)存儲(chǔ)分配策略，每個(gè)過(guò)程的活動(dòng)記錄可以與它的代碼放在一起存儲(chǔ)分配策略（2）

PROGRAMCNSUME CHARACTER*50 BUF INTEGER NEXT CHARACTER C,PRDUCE DATANEXT/1/,BUF/‘’/6 C=PRDUCE() BUF(NEXT,NEXT)=C NEXT=NEXT+1 IF(C.NE.‘’)GOTO6 WRITE(*,‘(A)’)BUF END CHARACTERFUNCTIONPRDUCE() CHARACTER*80 BUFFER INTEGER NEXT SAVEBUFFER,NEXT DATANEXT/81/ IF(NEXT.GT.80)THEN READ(*,‘(A)’)BUFFER NEXT=1 ENDIF PRDUCE=BUFFER(NEXT,NEXT) NEXT=NEXT+1 END存儲(chǔ)分配策略（3）存儲(chǔ)分配策略（4）棧分配遞歸過(guò)程要求棧分配允許動(dòng)態(tài)數(shù)據(jù)對(duì)象的存在滿足先入后出的次序控制棧：活動(dòng)記錄和棧的關(guān)系局部量的存儲(chǔ)空間包含在對(duì)應(yīng)調(diào)用的活動(dòng)記錄中局部量的值會(huì)隨著過(guò)程調(diào)用結(jié)束而丟失控制棧top的變化和活動(dòng)記錄的長(zhǎng)度相關(guān)通常，局部量相對(duì)于活動(dòng)記錄開(kāi)始點(diǎn)的偏移量可以記錄在符號(hào)表中存儲(chǔ)分配策略（5）例：活動(dòng)記錄在棧中的分配存儲(chǔ)分配策略（6）例：編譯時(shí)確定長(zhǎng)度的數(shù)據(jù)對(duì)象偏移量在符號(hào)表中的存放存儲(chǔ)分配策略（7）過(guò)程調(diào)用的實(shí)現(xiàn)：通過(guò)過(guò)程調(diào)用序列（callingsequences）實(shí)現(xiàn)，包括調(diào)用序列和返回序列調(diào)用序列：分配活動(dòng)記錄，信息的保存和填充參數(shù)、返回地址、老的控制棧top、寄存器的保存、局部對(duì)象的初始化等返回序列：恢復(fù)機(jī)器狀態(tài)，是調(diào)用者繼續(xù)執(zhí)行返回值、寄存器的恢復(fù)、重置控制棧top、跳轉(zhuǎn)到返回地址調(diào)用序列和活動(dòng)記錄不是一成不變的，語(yǔ)言、實(shí)現(xiàn)等都會(huì)導(dǎo)致不同過(guò)程調(diào)用序列的代碼分成兩部分，分別由調(diào)用過(guò)程和被調(diào)用過(guò)程負(fù)責(zé)，但劃分的界限不是唯一的存儲(chǔ)分配策略（8）圖：調(diào)用者和被調(diào)用者間的任務(wù)劃分存儲(chǔ)分配策略（9）調(diào)用序列（callsequences），過(guò)程p調(diào)用過(guò)程qp計(jì)算實(shí)參，依次放入q的活動(dòng)記錄中（也可以利用寄存器傳遞參數(shù)），改變top_sp的值p把返回地址和當(dāng)前的base_sp的值存入q的活動(dòng)記錄中，建立q的訪問(wèn)鏈，增加base_sp的值q保存寄存器的值（包括top_sp的值）和其它機(jī)器狀態(tài)信息q增加top_sp的值，初始化它的局部數(shù)據(jù)，并開(kāi)始執(zhí)行存儲(chǔ)分配策略（10）返回序列（returnsequences），過(guò)程p調(diào)用過(guò)程qq把返回值置入鄰近p的活動(dòng)記錄的地方（也可以利用特定的寄存器傳遞返回值）q恢復(fù)寄存器的值（包括top_sp和base_sp）和其它機(jī)器狀態(tài)信息q根據(jù)返回地址將控制返回pp根據(jù)參數(shù)個(gè)數(shù)調(diào)整top_sp的值，把返回值放入自己的活動(dòng)記錄中參數(shù)個(gè)數(shù)不確定？C語(yǔ)言中的printf保存描述參數(shù)的信息，如printf首先處理的第一個(gè)變?cè)ㄋ奈恢檬谴_定的）指出了其它參數(shù)的性質(zhì)存儲(chǔ)分配策略（11）動(dòng)態(tài)數(shù)組數(shù)組的界在編譯時(shí)刻無(wú)法確定，只能在運(yùn)行時(shí)刻確定procedure(n) integern,m[n] …end動(dòng)態(tài)數(shù)組不能分配在活動(dòng)記錄中在動(dòng)態(tài)數(shù)組的大小確定后，在該過(guò)程的活動(dòng)記錄緊鄰的棧中分配空間動(dòng)態(tài)數(shù)組的描述也可以考慮用內(nèi)情向量的方式存儲(chǔ)分配策略（12）動(dòng)態(tài)數(shù)組訪問(wèn)的示意存儲(chǔ)分配策略（13）懸空引用引用某個(gè)已釋放的存儲(chǔ)單元稱為懸空引用這是由于存儲(chǔ)空間可以釋放這是一個(gè)邏輯錯(cuò)誤：在大多數(shù)語(yǔ)言中，釋放的存儲(chǔ)單元的值是沒(méi)有定義的

main() { int*p; p:=dangle(); } int*dangle() { inti=23; return&i; }函數(shù)dangle返回后，指針p指向一個(gè)已釋放的存儲(chǔ)單元存儲(chǔ)分配策略（14）堆分配棧分配的局限不能使得活動(dòng)停止時(shí)，局部名字的值保持被調(diào)用者的活動(dòng)不能比調(diào)用者的活動(dòng)活得更長(zhǎng)（否則，活動(dòng)樹(shù)不能正確描繪過(guò)程間的控制流），只能滿足先入后出的次序堆分配把連續(xù)存儲(chǔ)區(qū)域分成塊需要時(shí)分配（活動(dòng)記錄或其它對(duì)象）釋放次序任意堆可以與棧分配結(jié)合起來(lái)C++語(yǔ)言中，基本保持棧的形式，堆用于動(dòng)態(tài)對(duì)象的分配C、Pascal語(yǔ)言中的指針的動(dòng)態(tài)分配等存儲(chǔ)分配策略（15）堆中，活躍的活動(dòng)記錄不一定相臨，可能存在空洞存儲(chǔ)分配策略（16）堆的釋放不釋放存儲(chǔ)空間溢出時(shí)停止顯式釋放Free（C，PL/1），deallocation（Ada）…有可能引起懸掛引用隱式釋放單引用引用計(jì)數(shù)垃圾收集（Garbagecollection）堆的分配和釋放的優(yōu)化訪問(wèn)非局部名字（1）如何通過(guò)活動(dòng)記錄正確訪問(wèn)名字，滿足作用域的要求？?jī)煞N作用域靜態(tài)作用域根據(jù)程序正文決定用于名字的聲明最接近的嵌套規(guī)則程序塊非局部名字的訪問(wèn)：訪問(wèn)鏈動(dòng)態(tài)作用域在運(yùn)行時(shí)，根據(jù)現(xiàn)行的活動(dòng)來(lái)決定用于名字的聲明，如Lisp等訪問(wèn)非局部名字（2）程序塊定義：起源于AlgolC語(yǔ)言中的定義：{declarationsstatements}允許嵌套最接近的嵌套規(guī)則：程序塊B中聲明的作用域包括B如果名字x沒(méi)有在B中聲明，則B中x的出現(xiàn)是在外圍程序塊B’的x聲明的作用域中，且滿足：B’有x的聲明B’比其它任何含x聲明的程序塊更接近被嵌套的B訪問(wèn)非局部名字（3）例：非局部名字的引用main(){inta=0;intb=0;{intb=1;{inta=2;printf(“%d,%d\n”,a,b);}{intb=3;printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}B0B1B2B3聲明作用域inta=0;B0-B2intb=0;B0-B1intb=1;B1-B3inta=2;B2intb=3;B321030100訪問(wèn)非局部名字（4）名字的存儲(chǔ)分配：基于棧分配：聲明的作用域決不超出它所在的程序塊程序塊當(dāng)作無(wú)參的過(guò)程，所以活動(dòng)記錄可以是程序塊的這類“過(guò)程”調(diào)用不需要參數(shù)傳遞，控制只能沿靜態(tài)正文進(jìn)入和退出程序塊每次為一個(gè)完整的過(guò)程體分配存儲(chǔ)空間只為過(guò)程分配活動(dòng)記錄過(guò)程內(nèi)嵌套的程序塊的生命所需要的存儲(chǔ)空間由過(guò)程負(fù)責(zé)留出要分配的變量在編譯時(shí)刻確定，不考慮控制流作用域不重疊的聲明可以共享一個(gè)存儲(chǔ)區(qū)域

a0 b0 b1 a2,b3訪問(wèn)非局部名字（5）無(wú)過(guò)程嵌套的靜態(tài)作用域一個(gè)過(guò)程的定義不能出現(xiàn)在另一個(gè)過(guò)程里面，如C語(yǔ)言對(duì)某個(gè)過(guò)程非局部的名字（過(guò)程中程序塊的非局部名字的處理見(jiàn)前面的內(nèi)容），其聲明在所有函數(shù)之外函數(shù)外聲明的作用域：該聲明后的所有函數(shù)體，但同名的局部聲明的出現(xiàn)將掩蓋全局聲明的作用例： inta[11]; readarray(){……a……} intpartition(y,z)inty,z;{……a……} quicksort(m,n)intm,n;{……} main(){……a……}訪問(wèn)非局部名字（6）存儲(chǔ)分配比較簡(jiǎn)單：聲明在任何過(guò)程外的所有名字的存儲(chǔ)單元靜態(tài)分配，其存儲(chǔ)位置在編譯時(shí)可知過(guò)程中可見(jiàn)的名字：非過(guò)程局部的，則使用靜態(tài)確定的地址訪問(wèn)其它的名字，局部于棧頂?shù)幕顒?dòng)紀(jì)錄，可以通過(guò)base_sp訪問(wèn)重要好處：程序中聲明的過(guò)程可以作為參數(shù)傳遞和作為結(jié)果返回（C語(yǔ)言中是傳遞過(guò)程的指針）非局部名字的訪問(wèn)不受過(guò)程激活方式的影響訪問(wèn)非局部名字（7）例： programpass(input,output); varm:integer; functionf(n:integer):integer; beginf:=m+nend{f}; functiong(n:integer):integer; beging:=m*nend{g}; procedureb(functionh(n:integer):integer); beginwrite(h(2))end; begin

m:=0; b(f);b(g);writeln end.變量m對(duì)所有的過(guò)程是非局部的，可以靜態(tài)分配它的存儲(chǔ)單元執(zhí)行結(jié)果是：20訪問(wèn)非局部名字（8）有過(guò)程嵌套的靜態(tài)作用域非局部名字的訪問(wèn)：尋找最接近的嵌套聲明，如下面例子中函數(shù)partition對(duì)a的訪問(wèn)

programsort(input,output);

vara:array[0..10ofinteger;x:integer;procedurereadarray;vari:integer;begin…a…end{readarray};procedureexchange(i,j:integer);beginx:=a[i];a[i]:=a[j];a[j]:=x;end{exchange};procedurequicksort(m,n:integer);vark,v:integer; functionpartition(y,z:integer):integer vari,j:integer; begin…a…;…v…;…exchange(i,j);…end begin……end{quicksort};begin……end{sort}.訪問(wèn)非局部名字（9）嵌套深度：過(guò)程的嵌套深度設(shè)主程序的嵌套深度是1從一個(gè)過(guò)程進(jìn)入一個(gè)被包圍的過(guò)程，嵌套深度加1名字的每次出現(xiàn)，把它的聲明所在過(guò)程的嵌套深度作為該名字的嵌套深度用于實(shí)現(xiàn)靜態(tài)作用域訪問(wèn)鏈：為每個(gè)活動(dòng)記錄增加一個(gè)訪問(wèn)鏈指針，如果過(guò)程p在源程序中直接嵌在q中，則p的活動(dòng)記錄的訪問(wèn)鏈指向最接近的那個(gè)q的活動(dòng)記錄的訪問(wèn)鏈實(shí)現(xiàn)過(guò)程嵌套的靜態(tài)作用域訪問(wèn)非局部名字（10）幻燈片41程序執(zhí)行時(shí)運(yùn)行棧的瞬像：訪問(wèn)非局部名字（11）靜態(tài)鏈（訪問(wèn)鏈）和動(dòng)態(tài)鏈（控制鏈）的比較：靜態(tài)鏈：指向源程序中包圍本過(guò)程的直接外層過(guò)程的一個(gè)最近活動(dòng)記錄的訪問(wèn)鏈通過(guò)靜態(tài)鏈實(shí)現(xiàn)非局部名字的訪問(wèn)通過(guò)靜態(tài)鏈訪問(wèn)非局部名字，訪問(wèn)速度慢動(dòng)態(tài)鏈：指向調(diào)用者的活動(dòng)記錄ABCDEARofAARofBARofCARofD動(dòng)態(tài)鏈靜態(tài)鏈訪問(wèn)非局部名字（12）訪問(wèn)鏈的建立：假定過(guò)程p的嵌套深度為np，它調(diào)用一個(gè)嵌套深度為nx的過(guò)程x：如果np<nx：如幻燈片44的B調(diào)用D過(guò)程x比過(guò)程p嵌得更深，x必定在p中聲明訪問(wèn)鏈指向棧中剛好在它下面的調(diào)用過(guò)程的活動(dòng)記錄如果np

>=nx：如幻燈片44的C調(diào)用E過(guò)程x和p的嵌套深度為1，2，…，nx–1的外圍過(guò)程必定相同從調(diào)用過(guò)程追蹤訪問(wèn)鏈np-nx+1次，即到達(dá)靜態(tài)包圍x和p的最內(nèi)過(guò)程的最新活動(dòng)記錄，這個(gè)訪問(wèn)鏈就是x必須指向的訪問(wèn)鏈np-nx+1可以在編譯時(shí)計(jì)算特別地，如果np=nx，如幻燈片44的C調(diào)用D，則D的訪問(wèn)鏈指向與C的訪問(wèn)鏈指向相同訪問(wèn)非局部名字（13）通過(guò)訪問(wèn)鏈訪問(wèn)非局部名字：假定過(guò)程p的嵌套深度為np，它引用一個(gè)嵌套深度為na的變量a，na<=np，則a的存儲(chǔ)單元可以如下找到：當(dāng)控制在p中時(shí)，p的一個(gè)活動(dòng)記錄必定在棧頂從棧頂追蹤訪問(wèn)鏈np-na次（這個(gè)次數(shù)編譯時(shí)刻可以計(jì)算）追蹤訪問(wèn)鏈np-na次后，到達(dá)a的聲明所在過(guò)程的活動(dòng)記錄，根據(jù)a的偏移量可以訪問(wèn)綜述：過(guò)程p中變量a的地址可以如下表示： （np-na

，a在活動(dòng)記錄中的偏移）過(guò)程調(diào)用發(fā)生時(shí)，非局部名字到存儲(chǔ)單元的結(jié)合可能發(fā)生變化訪問(wèn)非局部名字（14）過(guò)程作參數(shù)的處理：作為參數(shù)傳遞的過(guò)程必須取它的訪問(wèn)鏈和它一起傳遞例：

programparam(input,output); procedureb(functionh(n:integer):integer); beginwriteln(h(2))end procedurec; varm:integer; functionf(n:integer):integer; beginf:=m+nend{f}; beginm:=0;b(f)end{c}; begin c end.訪問(wèn)非局部名字（15）訪問(wèn)非局部名字（16）Display表：d[i]通過(guò)數(shù)組存放訪問(wèn)鏈，提高對(duì)非局部名字的訪問(wèn)效率如果當(dāng)前的活動(dòng)記錄對(duì)應(yīng)的過(guò)程p的嵌套深度為j，則Display表有j項(xiàng)，前j-1項(xiàng)指向依次嵌套在過(guò)程p外面的過(guò)程的最新活動(dòng)記錄，第j項(xiàng)指向過(guò)程p的這次活動(dòng)記錄同一個(gè)過(guò)程的不同活動(dòng)記錄間可以利用訪問(wèn)鏈鏈結(jié)，在調(diào)用序列和返回序列中進(jìn)行更新操作當(dāng)一個(gè)嵌套深度i的過(guò)程被調(diào)用時(shí)，建立一個(gè)新的活動(dòng)記錄在新的活動(dòng)記錄中保存d[i]的值令d[i]指向新的活動(dòng)記錄在一個(gè)活動(dòng)結(jié)束前，恢復(fù)d[i]被保存的值訪問(wèn)非局部名字（17）訪問(wèn)非局部名字（18）Display表的維護(hù)如果j<i，有i=j+1，被調(diào)用過(guò)程嵌套在調(diào)用過(guò)程中，Display表的前j項(xiàng)不需要變更，將d[i]指向新的活動(dòng)記錄，如上頁(yè)的c圖如果j>=i，調(diào)用者和被調(diào)用者外面包圍的嵌套深度為1，2，…，i-1的過(guò)程是同樣的，在新的活動(dòng)記錄中保存老的d[i]，置d[i]指向新的活動(dòng)記錄，保持Display表的前i–1項(xiàng)不變，如上頁(yè)的d圖Display表的保存可以放在寄存器中，受限于寄存器個(gè)數(shù)和非局部名字訪問(wèn)的頻繁程度可以在編譯時(shí)刻知道Display表的最大長(zhǎng)度，因此也可以將Display表存放為一個(gè)單獨(dú)的表或作為活動(dòng)記錄的一部分訪問(wèn)非局部名字（19）動(dòng)態(tài)作用域：當(dāng)一個(gè)過(guò)程被調(diào)用時(shí)，它的非局部名字到存儲(chǔ)單元的結(jié)合不會(huì)改變，即被調(diào)用過(guò)程的非局部名字a和它在調(diào)用過(guò)程中引用的是同樣的存儲(chǔ)單元新的結(jié)合僅為被調(diào)用過(guò)程的局部名字建立，這些名字占用新活動(dòng)記錄中的存儲(chǔ)單元在運(yùn)行時(shí)，一個(gè)名字a實(shí)施其影響，直到含a的聲明的一個(gè)過(guò)程開(kāi)始執(zhí)行時(shí)暫停；此過(guò)程停止時(shí)，該影響恢復(fù)訪問(wèn)非局部名字（20）例：動(dòng)態(tài)作用域和靜態(tài)作用域的對(duì)比

programdynamic(input,output); varr:real; procedureshow; beginwrite(r:5:3)end; proceduresmall; varr:real; beginr:=0.125;showend; begin r:=0.25; show;small;writeln; show;small;writeln; end靜態(tài)作用域的輸出： 動(dòng)態(tài)作用域的輸出： 0.2500.250 0.2500.125 0.2500.250 0.2500.125訪問(wèn)非局部名字（21）動(dòng)態(tài)作用域的實(shí)現(xiàn)：深訪問(wèn)訪問(wèn)鏈指向的活動(dòng)記錄和控制鏈指向的活動(dòng)記錄一樣，則實(shí)現(xiàn)了動(dòng)態(tài)作用域，因此可以省卻訪問(wèn)鏈，通過(guò)控制鏈搜索棧編譯時(shí)刻不能確定搜索的深度訪問(wèn)非局部名字需要較長(zhǎng)的時(shí)間，但活動(dòng)的開(kāi)始和結(jié)束不需要額外開(kāi)銷淺訪問(wèn)為每個(gè)名字在靜態(tài)分配的存儲(chǔ)空間中保存它的當(dāng)前值當(dāng)過(guò)程p的新活動(dòng)出現(xiàn)時(shí)，p的局部名字n接管分配給n的存儲(chǔ)單元，n的先前值可以保存在p的活動(dòng)記錄中，當(dāng)p的活動(dòng)結(jié)束時(shí)再恢復(fù)可以直接訪問(wèn)非局部名字，但活動(dòng)的開(kāi)始和結(jié)束需要維護(hù)的開(kāi)銷參數(shù)傳遞（1）過(guò)程和其調(diào)用者交換信息的方法：非局部名字參數(shù)返回值參數(shù)傳遞的方法：實(shí)現(xiàn)形參和實(shí)參聯(lián)系的方法不同的參數(shù)傳遞方法是因?yàn)閷?duì)表達(dá)式所表達(dá)的內(nèi)容的不同解釋左值右值參數(shù)傳遞的種類值調(diào)用（Call-by-Value）引用調(diào)用（Call-by-Reference）復(fù)寫-恢復(fù)調(diào)用（Copy-Restore）換名調(diào)用（Call-by-Name）……參數(shù)傳遞（2）值調(diào)用計(jì)算實(shí)參，并把它的右值傳遞給被調(diào)用過(guò)程C語(yǔ)言、Pascal語(yǔ)言支持這種方式形參當(dāng)作局部名，其存儲(chǔ)單元在被調(diào)用過(guò)程的活動(dòng)記錄中調(diào)用者計(jì)算實(shí)參，并把右值放在形參的存儲(chǔ)單元中形參的運(yùn)算不影響調(diào)用者活動(dòng)記錄中的值被調(diào)用過(guò)程可以通過(guò)非局部名字或通過(guò)顯式傳遞的指針值影響調(diào)用者參數(shù)傳遞（3）

swap(x,y) int*x,*y; { inttemp; temp=*x;*x=*y;*y=temp; } main() { inta=1,b=2; swap(&a,&b); printf(“aisnow%d,bisnow%d\n”,a,b); }參數(shù)傳遞（4）引用調(diào)用也稱為地址調(diào)用（call-by-address）或位置調(diào)用（call-by-location）調(diào)用者將參數(shù)的左值傳遞給被調(diào)用的過(guò)程如果實(shí)參是有左值的名字或表達(dá)式，則傳遞這個(gè)左值本身如果實(shí)參實(shí)沒(méi)有左值的表達(dá)式（如a+b或2等），則把它的值計(jì)算到新的存儲(chǔ)單元，然后傳遞這個(gè)單元的地址如Pascal語(yǔ)言中var參數(shù)是用這種方式傳遞的數(shù)組一般是用這種方式傳遞的參數(shù)傳遞（5）復(fù)寫-恢復(fù)值調(diào)用和引用調(diào)用的混合，也稱為復(fù)寫入和復(fù)寫出（copy-incopy-out）或值-結(jié)果（value-result）在控制流到被調(diào)用過(guò)程之前計(jì)算實(shí)參，實(shí)參的右值按值調(diào)用方式傳遞被調(diào)用過(guò)程，如果實(shí)參有左值，則在調(diào)用前確定它的左值當(dāng)控制返回時(shí)，將形參的當(dāng)前右值復(fù)寫回到實(shí)參的左值，該左值是上述調(diào)用前確定的左值。只有有左值的實(shí)參被復(fù)寫某些Fortran的實(shí)現(xiàn)使用了這種參數(shù)傳遞方式參數(shù)傳遞（6）使用復(fù)寫-恢復(fù)方式的原因避免了一個(gè)過(guò)程調(diào)用