1、高級語言及其語法描述高級語言及其語法描述引論引論詞法分析詞法分析語法分析語法分析語法分析語法分析自下而上自下而上屬性文法和語法制導翻譯屬性文法和語法制導翻譯1 12 23 34 45 56 6語義分析與中間代碼產生語義分析與中間代碼產生符號表符號表運行時存儲空間組織運行時存儲空間組織優化優化目標代碼生成目標代碼生成7 78 89 9101011111. 編譯模型的最后一個階段，以源程序的中編譯模型的最后一個階段，以源程序的中間代碼作為輸入，以所產生的等價的目標間代碼作為輸入，以所產生的等價的目標程序作為輸出。代碼生成器的輸入包括中程序作為輸出。代碼生成器的輸入包括中間代碼及符號表中的信息。間代

2、碼及符號表中的信息。2. 目標代碼的形式：目標代碼的形式：共有三種共有三種絕對機器代碼待裝配機器代碼匯編語言代碼3. 代碼生成需要著重考慮的兩個問題：代碼生成需要著重考慮的兩個問題： 如何使生成的目標代碼較短； 如何充分利用計算機的寄存器，減少目標代碼中訪問存儲單元的次數。這兩個問題都直接影響目標程序的執行速度代碼生成器的設計細節依賴于目標語言和操作系統：內存管理、寄存器管理等。其一般問題主要有：中間代碼表示可采用不同的形式：中間代碼表示可采用不同的形式： 線性表示法如后綴式線性表示法如后綴式 三地址表示法如四元式；三地址表示法如四元式； 抽象機表示法如棧式機器代碼；抽象機表示法如棧式機器代碼

3、； 圖表示法如語法樹。圖表示法如語法樹。1. 代碼生成器的輸入代碼生成器的輸入中間代碼的表示及中間代碼的表示及符號表中的信息符號表中的信息符號表登記了說明語句中說明的各種名字的種屬、類型等信息，根據這些信息可確定名字在所屬過程的數據區域中的相對地址，因此，代碼生成器可以利用這些信息來決定在中間代碼中的名字所指示的數據對象的運行時地址，它是可再定位的或絕對地址。2. 目標程序輸出的形式目標程序輸出的形式共有三種絕對機器代碼可立即執行待裝配機器代碼連接與裝入需一定代價，但靈活匯編語言代碼匯編器再加工3. 指令選擇指令選擇 指令集的一致性和完全性是重要因素。如果目標機器不能支持指令集的所有類型，則每

4、一種例外都需要特別的處理； 指令速度和機器用語也是重要因素。如果不考慮效率，則指令選擇可以直接做，對每種類型的中間代碼，可勾劃出其框架，例：對中間代碼x:=y+z 可翻譯成：LD R0, yADD R0, zST R0, x 生成代碼的質量取決于它的速度和大小。一個有著豐富的目標指令集的機器可以為一個給定的操作提供幾種實現方法，有些實現正確但不一定是高效的。例：如果目標機器有“加1”指令INC，則用INC a實現a:=a+1是最有效的，而不是下列指令序列：LD R0, aADD R0, #1ST R0, a4. 寄存器分配寄存器分配由于指令對寄存器的操作常常要比對存儲單元的操作快且指令短，因此

5、，如何充分利用寄存器，對于生成好的代碼非常重要。(1) 在寄存器分配期間，為程序的某一點選擇駐留在寄存器中的一組變量；(2) 在隨后的寄存器指派階段，挑出變量將要駐留的具體寄存器，選擇最優的寄存器指派方案是困難的，屬于NP完全問題。5. 計算順序選擇計算順序選擇6. 最重要的評價標準最重要的評價標準產生正確的代碼在此前提下，使設計的代碼生成器能夠易于實現、測試及維護，這也是重要的設計目標。計算完成的順序會影響目標代碼的有效性。要設計一個好的代碼生成器，必須預先熟悉目標機器和它的指令系統。如果用簡單代碼產生器依次把一條條中間代碼翻譯為目標代碼，可能會使目標代碼中包含冗余的指令或出現不太優的結構。

6、在目標代碼這一級上，可以借助一種簡單但有效的技術改進代碼質量，這就是窺孔優化(peephole optimization)窺孔優化方法是通過考察一小段目標指令(稱為窺孔)并把這些指令替換為更短和更快的一級指令，從而提高目標代碼的質量。窺孔是目標程序中的一個可移動的小窗口，窺孔中的代碼不一定是相鄰的，窺孔優化的一個特點是：優化后新產生的結果可能會給后面的優化提供進一步的機會。為了得到最大的優化效果，有時需要對目標代碼進行若干遍的處理。1. 冗余存取冗余存取(1) ST R0, A(2) LD R0, A因為指令(1)的執行能夠保證A的值在R0中，故可刪除指令(2)。如果(2)帶有標號，則不能保證

7、(2)一定是緊接著(1)執行的，此時不能刪除(2)，如果(1)和(2)在同一基本塊中，則這種變換一定是安全的。2. 不可達代碼不可達代碼在無條件跳轉指令之后的無標號指令應該刪除，因為它是永遠不會到達的。這種操作可以重復，刪除一序列指令。 例：例：出于調試目的，有源代碼：define debug 0中間代碼if debug=1 goto L1if (debug) goto L2 打印調試信息 L1：打印調試信息 L2：初步優化后if debug 1 goto L2打印調試信息L2：現在，既然在程序開始時已把debug置為0，因此debug 1, 所以上述程序段相當于goto L2打印調試信息 不可達代碼，可刪除L2：3. 控制流優化控制流優化中間代碼生成時，可能會產生連續跳轉的情況，這些不必要的連續跳轉在窺孔優化時可刪除，例：goto L1L1：goto L2goto L2L1：goto L2現在，如果沒有別的語句跳到L1，則如果L1:goto L2是緊跟在一個無條件語句之后，就可把它刪除。goto L1L1：if ab goto L2L3：if ab goto L2goto L3L3：如果只有一條指令如果只有一條指令跳向跳向L1且且L1緊跟在緊跟在一無條件指令后一無條件指令后還有：4. 強度削弱強度削弱有些指令可以用花費時間更短的指