編譯原理課件(hdu)CHAPTER9(Run-TimeEnvironments)

Chapter9

Run-TimeEnvironments概述存儲(chǔ)分配策略（Storage-allocationstrategies）訪問(wèn)非局部名字（Accesstononlocalnames）參數(shù)傳遞（Parameterpassing）11/23/20221Chapter9

Run-TimeEnvironme9.1概述在生成目標(biāo)代碼之前，必須了解目標(biāo)代碼執(zhí)行時(shí)的環(huán)境1、空間環(huán)境目標(biāo)代碼的運(yùn)行都是在操作系統(tǒng)分配的一塊存儲(chǔ)區(qū)內(nèi)進(jìn)行的這塊存儲(chǔ)區(qū)必須容納目標(biāo)代碼和目標(biāo)代碼運(yùn)行時(shí)的數(shù)據(jù)空間（目標(biāo)代碼中指令能訪問(wèn)的空間）11/23/202229.1概述在生成目標(biāo)代碼之前，必須了解目標(biāo)代碼執(zhí)行時(shí)的環(huán)9.1概述編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是設(shè)計(jì)程序語(yǔ)言時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定代碼生成器在生成目標(biāo)代碼時(shí)必須要體現(xiàn)該程序語(yǔ)言在設(shè)計(jì)時(shí)分配數(shù)據(jù)空間的規(guī)定11/23/202239.1概述編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)9.1概述2、寄存器環(huán)境寄存器是目標(biāo)機(jī)器中的寶貴資源如何分配寄存器提高程序運(yùn)行的效率是代碼生成器主要要解決的問(wèn)題，（詳細(xì)內(nèi)容見(jiàn)下一講）**數(shù)據(jù)空間分配和寄存器分配最后都體現(xiàn)在生成的目標(biāo)代碼中11/23/202249.1概述2、寄存器環(huán)境寄存器是目標(biāo)機(jī)器中的寶貴資源如何9.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)不同的語(yǔ)言有不同的分配數(shù)據(jù)空間的規(guī)定，有不同的組織運(yùn)行時(shí)刻存儲(chǔ)空間的方法11/23/202259.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)不同的語(yǔ)言有不同的分9.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)與差異：CPASCALALGOLFORTRAN過(guò)程遞歸調(diào)用過(guò)程嵌套定義動(dòng)態(tài)數(shù)組動(dòng)態(tài)內(nèi)存申請(qǐng)指針檢查√××√×√√×√√√√√×√×

×

×

×√11/23/202269.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)與差異：CPASCA9.1概述名字的聯(lián)編（BindingsofNames）名字的左值(l-value)—內(nèi)存地址，存儲(chǔ)名字的瞬時(shí)值名字的右值(r-value)—名字的瞬時(shí)值名字的聯(lián)編—將一個(gè)內(nèi)存地址與一個(gè)名字聯(lián)系起來(lái)在程序的一次運(yùn)行中，一個(gè)名字右值（瞬時(shí)值）可能會(huì)經(jīng)常改變，一個(gè)名字也可能被聯(lián)編到多個(gè)地址（如遞歸調(diào)用中）11/23/202279.1概述名字的聯(lián)編（BindingsofNames9.1概述運(yùn)行時(shí)刻內(nèi)存的典型劃分操作系統(tǒng)收到運(yùn)行目標(biāo)程序的指令，分配一塊連續(xù)的內(nèi)存空間使目標(biāo)程序在其上運(yùn)行P397Fig7.7這只是一個(gè)典型的劃分，具體語(yǔ)言不同，該劃分也不同棧（Stack）：支持過(guò)程的遞歸調(diào)用堆（Heap）：支持動(dòng)態(tài)內(nèi)存申請(qǐng)11/23/202289.1概述運(yùn)行時(shí)刻內(nèi)存的典型劃分操作系統(tǒng)收到運(yùn)行目標(biāo)程序9.1概述活動(dòng)記錄（ActivationRecords）是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過(guò)程的一次執(zhí)行所需要的信息，如局部數(shù)據(jù)活動(dòng)記錄的結(jié)構(gòu)P398Fig7.8參數(shù)域、狀態(tài)域、數(shù)據(jù)域TOP指向棧頂，TOP-SP指向局部數(shù)據(jù)區(qū)的開(kāi)始位置**這只是一個(gè)一般的結(jié)構(gòu)，具體語(yǔ)言不同，活動(dòng)記錄的結(jié)構(gòu)和內(nèi)容也有差異11/23/202299.1概述活動(dòng)記錄（ActivationRecords9.1概述過(guò)程的活動(dòng)（Activation）過(guò)程的一次完整執(zhí)行（第一條語(yǔ)句到最后一條語(yǔ)句），稱(chēng)為過(guò)程的一次活動(dòng)過(guò)程在執(zhí)行中稱(chēng)它為活著的如果允許遞歸調(diào)用，程序的一次執(zhí)行可能有同一個(gè)過(guò)程的多個(gè)實(shí)例是活著的**本章主要討論不同語(yǔ)言的目標(biāo)程序在運(yùn)行時(shí)的存儲(chǔ)分配策略及名字與其左值和右值的關(guān)系11/23/2022109.1概述過(guò)程的活動(dòng)（Activation）過(guò)程的一次完9.2存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配（Staticallocation）編譯時(shí)確定所需的全部數(shù)據(jù)空間的大小編譯時(shí)安排好每個(gè)名字的存儲(chǔ)位置（相對(duì)地址）采用靜態(tài)存儲(chǔ)分配的典型語(yǔ)言是FORTRAN11/23/2022119.2存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配（Staticalloc9.2存儲(chǔ)分配策略FORTRAN語(yǔ)言程序是段結(jié)構(gòu)的，主程序段+若干子程序（函數(shù)）段沒(méi)有動(dòng)態(tài)數(shù)據(jù)類(lèi)型，每個(gè)名字所需空間是確定的沒(méi)有遞歸調(diào)用，無(wú)需棧區(qū)沒(méi)有動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（如鏈表），沒(méi)有動(dòng)態(tài)內(nèi)存申請(qǐng)，無(wú)需堆區(qū)11/23/2022129.2存儲(chǔ)分配策略FORTRAN語(yǔ)言程序是段結(jié)構(gòu)的，主9.2存儲(chǔ)分配策略因此，編譯時(shí)可確定數(shù)據(jù)區(qū)大小，為每個(gè)名字分配好地址FORTRAN程序運(yùn)行時(shí)內(nèi)存劃分為目標(biāo)代碼區(qū)和靜態(tài)數(shù)據(jù)區(qū)，沒(méi)有棧區(qū)和堆區(qū)程序例子：P402example7.4Fig.7.10Fig.7.11Fig.7.1211/23/2022139.2存儲(chǔ)分配策略因此，編譯時(shí)可確定數(shù)據(jù)區(qū)大小，為每個(gè)名9.2存儲(chǔ)分配策略程序設(shè)計(jì)語(yǔ)言若允許遞歸調(diào)用、可變數(shù)組、可變數(shù)據(jù)結(jié)構(gòu)：編譯時(shí)無(wú)法確定運(yùn)行時(shí)需要的存儲(chǔ)空間大小動(dòng)態(tài)存儲(chǔ)分配包括：棧式分配（Stackallocation）和堆式分配（Heapallocation）只能在運(yùn)行時(shí)動(dòng)態(tài)地確定，采用動(dòng)態(tài)存儲(chǔ)分配11/23/2022149.2存儲(chǔ)分配策略程序設(shè)計(jì)語(yǔ)言若允許遞歸調(diào)用、可變數(shù)組、9.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的思想：在運(yùn)行空間中劃分一塊存儲(chǔ)空間作為棧區(qū)程序運(yùn)行時(shí)每當(dāng)調(diào)用一個(gè)過(guò)程，就將該過(guò)程的活動(dòng)記錄壓入棧中，過(guò)程執(zhí)行完畢將它的活動(dòng)記錄從棧中彈出例子：P405Fig.7.1311/23/2022159.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的思想：在運(yùn)行空間中劃分一9.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的實(shí)現(xiàn)反映在目標(biāo)代碼生成器的構(gòu)造策略中，最終體現(xiàn)在生成的目標(biāo)代碼中調(diào)用序列(CallSequence)目標(biāo)代碼中的一個(gè)指令序列，完成調(diào)用一個(gè)過(guò)程的一系列操作，包括為被調(diào)用過(guò)程分配一個(gè)活動(dòng)記錄，并在相應(yīng)的域中填入信息11/23/2022169.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的實(shí)現(xiàn)反映在目標(biāo)代碼生成器9.2存儲(chǔ)分配策略返回序列(ReturnSequence)目標(biāo)代碼中的一個(gè)指令序列，完成從一個(gè)被調(diào)用過(guò)程返回到它的調(diào)用過(guò)程的一系列操作，包括釋放被調(diào)用過(guò)程的活動(dòng)記錄，并復(fù)制出返回值具體內(nèi)容：P407Fig.7.1411/23/2022179.2存儲(chǔ)分配策略返回序列(ReturnSequenc9.2存儲(chǔ)分配策略有些程序設(shè)計(jì)語(yǔ)言允許用戶(hù)自由申請(qǐng)內(nèi)存空間，如C的malloc和free，PASCAL的new和dispose何時(shí)申請(qǐng)何時(shí)釋放由用戶(hù)決定有些程序設(shè)計(jì)語(yǔ)言在進(jìn)行數(shù)據(jù)空間分配時(shí)不服從棧式的存儲(chǔ)分配原則（即“先申請(qǐng)后釋放、后申請(qǐng)先釋放”）11/23/2022189.2存儲(chǔ)分配策略有些程序設(shè)計(jì)語(yǔ)言允許用戶(hù)自由申請(qǐng)內(nèi)存空9.2存儲(chǔ)分配策略這時(shí)采用堆式存儲(chǔ)分配方案運(yùn)行空間劃分一塊堆區(qū)用戶(hù)（顯式）或目標(biāo)代碼需要時(shí)從這堆中借用一塊，不用時(shí)退還**這是一種完全動(dòng)態(tài)的存儲(chǔ)分配方案11/23/2022199.2存儲(chǔ)分配策略這時(shí)采用堆式存儲(chǔ)分配方案運(yùn)行空間劃分一9.3訪問(wèn)非局部名字非局部名字相對(duì)于引用點(diǎn)所在的過(guò)程或分程序來(lái)說(shuō)的程序執(zhí)行時(shí)引用的在當(dāng)前過(guò)程（分程序）之外定義的變量稱(chēng)為非局部名字**本節(jié)主要討論棧式存儲(chǔ)分配中如何訪問(wèn)非局部名字11/23/2022209.3訪問(wèn)非局部名字非局部名字相對(duì)于引用點(diǎn)所在的過(guò)程或分9.3訪問(wèn)非局部名字最近嵌套的作用域規(guī)則（mostcloselynestedrule）P412這是大多數(shù)程序設(shè)計(jì)語(yǔ)言采用的作用域規(guī)則例子：P416Fig.7.22（過(guò)程）例子：P413Fig.7.18（塊或分程序）11/23/2022219.3訪問(wèn)非局部名字最近嵌套的作用域規(guī)則P4129.3訪問(wèn)非局部名字分程序（塊）結(jié)構(gòu)——ALGOL和C分程序（塊）含有局部數(shù)據(jù)說(shuō)明的語(yǔ)句序列有定界符號(hào)，允許嵌套例子：P413Fig.7.1811/23/2022229.3訪問(wèn)非局部名字分程序（塊）結(jié)構(gòu)——ALGOL9.3訪問(wèn)非局部名字過(guò)程（活動(dòng)記錄）采用棧式存儲(chǔ)分配，分程序中的局部數(shù)據(jù)在活動(dòng)記錄的局部數(shù)據(jù)區(qū)內(nèi)也采用棧式分配并列的分程序中的名字可分配同一個(gè)地址，因?yàn)樗鼈兯鶎俚姆殖绦虿粫?huì)在同一時(shí)刻存活訪問(wèn)同一過(guò)程中的局部名字可以從棧頂?shù)綏５走M(jìn)行定位（同一活動(dòng)記錄中）Fig.7.19**訪問(wèn)其它過(guò)程中的局部名字見(jiàn)下面的討論11/23/2022239.3訪問(wèn)非局部名字過(guò)程（活動(dòng)記錄）采用棧式存儲(chǔ)分配，分9.3訪問(wèn)非局部名字無(wú)過(guò)程嵌套定義——C程序中引用的名字或者在當(dāng)前的過(guò)程中被定義，或者在所有過(guò)程之外被定義在所有過(guò)程之外被定義的變量，稱(chēng)之為全局變量，被存放在靜態(tài)數(shù)據(jù)區(qū)，地址在編譯時(shí)刻確定（放符號(hào)表中）11/23/2022249.3訪問(wèn)非局部名字無(wú)過(guò)程嵌套定義——C程序中引用的9.3訪問(wèn)非局部名字過(guò)程中的局部名字聯(lián)編到過(guò)程的活動(dòng)記錄的局部數(shù)據(jù)區(qū)中訪問(wèn)非局部名字可根據(jù)符號(hào)表中該變量的地址直接到全局靜態(tài)數(shù)據(jù)區(qū)中查找11/23/2022259.3訪問(wèn)非局部名字過(guò)程中的局部名字聯(lián)編到過(guò)程的活動(dòng)記錄9.3訪問(wèn)非局部名字有過(guò)程嵌套定義——PASCALPASCAL語(yǔ)言的一個(gè)例子P416過(guò)程和函數(shù)的嵌套深度（nestingdepth）訪問(wèn)非局部名字的方法有兩種，一種是通過(guò)存取鏈，一種是通過(guò)DISPLAY表主程序?yàn)?11/23/2022269.3訪問(wèn)非局部名字有過(guò)程嵌套定義——PASCALP9.3訪問(wèn)非局部名字存取鏈（accesslinks）活動(dòng)記錄中的一個(gè)區(qū)，是一個(gè)指針若過(guò)程P直接嵌入在過(guò)程Q中，則P的活動(dòng)記錄中的存取鏈指向Q的最近的活動(dòng)記錄中的存取鏈11/23/2022279.3訪問(wèn)非局部名字存取鏈（accesslinks）活9.3訪問(wèn)非局部名字如何建立存取鏈？參見(jiàn)P417Fig.7.23（a）（b）（c）（d）區(qū)分兩種情況：P4181、Np<Nx，Np是調(diào)用者深度，Nx是被調(diào)用者深度2、Np>=NxNp–Nx+1

11/23/2022289.3訪問(wèn)非局部名字如何建立存取鏈？參見(jiàn)P417F9.3訪問(wèn)非局部名字如何利用存取鏈訪問(wèn)非局部名字？根據(jù)當(dāng)前過(guò)程的嵌套深度和非局部名字所在過(guò)程的嵌套深度，可以計(jì)算出需順著存取鏈前進(jìn)的步數(shù)，從而對(duì)非局部名字進(jìn)行訪問(wèn)Np–Na11/23/2022299.3訪問(wèn)非局部名字如何利用存取鏈訪問(wèn)非局部名字？根據(jù)當(dāng)9.3訪問(wèn)非局部名字DISPLAY表是一個(gè)指向活動(dòng)記錄的指針數(shù)組運(yùn)行時(shí)刻要訪問(wèn)的嵌套深度為i的非局部名字就在d[i]所指的活動(dòng)記錄中這種方法只要一步就可到達(dá)要訪問(wèn)的非局部名字的活動(dòng)記錄，比存取鏈方法高效11/23/2022309.3訪問(wèn)非局部名字DISPLAY表是一個(gè)指向活動(dòng)記錄的9.3訪問(wèn)非局部名字如何建立與維護(hù)DISPLAY表？DISPLAY表的大小由程序中嵌套深度最大的過(guò)程決定參見(jiàn)P421Fig.7.26（a）（b）（c）（d）11/23/2022319.3訪問(wèn)非局部名字如何建立與維護(hù)DISPLAY表？9.3訪問(wèn)非局部名字當(dāng)建立嵌套深度為i的過(guò)程的活動(dòng)記錄時(shí)，首先在新的活動(dòng)記錄中保存d[i]的值，然后置d[i]指向新的活動(dòng)記錄注意考慮調(diào)用和返回兩種情況當(dāng)從過(guò)程中返回時(shí)，從活動(dòng)記錄中恢復(fù)老的d[i]的值11/23/2022329.3訪問(wèn)非局部名字當(dāng)建立嵌套深度為i的過(guò)程的活動(dòng)記9.4參數(shù)傳遞傳值調(diào)用（Call-by-Value）把實(shí)在參數(shù)的右值傳遞給形式參數(shù)調(diào)用序列計(jì)算實(shí)在參數(shù)的值，并將它復(fù)制到被調(diào)用過(guò)程活動(dòng)記錄的參數(shù)域中這種參數(shù)傳遞方法對(duì)調(diào)用過(guò)程的活動(dòng)記錄沒(méi)有影響11/23/2022339.4參數(shù)傳遞傳值調(diào)用（Call-by-Value）把實(shí)9.4參數(shù)傳遞引用調(diào)用（Call-by-Reference）把實(shí)在參數(shù)的左值（地址）傳遞給形式參數(shù)調(diào)用序列將實(shí)在參數(shù)的左值（地址）復(fù)制到被調(diào)用過(guò)程活動(dòng)記錄的參數(shù)域中被調(diào)用過(guò)程對(duì)形式參數(shù)的引用其實(shí)是對(duì)實(shí)在參數(shù)的地址（在被調(diào)用過(guò)程的活動(dòng)記錄中）進(jìn)行引用11/23/2022349.4參數(shù)傳遞引用調(diào)用（Call-by-Referenc9.4參數(shù)傳遞復(fù)制恢復(fù)（Copy-Restore）傳遞參數(shù)同傳值調(diào)用在從被調(diào)用過(guò)程返回前，把形式參數(shù)的現(xiàn)行右值復(fù)制回相應(yīng)的實(shí)在參數(shù)的左值中這種方法與引用調(diào)用是有區(qū)別的：在被調(diào)用過(guò)程體中訪問(wèn)了非局部名字，而此非局部名字正是形式參數(shù)時(shí)P427Fig.7.3111/23/2022359.4參數(shù)傳遞復(fù)制恢復(fù)（Copy-Restore）傳遞參9.4參數(shù)傳遞傳名調(diào)用（Call-by-Name）用實(shí)在參數(shù)對(duì)過(guò)程體進(jìn)行宏擴(kuò)展，必要時(shí)對(duì)被調(diào)用過(guò)程中的名字進(jìn)行改名（防止與調(diào)用過(guò)程中的名字重復(fù)）**例子：P456練習(xí)7.6Fig.7.5311/23/2022369.4參數(shù)傳遞傳名調(diào)用（Call-by-Name）用實(shí)在TheEnd!11/23/202237TheEnd!11/22/202237Chapter9

Run-TimeEnvironments概述存儲(chǔ)分配策略（Storage-allocationstrategies）訪問(wèn)非局部名字（Accesstononlocalnames）參數(shù)傳遞（Parameterpassing）11/23/202238Chapter9

Run-TimeEnvironme9.1概述在生成目標(biāo)代碼之前，必須了解目標(biāo)代碼執(zhí)行時(shí)的環(huán)境1、空間環(huán)境目標(biāo)代碼的運(yùn)行都是在操作系統(tǒng)分配的一塊存儲(chǔ)區(qū)內(nèi)進(jìn)行的這塊存儲(chǔ)區(qū)必須容納目標(biāo)代碼和目標(biāo)代碼運(yùn)行時(shí)的數(shù)據(jù)空間（目標(biāo)代碼中指令能訪問(wèn)的空間）11/23/2022399.1概述在生成目標(biāo)代碼之前，必須了解目標(biāo)代碼執(zhí)行時(shí)的環(huán)9.1概述編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是設(shè)計(jì)程序語(yǔ)言時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定代碼生成器在生成目標(biāo)代碼時(shí)必須要體現(xiàn)該程序語(yǔ)言在設(shè)計(jì)時(shí)分配數(shù)據(jù)空間的規(guī)定11/23/2022409.1概述編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)9.1概述2、寄存器環(huán)境寄存器是目標(biāo)機(jī)器中的寶貴資源如何分配寄存器提高程序運(yùn)行的效率是代碼生成器主要要解決的問(wèn)題，（詳細(xì)內(nèi)容見(jiàn)下一講）**數(shù)據(jù)空間分配和寄存器分配最后都體現(xiàn)在生成的目標(biāo)代碼中11/23/2022419.1概述2、寄存器環(huán)境寄存器是目標(biāo)機(jī)器中的寶貴資源如何9.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)不同的語(yǔ)言有不同的分配數(shù)據(jù)空間的規(guī)定，有不同的組織運(yùn)行時(shí)刻存儲(chǔ)空間的方法11/23/2022429.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)不同的語(yǔ)言有不同的分9.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)與差異：CPASCALALGOLFORTRAN過(guò)程遞歸調(diào)用過(guò)程嵌套定義動(dòng)態(tài)數(shù)組動(dòng)態(tài)內(nèi)存申請(qǐng)指針檢查√××√×√√×√√√√√×√×

×

×

×√11/23/2022439.1概述幾種典型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)與差異：CPASCA9.1概述名字的聯(lián)編（BindingsofNames）名字的左值(l-value)—內(nèi)存地址，存儲(chǔ)名字的瞬時(shí)值名字的右值(r-value)—名字的瞬時(shí)值名字的聯(lián)編—將一個(gè)內(nèi)存地址與一個(gè)名字聯(lián)系起來(lái)在程序的一次運(yùn)行中，一個(gè)名字右值（瞬時(shí)值）可能會(huì)經(jīng)常改變，一個(gè)名字也可能被聯(lián)編到多個(gè)地址（如遞歸調(diào)用中）11/23/2022449.1概述名字的聯(lián)編（BindingsofNames9.1概述運(yùn)行時(shí)刻內(nèi)存的典型劃分操作系統(tǒng)收到運(yùn)行目標(biāo)程序的指令，分配一塊連續(xù)的內(nèi)存空間使目標(biāo)程序在其上運(yùn)行P397Fig7.7這只是一個(gè)典型的劃分，具體語(yǔ)言不同，該劃分也不同棧（Stack）：支持過(guò)程的遞歸調(diào)用堆（Heap）：支持動(dòng)態(tài)內(nèi)存申請(qǐng)11/23/2022459.1概述運(yùn)行時(shí)刻內(nèi)存的典型劃分操作系統(tǒng)收到運(yùn)行目標(biāo)程序9.1概述活動(dòng)記錄（ActivationRecords）是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過(guò)程的一次執(zhí)行所需要的信息，如局部數(shù)據(jù)活動(dòng)記錄的結(jié)構(gòu)P398Fig7.8參數(shù)域、狀態(tài)域、數(shù)據(jù)域TOP指向棧頂，TOP-SP指向局部數(shù)據(jù)區(qū)的開(kāi)始位置**這只是一個(gè)一般的結(jié)構(gòu)，具體語(yǔ)言不同，活動(dòng)記錄的結(jié)構(gòu)和內(nèi)容也有差異11/23/2022469.1概述活動(dòng)記錄（ActivationRecords9.1概述過(guò)程的活動(dòng)（Activation）過(guò)程的一次完整執(zhí)行（第一條語(yǔ)句到最后一條語(yǔ)句），稱(chēng)為過(guò)程的一次活動(dòng)過(guò)程在執(zhí)行中稱(chēng)它為活著的如果允許遞歸調(diào)用，程序的一次執(zhí)行可能有同一個(gè)過(guò)程的多個(gè)實(shí)例是活著的**本章主要討論不同語(yǔ)言的目標(biāo)程序在運(yùn)行時(shí)的存儲(chǔ)分配策略及名字與其左值和右值的關(guān)系11/23/2022479.1概述過(guò)程的活動(dòng)（Activation）過(guò)程的一次完9.2存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配（Staticallocation）編譯時(shí)確定所需的全部數(shù)據(jù)空間的大小編譯時(shí)安排好每個(gè)名字的存儲(chǔ)位置（相對(duì)地址）采用靜態(tài)存儲(chǔ)分配的典型語(yǔ)言是FORTRAN11/23/2022489.2存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配（Staticalloc9.2存儲(chǔ)分配策略FORTRAN語(yǔ)言程序是段結(jié)構(gòu)的，主程序段+若干子程序（函數(shù)）段沒(méi)有動(dòng)態(tài)數(shù)據(jù)類(lèi)型，每個(gè)名字所需空間是確定的沒(méi)有遞歸調(diào)用，無(wú)需棧區(qū)沒(méi)有動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（如鏈表），沒(méi)有動(dòng)態(tài)內(nèi)存申請(qǐng)，無(wú)需堆區(qū)11/23/2022499.2存儲(chǔ)分配策略FORTRAN語(yǔ)言程序是段結(jié)構(gòu)的，主9.2存儲(chǔ)分配策略因此，編譯時(shí)可確定數(shù)據(jù)區(qū)大小，為每個(gè)名字分配好地址FORTRAN程序運(yùn)行時(shí)內(nèi)存劃分為目標(biāo)代碼區(qū)和靜態(tài)數(shù)據(jù)區(qū)，沒(méi)有棧區(qū)和堆區(qū)程序例子：P402example7.4Fig.7.10Fig.7.11Fig.7.1211/23/2022509.2存儲(chǔ)分配策略因此，編譯時(shí)可確定數(shù)據(jù)區(qū)大小，為每個(gè)名9.2存儲(chǔ)分配策略程序設(shè)計(jì)語(yǔ)言若允許遞歸調(diào)用、可變數(shù)組、可變數(shù)據(jù)結(jié)構(gòu)：編譯時(shí)無(wú)法確定運(yùn)行時(shí)需要的存儲(chǔ)空間大小動(dòng)態(tài)存儲(chǔ)分配包括：棧式分配（Stackallocation）和堆式分配（Heapallocation）只能在運(yùn)行時(shí)動(dòng)態(tài)地確定，采用動(dòng)態(tài)存儲(chǔ)分配11/23/2022519.2存儲(chǔ)分配策略程序設(shè)計(jì)語(yǔ)言若允許遞歸調(diào)用、可變數(shù)組、9.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的思想：在運(yùn)行空間中劃分一塊存儲(chǔ)空間作為棧區(qū)程序運(yùn)行時(shí)每當(dāng)調(diào)用一個(gè)過(guò)程，就將該過(guò)程的活動(dòng)記錄壓入棧中，過(guò)程執(zhí)行完畢將它的活動(dòng)記錄從棧中彈出例子：P405Fig.7.1311/23/2022529.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的思想：在運(yùn)行空間中劃分一9.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的實(shí)現(xiàn)反映在目標(biāo)代碼生成器的構(gòu)造策略中，最終體現(xiàn)在生成的目標(biāo)代碼中調(diào)用序列(CallSequence)目標(biāo)代碼中的一個(gè)指令序列，完成調(diào)用一個(gè)過(guò)程的一系列操作，包括為被調(diào)用過(guò)程分配一個(gè)活動(dòng)記錄，并在相應(yīng)的域中填入信息11/23/2022539.2存儲(chǔ)分配策略棧式存儲(chǔ)分配的實(shí)現(xiàn)反映在目標(biāo)代碼生成器9.2存儲(chǔ)分配策略返回序列(ReturnSequence)目標(biāo)代碼中的一個(gè)指令序列，完成從一個(gè)被調(diào)用過(guò)程返回到它的調(diào)用過(guò)程的一系列操作，包括釋放被調(diào)用過(guò)程的活動(dòng)記錄，并復(fù)制出返回值具體內(nèi)容：P407Fig.7.1411/23/2022549.2存儲(chǔ)分配策略返回序列(ReturnSequenc9.2存儲(chǔ)分配策略有些程序設(shè)計(jì)語(yǔ)言允許用戶(hù)自由申請(qǐng)內(nèi)存空間，如C的malloc和free，PASCAL的new和dispose何時(shí)申請(qǐng)何時(shí)釋放由用戶(hù)決定有些程序設(shè)計(jì)語(yǔ)言在進(jìn)行數(shù)據(jù)空間分配時(shí)不服從棧式的存儲(chǔ)分配原則（即“先申請(qǐng)后釋放、后申請(qǐng)先釋放”）11/23/2022559.2存儲(chǔ)分配策略有些程序設(shè)計(jì)語(yǔ)言允許用戶(hù)自由申請(qǐng)內(nèi)存空9.2存儲(chǔ)分配策略這時(shí)采用堆式存儲(chǔ)分配方案運(yùn)行空間劃分一塊堆區(qū)用戶(hù)（顯式）或目標(biāo)代碼需要時(shí)從這堆中借用一塊，不用時(shí)退還**這是一種完全動(dòng)態(tài)的存儲(chǔ)分配方案11/23/2022569.2存儲(chǔ)分配策略這時(shí)采用堆式存儲(chǔ)分配方案運(yùn)行空間劃分一9.3訪問(wèn)非局部名字非局部名字相對(duì)于引用點(diǎn)所在的過(guò)程或分程序來(lái)說(shuō)的程序執(zhí)行時(shí)引用的在當(dāng)前過(guò)程（分程序）之外定義的變量稱(chēng)為非局部名字**本節(jié)主要討論棧式存儲(chǔ)分配中如何訪問(wèn)非局部名字11/23/2022579.3訪問(wèn)非局部名字非局部名字相對(duì)于引用點(diǎn)所在的過(guò)程或分9.3訪問(wèn)非局部名字最近嵌套的作用域規(guī)則（mostcloselynestedrule）P412這是大多數(shù)程序設(shè)計(jì)語(yǔ)言采用的作用域規(guī)則例子：P416Fig.7.22（過(guò)程）例子：P413Fig.7.18（塊或分程序）11/23/2022589.3訪問(wèn)非局部名字最近嵌套的作用域規(guī)則P4129.3訪問(wèn)非局部名字分程序（塊）結(jié)構(gòu)——ALGOL和C分程序（塊）含有局部數(shù)據(jù)說(shuō)明的語(yǔ)句序列有定界符號(hào)，允許嵌套例子：P413Fig.7.1811/23/2022599.3訪問(wèn)非局部名字分程序（塊）結(jié)構(gòu)——ALGOL9.3訪問(wèn)非局部名字過(guò)程（活動(dòng)記錄）采用棧式存儲(chǔ)分配，分程序中的局部數(shù)據(jù)在活動(dòng)記錄的局部數(shù)據(jù)區(qū)內(nèi)也采用棧式分配并列的分程序中的名字可分配同一個(gè)地址，因?yàn)樗鼈兯鶎俚姆殖绦虿粫?huì)在同一時(shí)刻存活訪問(wèn)同一過(guò)程中的局部名字可以從棧頂?shù)綏５走M(jìn)行定位（同一活動(dòng)記錄中）Fig.7.19**訪問(wèn)其它過(guò)程中的局部名字見(jiàn)下面的討論11/23/2022609.3訪問(wèn)非局部名字過(guò)程（活動(dòng)記錄）采用棧式存儲(chǔ)分配，分9.3訪問(wèn)非局部名字無(wú)過(guò)程嵌套定義——C程序中引用的名字或者在當(dāng)前的過(guò)程中被定義，或者在所有過(guò)程之外被定義在所有過(guò)程之外被定義的變量，稱(chēng)之為全局變量，被存放在靜態(tài)數(shù)據(jù)區(qū)，地址在編譯時(shí)刻確定（放符號(hào)表中）11/23/2022619.3訪問(wèn)非局部名字無(wú)過(guò)程嵌套定義——C程序中引用的9.3訪問(wèn)非局部名字過(guò)程中的局部名字聯(lián)編到過(guò)程的活動(dòng)記錄的局部數(shù)據(jù)區(qū)中訪問(wèn)非局部名字可根據(jù)符號(hào)表中該變量的地址直接到全局靜態(tài)數(shù)據(jù)區(qū)中查找11/23/2022629.3訪問(wèn)非局部名字過(guò)程中的局部名字聯(lián)編到過(guò)程的活動(dòng)記錄9.3訪問(wèn)非局部名字有過(guò)程嵌套定義——PASCALPASCAL語(yǔ)言的一個(gè)例子P416過(guò)程和函數(shù)的嵌套深度（nestingdepth）訪問(wèn)非局部名字的方法有兩種，一種是通過(guò)存取鏈，一種是通過(guò)DISPLAY表主程序?yàn)?11/23/2022639.3訪問(wèn)非局部名字有過(guò)程嵌套定義——PASCALP9.3訪問(wèn)非局部名字存取鏈（accesslinks）活動(dòng)記錄中的一個(gè)區(qū)，是一個(gè)指針若過(guò)程P直接嵌入在過(guò)程Q中，則P的活動(dòng)記錄中的存取鏈指向Q的最近的活動(dòng)記錄中的存取鏈11/23/2022649.3訪問(wèn)非局部名字存取鏈（accesslinks）活9.3訪問(wèn)非局部名字如何建立存取鏈？參見(jiàn)P417Fig.7.23（a）（b）（c）（d）區(qū)分兩種情況：P4181、Np<Nx，Np是調(diào)用者深度，Nx是被調(diào)用者深度2、Np>=NxNp–Nx+1

11/23/2022659.3訪問(wèn)非局部名字如何建立存取鏈？參見(jiàn)P417F9.3訪問(wèn)非局部名字如何利用存取鏈訪問(wèn)非局部名字？根據(jù)當(dāng)前過(guò)程的嵌套深度和非局部名字所在過(guò)程的嵌套深度，可以計(jì)算出需順著存取鏈前進(jìn)的步數(shù)，從而對(duì)非局部名字進(jìn)行訪問(wèn)Np–Na11/23/2022669.3訪問(wèn)非局部名字如何利