編譯原理課程講授課件

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

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