第9章運(yùn)行的存儲(chǔ)組織

1、第第9 9章章 運(yùn)行時(shí)的存儲(chǔ)組織運(yùn)行時(shí)的存儲(chǔ)組織school of computer science & technology harbin institute of technology重點(diǎn)：重點(diǎn)：符號(hào)表的內(nèi)容、組織，過程調(diào)用實(shí)現(xiàn)，符號(hào)表的內(nèi)容、組織，過程調(diào)用實(shí)現(xiàn)， 靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配的基本方法。靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配的基本方法。 難點(diǎn)：難點(diǎn)：參數(shù)傳遞，過程說明語句代碼結(jié)構(gòu)，參數(shù)傳遞，過程說明語句代碼結(jié)構(gòu)， 過程調(diào)用語句的代碼結(jié)構(gòu)，過程調(diào)用語句的代碼結(jié)構(gòu)， 過程調(diào)用語句的語法制導(dǎo)定義，過程調(diào)用語句的語法制導(dǎo)定義， 棧式存儲(chǔ)分配。棧式存儲(chǔ)分配。 2021-11-132第第9

2、章章 運(yùn)行時(shí)的存儲(chǔ)組織運(yùn)行時(shí)的存儲(chǔ)組織 9.1 與存儲(chǔ)組織有關(guān)的源語言概念與特征與存儲(chǔ)組織有關(guān)的源語言概念與特征9.2 存儲(chǔ)組織存儲(chǔ)組織9.3 靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配9.4 棧式存儲(chǔ)分配棧式存儲(chǔ)分配9.5 棧中非局部數(shù)據(jù)的訪問棧中非局部數(shù)據(jù)的訪問9.6 堆管理堆管理9.7 本章小結(jié)本章小結(jié)2021-11-1339.1 與存儲(chǔ)組織有關(guān)的源語言概念與特征與存儲(chǔ)組織有關(guān)的源語言概念與特征n編譯程序必須準(zhǔn)確地實(shí)現(xiàn)包含在源程序中的編譯程序必須準(zhǔn)確地實(shí)現(xiàn)包含在源程序中的各種抽象概念，如各種抽象概念，如名字名字、作用域作用域、數(shù)據(jù)類型數(shù)據(jù)類型、操作符操作符、過程過程、參數(shù)參數(shù)和和控制流結(jié)構(gòu)控制流結(jié)構(gòu)等，這

3、些等，這些概念反映了源語言所具有的一些特征，對(duì)它概念反映了源語言所具有的一些特征，對(duì)它們的支持往往會(huì)影響運(yùn)行時(shí)的存儲(chǔ)組織和分們的支持往往會(huì)影響運(yùn)行時(shí)的存儲(chǔ)組織和分配策略配策略 n給定一個(gè)源程序，編譯程序必須根據(jù)源語言給定一個(gè)源程序，編譯程序必須根據(jù)源語言的特征的特征(規(guī)定規(guī)定)為源程序中的許多問題做出決策，為源程序中的許多問題做出決策，包括何時(shí)、怎樣為名字分配內(nèi)存地址。包括何時(shí)、怎樣為名字分配內(nèi)存地址。n靜態(tài)策略靜態(tài)策略：在編譯時(shí)即可做出決定的策略：在編譯時(shí)即可做出決定的策略n動(dòng)態(tài)策略動(dòng)態(tài)策略：直到程序執(zhí)行時(shí)才能做出決定的策略：直到程序執(zhí)行時(shí)才能做出決定的策略2021-11-1349.1.1

4、名字及其綁定名字及其綁定 n“名字名字”、“變量變量”和和“標(biāo)識(shí)符標(biāo)識(shí)符” 的區(qū)別與聯(lián)的區(qū)別與聯(lián)系系n名字和變量分別表示編譯時(shí)的名字和運(yùn)行時(shí)該名名字和變量分別表示編譯時(shí)的名字和運(yùn)行時(shí)該名字所代表的內(nèi)存位置。字所代表的內(nèi)存位置。 n標(biāo)識(shí)符則是一個(gè)字符串，用于指示數(shù)據(jù)對(duì)象、過標(biāo)識(shí)符則是一個(gè)字符串，用于指示數(shù)據(jù)對(duì)象、過程、類或?qū)ο蟮娜肟?。程、類或?qū)ο蟮娜肟凇?n所有標(biāo)識(shí)符都是名字，但并不是所有的名字都是所有標(biāo)識(shí)符都是名字，但并不是所有的名字都是標(biāo)識(shí)符，名字還可以是表達(dá)式。例如，名字標(biāo)識(shí)符，名字還可以是表達(dá)式。例如，名字x.y可可能表示能表示x所代表結(jié)構(gòu)的域所代表結(jié)構(gòu)的域y。 n同一標(biāo)識(shí)符可以被聲明多

5、次，但每個(gè)聲明都引入同一標(biāo)識(shí)符可以被聲明多次，但每個(gè)聲明都引入一個(gè)新的變量。即使每個(gè)標(biāo)識(shí)符只被聲明一次，一個(gè)新的變量。即使每個(gè)標(biāo)識(shí)符只被聲明一次，局部于某個(gè)遞歸過程的標(biāo)識(shí)符在不同的運(yùn)行時(shí)刻局部于某個(gè)遞歸過程的標(biāo)識(shí)符在不同的運(yùn)行時(shí)刻也將指向不同的內(nèi)存位置。也將指向不同的內(nèi)存位置。 2021-11-135名字的綁名字的綁定定n從名字到值的兩步映射從名字到值的兩步映射n環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值n賦值改變狀態(tài)，但不改變環(huán)境。賦值改變狀態(tài)，但不改變環(huán)境。 n如果環(huán)境將名字如果環(huán)境將名字x映射到存儲(chǔ)單元映射到存儲(chǔ)單元s，我們就說，我們就說x被

6、被綁定綁定到到s名字名字內(nèi)存位置內(nèi)存位置(變量變量)狀態(tài)狀態(tài)值值環(huán)境環(huán)境2021-11-1369.1.2 聲明的作用域聲明的作用域nx的聲明的作用域是程序中的這樣一段區(qū)域，在該區(qū)的聲明的作用域是程序中的這樣一段區(qū)域，在該區(qū)域中，域中，x的引用均指向的引用均指向x的這一聲明。對(duì)于某種程序的這一聲明。對(duì)于某種程序設(shè)計(jì)語言，如果只通過考察其程序就可以確定某個(gè)設(shè)計(jì)語言，如果只通過考察其程序就可以確定某個(gè)聲明的作用域，則稱該語言使用聲明的作用域，則稱該語言使用靜態(tài)作用域靜態(tài)作用域；否則；否則稱該語言使用稱該語言使用動(dòng)態(tài)作用域動(dòng)態(tài)作用域。nc+、java和和c#等還提供了對(duì)等還提供了對(duì)作用域的顯式控制作用

7、域的顯式控制，其方法是使用其方法是使用public、private和和protected這樣的關(guān)這樣的關(guān)鍵字。鍵字。n聲明的作用域是通過符號(hào)表進(jìn)行管理的，詳見聲明的作用域是通過符號(hào)表進(jìn)行管理的，詳見8.4節(jié)節(jié)的討論。的討論。2021-11-1371. 靜態(tài)作用域靜態(tài)作用域n在具有程序塊結(jié)構(gòu)的語言中，變量聲明的靜在具有程序塊結(jié)構(gòu)的語言中，變量聲明的靜態(tài)作用域規(guī)則如下態(tài)作用域規(guī)則如下 ：n如果名字如果名字x的聲明的聲明d屬于程序塊屬于程序塊b，則，則d的作用域的作用域是是b的所有語句，只有滿足如下條件的程序塊的所有語句，只有滿足如下條件的程序塊b除外：除外：b嵌套在嵌套在b中中(可以是任意的嵌套深

8、度可以是任意的嵌套深度)，且且b中具有同一名字中具有同一名字x的一個(gè)新的聲明。的一個(gè)新的聲明。n令令b1, b2, , bk是包圍是包圍x的本次引用的所有程序塊，的本次引用的所有程序塊，bk-1是是bk的直接外層程序塊，的直接外層程序塊，bk-2是是bk-1的直接外層的直接外層程序塊，如此類推。找到使程序塊，如此類推。找到使x的某個(gè)聲明屬于的某個(gè)聲明屬于bi的的最大最大i，則，則x的本次引用指向的本次引用指向bi中的這個(gè)聲明。換中的這個(gè)聲明。換句話說，句話說，x的本次引用處在的本次引用處在bi中的這個(gè)聲明的作用中的這個(gè)聲明的作用域中。域中。 2021-11-1381. 靜態(tài)作用域靜態(tài)作用域表表

9、9.1 圖圖8.10所示程序中聲明的作用域所示程序中聲明的作用域2021-11-1392. 顯式訪問控制顯式訪問控制 n類和結(jié)構(gòu)為其成員引入了一種新的作用域類和結(jié)構(gòu)為其成員引入了一種新的作用域n如果如果p是某個(gè)帶有域是某個(gè)帶有域(成員成員)x的類的對(duì)象，則的類的對(duì)象，則p.x中中x的引用將指向該類定義中的域的引用將指向該類定義中的域x。與程序塊結(jié)構(gòu)類。與程序塊結(jié)構(gòu)類似的是，類似的是，類d中成員中成員x的聲明的作用域?qū)?huì)擴(kuò)展到的聲明的作用域?qū)?huì)擴(kuò)展到d的任何子類的任何子類d，除非，除非d中具有同一名字中具有同一名字x的一個(gè)局的一個(gè)局部聲明。部聲明。2021-11-13102. 顯式訪問控制顯式訪

10、問控制 n通過使用像通過使用像public、private和和protected這樣的關(guān)鍵這樣的關(guān)鍵字，字，c+或或java類的面向?qū)ο笳Z言提供了一種對(duì)超類的面向?qū)ο笳Z言提供了一種對(duì)超類中成員名字的顯式訪問控制。這些關(guān)鍵字通過限類中成員名字的顯式訪問控制。這些關(guān)鍵字通過限制訪問來支持封裝。因此，私有名的作用域只包含制訪問來支持封裝。因此，私有名的作用域只包含與該類及其友類相關(guān)聯(lián)的方法聲明和定義，保護(hù)名與該類及其友類相關(guān)聯(lián)的方法聲明和定義，保護(hù)名只對(duì)其子類是可訪問的，而公用名從類的外部也是只對(duì)其子類是可訪問的，而公用名從類的外部也是可以訪問的?？梢栽L問的。 2021-11-13113. 動(dòng)態(tài)作用

11、域動(dòng)態(tài)作用域 n動(dòng)態(tài)作用域規(guī)則相對(duì)于時(shí)間而靜態(tài)作用域規(guī)動(dòng)態(tài)作用域規(guī)則相對(duì)于時(shí)間而靜態(tài)作用域規(guī)則相對(duì)于空間則相對(duì)于空間n靜態(tài)作用域規(guī)則要求我們找出某個(gè)引用所指向的靜態(tài)作用域規(guī)則要求我們找出某個(gè)引用所指向的聲明，條件是該聲明處在包圍該引用的聲明，條件是該聲明處在包圍該引用的“空間上空間上最近的最近的”單元單元(程序塊程序塊)中。中。n動(dòng)態(tài)作用域也是要求我們找出某個(gè)引用所指向的動(dòng)態(tài)作用域也是要求我們找出某個(gè)引用所指向的聲明，但條件是該聲明處在包圍該引用的聲明，但條件是該聲明處在包圍該引用的“時(shí)間時(shí)間上最近的上最近的”單元單元(過程活動(dòng)過程活動(dòng))中。中。2021-11-13123. 動(dòng)態(tài)作用域動(dòng)態(tài)作用

12、域 n“動(dòng)態(tài)作用域動(dòng)態(tài)作用域”通常是指下面的策略通常是指下面的策略n名字名字x的引用指向帶有的引用指向帶有x聲明的最近被調(diào)用的過程聲明的最近被調(diào)用的過程中中x的這個(gè)聲明。的這個(gè)聲明。n例如，過程被當(dāng)做參數(shù)進(jìn)行傳遞時(shí)例如，過程被當(dāng)做參數(shù)進(jìn)行傳遞時(shí) 2021-11-13139.1.3 過程及其活動(dòng)過程及其活動(dòng) n將將“過程、函數(shù)和方法過程、函數(shù)和方法”統(tǒng)稱為統(tǒng)稱為“過程過程” n過程定義過程定義是一個(gè)聲明，它的最簡(jiǎn)單形式是把是一個(gè)聲明，它的最簡(jiǎn)單形式是把一個(gè)標(biāo)識(shí)符和一個(gè)語句聯(lián)系起來。該標(biāo)識(shí)符一個(gè)標(biāo)識(shí)符和一個(gè)語句聯(lián)系起來。該標(biāo)識(shí)符是是過程名過程名，而這個(gè)語句是，而這個(gè)語句是過程體過程體。 n當(dāng)過程名

13、出現(xiàn)在可執(zhí)行語句中時(shí)，稱相應(yīng)的當(dāng)過程名出現(xiàn)在可執(zhí)行語句中時(shí)，稱相應(yīng)的過程在該點(diǎn)被調(diào)用。過程在該點(diǎn)被調(diào)用。過程調(diào)用過程調(diào)用就是執(zhí)行被調(diào)就是執(zhí)行被調(diào)用過程的過程體。注意，過程調(diào)用也可以出用過程的過程體。注意，過程調(diào)用也可以出現(xiàn)在表達(dá)式中。現(xiàn)在表達(dá)式中。2021-11-13149.1.3 過程及其活動(dòng)過程及其活動(dòng) n出現(xiàn)在過程定義中的某些標(biāo)識(shí)符具有特殊的出現(xiàn)在過程定義中的某些標(biāo)識(shí)符具有特殊的意義，稱為該過程的形式參數(shù)，簡(jiǎn)稱為意義，稱為該過程的形式參數(shù)，簡(jiǎn)稱為形參形參。調(diào)用過程時(shí)，表達(dá)式作為實(shí)在參數(shù)調(diào)用過程時(shí)，表達(dá)式作為實(shí)在參數(shù)(或或?qū)崊?shí)參)傳傳遞給被調(diào)用的過程，以替換出現(xiàn)在過程體中遞給被調(diào)用的過程

14、，以替換出現(xiàn)在過程體中的對(duì)應(yīng)形式參數(shù)。的對(duì)應(yīng)形式參數(shù)。9.1.4節(jié)將討論實(shí)參和形參節(jié)將討論實(shí)參和形參的結(jié)合方法。的結(jié)合方法。n過程體的每次執(zhí)行叫做該過程的一個(gè)過程體的每次執(zhí)行叫做該過程的一個(gè)活動(dòng)活動(dòng)。過程過程p的一個(gè)活動(dòng)的生存期是從過程體執(zhí)行的的一個(gè)活動(dòng)的生存期是從過程體執(zhí)行的第一步到最后一步，包括執(zhí)行被第一步到最后一步，包括執(zhí)行被p調(diào)用的過程調(diào)用的過程的時(shí)間，以及再由這樣的過程調(diào)用其它過程的時(shí)間，以及再由這樣的過程調(diào)用其它過程所花的時(shí)間，等等。所花的時(shí)間，等等。 2021-11-13159.1.3 過程及其活動(dòng)過程及其活動(dòng) n如果如果a和和b是過程的活動(dòng)，那么它們的生存期是過程的活動(dòng)，那么它

15、們的生存期或者不交迭，或者嵌套。也就是說，如果在或者不交迭，或者嵌套。也就是說，如果在a結(jié)束之前結(jié)束之前b就開始了，那么就開始了，那么b必須在必須在a結(jié)束之前結(jié)束之前結(jié)束。結(jié)束。n如果同一個(gè)過程的一次新的活動(dòng)可以在前一如果同一個(gè)過程的一次新的活動(dòng)可以在前一次活動(dòng)結(jié)束前開始，則稱這樣的過程是次活動(dòng)結(jié)束前開始，則稱這樣的過程是遞歸遞歸的的。遞歸過程。遞歸過程p也可以間接地調(diào)用自己。也可以間接地調(diào)用自己。n如果某個(gè)過程是遞歸的，則在某一時(shí)刻可能如果某個(gè)過程是遞歸的，則在某一時(shí)刻可能有它的幾個(gè)活動(dòng)同時(shí)活躍，這時(shí)必須合理組有它的幾個(gè)活動(dòng)同時(shí)活躍，這時(shí)必須合理組織這些同時(shí)活躍著的活動(dòng)的內(nèi)存空間?？椷@些同時(shí)

16、活躍著的活動(dòng)的內(nèi)存空間。 2021-11-13169.1.4 參數(shù)傳遞方式參數(shù)傳遞方式 n當(dāng)一個(gè)過程調(diào)用另一個(gè)過程時(shí)，它們之間交當(dāng)一個(gè)過程調(diào)用另一個(gè)過程時(shí)，它們之間交換信息的方法通常是通過非局部名字和被調(diào)換信息的方法通常是通過非局部名字和被調(diào)用過程的參數(shù)來實(shí)現(xiàn)的。用過程的參數(shù)來實(shí)現(xiàn)的。 n傳值傳值n傳地址傳地址n傳值結(jié)果傳值結(jié)果n傳名傳名n其主要區(qū)別在于實(shí)參所代表的究竟是左值、其主要區(qū)別在于實(shí)參所代表的究竟是左值、右值還是實(shí)參的正文本身右值還是實(shí)參的正文本身 2021-11-13171. 傳值傳值n計(jì)算實(shí)參并將其右值傳遞給被調(diào)用過程計(jì)算實(shí)參并將其右值傳遞給被調(diào)用過程 n傳值方式可以如下實(shí)現(xiàn)：傳

17、值方式可以如下實(shí)現(xiàn)：n被調(diào)用過程為每個(gè)形參開辟一個(gè)稱為形式單元的被調(diào)用過程為每個(gè)形參開辟一個(gè)稱為形式單元的存儲(chǔ)單元，用于存放相應(yīng)實(shí)參的值。存儲(chǔ)單元，用于存放相應(yīng)實(shí)參的值。 n調(diào)用過程計(jì)算實(shí)參，并把右值放入相應(yīng)的形式單調(diào)用過程計(jì)算實(shí)參，并把右值放入相應(yīng)的形式單元中。元中。 調(diào)用者調(diào)用者被調(diào)用者被調(diào)用者直接使用直接使用a實(shí)際參數(shù)實(shí)際參數(shù)a形式參數(shù)形式參數(shù)xa的值的值單向傳值單向傳值2021-11-13182. 傳地址傳地址n調(diào)用過程將實(shí)參的地址傳遞給被調(diào)用過程調(diào)用過程將實(shí)參的地址傳遞給被調(diào)用過程 n傳地址方式可以如下實(shí)現(xiàn)：傳地址方式可以如下實(shí)現(xiàn)：n如果實(shí)參是一個(gè)具有左值的名字或表達(dá)式，則傳遞如果實(shí)

18、參是一個(gè)具有左值的名字或表達(dá)式，則傳遞該左值本身該左值本身 n如果實(shí)參是如果實(shí)參是a+b或或2這樣的沒有左值的表達(dá)式，則調(diào)這樣的沒有左值的表達(dá)式，則調(diào)用過程首先計(jì)算實(shí)參的值并將其存入一個(gè)新的存儲(chǔ)用過程首先計(jì)算實(shí)參的值并將其存入一個(gè)新的存儲(chǔ)單元，然后將這個(gè)新單元的地址傳遞給被調(diào)用過程單元，然后將這個(gè)新單元的地址傳遞給被調(diào)用過程 調(diào)用者調(diào)用者被調(diào)用者間址訪問被調(diào)用者間址訪問a實(shí)際參數(shù)實(shí)際參數(shù)a形式參數(shù)形式參數(shù)xa的地址的地址傳地址傳地址2021-11-13193. 傳值結(jié)果傳值結(jié)果n傳值結(jié)果就是將傳值和傳地址這兩種方式結(jié)合起來傳值結(jié)果就是將傳值和傳地址這兩種方式結(jié)合起來n傳值結(jié)果方式可以如下實(shí)現(xiàn)：

19、傳值結(jié)果方式可以如下實(shí)現(xiàn)：n實(shí)參的右值和左值同時(shí)傳給被調(diào)用過程。實(shí)參的右值和左值同時(shí)傳給被調(diào)用過程。n在被調(diào)用過程中，像傳值方式那樣使用實(shí)參的右值。在被調(diào)用過程中，像傳值方式那樣使用實(shí)參的右值。n當(dāng)控制返回調(diào)用過程時(shí)，根據(jù)傳遞來的實(shí)參的左值，當(dāng)控制返回調(diào)用過程時(shí)，根據(jù)傳遞來的實(shí)參的左值，將形參當(dāng)前的值復(fù)制到實(shí)參存儲(chǔ)單元。將形參當(dāng)前的值復(fù)制到實(shí)參存儲(chǔ)單元。 調(diào)用者調(diào)用者被調(diào)用者被調(diào)用者a實(shí)際參數(shù)實(shí)際參數(shù)a形式參數(shù)形式參數(shù)xa的值的值傳值傳值/傳地址傳地址a的地址的地址2021-11-13204. 傳名傳名n用實(shí)參表達(dá)式對(duì)形參進(jìn)行文字替換。用實(shí)參表達(dá)式對(duì)形參進(jìn)行文字替換。n傳名方式可以如下實(shí)現(xiàn)：傳

20、名方式可以如下實(shí)現(xiàn)：n在調(diào)用過程中設(shè)置計(jì)算實(shí)參左值或右值的形實(shí)轉(zhuǎn)在調(diào)用過程中設(shè)置計(jì)算實(shí)參左值或右值的形實(shí)轉(zhuǎn)換子程序。換子程序。n被調(diào)用過程為每個(gè)形參開辟一個(gè)存儲(chǔ)單元，用于被調(diào)用過程為每個(gè)形參開辟一個(gè)存儲(chǔ)單元，用于存放該實(shí)參的形實(shí)轉(zhuǎn)換子程序的入口地址。被調(diào)存放該實(shí)參的形實(shí)轉(zhuǎn)換子程序的入口地址。被調(diào)過程執(zhí)行時(shí)，每當(dāng)要向形參賦值或取該形參的值過程執(zhí)行時(shí)，每當(dāng)要向形參賦值或取該形參的值時(shí)，就調(diào)用相應(yīng)于該形參的形實(shí)轉(zhuǎn)換子程序，以時(shí)，就調(diào)用相應(yīng)于該形參的形實(shí)轉(zhuǎn)換子程序，以獲得相應(yīng)的實(shí)參地址或值。注意，形實(shí)轉(zhuǎn)換子程獲得相應(yīng)的實(shí)參地址或值。注意，形實(shí)轉(zhuǎn)換子程序的運(yùn)行環(huán)境是調(diào)用程序。形實(shí)轉(zhuǎn)換子程序又稱序的運(yùn)行環(huán)

21、境是調(diào)用程序。形實(shí)轉(zhuǎn)換子程序又稱為換名子程序?yàn)閾Q名子程序thunk。2021-11-1321例例procedure swap(var x, y: integer);var temp: integer; begin 調(diào)用調(diào)用swap(i, ai) temp := x;temp := i; x := y; i := ai; y := tempai := temp end2021-11-1322子程序子程序p(x,y,z);y:=y+1; z:=z+x傳值：傳值：2傳地址：傳地址：x=t=5,y=z=a=2a:=a+1=2+1a:=a+t=3+58傳值結(jié)果：傳值結(jié)果：x=t=5,y=z=a=2y:=

22、y+1=3z:=z+x=5+2=7y a=3z a=77傳名傳名a:=a+1=3a:=a+a+b=3+3+39主程序主程序a:=2; b:=3;p(a+b, a, a);print a臨時(shí)單元臨時(shí)單元: t:a+b=52021-11-1323編譯程序組織存儲(chǔ)空間時(shí)必須考慮的問編譯程序組織存儲(chǔ)空間時(shí)必須考慮的問題題n過程能否遞歸？過程能否遞歸？n當(dāng)控制從過程的活動(dòng)返回時(shí)，局部變量的值是否要當(dāng)控制從過程的活動(dòng)返回時(shí)，局部變量的值是否要保留？保留？n過程能否訪問非局部變量？過程能否訪問非局部變量？n過程調(diào)用的參數(shù)傳遞方式？過程調(diào)用的參數(shù)傳遞方式？n過程能否作為參數(shù)被傳遞？過程能否作為參數(shù)被傳遞？n過

23、程能否作為結(jié)果值傳遞？過程能否作為結(jié)果值傳遞？n存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配？存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配？n存儲(chǔ)塊是否必須顯式地釋放？存儲(chǔ)塊是否必須顯式地釋放？2021-11-13249.2 存儲(chǔ)組織存儲(chǔ)組織n9.2.1 運(yùn)行時(shí)內(nèi)存的劃分運(yùn)行時(shí)內(nèi)存的劃分n9.2.2 活動(dòng)記錄活動(dòng)記錄n9.2.3 局部數(shù)據(jù)的組織局部數(shù)據(jù)的組織n9.2.4 全局存儲(chǔ)分配策略全局存儲(chǔ)分配策略2021-11-13259.2.1 運(yùn)行時(shí)內(nèi)存的劃分運(yùn)行時(shí)內(nèi)存的劃分目標(biāo)代碼目標(biāo)代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)棧棧堆堆空閑空閑 空間空間2021-11-1326n過程的每個(gè)活動(dòng)所需要的信息用一塊連續(xù)的存儲(chǔ)過程的每個(gè)活動(dòng)所需要的信

24、息用一塊連續(xù)的存儲(chǔ)區(qū)來管理，這塊存儲(chǔ)區(qū)叫做區(qū)來管理，這塊存儲(chǔ)區(qū)叫做活動(dòng)記錄活動(dòng)記錄 n假定語言的特點(diǎn)為假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許過程允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，過程定義允許含有可變數(shù)組，過程定義允許/不允許嵌套。不允許嵌套。n采用棧式存儲(chǔ)分配機(jī)制采用棧式存儲(chǔ)分配機(jī)制n活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動(dòng)記錄壓入棧頂。活動(dòng)記錄一般含有連相應(yīng)的活動(dòng)記錄壓入棧頂?；顒?dòng)記錄一般含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。向量和臨時(shí)工作單元等。9.2.2

25、 活動(dòng)記錄活動(dòng)記錄2021-11-1327對(duì)任何局部變量對(duì)任何局部變量x的引的引用可表示為變址訪問用可表示為變址訪問: dxspdx:變量變量x相對(duì)于活動(dòng)記相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯錄起點(diǎn)的地址，在編譯時(shí)可確定。時(shí)可確定。參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元臨時(shí)變量臨時(shí)變量數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量簡(jiǎn)單變量簡(jiǎn)單變量sp 012舊舊sptop 每個(gè)過程的活動(dòng)記錄內(nèi)容每個(gè)過程的活動(dòng)記錄內(nèi)容 非嵌套語言非嵌套語言(如如c)2021-11-1328l 連接數(shù)據(jù)連接數(shù)據(jù)l 返回地址返回地址l 動(dòng)態(tài)鏈：指向調(diào)用該動(dòng)態(tài)鏈：指向調(diào)用該過程前的最新活動(dòng)記過程前的最新活動(dòng)記錄地址的指針。錄地址的指

26、針。l 靜態(tài)鏈：指向靜態(tài)直接靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的外層最新活動(dòng)記錄地址的指針，用來訪問非局部數(shù)指針，用來訪問非局部數(shù)據(jù)。據(jù)。靜態(tài)鏈靜態(tài)鏈動(dòng)態(tài)鏈動(dòng)態(tài)鏈形式單元形式單元臨時(shí)變量臨時(shí)變量數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量局部變量局部變量sp012返回地址返回地址top 每個(gè)過程的活動(dòng)記錄內(nèi)容每個(gè)過程的活動(dòng)記錄內(nèi)容 嵌套語言嵌套語言(如如pascal)2021-11-1329l形式單元：存放相形式單元：存放相應(yīng)的實(shí)在參數(shù)的地應(yīng)的實(shí)在參數(shù)的地址或值。址或值。l局部數(shù)據(jù)區(qū)：局部局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、變量、內(nèi)情向量、臨時(shí)工作單元臨時(shí)工作單元(如存如存放對(duì)表達(dá)式求值的放對(duì)表達(dá)式求值的結(jié)果結(jié)

27、果)。靜態(tài)鏈靜態(tài)鏈動(dòng)態(tài)鏈動(dòng)態(tài)鏈形式單元形式單元臨時(shí)變量臨時(shí)變量數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量局部變量局部變量sp 012返回地址返回地址top 每個(gè)過程的活動(dòng)記錄內(nèi)容每個(gè)過程的活動(dòng)記錄內(nèi)容2021-11-13309.2.3 局部數(shù)據(jù)的組織局部數(shù)據(jù)的組織n字節(jié)是可編址內(nèi)存的最小單位。字節(jié)是可編址內(nèi)存的最小單位。n變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。n一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間?，F(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。 n局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的

28、地址來表局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示。示。n數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有對(duì)齊的問題。數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有對(duì)齊的問題。n整數(shù)必須放在內(nèi)存中特定的位置，如被整數(shù)必須放在內(nèi)存中特定的位置，如被2、4、8整除整除的地址的地址2021-11-13319.2.3 局部數(shù)據(jù)的組織局部數(shù)據(jù)的組織在在sparc/solaris工作站上下面兩個(gè)結(jié)構(gòu)的工作站上下面兩個(gè)結(jié)構(gòu)的size分別是分別是24和和16，為什么不一樣？，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;char c2; long i;d

29、ouble f; double f;a; b;2021-11-13329.2.3 局部數(shù)據(jù)的組織局部數(shù)據(jù)的組織在在sparc/solaris工作站上下面兩個(gè)結(jié)構(gòu)的工作站上下面兩個(gè)結(jié)構(gòu)的size分別是分別是24和和16，為什么不一樣？，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c1; 0long i;4 char c2; 1char c2;8 long i; 4double f; 16 double f;8a; b;2021-11-13339.2.3 局部數(shù)據(jù)的組織局部數(shù)據(jù)的組織在在x86/linux機(jī)器的結(jié)果和機(jī)器的結(jié)果和s

30、parc/solaris工作工作站不一樣，是站不一樣，是20和和16。typedef struct _atypedef struct _bchar c1;0 char c1; 0long i;4 char c2; 1char c2;8 long i; 4double f; 12 double f;8a; b;2021-11-1334n靜態(tài)存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配策略(fortran) 如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定靜態(tài)分配方法：在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定出在運(yùn)行時(shí)刻的存儲(chǔ)空間中的位置。出在運(yùn)行時(shí)刻

31、的存儲(chǔ)空間中的位置。n動(dòng)態(tài)存儲(chǔ)分配策略動(dòng)態(tài)存儲(chǔ)分配策略(pascal) 如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，則必須采用動(dòng)態(tài)分配方法。允許遞歸過程及動(dòng)態(tài)則必須采用動(dòng)態(tài)分配方法。允許遞歸過程及動(dòng)態(tài)申請(qǐng)、釋放內(nèi)存。申請(qǐng)、釋放內(nèi)存。n棧式動(dòng)態(tài)存儲(chǔ)分配棧式動(dòng)態(tài)存儲(chǔ)分配n堆式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配9.2.4 全局存儲(chǔ)分配策略全局存儲(chǔ)分配策略 2021-11-13359.3 靜態(tài)存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配策略n如果在編譯時(shí)就能確定一個(gè)程序在運(yùn)行時(shí)所需如果在編譯時(shí)就能確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能安排好要的存儲(chǔ)空間的大小，則在編譯

32、時(shí)就能安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的地址，存儲(chǔ)空間的這種分配方法稱個(gè)數(shù)據(jù)項(xiàng)的地址，存儲(chǔ)空間的這種分配方法稱為靜態(tài)存儲(chǔ)分配。必須滿足如下條件：為靜態(tài)存儲(chǔ)分配。必須滿足如下條件：n數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置在編譯時(shí)必須數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置在編譯時(shí)必須是已知的；是已知的；n不允許過程的遞歸調(diào)用，因?yàn)橐粋€(gè)過程的所有活動(dòng)不允許過程的遞歸調(diào)用，因?yàn)橐粋€(gè)過程的所有活動(dòng)都是用同樣的局部名字綁定的；都是用同樣的局部名字綁定的；n數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立，因?yàn)闆]有運(yùn)行時(shí)的存儲(chǔ)分?jǐn)?shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立，因?yàn)闆]有運(yùn)行時(shí)的存儲(chǔ)分配機(jī)制。配機(jī)制

33、。2021-11-1336某分段式程序運(yùn)行時(shí)的內(nèi)存劃分某分段式程序運(yùn)行時(shí)的內(nèi)存劃分2021-11-1337n每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號(hào)及在該中，對(duì)每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號(hào)及在該區(qū)中的相對(duì)位置。區(qū)中的相對(duì)位置。n考慮子程序段：考慮子程序段：subroutine swap(a,b)t=aa=bb=treturnend寄存器保護(hù)區(qū)寄存器保護(hù)區(qū)返回地址返回地址atb01a2021-11-1338靜態(tài)存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配策略n順序分配算法（基于調(diào)用圖）順序分配算法（基于調(diào)用圖）n按照程序段出現(xiàn)的先后順

34、序逐段分配按照程序段出現(xiàn)的先后順序逐段分配1/222/153/184/176/105/23程序段程序段 區(qū)域區(qū)域1 0212 22363 37544 55715 72946 95104共需要共需要105個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元程序段號(hào)程序段號(hào)/所需數(shù)據(jù)空間所需數(shù)據(jù)空間能用更少的空間么？能用更少的空間么？2021-11-1339分層分配算法分層分配算法n允許程序段之間的覆蓋（覆蓋可能性分析）允許程序段之間的覆蓋（覆蓋可能性分析）程序段程序段 區(qū)域區(qū)域6095022 4016323402173114162共需要共需要63個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元1/222/153/184/176/105/23思考：如何設(shè)計(jì)

35、分配算法？思考：如何設(shè)計(jì)分配算法？2021-11-13409.4 棧式存儲(chǔ)分配策略棧式存儲(chǔ)分配策略n如果過程允許遞歸如果過程允許遞歸n某一時(shí)刻過程某一時(shí)刻過程a可能已被自己調(diào)用了若干次，但只可能已被自己調(diào)用了若干次，但只有最近一次處于執(zhí)行狀態(tài)。其余各次等待返回被中有最近一次處于執(zhí)行狀態(tài)。其余各次等待返回被中斷的那次調(diào)用斷的那次調(diào)用n必須保存每次調(diào)用相應(yīng)的數(shù)據(jù)區(qū)內(nèi)容（活動(dòng)記錄）必須保存每次調(diào)用相應(yīng)的數(shù)據(jù)區(qū)內(nèi)容（活動(dòng)記錄）n引入一個(gè)運(yùn)行棧引入一個(gè)運(yùn)行棧n讓過程的每次執(zhí)行和過程的活動(dòng)記錄相對(duì)應(yīng)。讓過程的每次執(zhí)行和過程的活動(dòng)記錄相對(duì)應(yīng)。n每調(diào)用一次過程，就把該過程的活動(dòng)記錄壓入棧中，每調(diào)用一次過程，就

36、把該過程的活動(dòng)記錄壓入棧中，返回時(shí)彈出。返回時(shí)彈出。n假設(shè)寄存器假設(shè)寄存器top標(biāo)記棧頂，局部名字標(biāo)記棧頂，局部名字x的相對(duì)地址為的相對(duì)地址為dx，則，則x的地址為的地址為top+dx 或或 dxtop2021-11-13419.4.1 調(diào)用序列和返回序列調(diào)用序列和返回序列 n過程調(diào)用和過程返回都需要執(zhí)行一些代碼來過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等n過程調(diào)用和返回是通過在目標(biāo)代碼中生成調(diào)過程調(diào)用和返回是通過在目標(biāo)代碼中生成調(diào)用序列和返回序列來實(shí)現(xiàn)的用序列和返回序列來實(shí)現(xiàn)的 n調(diào)用序列負(fù)責(zé)分配活動(dòng)記錄，并將相關(guān)信息填入調(diào)

37、用序列負(fù)責(zé)分配活動(dòng)記錄，并將相關(guān)信息填入活動(dòng)記錄中活動(dòng)記錄中 n返回序列負(fù)責(zé)恢復(fù)機(jī)器狀態(tài)，使調(diào)用過程能夠繼返回序列負(fù)責(zé)恢復(fù)機(jī)器狀態(tài)，使調(diào)用過程能夠繼續(xù)執(zhí)行續(xù)執(zhí)行 n調(diào)用序列和返回序列常常都分成兩部分，分調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中處于調(diào)用過程和被調(diào)用過程中2021-11-13429.4.1 調(diào)用序列和返回序列調(diào)用序列和返回序列n即使是同一種語言，過程調(diào)用序列、返回序列和活即使是同一種語言，過程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異n設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則：設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則：

38、n以活動(dòng)記錄中間的某個(gè)位置作為基地址；以活動(dòng)記錄中間的某個(gè)位置作為基地址；n長(zhǎng)度能較早確定的域放在活動(dòng)記錄的中間；長(zhǎng)度能較早確定的域放在活動(dòng)記錄的中間；n一般把臨時(shí)數(shù)據(jù)域放在局部數(shù)據(jù)域的后面，以便其一般把臨時(shí)數(shù)據(jù)域放在局部數(shù)據(jù)域的后面，以便其長(zhǎng)度的改變不會(huì)影響數(shù)據(jù)對(duì)象相對(duì)于中間那些域的長(zhǎng)度的改變不會(huì)影響數(shù)據(jù)對(duì)象相對(duì)于中間那些域的位置；位置；n用同樣的代碼來執(zhí)行各個(gè)活動(dòng)的狀態(tài)保存和恢復(fù)；用同樣的代碼來執(zhí)行各個(gè)活動(dòng)的狀態(tài)保存和恢復(fù)；n把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動(dòng)把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動(dòng)記錄的地方。記錄的地方。2021-11-13439.4.1 調(diào)用序列和返回序列

39、調(diào)用序列和返回序列調(diào)用者和被調(diào)用者之間的任務(wù)劃分調(diào)用者和被調(diào)用者之間的任務(wù)劃分2021-11-13449.4.1 調(diào)用序列和返回序列調(diào)用序列和返回序列一種可能的調(diào)用序列：一種可能的調(diào)用序列：n調(diào)用者計(jì)算實(shí)參調(diào)用者計(jì)算實(shí)參n調(diào)用者把返回地址和調(diào)用者把返回地址和sp的舊值存入被調(diào)用者的舊值存入被調(diào)用者的活動(dòng)記錄中，然后將的活動(dòng)記錄中，然后將sp移過調(diào)用者的局部移過調(diào)用者的局部數(shù)據(jù)域和臨時(shí)變量域，以及被調(diào)用者的參數(shù)數(shù)據(jù)域和臨時(shí)變量域，以及被調(diào)用者的參數(shù)域和狀態(tài)域域和狀態(tài)域n被調(diào)用者保存寄存器值和其它機(jī)器狀態(tài)信息被調(diào)用者保存寄存器值和其它機(jī)器狀態(tài)信息n被調(diào)用者初始化其局部數(shù)據(jù)，并開始執(zhí)行。被調(diào)用者初始

40、化其局部數(shù)據(jù)，并開始執(zhí)行。2021-11-13459.4.1 調(diào)用序列和返回序列調(diào)用序列和返回序列一種可能的返回序列：一種可能的返回序列： n被調(diào)用者將返回值放入臨近調(diào)用者的活動(dòng)被調(diào)用者將返回值放入臨近調(diào)用者的活動(dòng)記錄的地方。記錄的地方。n利用狀態(tài)域中的信息，被調(diào)用者恢復(fù)利用狀態(tài)域中的信息，被調(diào)用者恢復(fù)sp和和其它寄存器，并且按調(diào)用者代碼中的返回其它寄存器，并且按調(diào)用者代碼中的返回地址返回。地址返回。n盡管盡管sp的值減小了，調(diào)用者仍然可以將返的值減小了，調(diào)用者仍然可以將返回值復(fù)制到自己的活動(dòng)記錄中，并用它來回值復(fù)制到自己的活動(dòng)記錄中，并用它來計(jì)算一個(gè)表達(dá)式。計(jì)算一個(gè)表達(dá)式。2021-11-1

41、3469.4.1 調(diào)用序列和返回序列調(diào)用序列和返回序列過程的參數(shù)個(gè)數(shù)可變的情況過程的參數(shù)個(gè)數(shù)可變的情況n函數(shù)返回值改成用寄存器傳遞函數(shù)返回值改成用寄存器傳遞n編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼n被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置n被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等第三個(gè)參數(shù)等等n如如c語言的語言的printf2021-11-1347n過程調(diào)用的三地址碼過程調(diào)用的三地址碼:param x1param x2 param xncall p，n9.4.2 c語言的過程調(diào)用

42、和返回語言的過程調(diào)用和返回 2021-11-13481) 每個(gè)每個(gè)param xi(i=1,2,n)可直接翻譯成如下指令可直接翻譯成如下指令:(i+3)top:= xi (傳值傳值)(i+3)top:=addr(xi) (傳地址傳地址)2) call p，n 被翻譯成如下指令被翻譯成如下指令:1top:=sp (保護(hù)現(xiàn)行保護(hù)現(xiàn)行sp)3top:=n (傳遞參數(shù)個(gè)數(shù)傳遞參數(shù)個(gè)數(shù))jsr p (轉(zhuǎn)子指令轉(zhuǎn)子指令)參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址內(nèi)情向量?jī)?nèi)情向量局部變量局部變量老老sp臨時(shí)單元臨時(shí)單元對(duì)于對(duì)于par和和call產(chǎn)生的目標(biāo)代碼產(chǎn)生的目標(biāo)代碼top sp 調(diào)用過程的活動(dòng)記錄調(diào)用過程的活動(dòng)

43、記錄老老sp參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)形式單元形式單元形式單元形式單元2021-11-13493) 進(jìn)入過程進(jìn)入過程p后，首先應(yīng)執(zhí)行下述指令后，首先應(yīng)執(zhí)行下述指令:sp:=top+1 (定義新的定義新的sp)1sp:=返回地址返回地址 (保護(hù)返回地址保護(hù)返回地址)top:=top+l (新新top) l：過程：過程p的活動(dòng)記錄所需單元數(shù)，的活動(dòng)記錄所需單元數(shù)， 在編譯時(shí)可確定。在編譯時(shí)可確定。 參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量老老sp臨時(shí)單元臨時(shí)單元top 調(diào)用過程的活動(dòng)記錄調(diào)用過程的活動(dòng)記錄返回地址返回地址topsp2021-11-13504) 過程返回

44、時(shí)，應(yīng)執(zhí)行下列指令過程返回時(shí)，應(yīng)執(zhí)行下列指令:top:=sp-1 (恢復(fù)調(diào)用前恢復(fù)調(diào)用前top)sp:=0sp (恢復(fù)調(diào)用前恢復(fù)調(diào)用前sp)x:=2top (把返回地址取到把返回地址取到x中中)uj 0x (按按x返回返回) uj為無條件轉(zhuǎn)移指令，為無條件轉(zhuǎn)移指令， 即按即按x中的返回地址實(shí)行變址轉(zhuǎn)移中的返回地址實(shí)行變址轉(zhuǎn)移參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量老老sp臨時(shí)單元臨時(shí)單元調(diào)用過程的活動(dòng)記錄調(diào)用過程的活動(dòng)記錄topspsptop2021-11-13519.4.3 棧中的可變長(zhǎng)數(shù)據(jù)棧中的可變長(zhǎng)數(shù)據(jù)活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況活動(dòng)記錄的

45、長(zhǎng)度在編譯時(shí)不能確定的情況n局部數(shù)組的大小要等到過程激活時(shí)才能確定局部數(shù)組的大小要等到過程激活時(shí)才能確定n在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元針的單元n運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間間2021-11-13529.4.3 棧中的可變長(zhǎng)數(shù)據(jù)棧中的可變長(zhǎng)數(shù)據(jù)圖圖9.13 訪問動(dòng)態(tài)分配的數(shù)組訪問動(dòng)態(tài)分配的數(shù)組2021-11-1353棧式存儲(chǔ)分配策略的局限棧式存儲(chǔ)分配策略的局限棧式分配策略在下列情況下行不通：棧式分配策略在下列情況下行不通：n過程活動(dòng)停止后，局部名字的值還必須維持過程活動(dòng)停止后，局部名字的值還

46、必須維持n被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期更被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期更長(zhǎng)，此時(shí)活動(dòng)樹不能正確描繪程序的控制流長(zhǎng)，此時(shí)活動(dòng)樹不能正確描繪程序的控制流n不遵守棧式規(guī)則的有不遵守棧式規(guī)則的有pascal語言和語言和c語言的動(dòng)語言的動(dòng)態(tài)變量態(tài)變量njava禁止程序員自己釋放空間禁止程序員自己釋放空間 2021-11-13549.5 棧中非局部數(shù)據(jù)的訪問棧中非局部數(shù)據(jù)的訪問本節(jié)內(nèi)容本節(jié)內(nèi)容n無嵌套過程的靜態(tài)作用域的實(shí)現(xiàn)（無嵌套過程的靜態(tài)作用域的實(shí)現(xiàn)（c語言）語言）n包含嵌套過程的靜態(tài)作用域的實(shí)現(xiàn)（包含嵌套過程的靜態(tài)作用域的實(shí)現(xiàn)（pascal語言）語言）n動(dòng)態(tài)作用域的實(shí)現(xiàn)（動(dòng)態(tài)作用域的實(shí)現(xiàn)

47、（lisp語言）語言）2021-11-13559.5.1 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域n假定假定:允許過程遞歸調(diào)用、允許過程含有可變數(shù)允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如組，但過程定義不允許嵌套，如c語言語言。n過程體中的非局部引用可以直接使用靜態(tài)確定過程體中的非局部引用可以直接使用靜態(tài)確定的地址的地址n局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過sp指指針來訪問針來訪問n無須深入棧中取數(shù)據(jù)，無須訪問鏈無須深入棧中取數(shù)據(jù)，無須訪問鏈n過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回返回c

48、語言的函數(shù)聲明不能嵌套，函數(shù)不論在什語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況么情況下激活，要訪問的數(shù)據(jù)分成兩種情況:n非靜態(tài)局部變量（包括形式參數(shù)），它們分非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中n外部變量（包括定義在其它源文件中的外部外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)態(tài)數(shù)據(jù)區(qū) 9.5.1 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域2021-11-13562021-11-1357 全局?jǐn)?shù)據(jù)說明全局?jǐn)?shù)據(jù)說明mai

49、n( ) main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void r( ) r中的數(shù)據(jù)說明中的數(shù)據(jù)說明void q( ) q中的數(shù)據(jù)說明中的數(shù)據(jù)說明n主程序主程序過程過程q 過程過程rq的活動(dòng)記錄的活動(dòng)記錄主程序活動(dòng)記錄主程序活動(dòng)記錄topr的活動(dòng)記錄的活動(dòng)記錄sp參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量老老sp臨時(shí)單元臨時(shí)單元全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)區(qū)2021-11-13589.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域假定語言不僅允許過程的遞歸調(diào)用假定語言不僅允許過程的遞歸調(diào)用(和可變數(shù)和可變數(shù)組組)，而且允許過程定義的嵌套，如，而且允許過程定義的嵌套，如p

50、ascal，pl語言。語言。sortreadarrayexchangequicksortpartition2021-11-1359n(1) program sort(input, output);n(2) var a :array0.10 of integer;n(3) x :integer;n(4) procedure readarray;n(5) var i :integer;n(6) begin a end readarray;n(7) procedure exchange(i,j:integer);n(8) begin n(9) x:= ai; ai:=aj; aj:= x;n(10)

51、 end exchange ;program sort procedure readarray procedure exchange procedure quicksort function partition 2021-11-1360n(11) procedure quicksort(m,n:integer);n(12) var k,v:integer;n(13) function partition(y,z:integer): integer;n(14) var i,j:integer;n(15) begin an(16) vn(17) exchange(i,j);n(18) end pa

52、rtition;n(19) begin end quicksort;n(20) begin end gram sort procedure readarray procedure exchange procedure quicksort function partition 2021-11-13619.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域引入概念：引入概念：過程嵌套深度過程嵌套深度sort1readarray2exchange2quicksort2partition3n變量的嵌套深度變量的嵌套深度：它的聲明所在過程的嵌套：它的聲明所在過程的嵌套深度作為該名字的嵌

53、套深度深度作為該名字的嵌套深度2021-11-13629.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域1. 訪問鏈訪問鏈 2021-11-13639.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度為，它引用嵌套深度為na的變量的變量a，na np。如何訪問。如何訪問a的存儲(chǔ)單元？的存儲(chǔ)單元？n從棧頂?shù)幕顒?dòng)記錄開始從棧頂?shù)幕顒?dòng)記錄開始, 追蹤訪問鏈追蹤訪問鏈np-na次。次。n到達(dá)到達(dá)a的聲明所在過程的活動(dòng)記錄。的聲明所在過程的活動(dòng)記錄。n訪問鏈的追蹤用間接操作就可完成。訪問鏈的追蹤用間接操作就可完成。2021-11-1

54、3649.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域過程過程p對(duì)變量對(duì)變量a訪問時(shí)，訪問時(shí)，a的地址由下面的二元組的地址由下面的二元組表示：表示：（np na，a在活動(dòng)記錄中的偏移）在活動(dòng)記錄中的偏移）2021-11-13659.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域如何建立訪問鏈如何建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的的過程過程xnnp nx的情況的情況nx必須在必須在p中進(jìn)行定義，否則它對(duì)于中進(jìn)行定義，否則它對(duì)于p來說就是不來說就是不可訪問的可訪問的n被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動(dòng)記被調(diào)用過程的訪問鏈必

55、須指向調(diào)用過程的活動(dòng)記錄的訪問鏈錄的訪問鏈2021-11-13669.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域如何建立訪問鏈如何建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程xnnp nx的情況的情況np和和x的嵌套深度分別為的嵌套深度分別為1，2，nx 1的外圍過的外圍過程肯定相同程肯定相同n追蹤訪問鏈追蹤訪問鏈np nx + 1次，到達(dá)了靜態(tài)包圍次，到達(dá)了靜態(tài)包圍x和和p的的且離它們最近的那個(gè)過程的最新活動(dòng)記錄且離它們最近的那個(gè)過程的最新活動(dòng)記錄n所到達(dá)的訪問鏈就是所到達(dá)的訪問鏈就是x的活動(dòng)記錄中的訪問鏈的活動(dòng)記錄中的訪問鏈

56、應(yīng)該應(yīng)該指向的那個(gè)訪問鏈指向的那個(gè)訪問鏈2021-11-13679.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域2.過程型參數(shù)的訪問鏈過程型參數(shù)的訪問鏈program param(input, output); procedure b(function h(n: integer): integer); begin writeln(h(2) end b;procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin cen

57、d.過程作為參數(shù)傳遞時(shí)，怎樣在該過程作為參數(shù)傳遞時(shí)，怎樣在該過程被激活時(shí)建立它的訪問鏈過程被激活時(shí)建立它的訪問鏈從從b的訪問鏈難以建立的訪問鏈難以建立f的訪問鏈的訪問鏈激活激活fc傳遞參數(shù)傳遞參數(shù)f時(shí)，像時(shí)，像調(diào)用調(diào)用f一樣為一樣為f建立建立一個(gè)訪問鏈，該訪一個(gè)訪問鏈，該訪問鏈同問鏈同f一起傳遞給一起傳遞給b。f被激活時(shí)用這被激活時(shí)用這個(gè)訪問鏈建立個(gè)訪問鏈建立f的活的活動(dòng)記錄的訪問鏈動(dòng)記錄的訪問鏈2021-11-13689.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域program param(input, output);（過程作為參數(shù)過程作為參數(shù)）procedure b(funct

58、ion h( begin writeln(h(2) end ;procedure c; var m: integer; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin cend.2021-11-13699.5.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域program ret (input, output);（過程作為返回值過程作為返回值） var f: function (integer): integer;function a: function (integer): intege

59、r; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln ( g(2) end; begin f := a; b(f) end.retabaddm被調(diào)過程被調(diào)過程addm活動(dòng)的生存期超活動(dòng)的生存期超出了調(diào)用過程出了調(diào)用過程a活動(dòng)的生存期活動(dòng)的生存期棧式存儲(chǔ)分配棧式存儲(chǔ)分配策略失效！策略失效！活動(dòng)樹活動(dòng)樹2021-11-1

60、3703. display表表display表是一個(gè)指針數(shù)組表是一個(gè)指針數(shù)組d，在運(yùn)行過程中，若，在運(yùn)行過程中，若當(dāng)前活動(dòng)的過程的嵌套深度為當(dāng)前活動(dòng)的過程的嵌套深度為i，則，則di中存放當(dāng)前的中存放當(dāng)前的活動(dòng)記錄地址，活動(dòng)記錄地址，di-1,di-2, ,d1 中依次存放著當(dāng)前中依次存放著當(dāng)前活動(dòng)的過程的直接外層，活動(dòng)的過程的直接外層， , 直至最外層（主程序）直至最外層（主程序）等每一層過程的最新活動(dòng)地址。等每一層過程的最新活動(dòng)地址。 這樣，嵌套深度為這樣，嵌套深度為j的變量的變量a存放在由存放在由dj所指出所指出的活動(dòng)記錄中。的活動(dòng)記錄中。在運(yùn)行過程中維持一個(gè)在運(yùn)行過程中維持一個(gè)display表實(shí)