編譯原理課程講授課件

運(yùn)行時(shí)環(huán)境授課：胡靜本章研究問題在生成目標(biāo)代碼之前，需要把程序靜態(tài)的正文和實(shí)現(xiàn)這個(gè)程序的運(yùn)行時(shí)的活動(dòng)聯(lián)系起來，主要是存儲(chǔ)組織與管理活動(dòng)記錄的建立與管理存儲(chǔ)器的組織與存儲(chǔ)分配策略非局部名稱的訪問目標(biāo)程序運(yùn)行時(shí)的活動(dòng)過程的活動(dòng)過程的活動(dòng)主要討論的是過程的靜態(tài)源程序和它的目標(biāo)程序在運(yùn)行時(shí)的活動(dòng)之間的關(guān)系過程最簡(jiǎn)單的形式是一個(gè)標(biāo)識(shí)符和一段語句組成。函數(shù)是具有返回值的過程，也放入過程中進(jìn)行討論把完整的程序也看成過程過程的調(diào)用位置過程名出現(xiàn)在可執(zhí)行語句里時(shí)過程名出現(xiàn)在表達(dá)式里時(shí)過程中的定義的標(biāo)識(shí)符形式參數(shù)（相對(duì)應(yīng)實(shí)在參數(shù)）局部變量過程的活動(dòng)一個(gè)過程的活動(dòng)指的是該過程的一次執(zhí)行過程P一個(gè)活動(dòng)的生存期，指的是從執(zhí)行該過程體第一步操作到左后一步操作之間的操作序列，也包括執(zhí)行P時(shí)調(diào)用其他程序花費(fèi)的時(shí)間每次控制從過程P進(jìn)入過程Q后，如果沒有錯(cuò)誤，最后都要返回到過程P。如果a和b都是過程的活動(dòng)，那么它們的生存期或者是不重疊，或者是嵌套的。如果一個(gè)過程是遞歸的（直接遞歸或間接遞歸），在某一時(shí)刻可能有幾個(gè)活動(dòng)記錄活躍著

運(yùn)行時(shí)存儲(chǔ)器的劃分存儲(chǔ)組織產(chǎn)生的目標(biāo)代碼長(zhǎng)度在編譯時(shí)可以確定放在靜態(tài)區(qū)域，內(nèi)存的低地址區(qū)目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆靜態(tài)數(shù)據(jù)某些數(shù)據(jù)的長(zhǎng)度在編譯時(shí)可知放在靜態(tài)區(qū)域，其地址可以編譯到目標(biāo)代碼中拓廣的控制棧棧保存程序的斷點(diǎn)需要保存的各種狀態(tài)堆用來保存那些不能用活動(dòng)樹表示的語言的實(shí)現(xiàn)過程中產(chǎn)生的活動(dòng)信息?；顒?dòng)記錄活動(dòng)記錄的定義過程一次執(zhí)行所需要的信息用一塊連續(xù)的存儲(chǔ)區(qū)來管理，這塊存儲(chǔ)區(qū)叫做活動(dòng)記錄在過程調(diào)用時(shí)將活動(dòng)記錄壓入棧，在控制返回調(diào)用者時(shí)把活動(dòng)記錄彈出返回值實(shí)參可選的控制鏈可選的訪問鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)活動(dòng)記錄各部分信息臨時(shí)數(shù)據(jù)域：計(jì)算表達(dá)式時(shí)出現(xiàn)的那些值局部數(shù)據(jù)域：保存局部于過程執(zhí)行的數(shù)據(jù)機(jī)器狀態(tài)域：保存過程調(diào)用前的機(jī)器狀態(tài)信息，包括程序計(jì)數(shù)器的值和寄存器的值可選的訪問鏈：引用存于其它活動(dòng)記錄中的非局部變量（靜態(tài)鏈）可選的控制鏈：用來指向調(diào)用者的活動(dòng)記錄（動(dòng)態(tài)鏈）實(shí)在參數(shù)域：用于存放調(diào)用過程提供給被調(diào)用那個(gè)過程的參數(shù)返回值域：用于存放被調(diào)用返回給調(diào)用過程的值返回值實(shí)參可選的控制鏈可選的訪問鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)存儲(chǔ)分配策略存儲(chǔ)分配的三種策略靜態(tài)分配策略在編譯時(shí)為所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，且在運(yùn)行時(shí)始終保持不變棧式動(dòng)態(tài)分配策略在運(yùn)行時(shí)按棧方式管理運(yùn)行時(shí)的存儲(chǔ)空間堆式動(dòng)態(tài)分配策略在運(yùn)行時(shí)根據(jù)需要從堆數(shù)據(jù)區(qū)域分配和釋放存儲(chǔ)空間代碼靜態(tài)數(shù)據(jù)棧堆存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配在靜態(tài)分配中，名字在程序編譯時(shí)與存儲(chǔ)單元綁定，所以不需要運(yùn)行時(shí)支撐程序包。因?yàn)檫\(yùn)行時(shí)不改變綁定，所以每次過程活動(dòng)時(shí)，它的名字都綁定到同樣的存儲(chǔ)單元。這種性質(zhì)允許局部名字的值在過程停止活動(dòng)后仍然保持，即當(dāng)控制再次進(jìn)入過程時(shí)，局部名字的值同控制上一次離開時(shí)一樣。因?yàn)殪o態(tài)分配，所以編譯時(shí)在目標(biāo)代碼中能填上所有操作的數(shù)據(jù)對(duì)象的地址靜態(tài)分配的局限性數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置的約束在編譯時(shí)必須知道不允許遞歸過程，因?yàn)橐粋€(gè)過程的所有活動(dòng)使用同樣的局部名字綁定數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立，因?yàn)闆]有運(yùn)行時(shí)的存儲(chǔ)分配機(jī)制。棧式存儲(chǔ)分配棧式存儲(chǔ)分配的思想（基于控制棧）把存儲(chǔ)空間組織為棧，而且隨著過程活動(dòng)的開始和結(jié)束將活動(dòng)記錄進(jìn)棧和出棧過程每次調(diào)用時(shí)，局部量的存儲(chǔ)空間包含在該次調(diào)用的活動(dòng)記錄中。每次調(diào)用都引起新的活動(dòng)記錄進(jìn)棧，每次活動(dòng)時(shí)局部量都綁到新的存儲(chǔ)單元活動(dòng)記錄彈出棧時(shí)局部量的存儲(chǔ)空間將被釋放，所以活動(dòng)結(jié)束時(shí)局部量的值被刪除。棧式存儲(chǔ)分配調(diào)用序列：過程調(diào)用是通過在目標(biāo)代碼中生成調(diào)用序列來實(shí)現(xiàn)調(diào)用序列分配活動(dòng)記錄，并把信息填入它的域中返回序列恢復(fù)機(jī)器狀態(tài)，使調(diào)用過程能繼續(xù)執(zhí)行。調(diào)用序列的代碼常常分成兩部分，分別處于調(diào)用過程和被調(diào)用過程中。有助于設(shè)計(jì)調(diào)用序列和活動(dòng)記錄的一個(gè)原則是，長(zhǎng)度能較早確定的域放在活動(dòng)記錄的中間。棧式存儲(chǔ)分配在活動(dòng)記錄中，控制鏈、訪問鏈和機(jī)器狀態(tài)域出現(xiàn)在中間。臨時(shí)數(shù)據(jù)域的長(zhǎng)度可以在編譯時(shí)最終確定，但就前端而言，這個(gè)域的大小也可能是未知的。臨時(shí)數(shù)據(jù)放在局部數(shù)據(jù)域后面，它的長(zhǎng)度的改變不會(huì)影響數(shù)據(jù)對(duì)象相對(duì)于中間那些域的位置。返回值和實(shí)參放在活動(dòng)記錄的最開始。方便調(diào)用者和被調(diào)用者之間的數(shù)據(jù)交換。返回值實(shí)參可選的控制鏈可選的訪問鏈保存的機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)棧式存儲(chǔ)分配寄存器top_sp指向活動(dòng)記錄中機(jī)器狀態(tài)域的末端，在控制轉(zhuǎn)移到被調(diào)用過程之前用它來置top_sp的值，其調(diào)用序列是：調(diào)用者計(jì)算實(shí)參調(diào)用者把返回地址和top_sp的舊值存入被調(diào)用者的活動(dòng)記錄中被調(diào)用者保持寄存器值和其他機(jī)器狀態(tài)信息被調(diào)用者初始化其局部數(shù)據(jù)，并開始執(zhí)行……參數(shù)和返回值鏈和保存的狀態(tài)臨時(shí)變量和局部數(shù)據(jù)參數(shù)和返回值臨時(shí)變量和局部數(shù)據(jù)控制鏈鏈和保存的狀態(tài)控制鏈top_sp調(diào)用者的活動(dòng)記錄被調(diào)用者的活動(dòng)記錄調(diào)用者的任務(wù)被調(diào)用者的任務(wù)堆式存儲(chǔ)分配棧式存儲(chǔ)分配策略在下列情況下不能使用：活動(dòng)結(jié)束時(shí)必須保持局部名字的值被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期長(zhǎng)。堆式存儲(chǔ)器的策略：（堆管理器管理堆空間）把連續(xù)存儲(chǔ)區(qū)域分成塊，當(dāng)活動(dòng)記錄或其他對(duì)象需要時(shí)就分配。塊的釋放可以按任意次序進(jìn)行，所以經(jīng)過一段時(shí)間后，堆可能包含交錯(cuò)的正在使用的和已經(jīng)釋放的區(qū)域堆管理器的效率問題堆管理的效率問題是數(shù)據(jù)結(jié)構(gòu)理論中的特殊問題對(duì)每個(gè)感興趣的活動(dòng)記錄的大小，保存一個(gè)相應(yīng)大小的空閑塊的鏈表可能的話，為大小為s的請(qǐng)求分配一個(gè)大小為s’的塊，其中s’是大小等于s的最小塊。當(dāng)該塊最終被釋放后，將其鏈回原來的空閑塊鏈表對(duì)于大塊存儲(chǔ)空間，使用堆管理器管理。其具體管理方法可以參考操作系統(tǒng)中堆內(nèi)存的管理方法。對(duì)非局部名字的訪問語言的作用域規(guī)則確定了如何處理非局部名字的訪問詞法作用域規(guī)則（靜態(tài)作用域規(guī)則）：僅僅根據(jù)程序正文即可以確定用于名字的聲明。如最近嵌套規(guī)則動(dòng)態(tài)作用域規(guī)則：在運(yùn)行時(shí)根據(jù)當(dāng)前的活動(dòng)來決定用于名字的聲明。參數(shù)傳遞參數(shù)傳遞說明的作用域如果一個(gè)說明的作用域是在一個(gè)過程里，那么這個(gè)過程里出現(xiàn)的該說明中的名字都是局部于本過程的；除上述之外的名稱是非局部的。參數(shù)傳遞方式：過程的形式參數(shù)和實(shí)在參數(shù)的對(duì)應(yīng)方式。形式參數(shù)和實(shí)在參數(shù)的“左值”和“右值”之間的對(duì)應(yīng)關(guān)系劃分參數(shù)傳遞方式：傳值調(diào)用引用調(diào)用（傳地址調(diào)用）復(fù)制-恢復(fù)調(diào)用傳名調(diào)用參數(shù)傳遞——傳值調(diào)用傳值調(diào)用：計(jì)算實(shí)參，并把它的右值傳給被調(diào)用過程把形參當(dāng)作局部名字看待，形參的存儲(chǔ)單元在被調(diào)用過程的活動(dòng)記錄中調(diào)用者計(jì)算實(shí)參，并把其右值放入形參的存儲(chǔ)單元中傳值調(diào)用的顯著特征是對(duì)形參的運(yùn)算不影響調(diào)用者活動(dòng)記錄中的值打印結(jié)果ais1,bis2s)intx,y{inttemp;temp=x;x=y;y=temp;}main(){inta=1,b=2;s);printf(“ais%d,bis%d”,a,b);}參數(shù)傳遞——引用調(diào)用引用調(diào)用：傳遞時(shí)，調(diào)用過程把實(shí)參存儲(chǔ)單元的地址傳遞給被調(diào)用過程如果實(shí)參是有左值的名字或表達(dá)式，則傳遞這個(gè)左值本身；如果實(shí)參是表達(dá)式，沒有左值，則計(jì)算該表達(dá)式的值并存入新的存儲(chǔ)單元，然后傳遞這個(gè)單元的地址打印結(jié)果ais2,bis1s)intx,y{inttemp;temp=x;x=y;y=temp;}main(){inta=1,b=2;s);printf(“ais%d,bis%d”,a,b);}參數(shù)傳遞——復(fù)制-恢復(fù)傳值調(diào)用和引用調(diào)用的混合在控制流進(jìn)入被調(diào)用過程之前計(jì)算實(shí)參，實(shí)參的右值像傳值調(diào)用那樣傳遞給被調(diào)用過程，此外如果實(shí)參有左值的話，在調(diào)用之前確定它的左值當(dāng)控制返回時(shí)，將形參的當(dāng)前右值復(fù)制回實(shí)參的左值，該左值是上述調(diào)用前計(jì)算的左值。打印結(jié)果ais2,bis1s)intx,y{inttemp;temp=x;x=y;y=temp;}main(){inta=1,b=2;s);printf(“ais%d,bis%d”,a,b);}參數(shù)傳遞——傳名調(diào)用傳名調(diào)用的用法類似于宏過程被看做宏，也就是說，在調(diào)用過程中將調(diào)用替換為被調(diào)用過程的過程體，但要把任何一個(gè)出現(xiàn)的形式參數(shù)都文字的替換為相應(yīng)的實(shí)參被調(diào)用過程中局部名字要保持與調(diào)用過程中的名字不同打印