編譯原理實踐

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

目標程序區：用來存放目標代碼。2）

靜態數據區：用來存放編譯時就能確定存儲空間的數據。3）

運行棧區：用來存放運行時才能確定存儲空間的數據。4）

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

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

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