編譯原理實(shí)踐8-運(yùn)行時(shí)的存儲(chǔ)組織與分配

編譯原理實(shí)踐

--運(yùn)行時(shí)的存儲(chǔ)組織與分配在程序的執(zhí)行過程中，程序中數(shù)據(jù)的存取是通過對(duì)應(yīng)的存儲(chǔ)單元進(jìn)行的。在早期的計(jì)算機(jī)上，這個(gè)存儲(chǔ)管理工作是由程序員自己來完成。在程序執(zhí)行以前，首先要將用機(jī)器語言或匯編語言編寫的程序輸送到內(nèi)存的某個(gè)指定區(qū)域中，并預(yù)先給變量和數(shù)據(jù)分配相應(yīng)的內(nèi)存地址。而有了高級(jí)語言之后，程序員不必直接和內(nèi)存地址打交道，程序中使用的存儲(chǔ)單元都由邏輯變量(標(biāo)識(shí)符)來表示，它們對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)分配或由其生成的目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配。所以，對(duì)編譯程序來說，存儲(chǔ)的組織及管理是一個(gè)復(fù)雜而又十分重要的問題。另外，有些程序設(shè)計(jì)語言允許有遞歸過程，有的允許有可變長(zhǎng)度的串，有的允許有動(dòng)態(tài)數(shù)組，而有些語言則不允許有這些，為什么呢？這都是因?yàn)椴捎昧瞬煌拇鎯?chǔ)分配方式。1、存儲(chǔ)組織概述程序運(yùn)行時(shí)，系統(tǒng)將為程序分配一塊存儲(chǔ)空間。這塊空間用來存儲(chǔ)程序的目標(biāo)代碼以及目標(biāo)代碼運(yùn)行時(shí)需要或產(chǎn)生的各種數(shù)據(jù)：1）

目標(biāo)程序區(qū)：用來存放目標(biāo)代碼。2）

靜態(tài)數(shù)據(jù)區(qū)：用來存放編譯時(shí)就能確定存儲(chǔ)空間的數(shù)據(jù)。3）

運(yùn)行棧區(qū)：用來存放運(yùn)行時(shí)才能確定存儲(chǔ)空間的數(shù)據(jù)。4）

運(yùn)行堆區(qū)：用來存放運(yùn)行時(shí)用戶動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間的數(shù)據(jù)。運(yùn)行時(shí)存儲(chǔ)空間的劃分目標(biāo)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)棧自由空間堆存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配在運(yùn)行前就能確定數(shù)據(jù)空間的大小，因而在編譯時(shí)就能分配各種數(shù)據(jù)項(xiàng)的空間，如FORTRAN語言動(dòng)態(tài)存儲(chǔ)分配 不能在編譯時(shí)完全確定所有數(shù)據(jù)項(xiàng)的存儲(chǔ)空間，只能在編譯時(shí)產(chǎn)生各種必要的信息，而在運(yùn)行時(shí)，再動(dòng)態(tài)地分配數(shù)據(jù)項(xiàng)的存儲(chǔ)空間。包括棧式動(dòng)態(tài)存儲(chǔ)分配和堆式動(dòng)態(tài)存儲(chǔ)分配1）棧式動(dòng)態(tài)存儲(chǔ)分配：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)分程序或過程，其中各項(xiàng)數(shù)據(jù)項(xiàng)所需的存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，退出時(shí)，則釋放所占用的空間特點(diǎn)：效率很高，但是分配的內(nèi)存容量有限2）堆式動(dòng)態(tài)存儲(chǔ)分配： 允許用戶動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間，每當(dāng)需要時(shí)可從堆中分得一塊，用完之后再退還給堆特點(diǎn)：動(dòng)態(tài)內(nèi)存的生存期由我們決定，使用非常靈活，但問題也最多注意：我們接下來只討論棧式動(dòng)態(tài)存儲(chǔ)分配棧式動(dòng)態(tài)存儲(chǔ)分配在允許遞歸調(diào)用的語言中，每次遞歸調(diào)用都要重新分配局部變量。對(duì)于這種語言應(yīng)該采用“棧式動(dòng)態(tài)存儲(chǔ)分配”，其分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧，每當(dāng)調(diào)用一個(gè)過程時(shí)就將其活動(dòng)記錄壓入棧，在棧頂形成該過程工作時(shí)的數(shù)據(jù)區(qū)，而當(dāng)過程結(jié)束時(shí)再將其活動(dòng)記錄彈出棧。在這種分配方式下，過程的調(diào)用關(guān)系是先進(jìn)后出的棧模型，每個(gè)過程都可能有若干個(gè)不同的活動(dòng)記錄，每個(gè)活動(dòng)記錄代表了一次不同的調(diào)用。當(dāng)前的AR首地址由棧指針SP指出。AR中通常應(yīng)包含如下內(nèi)容：被調(diào)用過程非局部變量存儲(chǔ)區(qū)的首地址（靜態(tài)鏈、Display表）調(diào)用過程的AR首址（動(dòng)態(tài)鏈，oldSP)調(diào)用點(diǎn)的機(jī)器狀態(tài)形實(shí)參數(shù)通訊區(qū)返回值被調(diào)用過程的局部量和臨時(shí)變量存儲(chǔ)區(qū)返回指針returnedpointer動(dòng)態(tài)鏈dynamiclink靜態(tài)鏈staticlink機(jī)器狀態(tài)machinestates參數(shù)單元parameters局部變量localvariables臨時(shí)變量temporaries高地址低地址mainpQ callQ callQ

callpSPmain’sARp’sARQ’sAR(1)Q’sAR(2)棧增長(zhǎng)方向過程的一次執(zhí)行對(duì)應(yīng)一個(gè)AR1）簡(jiǎn)單語言的棧式存儲(chǔ)分配簡(jiǎn)單語言：無分程序結(jié)構(gòu)，過程定義不嵌套，但允許過程的遞歸調(diào)用。如C語言。C語言不允許過程嵌套定義，即不允許在一個(gè)過程內(nèi)定義另一個(gè)過程。C語言的全局變量只能出現(xiàn)在源程序的開頭，可采用靜態(tài)存儲(chǔ)分配，編譯時(shí)候就確定它們的地址計(jì)算局部變量或形參絕對(duì)地址的公式為：絕對(duì)地址=SP+相對(duì)地址比較簡(jiǎn)單，具體不再討論2）嵌套過程語言的棧式存儲(chǔ)分配嵌套過程語言：允許過程嵌套，如pascal,PL/0。AR中必須有一些內(nèi)容，用于解決對(duì)非局部變量的引用問題“嵌套層次”，或稱層數(shù)。主程序?yàn)?,過程S在層數(shù)為i的過程R定義，則S層數(shù)為i+1一個(gè)過程可以引用包圍它的任一外層過程所定義的變量，解決方法很多，常見的方法：雙指針方法和Display表方法雙指針方法簡(jiǎn)單直接，但當(dāng)嵌套層次較多時(shí)，對(duì)非局部量的訪問效率較低！Display表方法效率較高，實(shí)現(xiàn)略復(fù)雜對(duì)于PL/0的編譯程序，采用的是雙指針方法PL/0數(shù)據(jù)動(dòng)態(tài)存儲(chǔ)采用的技術(shù)措施編譯時(shí)為每一變量名、過程名和程序段確定一個(gè)反映靜態(tài)嵌套深度的級(jí)別level調(diào)用一個(gè)過程時(shí)，把他的活動(dòng)記錄壓入運(yùn)行時(shí)的棧頂，返回時(shí)彈出相應(yīng)的活動(dòng)記錄?；顒?dòng)記錄包括：靜態(tài)鏈接SL：指向定義該過程的直接外層過程的活動(dòng)記錄的基地址，以確保變量的正確存取動(dòng)態(tài)鏈接DL：指向調(diào)用該過程前正在運(yùn)行的那個(gè)過程的活動(dòng)紀(jì)錄的基地址，以確保能返回到調(diào)用過程段返回地址RA：保存該被調(diào)用過程返回后的地址，也就是調(diào)用過程指令的下一條指令的地址為過程局部變量預(yù)留的存儲(chǔ)單元所有運(yùn)算操作都從棧頂找到它的操作數(shù)，并以計(jì)算結(jié)果代之編譯原理實(shí)踐

--目標(biāo)計(jì)算機(jī)及其解釋程序當(dāng)前任務(wù)：將PL/0源程序翻譯成為目標(biāo)代碼程序通常先將源程序翻譯成一種中間代碼程序，然后再對(duì)中間代碼程序進(jìn)行處理將中間代碼程序翻譯成某一種計(jì)算機(jī)的匯編指令程序，由該計(jì)算機(jī)的匯編程序?qū)ι傻膮R編指令程序匯編，獲得可以在該計(jì)算機(jī)上執(zhí)行的目標(biāo)程序編寫一個(gè)獨(dú)立的解釋程序，解釋執(zhí)行生成的中間代碼程序PL/0編譯程序不僅完成通常的詞法分析、語法分析，而且還產(chǎn)生中間代碼和“目標(biāo)”代碼。最終我們要“運(yùn)行”該目標(biāo)碼。為了不致陷入與本課程無關(guān)的實(shí)際機(jī)器的特有性質(zhì)的考慮中去，我們假想有臺(tái)適合PL/0程序運(yùn)行的計(jì)算機(jī)，我們稱之為PL/0處理機(jī)。PL/0處理機(jī)順序解釋生成的目標(biāo)代碼，我們稱之為解釋程序。注意：這里的假設(shè)與我們的編譯概念并不矛盾，在本課程中我們寫的只是一個(gè)示范性的編譯程序，它的后端無法完整地實(shí)現(xiàn)，因而只能在一個(gè)解釋性的環(huán)境下予以模擬。從另一個(gè)角度上講，把解釋程序就看成是PL/0機(jī)硬件，把解釋執(zhí)行看成是PL/0的硬件執(zhí)行，那么我們所做的工作：由PL/0源語言程序到PL/0機(jī)器指令的變換，就是一個(gè)完整的編譯程序。目標(biāo)計(jì)算機(jī)的組織結(jié)構(gòu)和指令格式數(shù)據(jù)存儲(chǔ)器的動(dòng)態(tài)存儲(chǔ)器管理目標(biāo)計(jì)算機(jī)指令系統(tǒng)及其解釋解釋程序interpret及其執(zhí)行1.目標(biāo)計(jì)算機(jī)的組織結(jié)構(gòu)和指令格式目標(biāo)計(jì)算機(jī)的組織結(jié)構(gòu)程序存儲(chǔ)器code數(shù)據(jù)存儲(chǔ)器s程序地址寄存器p地址寄存器t指令寄存器i基本地址寄存器b目標(biāo)計(jì)算機(jī)的指令結(jié)構(gòu)LIT指令，把一個(gè)常數(shù)放入棧頂LOD指令，把一個(gè)變量放入棧頂STO指令，從棧頂把數(shù)放入一個(gè)變量單元里CAL指令，調(diào)用一個(gè)過程INT指令，預(yù)留數(shù)據(jù)存儲(chǔ)位置JMP指令，無條件轉(zhuǎn)移JPC指令，有條件轉(zhuǎn)移OPR一組算術(shù)和關(guān)系運(yùn)算指令PL/0計(jì)算機(jī)的指令格式FLAINT———常量LIT———常量LOD層次差數(shù)據(jù)地址STO層次差數(shù)據(jù)地址CAL層次差程序地址JMP———程序地址JPC———程序地址OPR———運(yùn)算類別層次差為變量名或過程名引用和聲明之間的靜態(tài)層次差別，程序地址為目標(biāo)數(shù)組code的下標(biāo)，數(shù)據(jù)地址為變量在局部存貯中的相對(duì)地址PL/0的編譯程序?yàn)槊恳粭lPL/0源程序的可執(zhí)行語句生成后綴式目標(biāo)代碼。這種代碼生成方式對(duì)于表達(dá)式、賦值語句、過程調(diào)用等的翻譯較簡(jiǎn)單如賦值語句X:=YopZ（op為某個(gè)運(yùn)算符），將被翻譯成下面的目標(biāo)代碼序列：（設(shè)指令計(jì)數(shù)從第100號(hào)開始）100LODLevel_diff_Y,Addr_Y101LODLevel_diff_Z,Addr_Z102OPR0,op103STOLevel_diff_X,Addr_X2.數(shù)據(jù)存儲(chǔ)器的動(dòng)態(tài)存儲(chǔ)器管理每一個(gè)PL/0過程可能含有局部變量。過程可以遞歸調(diào)用，每次遞歸調(diào)用，被調(diào)用過程又要求有自己的局部變量，因此不可能在編譯時(shí)就為局部變量確定好固定的存儲(chǔ)位置。只能在每次執(zhí)行過程調(diào)用時(shí)才為過程的一組局部變量確定相應(yīng)的存儲(chǔ)位置。過程一結(jié)束，存儲(chǔ)位置又被釋放。后進(jìn)先出—lastinfirstout按照棧的原理來管理數(shù)據(jù)存儲(chǔ)器數(shù)據(jù)動(dòng)態(tài)存儲(chǔ)分析在調(diào)用一個(gè)過程時(shí)，先在棧頂為過程及其變量分配一些位置，叫做過程段每個(gè)過程在過程段里存放一些自己的數(shù)據(jù)，至少有被調(diào)用時(shí)的程序地址RA(返回地址)以及調(diào)用過程的段地址DL(動(dòng)態(tài)鏈接)還需要有第二個(gè)鏈，能正確反映變量存取的路線，稱為SL(靜態(tài)鏈接)地址于是由編譯程序表示為數(shù)據(jù)對(duì)l和a的形式。第一個(gè)數(shù)l表示調(diào)用者(調(diào)用程序段)與被調(diào)用變量之間的靜態(tài)級(jí)差，它等于找到變量所在段須通過的SL鏈的個(gè)數(shù)。第二個(gè)數(shù)a是位移，即變量在所在段的相對(duì)地址程序靜態(tài)級(jí)別和動(dòng)態(tài)存儲(chǔ)分配編譯程序在編譯過程中能為程序的每一個(gè)變量名、過程名以及程序段分配一個(gè)靜態(tài)嵌套深度，或者說靜態(tài)級(jí)別調(diào)用語句被翻譯成call,a，其中a是被調(diào)用代碼程序在程序存儲(chǔ)器的開始地址，l是調(diào)用程序段的級(jí)與被調(diào)用過程的級(jí)之差函數(shù)base(l)數(shù)據(jù)動(dòng)態(tài)存儲(chǔ)采用的技術(shù)措施編譯時(shí)為每一變量名、過程名和程序段確定一個(gè)反映靜態(tài)嵌套深度的級(jí)別level采用數(shù)據(jù)棧的管