1、LI Wensheng, SCST, BUPT 第第7章章 運(yùn)行環(huán)境運(yùn)行環(huán)境知識(shí)點(diǎn)：活動(dòng)記錄、控制棧知識(shí)點(diǎn)：活動(dòng)記錄、控制棧 棧式存儲(chǔ)分配棧式存儲(chǔ)分配 非局部名字的訪問(wèn)非局部名字的訪問(wèn) 參數(shù)傳遞方式參數(shù)傳遞方式1Wensheng Li BUPT 2008運(yùn)行環(huán)境運(yùn)行環(huán)境n程序運(yùn)行時(shí)刻的環(huán)境，即運(yùn)行中程序的信息是怎樣程序運(yùn)行時(shí)刻的環(huán)境，即運(yùn)行中程序的信息是怎樣存儲(chǔ)和訪問(wèn)的。存儲(chǔ)和訪問(wèn)的。n執(zhí)行過(guò)程中，程序中數(shù)據(jù)的存取是通過(guò)對(duì)應(yīng)的存儲(chǔ)執(zhí)行過(guò)程中，程序中數(shù)據(jù)的存取是通過(guò)對(duì)應(yīng)的存儲(chǔ)單元來(lái)進(jìn)行的。單元來(lái)進(jìn)行的。n存儲(chǔ)組織與管理存儲(chǔ)組織與管理早期的計(jì)算機(jī)上，存儲(chǔ)管理工作是由程序員自己來(lái)完成早期的計(jì)算機(jī)上，

2、存儲(chǔ)管理工作是由程序員自己來(lái)完成有了高級(jí)語(yǔ)言之后，程序中使用的存儲(chǔ)單元都由有了高級(jí)語(yǔ)言之后，程序中使用的存儲(chǔ)單元都由標(biāo)識(shí)符標(biāo)識(shí)符來(lái)來(lái)表示，它們對(duì)應(yīng)的內(nèi)存地址由編譯程序在編譯時(shí)或由其生表示，它們對(duì)應(yīng)的內(nèi)存地址由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序在運(yùn)行時(shí)進(jìn)行分配。成的目標(biāo)程序在運(yùn)行時(shí)進(jìn)行分配。n存儲(chǔ)的組織及管理是編譯程序要完成的一個(gè)復(fù)雜而存儲(chǔ)的組織及管理是編譯程序要完成的一個(gè)復(fù)雜而又十分重要的工作。又十分重要的工作。2Wensheng Li BUPT 2008運(yùn)行環(huán)境運(yùn)行環(huán)境7.1 7.1 程序運(yùn)行時(shí)的存儲(chǔ)組織程序運(yùn)行時(shí)的存儲(chǔ)組織7.2 7.2 存儲(chǔ)分配策略存儲(chǔ)分配策略7.3 7.3 訪問(wèn)非局部

3、名字訪問(wèn)非局部名字7.4 7.4 參數(shù)傳遞機(jī)制參數(shù)傳遞機(jī)制 小小 結(jié)結(jié)3Wensheng Li BUPT 20087.1 7.1 程序運(yùn)行時(shí)的存儲(chǔ)組織程序運(yùn)行時(shí)的存儲(chǔ)組織概念：過(guò)程與活動(dòng)概念：過(guò)程與活動(dòng)一、程序運(yùn)行空間的劃分一、程序運(yùn)行空間的劃分二、控制棧與活動(dòng)記錄二、控制棧與活動(dòng)記錄三、作用域及名字綁定三、作用域及名字綁定4Wensheng Li BUPT 2008概念：過(guò)程與活動(dòng)概念：過(guò)程與活動(dòng)n過(guò)程的定義過(guò)程的定義一個(gè)聲明語(yǔ)句一個(gè)聲明語(yǔ)句把一個(gè)標(biāo)識(shí)符和一個(gè)語(yǔ)句聯(lián)系起來(lái)把一個(gè)標(biāo)識(shí)符和一個(gè)語(yǔ)句聯(lián)系起來(lái)標(biāo)識(shí)符是過(guò)程名，語(yǔ)句是過(guò)程體。標(biāo)識(shí)符是過(guò)程名，語(yǔ)句是過(guò)程體。n過(guò)程的分類(lèi)過(guò)程的分類(lèi)過(guò)程：沒(méi)有

4、返回值的過(guò)程過(guò)程：沒(méi)有返回值的過(guò)程函數(shù)：有返回值的過(guò)程函數(shù)：有返回值的過(guò)程也可以把函數(shù)、一個(gè)完整的程序看作過(guò)程也可以把函數(shù)、一個(gè)完整的程序看作過(guò)程n過(guò)程引用：過(guò)程名出現(xiàn)在一個(gè)可執(zhí)行語(yǔ)句中過(guò)程引用：過(guò)程名出現(xiàn)在一個(gè)可執(zhí)行語(yǔ)句中n參數(shù)：參數(shù)：形參、實(shí)參形參、實(shí)參5Wensheng Li BUPT 2008活動(dòng)活動(dòng)n活動(dòng)活動(dòng)一個(gè)過(guò)程的每次執(zhí)行稱(chēng)為它的一次活動(dòng)一個(gè)過(guò)程的每次執(zhí)行稱(chēng)為它的一次活動(dòng)如果一個(gè)過(guò)程在執(zhí)行中，則稱(chēng)它的這次活動(dòng)是如果一個(gè)過(guò)程在執(zhí)行中，則稱(chēng)它的這次活動(dòng)是活著的活著的n過(guò)程與活動(dòng)過(guò)程與活動(dòng)過(guò)程是一個(gè)靜態(tài)概念，活動(dòng)是一個(gè)動(dòng)態(tài)概念過(guò)程是一個(gè)靜態(tài)概念，活動(dòng)是一個(gè)動(dòng)態(tài)概念過(guò)程與活動(dòng)之間可以是過(guò)

5、程與活動(dòng)之間可以是1:1、1:m的關(guān)系的關(guān)系遞歸過(guò)程，同一時(shí)刻可能有若干個(gè)活動(dòng)是活著的遞歸過(guò)程，同一時(shí)刻可能有若干個(gè)活動(dòng)是活著的每個(gè)活動(dòng)都有自己獨(dú)立的存儲(chǔ)空間每個(gè)活動(dòng)都有自己獨(dú)立的存儲(chǔ)空間/ /數(shù)據(jù)空間數(shù)據(jù)空間PPPP有有3個(gè)活著的活動(dòng)個(gè)活著的活動(dòng)P有有2個(gè)活著的活動(dòng)個(gè)活著的活動(dòng)P有有1個(gè)活著的活動(dòng)個(gè)活著的活動(dòng)6Wensheng Li BUPT 2008活動(dòng)的生存期活動(dòng)的生存期n程序執(zhí)行時(shí)程序執(zhí)行時(shí), ,過(guò)程之間的控制流過(guò)程之間的控制流是連續(xù)的是連續(xù)的過(guò)程的每一次執(zhí)行都是從過(guò)程體的起點(diǎn)開(kāi)始，最后控制返回到直接過(guò)程的每一次執(zhí)行都是從過(guò)程體的起點(diǎn)開(kāi)始，最后控制返回到直接跟隨本次調(diào)用點(diǎn)的位置。跟隨本

6、次調(diào)用點(diǎn)的位置。n活動(dòng)的生存期活動(dòng)的生存期過(guò)程體的執(zhí)行中，第一步和最后一步之間的一系列步驟的執(zhí)行時(shí)間過(guò)程體的執(zhí)行中，第一步和最后一步之間的一系列步驟的執(zhí)行時(shí)間過(guò)程過(guò)程P的一次活動(dòng)的生存期，包括執(zhí)行過(guò)程的一次活動(dòng)的生存期，包括執(zhí)行過(guò)程P所調(diào)用的過(guò)程的時(shí)間，所調(diào)用的過(guò)程的時(shí)間，以及這些過(guò)程所調(diào)用的過(guò)程的時(shí)間以及這些過(guò)程所調(diào)用的過(guò)程的時(shí)間如果如果a和和b是過(guò)程的活動(dòng)，那么它們的生存期要么是不重疊，要么是是過(guò)程的活動(dòng)，那么它們的生存期要么是不重疊，要么是嵌套的。嵌套的。n遞歸過(guò)程：遞歸過(guò)程：如果一個(gè)過(guò)程，它的不同活動(dòng)的生存期可以嵌套，則這個(gè)過(guò)程是遞如果一個(gè)過(guò)程，它的不同活動(dòng)的生存期可以嵌套，則這個(gè)過(guò)程

7、是遞歸的歸的直接遞歸、間接遞歸直接遞歸、間接遞歸ababab7Wensheng Li BUPT 2008一、程序運(yùn)行空間的劃分一、程序運(yùn)行空間的劃分n編譯程序在編譯源程序時(shí)，向操作系統(tǒng)申請(qǐng)一塊編譯程序在編譯源程序時(shí)，向操作系統(tǒng)申請(qǐng)一塊內(nèi)存區(qū)域，以便被編譯程序在其中運(yùn)行內(nèi)存區(qū)域，以便被編譯程序在其中運(yùn)行代碼區(qū)代碼區(qū)/ 保存目標(biāo)代碼保存目標(biāo)代碼 靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū) 控制棧控制棧 堆堆 編譯時(shí)可以確定代碼段的長(zhǎng)度，編譯時(shí)可以確定代碼段的長(zhǎng)度，可以放在一個(gè)靜態(tài)確定的區(qū)域內(nèi)可以放在一個(gè)靜態(tài)確定的區(qū)域內(nèi)編譯時(shí)可確定大小的數(shù)據(jù)對(duì)象，放在靜態(tài)確編譯時(shí)可確定大小的數(shù)據(jù)對(duì)象，放在靜態(tài)確定的區(qū)域內(nèi)，目標(biāo)地址可以編

8、入目標(biāo)代碼中定的區(qū)域內(nèi)，目標(biāo)地址可以編入目標(biāo)代碼中用于管理過(guò)程的活動(dòng)、用于管理過(guò)程的活動(dòng)、保存斷點(diǎn)的現(xiàn)場(chǎng)信息，用于返回時(shí)的恢復(fù)保存斷點(diǎn)的現(xiàn)場(chǎng)信息，用于返回時(shí)的恢復(fù)程序控制下進(jìn)行的動(dòng)態(tài)存儲(chǔ)分配，程序控制下進(jìn)行的動(dòng)態(tài)存儲(chǔ)分配，分配在堆中，如分配在堆中，如Pascal中中new函數(shù)函數(shù)?8Wensheng Li BUPT 2008二、控制棧與活動(dòng)記錄二、控制棧與活動(dòng)記錄n控制棧：用于保存控制信息的棧?？刂茥＃河糜诒４婵刂菩畔⒌臈?。程序執(zhí)行過(guò)程中使用控制棧來(lái)保存活動(dòng)的生存蹤跡及活動(dòng)程序執(zhí)行過(guò)程中使用控制棧來(lái)保存活動(dòng)的生存蹤跡及活動(dòng)的運(yùn)行環(huán)境。的運(yùn)行環(huán)境。 n活動(dòng)記錄：一個(gè)連續(xù)的存儲(chǔ)塊活動(dòng)記錄：一個(gè)連續(xù)

9、的存儲(chǔ)塊記錄過(guò)程在一次執(zhí)行中所需要的信息記錄過(guò)程在一次執(zhí)行中所需要的信息n通常，活動(dòng)記錄分配在控制棧中（像通常，活動(dòng)記錄分配在控制棧中（像PascalPascal、C C）當(dāng)一個(gè)過(guò)程被調(diào)用時(shí)，被調(diào)用過(guò)程的一次新的活動(dòng)被激活，當(dāng)一個(gè)過(guò)程被調(diào)用時(shí)，被調(diào)用過(guò)程的一次新的活動(dòng)被激活，在棧頂為該活動(dòng)創(chuàng)建一個(gè)新的活動(dòng)記錄來(lái)保存其環(huán)境信息；在棧頂為該活動(dòng)創(chuàng)建一個(gè)新的活動(dòng)記錄來(lái)保存其環(huán)境信息；當(dāng)活動(dòng)結(jié)束，控制從被調(diào)用過(guò)程返回時(shí)，釋放該活動(dòng)記錄，當(dāng)活動(dòng)結(jié)束，控制從被調(diào)用過(guò)程返回時(shí)，釋放該活動(dòng)記錄，使調(diào)用過(guò)程的活動(dòng)記錄成為棧頂活動(dòng)記錄，即恢復(fù)調(diào)用過(guò)使調(diào)用過(guò)程的活動(dòng)記錄成為棧頂活動(dòng)記錄，即恢復(fù)調(diào)用過(guò)程的執(zhí)行環(huán)境。程

10、的執(zhí)行環(huán)境。 9Wensheng Li BUPT 2008活動(dòng)記錄的內(nèi)容活動(dòng)記錄的內(nèi)容返回值返回值實(shí)參區(qū)域?qū)崊^(qū)域控制鏈控制鏈訪問(wèn)鏈訪問(wèn)鏈機(jī)器狀態(tài)域機(jī)器狀態(tài)域局部數(shù)據(jù)區(qū)局部數(shù)據(jù)區(qū)臨時(shí)數(shù)據(jù)區(qū)臨時(shí)數(shù)據(jù)區(qū)存放中間計(jì)算結(jié)果存放中間計(jì)算結(jié)果在本次活動(dòng)中，為過(guò)程中定義的局部變量在本次活動(dòng)中，為過(guò)程中定義的局部變量分配的存儲(chǔ)空間分配的存儲(chǔ)空間保存斷點(diǎn)的現(xiàn)場(chǎng)信息，寄存器、保存斷點(diǎn)的現(xiàn)場(chǎng)信息，寄存器、PSWPSW等等指向直接外圍過(guò)程的最近一次活動(dòng)的活動(dòng)指向直接外圍過(guò)程的最近一次活動(dòng)的活動(dòng)記錄的指針，用于對(duì)非局部名字的訪問(wèn)記錄的指針，用于對(duì)非局部名字的訪問(wèn)指向調(diào)用過(guò)程的活動(dòng)記錄的指針，指向調(diào)用過(guò)程的活動(dòng)記錄的指針

11、，用于本活動(dòng)結(jié)束時(shí)的恢復(fù)用于本活動(dòng)結(jié)束時(shí)的恢復(fù)調(diào)用過(guò)程提供給本活動(dòng)的實(shí)參值調(diào)用過(guò)程提供給本活動(dòng)的實(shí)參值本活動(dòng)返回給調(diào)用過(guò)程的值本活動(dòng)返回給調(diào)用過(guò)程的值根據(jù)確定每個(gè)域所需空間大小的時(shí)間早晚安排其位置。根據(jù)確定每個(gè)域所需空間大小的時(shí)間早晚安排其位置。(1) 早：中間早：中間 晚：兩頭晚：兩頭 (2) 用于通信：前面用于通信：前面 自己用的：后面自己用的：后面10Wensheng Li BUPT 2008活動(dòng)記錄中內(nèi)容的安排原則活動(dòng)記錄中內(nèi)容的安排原則n大小能夠較早確定的區(qū)域放在活動(dòng)記錄的中間，大小能夠較早確定的區(qū)域放在活動(dòng)記錄的中間，大小較晚才能確定、并且變化較多的區(qū)域放在活大小較晚才能確定、并且

12、變化較多的區(qū)域放在活動(dòng)記錄的兩頭。動(dòng)記錄的兩頭。控制鏈、訪問(wèn)鏈、機(jī)器狀態(tài)域，是編譯器設(shè)計(jì)的一部分，控制鏈、訪問(wèn)鏈、機(jī)器狀態(tài)域，是編譯器設(shè)計(jì)的一部分，編譯器構(gòu)造時(shí)就可以確定它們的大小，所以把這些區(qū)域編譯器構(gòu)造時(shí)就可以確定它們的大小，所以把這些區(qū)域放在活動(dòng)記錄的中間。放在活動(dòng)記錄的中間。參數(shù)域放在前面，便于調(diào)用過(guò)程進(jìn)行參數(shù)傳遞，同時(shí)，參數(shù)域放在前面，便于調(diào)用過(guò)程進(jìn)行參數(shù)傳遞，同時(shí)，被調(diào)用過(guò)程也可很方便地進(jìn)行訪問(wèn)。被調(diào)用過(guò)程也可很方便地進(jìn)行訪問(wèn)。返回值域放在最前面，便于調(diào)用過(guò)程可以根據(jù)自己的棧返回值域放在最前面，便于調(diào)用過(guò)程可以根據(jù)自己的棧指針訪問(wèn)該區(qū)域，取回返回值。指針訪問(wèn)該區(qū)域，取回返回值。局部

13、數(shù)據(jù)局部數(shù)據(jù)/ /臨時(shí)數(shù)據(jù)安排在最后，其大小變化不會(huì)影響臨時(shí)數(shù)據(jù)安排在最后，其大小變化不會(huì)影響到活動(dòng)記錄中其他數(shù)據(jù)的存取。并且調(diào)用過(guò)程也無(wú)權(quán)訪到活動(dòng)記錄中其他數(shù)據(jù)的存取。并且調(diào)用過(guò)程也無(wú)權(quán)訪問(wèn)被調(diào)用過(guò)程中的局部數(shù)據(jù)。問(wèn)被調(diào)用過(guò)程中的局部數(shù)據(jù)。11Wensheng Li BUPT 2008局部數(shù)據(jù)的安排局部數(shù)據(jù)的安排n常識(shí)：常識(shí)：程序運(yùn)行時(shí)使用連續(xù)的存儲(chǔ)空間程序運(yùn)行時(shí)使用連續(xù)的存儲(chǔ)空間內(nèi)存可編址的最小單位是字節(jié)內(nèi)存可編址的最小單位是字節(jié)一個(gè)機(jī)器字由若干個(gè)字節(jié)組成一個(gè)機(jī)器字由若干個(gè)字節(jié)組成一個(gè)名字所需存儲(chǔ)空間的大小由其類(lèi)型決定一個(gè)名字所需存儲(chǔ)空間的大小由其類(lèi)型決定需多個(gè)字節(jié)表示的數(shù)據(jù)對(duì)象，存放在連

14、續(xù)字節(jié)的存儲(chǔ)塊中，需多個(gè)字節(jié)表示的數(shù)據(jù)對(duì)象，存放在連續(xù)字節(jié)的存儲(chǔ)塊中，第一個(gè)字節(jié)的地址作為它的地址第一個(gè)字節(jié)的地址作為它的地址n局部數(shù)據(jù)的安排局部數(shù)據(jù)的安排局部數(shù)據(jù)區(qū)是在編譯過(guò)程中檢查聲明語(yǔ)句時(shí)安排的局部數(shù)據(jù)區(qū)是在編譯過(guò)程中檢查聲明語(yǔ)句時(shí)安排的長(zhǎng)度可變的數(shù)據(jù)對(duì)象，放在該區(qū)域之外長(zhǎng)度可變的數(shù)據(jù)對(duì)象，放在該區(qū)域之外n數(shù)據(jù)對(duì)象的存儲(chǔ)安排受目標(biāo)機(jī)器編址限制的影響數(shù)據(jù)對(duì)象的存儲(chǔ)安排受目標(biāo)機(jī)器編址限制的影響12Wensheng Li BUPT 2008編址限制的影響編址限制的影響n(yōu)整數(shù)加法指令可能要求整數(shù)整數(shù)加法指令可能要求整數(shù)的地址能夠被的地址能夠被4 4整除整除n要求地址對(duì)齊要求地址對(duì)齊如：如：x:i

15、nteger; y:char; z:integer; n為求分配上的全局統(tǒng)一，而多余出來(lái)的無(wú)用空間為求分配上的全局統(tǒng)一，而多余出來(lái)的無(wú)用空間叫做填塞（叫做填塞（padding）如果如果char占一個(gè)字節(jié)，占一個(gè)字節(jié)，integer占占2個(gè)字節(jié)個(gè)字節(jié), ,x、y、z共需要共需要5個(gè)字節(jié)。個(gè)字節(jié)。如果要求從雙字節(jié)地址分配，如果要求從雙字節(jié)地址分配，則需要為這三個(gè)變量分配則需要為這三個(gè)變量分配6個(gè)字節(jié)，個(gè)字節(jié)，13Wensheng Li BUPT 2008三、作用域及名字綁定三、作用域及名字綁定n聲明是一個(gè)把信息與名字聯(lián)系起來(lái)的語(yǔ)法結(jié)構(gòu)聲明是一個(gè)把信息與名字聯(lián)系起來(lái)的語(yǔ)法結(jié)構(gòu)顯式聲明（如顯式聲明（如

16、PASCAL中的聲明：中的聲明：var i:integer）隱含聲明（如隱含聲明（如FORTRAN程序）程序）n在一個(gè)程序的不同部分可能有對(duì)同一個(gè)名字的相互在一個(gè)程序的不同部分可能有對(duì)同一個(gè)名字的相互獨(dú)立的聲明獨(dú)立的聲明n一個(gè)聲明起作用的程序部分稱(chēng)為該聲明的作用域一個(gè)聲明起作用的程序部分稱(chēng)為該聲明的作用域n語(yǔ)言的作用域規(guī)則決定了當(dāng)這樣的名字在程序正文語(yǔ)言的作用域規(guī)則決定了當(dāng)這樣的名字在程序正文中出現(xiàn)時(shí)應(yīng)該使用哪一個(gè)聲明中出現(xiàn)時(shí)應(yīng)該使用哪一個(gè)聲明nPascal中的名字遵循中的名字遵循“最近嵌套原則最近嵌套原則”n編譯過(guò)程中，名字的作用域信息記錄在符號(hào)表中編譯過(guò)程中，名字的作用域信息記錄在符號(hào)表中

17、14Wensheng Li BUPT 2008名字的綁定名字的綁定n把名字對(duì)應(yīng)到存儲(chǔ)單元的過(guò)程把名字對(duì)應(yīng)到存儲(chǔ)單元的過(guò)程n名字與存儲(chǔ)單元的對(duì)應(yīng)關(guān)系：名字與存儲(chǔ)單元的對(duì)應(yīng)關(guān)系： 1:1 1:mn當(dāng)當(dāng)environment把一個(gè)存儲(chǔ)單元把一個(gè)存儲(chǔ)單元S與一個(gè)名字與一個(gè)名字X聯(lián)系起來(lái)時(shí)，稱(chēng)聯(lián)系起來(lái)時(shí)，稱(chēng)X受限于受限于S。nS的大小取決于的大小取決于X的類(lèi)型的類(lèi)型一個(gè)活動(dòng)中的名字與其存儲(chǔ)單元之間一個(gè)活動(dòng)中的名字與其存儲(chǔ)單元之間一個(gè)遞歸過(guò)程中的名字與其存儲(chǔ)單元之間一個(gè)遞歸過(guò)程中的名字與其存儲(chǔ)單元之間名字名字X 存儲(chǔ)單元存儲(chǔ)單元S S的內(nèi)容的內(nèi)容Venvironmentstate地址為名字的左值地址為名字

18、的左值名字的右值名字的右值15Wensheng Li BUPT 2008與存儲(chǔ)組織與管理有關(guān)的其他問(wèn)題與存儲(chǔ)組織與管理有關(guān)的其他問(wèn)題n名字的存儲(chǔ)空間如何組織、名字綁定的方法等主要名字的存儲(chǔ)空間如何組織、名字綁定的方法等主要取決于對(duì)以下問(wèn)題的回答：取決于對(duì)以下問(wèn)題的回答：過(guò)程是否可遞歸？過(guò)程是否可遞歸？當(dāng)控制從過(guò)程的一次活動(dòng)返回時(shí)，對(duì)局部名字的值如何當(dāng)控制從過(guò)程的一次活動(dòng)返回時(shí)，對(duì)局部名字的值如何處理？處理？過(guò)程是否可以引用非局部的名字？過(guò)程是否可以引用非局部的名字？過(guò)程調(diào)用時(shí)如何傳遞參數(shù)？過(guò)程調(diào)用時(shí)如何傳遞參數(shù)？過(guò)程是否可以作為參數(shù)傳遞？過(guò)程是否可以作為參數(shù)傳遞？過(guò)程可否作為結(jié)果被返回？過(guò)程可

19、否作為結(jié)果被返回？存儲(chǔ)空間能否在程序控制下進(jìn)行動(dòng)態(tài)分配？存儲(chǔ)空間能否在程序控制下進(jìn)行動(dòng)態(tài)分配？存儲(chǔ)空間是否必須顯式地歸還？存儲(chǔ)空間是否必須顯式地歸還？16Wensheng Li BUPT 20087.2 7.2 存儲(chǔ)分配策略存儲(chǔ)分配策略n運(yùn)行時(shí)刻存儲(chǔ)空間的劃分，除目標(biāo)代碼外，其余三運(yùn)行時(shí)刻存儲(chǔ)空間的劃分，除目標(biāo)代碼外，其余三種數(shù)據(jù)空間采用的存儲(chǔ)分配策略是不同的。種數(shù)據(jù)空間采用的存儲(chǔ)分配策略是不同的。靜態(tài)存儲(chǔ)分配：編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配存儲(chǔ)空間靜態(tài)存儲(chǔ)分配：編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配存儲(chǔ)空間棧式存儲(chǔ)分配：運(yùn)行時(shí)把存儲(chǔ)器作為棧進(jìn)行管理，數(shù)據(jù)對(duì)棧式存儲(chǔ)分配：運(yùn)行時(shí)把存儲(chǔ)器作為棧進(jìn)行管理，數(shù)據(jù)對(duì)象分配

20、在棧中象分配在棧中堆式存儲(chǔ)分配：運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，對(duì)用戶(hù)提堆式存儲(chǔ)分配：運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，對(duì)用戶(hù)提出的存儲(chǔ)空間的申請(qǐng)與歸還進(jìn)行存儲(chǔ)分配與回收。出的存儲(chǔ)空間的申請(qǐng)與歸還進(jìn)行存儲(chǔ)分配與回收。一、靜態(tài)存儲(chǔ)分配一、靜態(tài)存儲(chǔ)分配二、棧式存儲(chǔ)分配二、棧式存儲(chǔ)分配三、堆式存儲(chǔ)分配三、堆式存儲(chǔ)分配17Wensheng Li BUPT 2008一、靜態(tài)存儲(chǔ)分配一、靜態(tài)存儲(chǔ)分配n條件：條件：源程序中出現(xiàn)的各種數(shù)據(jù)所需要的存儲(chǔ)空間源程序中出現(xiàn)的各種數(shù)據(jù)所需要的存儲(chǔ)空間的大小在的大小在編譯時(shí)可以確定編譯時(shí)可以確定n存儲(chǔ)分配：編譯時(shí)存儲(chǔ)分配：編譯時(shí), ,為他們分配為他們分配固定的固定的存儲(chǔ)空間存儲(chǔ)空

21、間n運(yùn)行時(shí)：運(yùn)行時(shí)：總是總是使用這些存儲(chǔ)空間使用這些存儲(chǔ)空間過(guò)程每次被激活，同一名字都使用相同的存儲(chǔ)空間過(guò)程每次被激活，同一名字都使用相同的存儲(chǔ)空間允許局部名字的值在活動(dòng)結(jié)束后被保留下來(lái)允許局部名字的值在活動(dòng)結(jié)束后被保留下來(lái)當(dāng)控制再次進(jìn)入時(shí)，局部名字的值即上次離開(kāi)時(shí)的值當(dāng)控制再次進(jìn)入時(shí)，局部名字的值即上次離開(kāi)時(shí)的值n數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：每個(gè)過(guò)程的活動(dòng)記錄的位置及大小每個(gè)過(guò)程的活動(dòng)記錄的位置及大小記錄中每一個(gè)名字所占用的存儲(chǔ)空間的位置及大小記錄中每一個(gè)名字所占用的存儲(chǔ)空間的位置及大小數(shù)據(jù)在運(yùn)行時(shí)刻的地址可以填入到目標(biāo)代碼中數(shù)據(jù)在運(yùn)行時(shí)刻的地址可以填入到目標(biāo)代碼中18Wensheng Li BUP

22、T 2008靜態(tài)存儲(chǔ)分配策略對(duì)源語(yǔ)言的限制靜態(tài)存儲(chǔ)分配策略對(duì)源語(yǔ)言的限制n數(shù)據(jù)對(duì)象的大小和它們?cè)趦?nèi)存中的位置必須在編譯數(shù)據(jù)對(duì)象的大小和它們?cè)趦?nèi)存中的位置必須在編譯時(shí)都能夠確定時(shí)都能夠確定n不允許過(guò)程遞歸調(diào)用不允許過(guò)程遞歸調(diào)用因?yàn)槭褂渺o態(tài)存儲(chǔ)分配，一個(gè)過(guò)程里聲明的局部數(shù)據(jù)在該因?yàn)槭褂渺o態(tài)存儲(chǔ)分配，一個(gè)過(guò)程里聲明的局部數(shù)據(jù)在該過(guò)程的所有活動(dòng)中都結(jié)合到同一個(gè)地址。過(guò)程的所有活動(dòng)中都結(jié)合到同一個(gè)地址。n不能建立動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)不能建立動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)因?yàn)闆](méi)有在運(yùn)行時(shí)進(jìn)行存儲(chǔ)分配的機(jī)制。因?yàn)闆](méi)有在運(yùn)行時(shí)進(jìn)行存儲(chǔ)分配的機(jī)制。19Wensheng Li BUPT 2008靜態(tài)存儲(chǔ)分配策略的實(shí)現(xiàn)靜態(tài)存儲(chǔ)分配策略的實(shí)現(xiàn)

23、n編譯器處理聲明語(yǔ)句時(shí)，每遇到一個(gè)變量名就創(chuàng)建一個(gè)符號(hào)編譯器處理聲明語(yǔ)句時(shí)，每遇到一個(gè)變量名就創(chuàng)建一個(gè)符號(hào)表?xiàng)l目，填入相應(yīng)的屬性，包括目標(biāo)地址。表?xiàng)l目，填入相應(yīng)的屬性，包括目標(biāo)地址。n每個(gè)變量所需空間的大小由其類(lèi)型確定，并且在編譯時(shí)刻是每個(gè)變量所需空間的大小由其類(lèi)型確定，并且在編譯時(shí)刻是已知的。已知的。n根據(jù)名字出現(xiàn)的先后順序，連續(xù)分配空間根據(jù)名字出現(xiàn)的先后順序，連續(xù)分配空間name type address . lengthN1 0 n1N2 n1 n2N3 n1+n2 n3. . . 代碼區(qū)代碼區(qū) 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) N1N2程程序序的的邏邏輯輯空空間間0LA.20Wensheng Li BUP

24、T 2008PROGRAM CNSUME CHARACTER *50 BUF INTEGER NEXT CHARACTER C, PRDUCE DATA NEXT /1/, BUF / /6 C=PRDUCE() BUF (NEXT:NEXT)=C NEXT=NEXT+1 IF (C .NE. ) GOTO 6 WRITE (*, (A) ) BUF ENDFortran程序舉例程序舉例CHARACTER FUNCTION PRDUCE() CHARACTER *80 BUFFER INTEGER NEXT SAVE BUFFER,NEXT DATA NEXT /81/ IF (NEXT .G

25、T. 80) THEN READ (*, (A) ) BUFFER NEXT=1 END IF PRDUCE=BUFFER (NEXT:NEXT) NEXT=NEXT+1 END21Wensheng Li BUPT 2008存儲(chǔ)空間分配存儲(chǔ)空間分配CNSUME的代碼的代碼PRDUCE的代碼的代碼靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū)代碼區(qū)代碼區(qū)CNSUME的活動(dòng)記錄的活動(dòng)記錄PRDUCE的活動(dòng)記錄的活動(dòng)記錄CHARACTER *50 BUFINTEGER NEXTCHARACTER CCHARACTER *80 BUFFERINTEGER NEXT22Wensheng Li BUPT 2008二、棧式存儲(chǔ)分配二

26、、棧式存儲(chǔ)分配n存儲(chǔ)空間被組織成棧存儲(chǔ)空間被組織成棧n存儲(chǔ)管理存儲(chǔ)管理活動(dòng)開(kāi)始時(shí)，與活動(dòng)相應(yīng)的活動(dòng)記錄入棧，局部變量的活動(dòng)開(kāi)始時(shí)，與活動(dòng)相應(yīng)的活動(dòng)記錄入棧，局部變量的存儲(chǔ)空間分配在該活動(dòng)記錄中。同一過(guò)程中聲明的名字存儲(chǔ)空間分配在該活動(dòng)記錄中。同一過(guò)程中聲明的名字在不同的活動(dòng)中被結(jié)合到不同的存儲(chǔ)空間。在不同的活動(dòng)中被結(jié)合到不同的存儲(chǔ)空間?；顒?dòng)結(jié)束時(shí)，活動(dòng)記錄出棧，分配給局部名字的存儲(chǔ)空活動(dòng)結(jié)束時(shí)，活動(dòng)記錄出棧，分配給局部名字的存儲(chǔ)空間被釋放。名字的值將丟失，不可再用。間被釋放。名字的值將丟失，不可再用。.top.ntopq的活動(dòng)開(kāi)始的活動(dòng)開(kāi)始qa.topq的活動(dòng)結(jié)束的活動(dòng)結(jié)束23Wensheng

27、 Li BUPT 2008 program sort(input, output); var a: array0.10 of integer; x: integer; procedure readarray; var i: integer; begin for i:=1 to 9 do read(ai) end; prcedure exchange(i, j: integer); begin x:=ai; ai:=aj; aj:=x end; procedure quicksort(m, n: integer); var k, v: integer; function partition(y,

28、 z: integer): integer; var i, j: integer; begin a ; v ; exchange(i, j); end; begin if (nm) then begin i:=partition(m, n); quicksort(m,i-1); quicksort(i+1, n) end end quicksort; begin a0:=-999; a10=999; readarray; quicksort(1, 9) end sort.對(duì)讀入的數(shù)據(jù)進(jìn)行排序的PASCAL程序24Wensheng Li BUPT 2008控制棧的變化舉例控制棧的變化舉例Ssa

29、: arrayx : integerr r i : integer q(1,9)p(1,9) =4 q(1,9) k : integer v : integerp(1,9) i : integer j : integere(1,9) q(1,3) q(1,3) k : integer v : integerp(1,3) =1 e(1,9)p(1,3) i : integer j : integere(1,3)e(1,3) q(1,0) q(1,0) k : integer v : integer q(2,3) q(2,3) k : integer v : integerk入棧？入棧？出棧？出棧

30、？25Wensheng Li BUPT 2008調(diào)用序列調(diào)用序列n除局部數(shù)據(jù)外，除局部數(shù)據(jù)外，活動(dòng)記錄中還活動(dòng)記錄中還有實(shí)現(xiàn)過(guò)程調(diào)有實(shí)現(xiàn)過(guò)程調(diào)用和返回的控用和返回的控制信息制信息n活動(dòng)記錄的入活動(dòng)記錄的入棧，實(shí)現(xiàn)了控棧，實(shí)現(xiàn)了控制從調(diào)用過(guò)程制從調(diào)用過(guò)程到被調(diào)用過(guò)程到被調(diào)用過(guò)程的轉(zhuǎn)移的轉(zhuǎn)移n控制的轉(zhuǎn)移由控制的轉(zhuǎn)移由一段代碼（即一段代碼（即調(diào)用序列調(diào)用序列）來(lái)）來(lái)實(shí)現(xiàn)實(shí)現(xiàn)調(diào)用過(guò)程調(diào)用過(guò)程 p的活動(dòng)記錄的活動(dòng)記錄被調(diào)用過(guò)程被調(diào)用過(guò)程q的活動(dòng)記錄的活動(dòng)記錄返回值域返回值域參數(shù)域參數(shù)域控制鏈控制鏈訪問(wèn)鏈訪問(wèn)鏈機(jī)器狀態(tài)域機(jī)器狀態(tài)域局部數(shù)據(jù)域局部數(shù)據(jù)域臨時(shí)數(shù)據(jù)域臨時(shí)數(shù)據(jù)域返回值域返回值域參數(shù)域參數(shù)域控制鏈控

31、制鏈訪問(wèn)鏈訪問(wèn)鏈機(jī)器狀態(tài)域機(jī)器狀態(tài)域局部數(shù)據(jù)域局部數(shù)據(jù)域臨時(shí)數(shù)據(jù)域臨時(shí)數(shù)據(jù)域top_eptop_sptop_ep top_sp PSWtop_sp 26Wensheng Li BUPT 2008調(diào)用序列的安排調(diào)用序列的安排n參數(shù)傳遞：參數(shù)傳遞： p計(jì)算實(shí)參的值，寫(xiě)入計(jì)算實(shí)參的值，寫(xiě)入q的活動(dòng)記錄的參數(shù)域；的活動(dòng)記錄的參數(shù)域；n控制信息設(shè)置：控制信息設(shè)置： p將返回地址寫(xiě)入將返回地址寫(xiě)入q的活動(dòng)記錄的機(jī)器狀態(tài)域中的活動(dòng)記錄的機(jī)器狀態(tài)域中 p將當(dāng)前的將當(dāng)前的top_ep的值寫(xiě)入的值寫(xiě)入q的活動(dòng)記錄的控制鏈域的活動(dòng)記錄的控制鏈域 p為為q建立訪問(wèn)鏈建立訪問(wèn)鏈 p設(shè)置新的設(shè)置新的top_ep的值的值(

32、 (指向指向q的活動(dòng)記錄中某個(gè)位置的活動(dòng)記錄中某個(gè)位置) )n進(jìn)入進(jìn)入q的代碼的代碼( (goto語(yǔ)句語(yǔ)句) )nq保存寄存器的值、以及其他機(jī)器狀態(tài)信息保存寄存器的值、以及其他機(jī)器狀態(tài)信息nq增加增加top_sp的值，初始化局部變量的值，初始化局部變量n開(kāi)始執(zhí)行開(kāi)始執(zhí)行27Wensheng Li BUPT 2008返回序列返回序列nq把返回值寫(xiě)入自己活動(dòng)記錄的返回值域把返回值寫(xiě)入自己活動(dòng)記錄的返回值域nq恢復(fù)斷點(diǎn)狀態(tài)：恢復(fù)斷點(diǎn)狀態(tài)：寄存器的值寄存器的值 top_sp和和top_ep的值的值機(jī)器狀態(tài)機(jī)器狀態(tài)n根據(jù)返回地址返回到根據(jù)返回地址返回到p的代碼中（的代碼中（goto語(yǔ)句）語(yǔ)句）np把返回

33、值取入自己的活動(dòng)記錄中把返回值取入自己的活動(dòng)記錄中np繼續(xù)執(zhí)行繼續(xù)執(zhí)行28Wensheng Li BUPT 2008調(diào)用序列與活動(dòng)記錄調(diào)用序列與活動(dòng)記錄n區(qū)別：區(qū)別：活動(dòng)記錄是一塊連續(xù)的存儲(chǔ)區(qū)域，保存一個(gè)活動(dòng)所需的全活動(dòng)記錄是一塊連續(xù)的存儲(chǔ)區(qū)域，保存一個(gè)活動(dòng)所需的全部信息，與活動(dòng)一一對(duì)應(yīng)。部信息，與活動(dòng)一一對(duì)應(yīng)。調(diào)用序列是一段代碼，完成活動(dòng)記錄的入棧，實(shí)現(xiàn)控制從調(diào)用序列是一段代碼，完成活動(dòng)記錄的入棧，實(shí)現(xiàn)控制從調(diào)用過(guò)程到被調(diào)用過(guò)程的轉(zhuǎn)移。調(diào)用過(guò)程到被調(diào)用過(guò)程的轉(zhuǎn)移。調(diào)用序列邏輯上是一個(gè)整體，物理上被分成兩部分，分屬調(diào)用序列邏輯上是一個(gè)整體，物理上被分成兩部分，分屬于調(diào)用過(guò)程和被調(diào)用過(guò)程。于調(diào)用

34、過(guò)程和被調(diào)用過(guò)程。n聯(lián)系：聯(lián)系：調(diào)用序列的實(shí)現(xiàn)與活動(dòng)記錄中內(nèi)容的安排有密切關(guān)系調(diào)用序列的實(shí)現(xiàn)與活動(dòng)記錄中內(nèi)容的安排有密切關(guān)系29Wensheng Li BUPT 2008可變長(zhǎng)數(shù)據(jù)的處理可變長(zhǎng)數(shù)據(jù)的處理n某些語(yǔ)言允許由實(shí)參的值決定被調(diào)用過(guò)程中局部數(shù)某些語(yǔ)言允許由實(shí)參的值決定被調(diào)用過(guò)程中局部數(shù)組的大小組的大小可變數(shù)組可變數(shù)組n可變數(shù)組的大小只有到執(zhí)行過(guò)程調(diào)用時(shí)才能確定可變數(shù)組的大小只有到執(zhí)行過(guò)程調(diào)用時(shí)才能確定n編譯時(shí)可以確定數(shù)組的個(gè)數(shù)編譯時(shí)可以確定數(shù)組的個(gè)數(shù)n活動(dòng)記錄中只設(shè)置相應(yīng)于可變數(shù)組的指針，而不包活動(dòng)記錄中只設(shè)置相應(yīng)于可變數(shù)組的指針，而不包括這些數(shù)組的數(shù)據(jù)空間括這些數(shù)組的數(shù)據(jù)空間n可變數(shù)組

35、的數(shù)據(jù)空間放在活動(dòng)記錄之外可變數(shù)組的數(shù)據(jù)空間放在活動(dòng)記錄之外30Wensheng Li BUPT 2008可變數(shù)組的空間分配可變數(shù)組的空間分配調(diào)用過(guò)程調(diào)用過(guò)程 p的活動(dòng)記錄的活動(dòng)記錄被調(diào)用過(guò)程被調(diào)用過(guò)程q的活動(dòng)記錄的活動(dòng)記錄返回值域返回值域/ /參數(shù)域參數(shù)域控制鏈控制鏈訪問(wèn)鏈訪問(wèn)鏈/ /機(jī)器狀態(tài)域機(jī)器狀態(tài)域局部局部/ /臨時(shí)數(shù)據(jù)域臨時(shí)數(shù)據(jù)域top_eptop_eptop_sptop_sp返回值域返回值域/ /參數(shù)域參數(shù)域控制鏈控制鏈訪問(wèn)鏈訪問(wèn)鏈/ /機(jī)器狀態(tài)域機(jī)器狀態(tài)域局部數(shù)據(jù)域局部數(shù)據(jù)域臨時(shí)數(shù)據(jù)域臨時(shí)數(shù)據(jù)域pointer to array Apointer to array B數(shù)組數(shù)組A數(shù)組

36、數(shù)組B31Wensheng Li BUPT 2008三、堆式存儲(chǔ)分配三、堆式存儲(chǔ)分配n如果如果具體的存儲(chǔ)需求在編譯時(shí)刻可以確定具體的存儲(chǔ)需求在編譯時(shí)刻可以確定采取采取靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配策略策略n如果某些存儲(chǔ)需求在編譯時(shí)不能確定，但在程序執(zhí)如果某些存儲(chǔ)需求在編譯時(shí)不能確定，但在程序執(zhí)行期間，在程序的入口點(diǎn)上可以知道行期間，在程序的入口點(diǎn)上可以知道采用采用棧式存儲(chǔ)分配棧式存儲(chǔ)分配策略策略n棧式存儲(chǔ)分配策略不能處理的存儲(chǔ)需求：棧式存儲(chǔ)分配策略不能處理的存儲(chǔ)需求：程序設(shè)計(jì)語(yǔ)言中的某些數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)需求程序設(shè)計(jì)語(yǔ)言中的某些數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)需求活動(dòng)停止時(shí)局部名字的值必須被保存下來(lái)活動(dòng)停止時(shí)局部名字的值

37、必須被保存下來(lái)被調(diào)用過(guò)程的活動(dòng)生存期超過(guò)調(diào)用過(guò)程的生存期，這種語(yǔ)被調(diào)用過(guò)程的活動(dòng)生存期超過(guò)調(diào)用過(guò)程的生存期，這種語(yǔ)言的過(guò)程間的控制流不能用活動(dòng)樹(shù)正確地描述。言的過(guò)程間的控制流不能用活動(dòng)樹(shù)正確地描述。共性：共性：活動(dòng)記錄的釋放不需要遵循先進(jìn)后出的原則活動(dòng)記錄的釋放不需要遵循先進(jìn)后出的原則32Wensheng Li BUPT 2008q(1,9) 控制鏈控制鏈堆式存儲(chǔ)分配與棧式存儲(chǔ)分配的比較堆式存儲(chǔ)分配與棧式存儲(chǔ)分配的比較n相同點(diǎn)：相同點(diǎn)：動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配n不同點(diǎn)：不同點(diǎn)：組織形式：棧、堆組織形式：棧、堆釋放順序：釋放順序：棧：先進(jìn)后出棧：先進(jìn)后出堆：任意堆：任意Sr p(1,9) =4

38、q(1,9) q(1,3) s 控制鏈控制鏈r 控制鏈控制鏈p(1,9) 控制鏈控制鏈q(1,3) 控制鏈控制鏈33Wensheng Li BUPT 20087.3 7.3 訪問(wèn)非局部名字訪問(wèn)非局部名字一、程序塊一、程序塊二、非嵌套過(guò)程的靜態(tài)作用域二、非嵌套過(guò)程的靜態(tài)作用域三、嵌套過(guò)程的靜態(tài)作用域三、嵌套過(guò)程的靜態(tài)作用域四、動(dòng)態(tài)作用域四、動(dòng)態(tài)作用域n對(duì)非局部名字的引用取決于對(duì)非局部名字的引用取決于作用域規(guī)則作用域規(guī)則靜態(tài)作用域規(guī)則：詞法作用域規(guī)則、靜態(tài)作用域規(guī)則：詞法作用域規(guī)則、最近嵌套最近嵌套規(guī)則規(guī)則動(dòng)態(tài)作用域規(guī)則：由運(yùn)行時(shí)最近的活動(dòng)決定可應(yīng)用到一動(dòng)態(tài)作用域規(guī)則：由運(yùn)行時(shí)最近的活動(dòng)決定可應(yīng)用

39、到一個(gè)名字上的聲明個(gè)名字上的聲明n對(duì)非局部名字的訪問(wèn)通過(guò)對(duì)非局部名字的訪問(wèn)通過(guò)訪問(wèn)鏈訪問(wèn)鏈實(shí)現(xiàn)實(shí)現(xiàn)n關(guān)鍵：訪問(wèn)鏈如何創(chuàng)建、使用、維護(hù)關(guān)鍵：訪問(wèn)鏈如何創(chuàng)建、使用、維護(hù)34Wensheng Li BUPT 2008一、程序塊一、程序塊n程序塊的基本結(jié)構(gòu)程序塊的基本結(jié)構(gòu)begin 聲明語(yǔ)句聲明語(yǔ)句 語(yǔ)句序列語(yǔ)句序列endn塊可以嵌套塊可以嵌套n塊之間的關(guān)系塊之間的關(guān)系n最近嵌套規(guī)則最近嵌套規(guī)則B1B2B3B4var x, yvar x, avar yvar aref. a, x, y35Wensheng Li BUPT 2008靜態(tài)作用域舉例靜態(tài)作用域舉例main() int a=0; int b=

40、0; int b=1; int a=2; p r i n t f ( “ % d %dn”,a,b); int b=3; p r i n t f ( “ % d %dn”,a,b); printf(“%d %dn”,a,b); printf(“%d %dn”,a,b);B1B2B3B4a=2a=0b=0b=12 , 10 , 30 , 10 , 0b=336Wensheng Li BUPT 2008二、非嵌套過(guò)程的靜態(tài)作用域二、非嵌套過(guò)程的靜態(tài)作用域n過(guò)程定義不允許嵌套過(guò)程定義不允許嵌套獨(dú)立的獨(dú)立的順序的順序的n聲明語(yǔ)句的位置聲明語(yǔ)句的位置過(guò)程過(guò)程/ /函數(shù)內(nèi)部函數(shù)內(nèi)部所有過(guò)程之外所有過(guò)程之外

41、n在一個(gè)過(guò)程中引用的名字在一個(gè)過(guò)程中引用的名字局部的局部的全局的全局的int a11;readarray() a int partition(int y, int z) a quicksort(int m, int n) int i; i=partition(m,n); quicksort(m,i-1); quicksort(i+1,n); main () readarray; quicksort(0,10); 37Wensheng Li BUPT 2008變量的存儲(chǔ)分配變量的存儲(chǔ)分配n全局變量全局變量靜態(tài)地進(jìn)行分配靜態(tài)地進(jìn)行分配分配在靜態(tài)數(shù)據(jù)區(qū)中分配在靜態(tài)數(shù)據(jù)區(qū)中編譯時(shí)知道它們的位置，可編譯

42、時(shí)知道它們的位置，可以將全局變量對(duì)應(yīng)的存儲(chǔ)單以將全局變量對(duì)應(yīng)的存儲(chǔ)單元的地址編入目標(biāo)代碼中元的地址編入目標(biāo)代碼中n局部變量局部變量動(dòng)態(tài)地進(jìn)行分配動(dòng)態(tài)地進(jìn)行分配分配在活動(dòng)記錄中分配在活動(dòng)記錄中棧式存儲(chǔ)分配棧式存儲(chǔ)分配通過(guò)對(duì)棧指針的偏移訪問(wèn)當(dāng)通過(guò)對(duì)棧指針的偏移訪問(wèn)當(dāng)前活動(dòng)記錄中的局部名字前活動(dòng)記錄中的局部名字代碼區(qū)代碼區(qū)/ / 保存目標(biāo)代碼保存目標(biāo)代碼 靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū)控制?？刂茥６讯逊祷刂涤蚍祷刂涤騾?shù)域參數(shù)域控制鏈控制鏈訪問(wèn)鏈訪問(wèn)鏈機(jī)器狀態(tài)域機(jī)器狀態(tài)域局部數(shù)據(jù)域局部數(shù)據(jù)域臨時(shí)數(shù)據(jù)域臨時(shí)數(shù)據(jù)域top_sptop_ep38Wensheng Li BUPT 2008過(guò)程作為參數(shù)傳遞、作為結(jié)果返回

43、過(guò)程作為參數(shù)傳遞、作為結(jié)果返回n對(duì)非局部名字采用靜態(tài)存儲(chǔ)分配對(duì)非局部名字采用靜態(tài)存儲(chǔ)分配n前提（源語(yǔ)言）前提（源語(yǔ)言）靜態(tài)作用域規(guī)則靜態(tài)作用域規(guī)則過(guò)程定義不允許嵌套過(guò)程定義不允許嵌套n效果效果一個(gè)過(guò)程的非局部名，對(duì)其他過(guò)程也是非局部的一個(gè)過(guò)程的非局部名，對(duì)其他過(guò)程也是非局部的非局部名字的存儲(chǔ)空間由編譯程序靜態(tài)地進(jìn)行分配非局部名字的存儲(chǔ)空間由編譯程序靜態(tài)地進(jìn)行分配它的靜態(tài)地址在所有的過(guò)程中都可以引用它的靜態(tài)地址在所有的過(guò)程中都可以引用過(guò)程對(duì)非局部名字的引用與過(guò)程是如何激活的無(wú)關(guān)過(guò)程對(duì)非局部名字的引用與過(guò)程是如何激活的無(wú)關(guān)n結(jié)果結(jié)果無(wú)論過(guò)程作為參數(shù)傳遞、還是作為結(jié)果返回，其中對(duì)非無(wú)論過(guò)程作為參數(shù)傳

44、遞、還是作為結(jié)果返回，其中對(duì)非局部名字的引用，都是對(duì)靜態(tài)分配給它的存儲(chǔ)單元進(jìn)行局部名字的引用，都是對(duì)靜態(tài)分配給它的存儲(chǔ)單元進(jìn)行訪問(wèn)。訪問(wèn)。39Wensheng Li BUPT 2008示例示例 int m; int plusv( int n) return m+n; int mulv( int n) return m*n; void cproc( int pform( int n) ) cout pform(2) endl ; void main( ) m=0; cproc(plusv); cproc(mulv); pass訪問(wèn)鏈訪問(wèn)鏈mcproc訪問(wèn)鏈訪問(wèn)鏈02220cproc訪問(wèn)鏈訪問(wèn)鏈m

45、ulvn=2訪問(wèn)鏈訪問(wèn)鏈00plusvn=2訪問(wèn)鏈訪問(wèn)鏈40Wensheng Li BUPT 2008三、嵌套過(guò)程的靜態(tài)作用域三、嵌套過(guò)程的靜態(tài)作用域n過(guò)程定義允許嵌套過(guò)程定義允許嵌套n最近嵌套規(guī)則最近嵌套規(guī)則Program sort(input,output); var a: array0.10 of integer; x: integer; procedure readarray; var i: integer; begin a end; prcedure exchange(i,j:integer); begin x:=ai; ai:=aj; aj:=x end;procedure qui

46、cksort(m,n:integer); var k,v: integer; function partition(y,z:integer):integer; var i,j: integer; begin a ; v ; exchange(i,j); end; begin end quicksort;begin end sort.41Wensheng Li BUPT 2008過(guò)程及名字的嵌套關(guān)系過(guò)程及名字的嵌套關(guān)系PROC quicksortparam. m, nvar k, vFUN partitionparam. y, zvar. i, jref. a, vcall exchangePR

47、OC exchangeparam. i, jref. a, xPROC readarrayparam. i, jref. a, xvar a, x主程序主程序 sortn嵌套深度嵌套深度主程序：主程序：1 1每進(jìn)入一個(gè)過(guò)每進(jìn)入一個(gè)過(guò)程，深度加程，深度加1 112223n名字的嵌套深度名字的嵌套深度聲明時(shí)所在過(guò)聲明時(shí)所在過(guò)程的嵌套深度程的嵌套深度42Wensheng Li BUPT 2008訪問(wèn)鏈訪問(wèn)鏈被調(diào)用過(guò)程活動(dòng)記錄的訪被調(diào)用過(guò)程活動(dòng)記錄的訪問(wèn)鏈指向其直接外層過(guò)程問(wèn)鏈指向其直接外層過(guò)程的最新活動(dòng)的活動(dòng)記錄的最新活動(dòng)的活動(dòng)記錄實(shí)現(xiàn)嵌套過(guò)程的靜態(tài)作用域規(guī)則實(shí)現(xiàn)嵌套過(guò)程的靜態(tài)作用域規(guī)則通過(guò)訪問(wèn)鏈可

48、以實(shí)現(xiàn)對(duì)非局部名字的訪問(wèn)通過(guò)訪問(wèn)鏈可以實(shí)現(xiàn)對(duì)非局部名字的訪問(wèn)pqpaccessqaccesspqrpaccessraccessqaccessxqprxaccesspaccessraccessqaccess43Wensheng Li BUPT 2008訪問(wèn)鏈的使用訪問(wèn)鏈的使用n過(guò)程過(guò)程p引用非局部名字引用非局部名字a，嵌套深度分別為嵌套深度分別為np，na nanpn當(dāng)控制處于當(dāng)控制處于p中時(shí)，中時(shí)，p的活動(dòng)記錄在棧頂?shù)幕顒?dòng)記錄在棧頂n訪問(wèn)鏈的使用訪問(wèn)鏈的使用從棧頂活動(dòng)記錄出發(fā)，沿訪問(wèn)鏈前進(jìn)從棧頂活動(dòng)記錄出發(fā)，沿訪問(wèn)鏈前進(jìn) np-na 步步到達(dá)到達(dá)a的聲明所在過(guò)程的最新活動(dòng)記錄的聲明所在過(guò)程的最

49、新活動(dòng)記錄在該活動(dòng)記錄中，相對(duì)于訪問(wèn)鏈的某個(gè)固定偏移處即在該活動(dòng)記錄中，相對(duì)于訪問(wèn)鏈的某個(gè)固定偏移處即a的存儲(chǔ)位置的存儲(chǔ)位置該值在編譯時(shí)可以計(jì)算出來(lái)該值在編譯時(shí)可以計(jì)算出來(lái)該值在編譯時(shí)可以計(jì)算出來(lái)該值在編譯時(shí)可以計(jì)算出來(lái)n符號(hào)表符號(hào)表中，變量名字的目標(biāo)地址：中，變量名字的目標(biāo)地址： np中非局部名字中非局部名字a的地址：的地址： 44Wensheng Li BUPT 2008訪問(wèn)鏈的建立訪問(wèn)鏈的建立n在調(diào)用序列中由調(diào)用過(guò)程在調(diào)用序列中由調(diào)用過(guò)程p創(chuàng)建被調(diào)用過(guò)程創(chuàng)建被調(diào)用過(guò)程q的訪的訪問(wèn)鏈問(wèn)鏈n過(guò)程過(guò)程p和和q的嵌套深度分別為的嵌套深度分別為np和和nqnq的活動(dòng)記錄中訪問(wèn)鏈的建立依賴(lài)于的活動(dòng)記

50、錄中訪問(wèn)鏈的建立依賴(lài)于q與與p的關(guān)系的關(guān)系 q嵌套在嵌套在p中中 nqnp q不嵌套在不嵌套在p中中 nq=np nqnpn靜態(tài)文本中靜態(tài)文本中q與與p的關(guān)系：的關(guān)系：pqnq=np+1paccessqaccessnq活動(dòng)記錄中的訪問(wèn)鏈指向棧中剛好在其前面的活動(dòng)記錄中的訪問(wèn)鏈指向棧中剛好在其前面的p的活動(dòng)記錄的訪問(wèn)鏈的活動(dòng)記錄的訪問(wèn)鏈n調(diào)用序列中，調(diào)用序列中，p把把base-sp的值寫(xiě)入的值寫(xiě)入q的活動(dòng)記錄的活動(dòng)記錄的訪問(wèn)鏈的訪問(wèn)鏈46Wensheng Li BUPT 2008q不嵌套在不嵌套在p中中nq=npn靜態(tài)文本中靜態(tài)文本中q與與p的關(guān)系：的關(guān)系：xqpnq=npp和和q具有共同的直接

51、外層具有共同的直接外層xaccesspaccessqaccessnq活動(dòng)記錄中的訪問(wèn)鏈與活動(dòng)記錄中的訪問(wèn)鏈與p的活動(dòng)記錄的訪問(wèn)鏈指向的活動(dòng)記錄的訪問(wèn)鏈指向棧中剛好在棧中剛好在p前面的前面的x的活動(dòng)記錄訪問(wèn)鏈的活動(dòng)記錄訪問(wèn)鏈n調(diào)用序列中，調(diào)用序列中，p把自己的訪問(wèn)鏈的值把自己的訪問(wèn)鏈的值復(fù)制復(fù)制到到q的活動(dòng)的活動(dòng)記錄的訪問(wèn)鏈記錄的訪問(wèn)鏈47Wensheng Li BUPT 2008q不嵌套在不嵌套在p中中nqy? x : y ; nmax(5, 3+4)max(5, 3+4)：將將x x替換為替換為5 5，y y替換為替換為7 7，得到：，得到：57? 5:757? 5:7。n用相應(yīng)的實(shí)參的值替

52、代過(guò)程體中出現(xiàn)的所有形參。用相應(yīng)的實(shí)參的值替代過(guò)程體中出現(xiàn)的所有形參。n是是C+C+和和PascalPascal語(yǔ)言的內(nèi)置機(jī)制，本質(zhì)上，也是語(yǔ)言的內(nèi)置機(jī)制，本質(zhì)上，也是C C語(yǔ)言和語(yǔ)言和JavaJava語(yǔ)言參數(shù)傳遞的唯一機(jī)制。語(yǔ)言參數(shù)傳遞的唯一機(jī)制。n在這些語(yǔ)言中，參數(shù)被看作是過(guò)程的局部變量，初值由調(diào)用在這些語(yǔ)言中，參數(shù)被看作是過(guò)程的局部變量，初值由調(diào)用時(shí)的實(shí)參給出。時(shí)的實(shí)參給出。n在過(guò)程中，參數(shù)和局部變量一樣可以被賦值，但其結(jié)果不影在過(guò)程中，參數(shù)和局部變量一樣可以被賦值，但其結(jié)果不影響過(guò)程體之外的變量的值。響過(guò)程體之外的變量的值。 57Wensheng Li BUPT 2008傳值調(diào)用的實(shí)現(xiàn)

53、傳值調(diào)用的實(shí)現(xiàn)n調(diào)用過(guò)程對(duì)實(shí)參求值，調(diào)用過(guò)程對(duì)實(shí)參求值，并把實(shí)參的并把實(shí)參的右值右值寫(xiě)入被寫(xiě)入被調(diào)用過(guò)程活動(dòng)記錄的形調(diào)用過(guò)程活動(dòng)記錄的形參存儲(chǔ)單元中。參存儲(chǔ)單元中。n被調(diào)用過(guò)程在形參上的被調(diào)用過(guò)程在形參上的操作不影響調(diào)用過(guò)程活操作不影響調(diào)用過(guò)程活動(dòng)記錄中的值動(dòng)記錄中的值referenceab12swapxytemp121 2 1n執(zhí)行結(jié)果執(zhí)行結(jié)果 a=1b=258Wensheng Li BUPT 2008參數(shù)是指針類(lèi)型的情況參數(shù)是指針類(lèi)型的情況n傳值調(diào)用并不意味著參數(shù)的使用一定不會(huì)影響過(guò)程體外變量傳值調(diào)用并不意味著參數(shù)的使用一定不會(huì)影響過(guò)程體外變量的值。的值。n如果參數(shù)的類(lèi)型為指針或引用，參數(shù)

54、的值就是一個(gè)地址如果參數(shù)的類(lèi)型為指針或引用，參數(shù)的值就是一個(gè)地址通過(guò)它可以改變過(guò)程體外部的內(nèi)存值。如，有通過(guò)它可以改變過(guò)程體外部的內(nèi)存值。如，有C C語(yǔ)言函數(shù)語(yǔ)言函數(shù)void init_ptr(int* p) *p=3; 對(duì)參數(shù)對(duì)參數(shù)p p的直接賦值不會(huì)改變過(guò)程體外的實(shí)參的值。如：的直接賦值不會(huì)改變過(guò)程體外的實(shí)參的值。如：void init_ptr(int* p) p=(int*) malloc(sizeof(int); n在一些語(yǔ)言中，某些值是隱式指針或引用在一些語(yǔ)言中，某些值是隱式指針或引用如如C C語(yǔ)言中的數(shù)組是隱式指針（指向數(shù)組的第一個(gè)位置）語(yǔ)言中的數(shù)組是隱式指針（指向數(shù)組的第一個(gè)位置

55、）可以使用數(shù)組參數(shù)來(lái)改變存儲(chǔ)在數(shù)組中的值。如：可以使用數(shù)組參數(shù)來(lái)改變存儲(chǔ)在數(shù)組中的值。如：void init_array_0(int p) p0=0;59Wensheng Li BUPT 2008二、引用調(diào)用二、引用調(diào)用n原則上要求：實(shí)參必須是已經(jīng)分配了存儲(chǔ)空間的變量。原則上要求：實(shí)參必須是已經(jīng)分配了存儲(chǔ)空間的變量。n調(diào)用過(guò)程把一個(gè)指向?qū)崊⒋鎯?chǔ)單元的指針傳遞給被調(diào)用過(guò)程調(diào)用過(guò)程把一個(gè)指向?qū)崊⒋鎯?chǔ)單元的指針傳遞給被調(diào)用過(guò)程的相應(yīng)形參的相應(yīng)形參n在目標(biāo)代碼中，被調(diào)用過(guò)程通過(guò)傳遞給形參的指針間接地引在目標(biāo)代碼中，被調(diào)用過(guò)程通過(guò)傳遞給形參的指針間接地引用實(shí)參，因此，可以把形參看成是實(shí)參的別名，任何對(duì)形

56、參用實(shí)參，因此，可以把形參看成是實(shí)參的別名，任何對(duì)形參的引用就是對(duì)相應(yīng)實(shí)參的引用。的引用就是對(duì)相應(yīng)實(shí)參的引用。nFortranFortran語(yǔ)言中唯一的參數(shù)傳遞機(jī)制。語(yǔ)言中唯一的參數(shù)傳遞機(jī)制。n在在PascalPascal語(yǔ)言中，通過(guò)在形參前加關(guān)鍵字語(yǔ)言中，通過(guò)在形參前加關(guān)鍵字varvar來(lái)指定采用引用來(lái)指定采用引用調(diào)用機(jī)制。調(diào)用機(jī)制。procedure inc_1(var x: integer); begin x:=x+1 end;n在在C+C+中，通過(guò)在形參的類(lèi)型關(guān)鍵字后加符號(hào)中，通過(guò)在形參的類(lèi)型關(guān)鍵字后加符號(hào)&來(lái)指明采來(lái)指明采用引用調(diào)用機(jī)制，如：用引用調(diào)用機(jī)制，如：void in

57、c_1(int& x) x+ ; 60Wensheng Li BUPT 2008引用調(diào)用引用調(diào)用nC C語(yǔ)言可以通過(guò)傳遞引用或顯式指針來(lái)實(shí)現(xiàn)引用調(diào)用語(yǔ)言可以通過(guò)傳遞引用或顯式指針來(lái)實(shí)現(xiàn)引用調(diào)用的效果的效果nC C語(yǔ)言使用語(yǔ)言使用&指示變量的地址，使用操作指示變量的地址，使用操作* *撤撤銷(xiāo)引用指針。銷(xiāo)引用指針。n如：如：void inc_1(int* x) / C 模擬引用調(diào)用模擬引用調(diào)用 (*x)+; int a;inc_1(&a); 61Wensheng Li BUPT 2008引用調(diào)用的實(shí)現(xiàn)引用調(diào)用的實(shí)現(xiàn)n調(diào)用過(guò)程對(duì)實(shí)參求值，調(diào)用過(guò)程對(duì)實(shí)參求值，并把實(shí)參的并把實(shí)參

58、的左值左值寫(xiě)入被寫(xiě)入被調(diào)用過(guò)程活動(dòng)記錄的形調(diào)用過(guò)程活動(dòng)記錄的形參存儲(chǔ)單元中。參存儲(chǔ)單元中。n若實(shí)參是表達(dá)式，計(jì)算若實(shí)參是表達(dá)式，計(jì)算表達(dá)式的值，并把它存表達(dá)式的值，并把它存入臨時(shí)存儲(chǔ)單元，然后入臨時(shí)存儲(chǔ)單元，然后傳遞這個(gè)單元的地址。傳遞這個(gè)單元的地址。n被調(diào)用過(guò)程通過(guò)形參間被調(diào)用過(guò)程通過(guò)形參間接地引用實(shí)參接地引用實(shí)參n執(zhí)行結(jié)果執(zhí)行結(jié)果 a=2 b=1referenceab12swapxytemp1 2 162Wensheng Li BUPT 2008三、復(fù)制恢復(fù)三、復(fù)制恢復(fù)n傳值調(diào)用和引用調(diào)用的傳值調(diào)用和引用調(diào)用的一種混合形式一種混合形式n調(diào)用過(guò)程計(jì)算實(shí)參，實(shí)調(diào)用過(guò)程計(jì)算實(shí)參，實(shí)參的右值被傳遞到被調(diào)參的右值被傳遞到被調(diào)用過(guò)程中。要求在調(diào)用用過(guò)程中。要求在調(diào)用之前求出實(shí)參的左值。之前求出實(shí)參的左值。n從被調(diào)用過(guò)程返回時(shí)，從被調(diào)用過(guò)程返回時(shí)，把形參的現(xiàn)行右值復(fù)制把形參的現(xiàn)行右值復(fù)制到相應(yīng)實(shí)參的左值中。到相應(yīng)實(shí)參的左值中。只有具有左值的實(shí)參被只有具有左值的實(shí)參被復(fù)制下來(lái)復(fù)制下來(lái)referenceab12swapxytemp121 2 1 2 1n執(zhí)行結(jié)果執(zhí)行結(jié)果 a=2 b=163Wensheng