【正文】 ”, a, b)。 var r : real。 begin … end {quicksort}。 b(g)。 } printf(“%d %d\n”, a, b)。 end. 活動(dòng)樹（ activation tree） ?控制流 ? 順序性：程序的執(zhí)行 ?一組操作步驟序列，在每個(gè)步驟，控制流開始于程序的特定位置 ? 過程的執(zhí)行：起始于過程體開始，最終控制權(quán)返回到過程調(diào)用點(diǎn)之后 ?活動(dòng)樹 表示 ?活動(dòng) ：一次 執(zhí)行 （ execution） ?過程 P的 生存期 ， lifetime： ? 過程體執(zhí)行的第一步操作到最后一步操作的操作序列，包括 P調(diào)用其他過程的時(shí)間 過程的活動(dòng) ? p調(diào)用 q，控制最終會(huì)返回 p——每次控制流從 p轉(zhuǎn)移到 q，總會(huì)返回到 p ?過程的生命期或者不重疊、或者嵌套 ——b在 a退出之前進(jìn)入，則必在 a之前退出 ? 利用輸出語(yǔ)句演示嵌套 execution begin… … enter readarray leave quicksort(1, 3) leave readarray enter quicksort(5, 9) enter quicksort(1, 9) … enter partition(1, 9) leave quicksort(5, 9) leave partition(1, 9) leave quicksort(1, 9) enter quicksort(1, 3) execution terminated. 遞歸 ? 過程 p的某個(gè)活動(dòng)尚未結(jié)束，可以開始它的一個(gè)新的活動(dòng) ? 間接遞歸 ? 活動(dòng)樹 1. 結(jié)點(diǎn) ——過程的活動(dòng) 2. 根結(jié)點(diǎn) ——主程序的活動(dòng) 3. a是 b的父結(jié)點(diǎn) ??控制流從 a到 b 4. a在 b的左邊 ??a的生存期在 b之前 例 控制棧（ control stack） ?活動(dòng)樹深度優(yōu)先遍歷 ?控制流變化 ?控制棧 ?當(dāng)活動(dòng)開始，對(duì)應(yīng)結(jié)點(diǎn)入棧 ?結(jié)束后，將其彈出 ?當(dāng)前棧內(nèi)容 ——到根結(jié)點(diǎn)的路徑 例 作用域 ?聲明（ declaration）：規(guī)定名字的含義 ?顯式聲明、隱式聲明（ Fortran） ?同一名字在程序不同位置的不同聲明 ?作用域（ scope）：聲明起作用的范圍 ? 局部的（ local）、非局部的（ nonlocal） ?作用域規(guī)則 ? 確定聲明起作用的范圍 ? 名字對(duì)應(yīng)哪個(gè)聲明 ?利用符號(hào)表 名字的綁定（ binding） ?名字只聲明一次，運(yùn)行時(shí)也可能指向不同數(shù)據(jù)對(duì)象 ?環(huán)境 （ environment）：函數(shù) ? 名字 ?存儲(chǔ)位置，名字 ?lvalue ?狀態(tài) （ state）：函數(shù) ? 存儲(chǔ)位置 ?存儲(chǔ)數(shù)據(jù)， lvalue?rvalue 環(huán)境和狀態(tài) ?賦值語(yǔ)句改變狀態(tài)，但不改變環(huán)境 ?對(duì)某個(gè)環(huán)境，若名字 x對(duì)應(yīng)存儲(chǔ)位置 s? x綁定 到 s， s是 x的一個(gè) 綁定 ?綁定 ——聲明的動(dòng)態(tài)概念 ? Pascal過程的局部名字，不同活動(dòng) ?不同存儲(chǔ)位置 過程的定義 過程的活動(dòng) 名字的聲明 名字的綁定 聲明的作用域 綁定的生存期 靜態(tài)概念 動(dòng)態(tài)概念 影響存儲(chǔ)組織的幾個(gè)問題 1. 過程可否遞歸？ 2. 過程活動(dòng)結(jié)束時(shí)，局部名字值如何處理 3. 過程可否訪問非局部名字？ 4. 過程被調(diào)用時(shí)，參數(shù)如何傳遞 5. 過程可否作為參數(shù) 6. 過程可否作為返回類型 7. 程序可否動(dòng)態(tài)控制存儲(chǔ)分配 8. 存儲(chǔ)是否必須顯式釋放？ 存儲(chǔ)組織 ? 運(yùn)行時(shí)存儲(chǔ)細(xì)化 ?存儲(chǔ)目標(biāo)代碼 ——大小固定 ?存儲(chǔ)數(shù)據(jù)對(duì)象 ——部分固定 ?控制棧 ——保存過程的活動(dòng)信息 活動(dòng)信息的保存 ?過程調(diào)用 ? 當(dāng)前過程活動(dòng)終止 ? 狀態(tài)信息（寄存器、 PC） ?控制棧 ?調(diào)用返回 ? 從控制棧恢復(fù)狀態(tài)信息 ? 停止的過程活動(dòng)重新開始 ?局部數(shù)據(jù)對(duì)象 ?控制棧 ?堆 ? 動(dòng)態(tài)內(nèi)存分配 ? 也可能保存活動(dòng)信息 活動(dòng)記錄 (activation record) 存放被調(diào)用函數(shù)傳遞給調(diào)用函數(shù)的返回結(jié)果 調(diào)用函數(shù)向被調(diào)用函數(shù)傳遞實(shí)際參數(shù)的區(qū)域 調(diào)用函數(shù)（父函數(shù)）活動(dòng)記錄的指針 用來訪問那些保存在其他 活動(dòng)記錄中的非局部數(shù)據(jù) 函數(shù)調(diào)用前時(shí)刻機(jī)器狀態(tài)相關(guān)的 一些信息：程序計(jì)數(shù)器、寄存器 … 保存局部數(shù)據(jù) 保存臨時(shí)數(shù)據(jù)：表達(dá)式計(jì)算中間結(jié)果 … 局部數(shù)據(jù)布局 ?例 ?類型 ?占用空間 ?對(duì)齊（ align），補(bǔ)丁（ padding）， 壓縮（ pack） ?char a。 procedure readarray。 quicksort(i + 1, n) end end。 { int a = 2。 begin g := m * n end。 procedure quicksort(m, n : integer)。 begin c end. 過程作為參數(shù)的情況（續(xù)） ?當(dāng)過程作為參數(shù)傳遞時(shí)，對(duì)應(yīng)的訪問鏈接也一起傳遞 Display表 ?一維數(shù)組 d[i]：將嵌套深度為 i的過程的訪問鏈接串起來 Display表（續(xù)） display表的設(shè)置 ?當(dāng)設(shè)置嵌套深度為 i的過程的活動(dòng)記錄 ?舊的 d[i]值保存入新的活動(dòng)記錄 ?設(shè)置 d[i]指向新的活動(dòng)記錄 ?正確性：假定嵌套深度 j的過程調(diào)用深度 i的過程 ? ji： ?i=j+1， d[1]~d[j]無需改變， d[i]指向新活動(dòng)記錄，上面 (a)圖 ? j=i： ?包含兩個(gè)過程，嵌套深度 1,2,…,i 1的過程必然是相同的，將舊 d[i]保存到新活動(dòng)記錄，并設(shè)置它指向新活動(dòng)記錄即可，上面 (d)圖 動(dòng)態(tài)作用域 ?嵌套關(guān)系，調(diào)用關(guān)系 決定名字綁定 program dynamic(input, output)。 temp = x。 procedure swap(var x, y : integer)。