第六章運(yùn)行時(shí)存儲(chǔ)空間的

組織和管理

編譯程序在完成詞法、語法和語義分析后，在生成目標(biāo)代碼之前，需要把程序的靜態(tài)正文和實(shí)現(xiàn)這個(gè)程序的運(yùn)行時(shí)的活動(dòng)聯(lián)系起來弄清楚將來在代碼運(yùn)行時(shí)刻，源代碼中的各種變量、常量等用戶定義的量是如何存放的，如何去訪問它們。

在程序的執(zhí)行過程中，程序中數(shù)據(jù)的存取是通過與之對(duì)應(yīng)的存儲(chǔ)單元來進(jìn)行的。在程序語言中，程序使用的存儲(chǔ)單元都是由標(biāo)識(shí)符來表示的。它們對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配。所以對(duì)于編譯程序來說存儲(chǔ)組織與管理是一個(gè)復(fù)雜而又十分重要的問題。第六章運(yùn)行時(shí)存儲(chǔ)空間的

組織和管理1本章內(nèi)容:討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)安排程序執(zhí)行過程中，所有活動(dòng)記錄的組織方式存儲(chǔ)器的組織與存儲(chǔ)分配的策略非局部名稱的訪問參數(shù)傳遞第六章運(yùn)行時(shí)存儲(chǔ)空間的組織和管理26.1局部存儲(chǔ)分配策略過程的每一次運(yùn)行稱為一次活動(dòng)（activation）?；顒?dòng)是一個(gè)動(dòng)態(tài)的概念，它有有限的生存期?；顒?dòng)的生存期是指從進(jìn)入活動(dòng)的第一條指令執(zhí)行到離開此活動(dòng)前的最后一條指令執(zhí)行的這段時(shí)間，其中包括調(diào)用其它過程時(shí)其它活動(dòng)的生存期。6.1局部存儲(chǔ)分配策略過程的每一次運(yùn)行稱為一次活動(dòng)（act36.1.2名字的作用域和綁定名字的作用域一個(gè)聲明起作用的程序部分稱為該聲明的作用域。即使一個(gè)名字在程序中只聲明一次，該名字在程序運(yùn)行時(shí)也可能表示不同的數(shù)據(jù)對(duì)象。6.1.2名字的作用域和綁定名字的作用域4名字的綁定

運(yùn)行時(shí)為名字X分配存儲(chǔ)空間S，這一過程稱為綁定（binding）。 換句話說，綁定是名字X與存儲(chǔ)空間S的結(jié)合。X是一個(gè)對(duì)象：既可以是數(shù)據(jù)對(duì)象，如變量，與之結(jié)合的是一個(gè)存儲(chǔ)單元；也可以是操作對(duì)象，如過程，與之結(jié)合的是可執(zhí)行的代碼。我們的討論僅限于X是一個(gè)數(shù)據(jù)對(duì)象。名字的綁定X是一個(gè)對(duì)象：5

名字的聲明與名字的綁定均需要有對(duì)應(yīng)的存儲(chǔ)空間，而存儲(chǔ)空間的對(duì)應(yīng)方式，一個(gè)是靜態(tài)的，一個(gè)是動(dòng)態(tài)的。聲明時(shí)關(guān)心的是聲明的作用域，即當(dāng)一個(gè)名字被引用時(shí)，在不同的作用域中與該名字的不同聲明結(jié)合；綁定時(shí)關(guān)心的是綁定的生存期，即當(dāng)一個(gè)名字在運(yùn)行時(shí)被實(shí)際分配的存儲(chǔ)單元，名字與存儲(chǔ)單元結(jié)合的這段時(shí)間被稱為綁定的生存期，顯然此生存期應(yīng)該和名字的生存期一致。靜態(tài) 動(dòng)態(tài)過程的定義 過程的活動(dòng) 名字的聲明 名字的綁定聲明的作用域 綁定的生存期符號(hào)表 活動(dòng)記錄靜態(tài)與動(dòng)態(tài)名字的聲明與名字的綁定均需要有對(duì)應(yīng)的存儲(chǔ)空間6變量與值的兩步映射

環(huán)境改變存儲(chǔ)，狀態(tài)改變值。例5.3若有變量聲明x:real和常量聲明constpi=3.14，則賦值句中變量和常量的映射關(guān)系：常量沒有左值（存儲(chǔ)空間），所以不能被賦值。變量與值的兩步映射環(huán)境改變存儲(chǔ)，狀態(tài)改變值。76.1.3活動(dòng)記錄為了管理過程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，我們把這樣的一個(gè)連續(xù)存儲(chǔ)塊稱為活動(dòng)紀(jì)錄。返回值臨時(shí)數(shù)據(jù)參數(shù)控制鏈訪問鏈機(jī)器狀態(tài)局部數(shù)據(jù)6.1.3活動(dòng)記錄為了管理過程在一次執(zhí)行8返回值實(shí)在參數(shù)控制鏈訪問鏈保存機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)變量控制鏈:指向調(diào)用過程活動(dòng)的活動(dòng)記錄。訪問鏈：指向本活動(dòng)要訪問的非局部數(shù)據(jù)所在的活動(dòng)記錄。保存機(jī)器狀態(tài)：調(diào)用過程活動(dòng)在調(diào)用點(diǎn)的機(jī)器狀態(tài)，包括計(jì)數(shù)器，各種寄存器的值。局部數(shù)據(jù)：過程中定義的局部量。臨時(shí)變量：編譯產(chǎn)生。返回值實(shí)在參數(shù)控制鏈訪問鏈保存機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)變量控制鏈96.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。6.1.4局部數(shù)據(jù)的安排106.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。6.1.4局部數(shù)據(jù)的安排116.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。6.1.4局部數(shù)據(jù)的安排126.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示。6.1.4局部數(shù)據(jù)的安排136.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示。數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有一個(gè)對(duì)齊問題。6.1.4局部數(shù)據(jù)的安排146.1.5

程序塊本身含有局部變量聲明的語句可以嵌套最接近的嵌套作用域規(guī)則并列程序塊不會(huì)同時(shí)活躍并列程序塊的變量可以重疊分配6.1.5程序塊15main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/main()16main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/聲

明

作

用

域

inta=0;B0

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

main()聲明作用域inta=017main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/聲

明

作

用

域

inta=0;B0

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

a0b0b1a2,b3重疊分配存儲(chǔ)單元

main()聲明作用域inta=0186.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存196.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存206.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存216.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略棧式分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存226.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略棧式分配策略堆式分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存23靜態(tài)分配策略在編譯是對(duì)所有對(duì)象分配固定的存儲(chǔ)單元。且在運(yùn)行是保持不變。棧式動(dòng)態(tài)分配策略在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)的分配于棧頂，一旦退出，它所占空間就予以釋放。堆式動(dòng)態(tài)存儲(chǔ)策略在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲(chǔ)空間的申請(qǐng)與歸還（回收），凡申請(qǐng)者分給一塊，凡釋放者退回給堆。靜態(tài)分配策略在編譯是對(duì)所有對(duì)象分配固定的存儲(chǔ)單元。246.2.1

運(yùn)行時(shí)內(nèi)存的劃分代碼靜態(tài)數(shù)據(jù)棧堆6.2.1運(yùn)行時(shí)內(nèi)存的劃分代碼靜態(tài)數(shù)據(jù)棧堆256.2.2靜態(tài)存儲(chǔ)分配

如果在編譯時(shí)就能夠確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。存儲(chǔ)空間的這種分配方法叫做靜態(tài)分配。

特點(diǎn)：綁定是1對(duì)1的映射。名字在程序編譯時(shí)與存儲(chǔ)空間結(jié)合，每次過程活動(dòng)時(shí)，它的名字映射到同一存儲(chǔ)單元。程序運(yùn)行時(shí)不再有對(duì)存儲(chǔ)空間的分配。6.2.2靜態(tài)存儲(chǔ)分配26靜態(tài)分配的限制：①數(shù)據(jù)對(duì)象的大小和它在內(nèi)存中位置的限制必須在編譯時(shí)確定，如數(shù)組的大小不能是動(dòng)態(tài)的；②不允許程序遞歸，因?yàn)橐粋€(gè)過程的所有活動(dòng)使用同樣的名字綁定，即綁定是一對(duì)一的；③不能動(dòng)態(tài)生成或撤消數(shù)據(jù)，因?yàn)檫\(yùn)行時(shí)沒有存儲(chǔ)分配機(jī)制。完全采用靜態(tài)分配的語言：早期的FORTRAN。允許分別編譯的數(shù)據(jù)定義模塊（如全程引用的數(shù)據(jù)），也可以采用靜態(tài)分配，因?yàn)樗鼈円话阍谡麄€(gè)程序運(yùn)行的期間是被共享的。靜態(tài)分配的限制：276.2.3棧式存儲(chǔ)分配存儲(chǔ)空間被組織成棧，活動(dòng)記錄的推入和彈出分別對(duì)應(yīng)于活動(dòng)的開始和結(jié)束。

與靜態(tài)分配不同的是，在每次活動(dòng)中把局部名字和新的存儲(chǔ)單元綁定，在活動(dòng)結(jié)束時(shí)，活動(dòng)記錄從棧中彈出，因而局部名字的存儲(chǔ)空間也隨之消失。6.2.3棧式存儲(chǔ)分配286.2.3棧式分配

活動(dòng)樹:用樹來描繪控制進(jìn)入和離開活動(dòng)的方式sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(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)6.2.3棧式分配sq(1,9)rp(1,9)q(1,3)29活動(dòng)樹的特點(diǎn)：每個(gè)結(jié)點(diǎn)代表某過程的一個(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)入b的活動(dòng)結(jié)點(diǎn)a處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期活動(dòng)樹上各節(jié)點(diǎn)之間具有下述關(guān)系：同一層次的活動(dòng)生存期不交；任一時(shí)刻，處在生存期的活動(dòng)構(gòu)成一條從根到某節(jié)點(diǎn)的路徑；路徑上各節(jié)點(diǎn)生存期是嵌套的（后進(jìn)先出）?；顒?dòng)樹的特點(diǎn)：30當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中控制棧的內(nèi)容：s,q(1,9),q(1,3),q(2,3)

sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(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)當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中sq(1,9)rp(131運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息32運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

sa:arrays運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息33運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

si:integerra:arraysr運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息34運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

sk:integerq(1,9)a:arraysq(1,9)r運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息35運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）sk:integerq(1,9)a:arrayq(1,3)k:integersq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息36過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或37過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列

過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或38過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列

過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程返回序列

過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或39過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列

過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程返回序列

過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或40調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)41過程p調(diào)用過程q的調(diào)用序列p計(jì)算實(shí)參，依次放入棧頂，并在棧頂留出放返回值的空間。top_sp的值在此過程中被改變p把返回地址和當(dāng)前base_sp的值存入q的活動(dòng)記錄中，建立q的訪問鏈，增加base_sp的值q保存寄存器的值和其它機(jī)器狀態(tài)信息q根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體過程p調(diào)用過程q的調(diào)用序列42調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)43過程p調(diào)用過程q的返回序列q把返回值置入鄰近p的活動(dòng)記錄的地方q對(duì)應(yīng)調(diào)用序列的步驟（4），減小top_sp的值

q恢復(fù)寄存器（包括base_sp）和機(jī)器狀態(tài)，返回pp根據(jù)參數(shù)個(gè)數(shù)與類型和返回值類型調(diào)整top_sp，然后取出返回值過程p調(diào)用過程q的返回序列44調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)45過程的參數(shù)個(gè)數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等過程的參數(shù)個(gè)數(shù)可變的情況46調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)47活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況局部數(shù)組的大小要等到過程激活時(shí)才能確定在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況48訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組控制鏈top_sp

base_sp

p的活動(dòng)記錄數(shù)組A的指針數(shù)組B的指針數(shù)組A數(shù)組B控制鏈訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組控制鏈top_49懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元50懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元main() | intdangle(){ | { intq; | intj=20; q=dangle(); | return&j;} | }懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元516.3.3堆式存儲(chǔ)分配

1．局部名的值在活動(dòng)結(jié)束時(shí)必須被保存。

2.被調(diào)用者的活動(dòng)生存期超過調(diào)用者。用活動(dòng)樹不能夠正確描繪這種語言的過程之間的控制流。new(p);dispose(p);6.3.3堆式存儲(chǔ)分配526.3非局部名字的訪問本節(jié)介紹無過程嵌套的靜態(tài)作用域（C語言）有過程嵌套的靜態(tài)作用域（Pascal語言）動(dòng)態(tài)作用域（Lisp語言）6.3非局部名字的訪問本節(jié)介紹536.3.1

無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過base_sp指針來訪問無須深入棧中取數(shù)據(jù)，無須訪問鏈過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回6.3.1無過程嵌套的靜態(tài)作用域546.3.2

有過程嵌套的靜態(tài)作用域過程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 36.3.2有過程嵌套的靜態(tài)作用域556.3.2

有過程嵌套的靜態(tài)作用域過程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度6.3.2有過程嵌套的靜態(tài)作用域566.3

非局部名字的訪問尋找非局部名字存儲(chǔ)單元的訪問鏈sa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈6.3非局部名字的訪問尋找非局部名字存儲(chǔ)單元的訪問鏈sa576.3

非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na

np。如何訪問a的存儲(chǔ)單元？sort 1 readarray 2 exchange 2 quicksort 2 partition 36.3非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌586.3

非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na

np。如何訪問a的存儲(chǔ)單元？從棧頂?shù)幕顒?dòng)記錄開始，追蹤訪問鏈np

na次。6.3非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌596.3

非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na

np。如何訪問a的存儲(chǔ)單元？從棧頂?shù)幕顒?dòng)記錄開始，追蹤訪問鏈np

na次。到達(dá)a的聲明所在過程的活動(dòng)記錄。6.3非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌606.3

非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na

np。如何訪問a的存儲(chǔ)單元？從棧頂?shù)幕顒?dòng)記錄開始，追蹤訪問鏈np

na次。到達(dá)a的聲明所在過程的活動(dòng)記錄。訪問鏈的追蹤用間接操作就可完成。6.3非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌616.3

非局部名字的訪問訪問非局部名字的存儲(chǔ)單元sa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈sortreadarrayexchangequicksortpartition6.3非局部名字的訪問訪問非局部名字的存儲(chǔ)單元sa,x626.3

非局部名字的訪問過程p對(duì)變量a訪問時(shí)，a的地址由下面的二元組表示：（np

na，a在活動(dòng)記錄中的偏移）6.3非局部名字的訪問過程p對(duì)變量a訪問時(shí)，a的地址由下面636.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp<nx的情況sort 1 readarray 2 exchange 2 quicksort 2 partition 36.3非局部名字的訪問建立訪問鏈646.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp<nx的情況x肯定就聲明在p中6.3非局部名字的訪問建立訪問鏈656.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp<nx的情況x肯定就聲明在p中被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動(dòng)記錄的訪問鏈6.3非局部名字的訪問建立訪問鏈666.3

非局部名字的訪問建立訪問鏈sa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈sortreadarrayexchangequicksortpartition6.3非局部名字的訪問建立訪問鏈sa,xq(1,9)676.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp

nx的情況sort 1 readarray 2 exchange 2 quicksort 2 partition 36.3非局部名字的訪問建立訪問鏈686.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp

nx的情況p和x的嵌套深度分別為1，2，…，nx1的外圍過程肯定相同6.3非局部名字的訪問建立訪問鏈696.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp

nx的情況p和x的嵌套深度分別為1，2，…，nx1的外圍過程肯定相同追蹤訪問鏈np

nx+1次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過程的最新活動(dòng)記錄6.3非局部名字的訪問建立訪問鏈706.3

非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp

nx的情況p和x的嵌套深度分別為1，2，…，nx1的外圍過程肯定相同追蹤訪問鏈np

nx+1次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過程的最新活動(dòng)記錄所到達(dá)的訪問鏈就是x的活動(dòng)記錄中的訪問鏈應(yīng)該指向的那個(gè)訪問鏈6.3非局部名字的訪問建立訪問鏈716.3

非局部名字的訪問建立訪問鏈sa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈sortreadarrayexchangequicksortpartition6.3非局部名字的訪問建立訪問鏈sa,xq(1,9)726.3

非局部名字的訪問programparam(input,output);（過程作為參數(shù)） 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.6.3非局部名字的訪問programparam(inpu736.3

非局部名字的訪問programparam(input,output);（過程作為參數(shù)） 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. 過程作為參數(shù)傳遞時(shí)，怎樣在該過程被激活時(shí)建立它的訪問鏈。6.3非局部名字的訪問programparam(inpu746.3

非局部名字的訪問programparam(input,output);（過程作為參數(shù)） 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. 過程作為參數(shù)傳遞時(shí)，怎樣在該過程被激活時(shí)建立它的訪問鏈從b的訪問鏈難以建立f的訪問鏈6.3非局部名字的訪問programparam(inpu756.3

非局部名字的訪問programparam(input,output);（過程作為參數(shù)） procedureb(functionh(… beginwriteln(h(2))end; procedurec; varm:integer; functionf(n:integer)… beginf:=m+nend{f}; beginm:=0;b(f)end{c};begin c end.訪問鏈訪問鏈paramcmb<f,>6.3非局部名字的訪問programparam(inpu766.3

非局部名字的訪問programret(input,output);（過程作為返回值）varf:function(integer):integer;

functiona:function(integer):integer;

varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end.6.3非局部名字的訪問programret(input776.3

非局部名字的訪問programret(input,output);（過程作為返回值）varf:function(integer):integer;

functiona:function(integer):integer;

varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end.retabaddm6.3非局部名字的訪問programret(input786.3

非局部名字的訪問 C語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況:非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)

6.3非局部名字的訪問 C語言的函數(shù)聲明不能嵌套，函數(shù)不論796.3

非局部名字的訪問6.3.3

動(dòng)態(tài)作用域被調(diào)用過程的非局部名字a和它在調(diào)用過程中引用的是同樣的存儲(chǔ)單元。6.3非局部名字的訪問6.3.3動(dòng)態(tài)作用域806.3

非局部名字的訪問6.3.3

動(dòng)態(tài)作用域被調(diào)用過程的非局部名字a和它在調(diào)用過程中引用的是同樣的存儲(chǔ)單元。新的綁定僅為被調(diào)用過程的局部名字建立，這些名字在被調(diào)用過程的活動(dòng)記錄中占用的存儲(chǔ)單元。6.3非局部名字的訪問6.3.3動(dòng)態(tài)作用域816.3

非局部名字的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.6.3非局部名字的訪問programdynamic(in826.3

非局部名字的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局部名字的訪問programdynamic(in836.3

非局部名字的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin 靜態(tài)作用域r:=0.25; 0.250 0.250show;small;writeln; 0.250 0.250show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局部名字的訪問programdynamic(in846.3

非局部名字的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin 動(dòng)態(tài)作用域r:=0.25; 0.250 0.125show;small;writeln; 0.250 0.125show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局部名字的訪問programdynamic(in856.3

非局部名字的訪問實(shí)現(xiàn)動(dòng)態(tài)作用域的方法深訪問

用控制鏈搜索運(yùn)行棧，尋找包含該非局部名字的第一個(gè)活動(dòng)記錄淺訪問為每個(gè)名字在靜態(tài)分配的存儲(chǔ)空間中保存它的當(dāng)前值當(dāng)過程p的新活動(dòng)出現(xiàn)時(shí)，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的存儲(chǔ)單元。n的先前值可以保存在p的活動(dòng)記錄中，當(dāng)p的活動(dòng)結(jié)束時(shí)再恢復(fù)6.3非局部名字的訪問實(shí)現(xiàn)動(dòng)態(tài)作用域的方法866.4

參數(shù)傳遞6.4.1值調(diào)用實(shí)參的右值傳給被調(diào)用過程

值調(diào)用可以如下實(shí)現(xiàn)把形參當(dāng)作所在過程的局部名看待，形參的存儲(chǔ)單元在該過程的活動(dòng)記錄中。6.4參數(shù)傳遞6.4.1值調(diào)用876.4

參數(shù)傳遞6.4.1值調(diào)用實(shí)參的右值傳給被調(diào)用過程

值調(diào)用可以如下實(shí)現(xiàn)把形參當(dāng)作所在過程的局部名看待，形參的存儲(chǔ)單元在該過程的活動(dòng)記錄中。調(diào)用過程計(jì)算實(shí)參，并把右值放入形參的存儲(chǔ)單元中。

6.4參數(shù)傳遞6.4.1值調(diào)用886.4

參數(shù)傳遞6.4.2引用調(diào)用實(shí)參的左值傳給被調(diào)用過程

引用調(diào)用可以如下實(shí)現(xiàn)：把實(shí)參的左值放入形參的存儲(chǔ)單元。6.4參數(shù)傳遞6.4.2引用調(diào)用896.4

參數(shù)傳遞6.4.2引用調(diào)用實(shí)參的左值傳給被調(diào)用過程

引用調(diào)用可以如下實(shí)現(xiàn)：把實(shí)參的左值放入形參的存儲(chǔ)單元。在被調(diào)用過程的目標(biāo)代碼中，任何對(duì)形參的引用都是通過傳給該過程的指針來間接引用實(shí)參的。6.4參數(shù)傳遞6.4.2引用調(diào)用906.4

參數(shù)傳遞6.4.3復(fù)寫-恢復(fù)調(diào)用值調(diào)用和引用調(diào)用的混合復(fù)寫-恢復(fù)調(diào)用可以如下實(shí)現(xiàn)： 實(shí)參的右值和左值同時(shí)傳給被調(diào)用過程。6.4參數(shù)傳遞6.4.3復(fù)寫-恢復(fù)調(diào)用916.4

參數(shù)傳遞6.4.3復(fù)寫-恢復(fù)調(diào)用值調(diào)用和引用調(diào)用的混合復(fù)寫-恢復(fù)調(diào)用可以如下實(shí)現(xiàn)： 實(shí)參的右值和左值同時(shí)傳給被調(diào)用過程。 在被調(diào)用過程中，像值調(diào)用那樣使用實(shí)參的右值。6.4參數(shù)傳遞6.4.3復(fù)寫-恢復(fù)調(diào)用926.4

參數(shù)傳遞6.4.3復(fù)寫-恢復(fù)調(diào)用值調(diào)用和引用調(diào)用的混合復(fù)寫-恢復(fù)調(diào)用可以如下實(shí)現(xiàn)： 實(shí)參的右值和左值同時(shí)傳給被調(diào)用過程。 在被調(diào)用過程中，像值調(diào)用那樣使用實(shí)參的右值。 當(dāng)控制返回調(diào)用過程時(shí)，根據(jù)傳遞來的實(shí)參的左值，將形參當(dāng)前的值復(fù)寫到實(shí)參存儲(chǔ)單元。

6.4參數(shù)傳遞6.4.3復(fù)寫-恢復(fù)調(diào)用936.4

參數(shù)傳遞6.4.4換名調(diào)用用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換。procedureswap(varx,y:integer); vartemp:integer; begin temp:=x; x:=y; y:=temp end6.4參數(shù)傳遞6.4.4換名調(diào)用946.4

參數(shù)傳遞6.4.4換名調(diào)用用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換。procedureswap(varx,y:integer); vartemp:integer; begin 調(diào)用swap(i,a[i])

temp:=x; x:=y; y:=temp end6.4參數(shù)傳遞6.4.4換名調(diào)用956.4

參數(shù)傳遞6.4.4換名調(diào)用用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換。procedureswap(varx,y:integer); vartemp:integer; begin 調(diào)用swap(i,a[i])

temp:=x; temp:=i;

x:=y; i:=a[i];

y:=temp a[i]:=temp end6.4參數(shù)傳遞6.4.4換名調(diào)用96本章要點(diǎn)影響存儲(chǔ)分配策略的語言特征各種存儲(chǔ)分配策略，主要了解靜態(tài)分配和動(dòng)態(tài)棧式分配活動(dòng)記錄中各種數(shù)據(jù)域的作用和安排非局部數(shù)據(jù)訪問的實(shí)現(xiàn)方法各種參數(shù)傳遞方式及其實(shí)現(xiàn)本章要點(diǎn)影響存儲(chǔ)分配策略的語言特征97第六章運(yùn)行時(shí)存儲(chǔ)空間的

組織和管理

編譯程序在完成詞法、語法和語義分析后，在生成目標(biāo)代碼之前，需要把程序的靜態(tài)正文和實(shí)現(xiàn)這個(gè)程序的運(yùn)行時(shí)的活動(dòng)聯(lián)系起來弄清楚將來在代碼運(yùn)行時(shí)刻，源代碼中的各種變量、常量等用戶定義的量是如何存放的，如何去訪問它們。

在程序的執(zhí)行過程中，程序中數(shù)據(jù)的存取是通過與之對(duì)應(yīng)的存儲(chǔ)單元來進(jìn)行的。在程序語言中，程序使用的存儲(chǔ)單元都是由標(biāo)識(shí)符來表示的。它們對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配。所以對(duì)于編譯程序來說存儲(chǔ)組織與管理是一個(gè)復(fù)雜而又十分重要的問題。第六章運(yùn)行時(shí)存儲(chǔ)空間的

組織和管理98本章內(nèi)容:討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)安排程序執(zhí)行過程中，所有活動(dòng)記錄的組織方式存儲(chǔ)器的組織與存儲(chǔ)分配的策略非局部名稱的訪問參數(shù)傳遞第六章運(yùn)行時(shí)存儲(chǔ)空間的組織和管理996.1局部存儲(chǔ)分配策略過程的每一次運(yùn)行稱為一次活動(dòng)（activation）?；顒?dòng)是一個(gè)動(dòng)態(tài)的概念，它有有限的生存期?；顒?dòng)的生存期是指從進(jìn)入活動(dòng)的第一條指令執(zhí)行到離開此活動(dòng)前的最后一條指令執(zhí)行的這段時(shí)間，其中包括調(diào)用其它過程時(shí)其它活動(dòng)的生存期。6.1局部存儲(chǔ)分配策略過程的每一次運(yùn)行稱為一次活動(dòng)（act1006.1.2名字的作用域和綁定名字的作用域一個(gè)聲明起作用的程序部分稱為該聲明的作用域。即使一個(gè)名字在程序中只聲明一次，該名字在程序運(yùn)行時(shí)也可能表示不同的數(shù)據(jù)對(duì)象。6.1.2名字的作用域和綁定名字的作用域101名字的綁定

運(yùn)行時(shí)為名字X分配存儲(chǔ)空間S，這一過程稱為綁定（binding）。 換句話說，綁定是名字X與存儲(chǔ)空間S的結(jié)合。X是一個(gè)對(duì)象：既可以是數(shù)據(jù)對(duì)象，如變量，與之結(jié)合的是一個(gè)存儲(chǔ)單元；也可以是操作對(duì)象，如過程，與之結(jié)合的是可執(zhí)行的代碼。我們的討論僅限于X是一個(gè)數(shù)據(jù)對(duì)象。名字的綁定X是一個(gè)對(duì)象：102

名字的聲明與名字的綁定均需要有對(duì)應(yīng)的存儲(chǔ)空間，而存儲(chǔ)空間的對(duì)應(yīng)方式，一個(gè)是靜態(tài)的，一個(gè)是動(dòng)態(tài)的。聲明時(shí)關(guān)心的是聲明的作用域，即當(dāng)一個(gè)名字被引用時(shí)，在不同的作用域中與該名字的不同聲明結(jié)合；綁定時(shí)關(guān)心的是綁定的生存期，即當(dāng)一個(gè)名字在運(yùn)行時(shí)被實(shí)際分配的存儲(chǔ)單元，名字與存儲(chǔ)單元結(jié)合的這段時(shí)間被稱為綁定的生存期，顯然此生存期應(yīng)該和名字的生存期一致。靜態(tài) 動(dòng)態(tài)過程的定義 過程的活動(dòng) 名字的聲明 名字的綁定聲明的作用域 綁定的生存期符號(hào)表 活動(dòng)記錄靜態(tài)與動(dòng)態(tài)名字的聲明與名字的綁定均需要有對(duì)應(yīng)的存儲(chǔ)空間103變量與值的兩步映射

環(huán)境改變存儲(chǔ)，狀態(tài)改變值。例5.3若有變量聲明x:real和常量聲明constpi=3.14，則賦值句中變量和常量的映射關(guān)系：常量沒有左值（存儲(chǔ)空間），所以不能被賦值。變量與值的兩步映射環(huán)境改變存儲(chǔ)，狀態(tài)改變值。1046.1.3活動(dòng)記錄為了管理過程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，我們把這樣的一個(gè)連續(xù)存儲(chǔ)塊稱為活動(dòng)紀(jì)錄。返回值臨時(shí)數(shù)據(jù)參數(shù)控制鏈訪問鏈機(jī)器狀態(tài)局部數(shù)據(jù)6.1.3活動(dòng)記錄為了管理過程在一次執(zhí)行105返回值實(shí)在參數(shù)控制鏈訪問鏈保存機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)變量控制鏈:指向調(diào)用過程活動(dòng)的活動(dòng)記錄。訪問鏈：指向本活動(dòng)要訪問的非局部數(shù)據(jù)所在的活動(dòng)記錄。保存機(jī)器狀態(tài)：調(diào)用過程活動(dòng)在調(diào)用點(diǎn)的機(jī)器狀態(tài)，包括計(jì)數(shù)器，各種寄存器的值。局部數(shù)據(jù)：過程中定義的局部量。臨時(shí)變量：編譯產(chǎn)生。返回值實(shí)在參數(shù)控制鏈訪問鏈保存機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)變量控制鏈1066.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。6.1.4局部數(shù)據(jù)的安排1076.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。6.1.4局部數(shù)據(jù)的安排1086.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。6.1.4局部數(shù)據(jù)的安排1096.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示。6.1.4局部數(shù)據(jù)的安排1106.1.4局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示。數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有一個(gè)對(duì)齊問題。6.1.4局部數(shù)據(jù)的安排1116.1.5

程序塊本身含有局部變量聲明的語句可以嵌套最接近的嵌套作用域規(guī)則并列程序塊不會(huì)同時(shí)活躍并列程序塊的變量可以重疊分配6.1.5程序塊112main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/main()113main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/聲

明

作

用

域

inta=0;B0

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

main()聲明作用域inta=0114main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/聲

明

作

用

域

inta=0;B0

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

a0b0b1a2,b3重疊分配存儲(chǔ)單元

main()聲明作用域inta=01156.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存1166.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存1176.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存1186.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略棧式分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存1196.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略棧式分配策略堆式分配策略6.2全局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存120靜態(tài)分配策略在編譯是對(duì)所有對(duì)象分配固定的存儲(chǔ)單元。且在運(yùn)行是保持不變。棧式動(dòng)態(tài)分配策略在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)的分配于棧頂，一旦退出，它所占空間就予以釋放。堆式動(dòng)態(tài)存儲(chǔ)策略在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲(chǔ)空間的申請(qǐng)與歸還（回收），凡申請(qǐng)者分給一塊，凡釋放者退回給堆。靜態(tài)分配策略在編譯是對(duì)所有對(duì)象分配固定的存儲(chǔ)單元。1216.2.1

運(yùn)行時(shí)內(nèi)存的劃分代碼靜態(tài)數(shù)據(jù)棧堆6.2.1運(yùn)行時(shí)內(nèi)存的劃分代碼靜態(tài)數(shù)據(jù)棧堆1226.2.2靜態(tài)存儲(chǔ)分配

如果在編譯時(shí)就能夠確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。存儲(chǔ)空間的這種分配方法叫做靜態(tài)分配。

特點(diǎn)：綁定是1對(duì)1的映射。名字在程序編譯時(shí)與存儲(chǔ)空間結(jié)合，每次過程活動(dòng)時(shí)，它的名字映射到同一存儲(chǔ)單元。程序運(yùn)行時(shí)不再有對(duì)存儲(chǔ)空間的分配。6.2.2靜態(tài)存儲(chǔ)分配123靜態(tài)分配的限制：①數(shù)據(jù)對(duì)象的大小和它在內(nèi)存中位置的限制必須在編譯時(shí)確定，如數(shù)組的大小不能是動(dòng)態(tài)的；②不允許程序遞歸，因?yàn)橐粋€(gè)過程的所有活動(dòng)使用同樣的名字綁定，即綁定是一對(duì)一的；③不能動(dòng)態(tài)生成或撤消數(shù)據(jù)，因?yàn)檫\(yùn)行時(shí)沒有存儲(chǔ)分配機(jī)制。完全采用靜態(tài)分配的語言：早期的FORTRAN。允許分別編譯的數(shù)據(jù)定義模塊（如全程引用的數(shù)據(jù)），也可以采用靜態(tài)分配，因?yàn)樗鼈円话阍谡麄€(gè)程序運(yùn)行的期間是被共享的。靜態(tài)分配的限制：1246.2.3棧式存儲(chǔ)分配存儲(chǔ)空間被組織成棧，活動(dòng)記錄的推入和彈出分別對(duì)應(yīng)于活動(dòng)的開始和結(jié)束。

與靜態(tài)分配不同的是，在每次活動(dòng)中把局部名字和新的存儲(chǔ)單元綁定，在活動(dòng)結(jié)束時(shí)，活動(dòng)記錄從棧中彈出，因而局部名字的存儲(chǔ)空間也隨之消失。6.2.3棧式存儲(chǔ)分配1256.2.3棧式分配

活動(dòng)樹:用樹來描繪控制進(jìn)入和離開活動(dòng)的方式sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(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)6.2.3棧式分配sq(1,9)rp(1,9)q(1,3)126活動(dòng)樹的特點(diǎn)：每個(gè)結(jié)點(diǎn)代表某過程的一個(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)入b的活動(dòng)結(jié)點(diǎn)a處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期活動(dòng)樹上各節(jié)點(diǎn)之間具有下述關(guān)系：同一層次的活動(dòng)生存期不交；任一時(shí)刻，處在生存期的活動(dòng)構(gòu)成一條從根到某節(jié)點(diǎn)的路徑；路徑上各節(jié)點(diǎn)生存期是嵌套的（后進(jìn)先出）?；顒?dòng)樹的特點(diǎn)：127當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中控制棧的內(nèi)容：s,q(1,9),q(1,3),q(2,3)

sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(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)當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中sq(1,9)rp(1128運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息129運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

sa:arrays運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息130運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

si:integerra:arraysr運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息131運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）

sk:integerq(1,9)a:arraysq(1,9)r運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息132運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）sk:integerq(1,9)a:arrayq(1,3)k:integersq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息133過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或134過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列

過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或135過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列

過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程返回序列

過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或136過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列

過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程返回序列

過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或137調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)138過程p調(diào)用過程q的調(diào)用序列p計(jì)算實(shí)參，依次放入棧頂，并在棧頂留出放返回值的空間。top_sp的值在此過程中被改變p把返回地址和當(dāng)前base_sp的值存入q的活動(dòng)記錄中，建立q的訪問鏈，增加base_sp的值q保存寄存器的值和其它機(jī)器狀態(tài)信息q根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體過程p調(diào)用過程q的調(diào)用序列139調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)140過程p調(diào)用過程q的返回序列q把返回值置入鄰近p的活動(dòng)記錄的地方q對(duì)應(yīng)調(diào)用序列的步驟（4），減小top_sp的值

q恢復(fù)寄存器（包括base_sp）和機(jī)器狀態(tài)，返回pp根據(jù)參數(shù)個(gè)數(shù)與類型和返回值類型調(diào)整top_sp，然后取出返回值過程p調(diào)用過程q的返回序列141調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)142過程的參數(shù)個(gè)數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等過程的參數(shù)個(gè)數(shù)可變的情況143調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈訪問鏈和機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)

控制鏈訪問鏈和機(jī)器狀態(tài)top_sp

base_sp

被調(diào)用者的責(zé)任調(diào)用者的責(zé)任被調(diào)用者的活動(dòng)記錄調(diào)用者的活動(dòng)記錄棧調(diào)用者和被調(diào)用者之間的任務(wù)劃分返回值和參數(shù)控制鏈局部數(shù)據(jù)臨時(shí)144活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況局部數(shù)組的大小要等到過程激活時(shí)才能確定在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況145訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組控制鏈top_sp

base_sp

p的活動(dòng)記錄數(shù)組A的指針數(shù)組B的指針數(shù)組A數(shù)組B控制鏈訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組控制鏈top_146懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元147懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元main() | intdangle(){ | { intq; | intj=20; q=dangle(); | return&j;} | }懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元1486.3.3堆式存儲(chǔ)分配

1．局部名的值在活動(dòng)結(jié)束時(shí)必須被保存。

2.被調(diào)用者的活動(dòng)生存期超過調(diào)用者。用活動(dòng)樹不能夠正確描繪這種語言的過程之間的控制流。new(p);dispose(p);6.3.3堆式存儲(chǔ)分配1496.3非局部名字的訪問本節(jié)介紹無過程嵌套的靜態(tài)作用域（C語言）有過程嵌套的靜態(tài)作用域（Pascal語言）動(dòng)態(tài)作用域（Lisp語言）6.3非局部名字的訪問本節(jié)介紹1506.3.1

無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過base_sp指針來訪問無須深入棧中取數(shù)據(jù)，無須訪問鏈過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回6.3.1無過程嵌套的靜態(tài)作用域1516.3.2

有過程嵌套的靜態(tài)作用域過程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 36.3.2有過程嵌套的靜態(tài)作用域1526.3.2

有過程嵌套的靜態(tài)作用域過程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度6.3.2有過程嵌套的靜態(tài)作用域1536.3

非局部名字