1、第八章 源程序的中間形式8.1 波蘭表示8.2 N元表示8.3 抽象機代碼18.1 波蘭表示 一般編譯程序都生成中間代碼，然后再生成目標代碼。主要優點是可移植（與具體目標程序無關），且易于目標代碼優化。 中間代碼有多種形式： 波蘭表示 N元表示 抽象機代碼 波蘭表示算術表達式： F * 3.1416 * R * ( H + R )轉換成如波蘭表示：F 3.1416 * R * H R + *2由中綴表達式翻譯為波蘭表示算法很容易實現可以構造一個類似于算符優先分析法的算法，設立一個操作符棧。當讀到操作數時，就立即輸出該操作數；當遇到操作符時，則要與棧頂操作符比較優先級，若棧頂操作符優先級高于棧外

2、，則輸出該棧頂操作符；反之，則棧外操作符入棧。對于賦值語句，則需規定賦值符號的優先級低于其它操作符，所以：賦值語句的波蘭表示 A := F * 3.1416 * R * ( H + R ) A F 3.1416 * R * H R + * :=3算法： 設一個操作符棧；當讀到操作數時，立即輸出該操作數，當掃描到操作符時，與棧頂操作符比較優先級，若棧頂操作符優先級高于棧外，則輸出該棧頂操作符；反之，則棧外操作符入棧。#a+b#ab+#優先級最低操作符棧由中綴表達式翻譯為波蘭表示算法很容易實現可以構造一個類似于算符優先分析法的算法，設立一個操作符棧。4* ( H + R ) F 3.1416 *

3、R *轉換算法波蘭表示算術表達式： F * 3.1416 * R * ( H + R )波蘭表示： F3.1416 * R * HR + *操作符棧 輸入 輸出 F * 3.1416 * R * ( H + R ) * 3.1416 * R * ( H + R ) F* 3.1416 * R * ( H + R ) F * * R * ( H + R ) F 3.1416 * R * ( H + R ) F 3.1416 * * ( H + R ) F 3.1416 * R*( H + R ) F 3.1416 * R *( + R ) F 3.1416 * R * H*( ) F 3.141

4、6 * R * HR F 3.1416 * R * HR*5波蘭表示法的優點：在不使用括號的情況下可以無二義地說明算術表達式。波蘭表示法更容易轉換成機器的匯編語言或機器語言。 操作數出現在緊靠操作符的左邊，而操作符在波蘭表示中的順序即為進行計算的順序。波蘭表示不僅能用來作為算術表達式的中間代碼形式，而且也能作為其它語言結構的中間代碼形式。6if 語句的波蘭表示 有如下 if 語句：if then else 波蘭表示為 ： BZ BRBZ：二目操作符，如果的計算結果為0 (false)，則產生一個的轉移，而label1是的頭一個符號。BR：一目操作符，它產生一個的轉移，而是一個緊跟在后面的符號（

5、即 if語句后的第一個語句的頭一個符號）。label1label27由 if 語句的波蘭表示可生成如下的目標程序框架：其它語言結構也很容易將其翻譯成波蘭表示，但使用波蘭表示優化不是十分方便。波蘭表示為 ： BZ BRBZ label1BR label2label1：label2：計算表達式值若值為零無條件轉移語句組1語句組2YN88.2 N元表示 在該表示中，每條指令由 n 個域所組成，通常第一個域表示操作符，其余為操作數。常用的 n 元表示是： 三元式 四元式三元式操作符 左操作數 右操作數表達式的三元式：w * x + ( y + z )(1) * , w , x(2) + , y , z

6、(3) + , (1) , (2) 第三個三元式中的操作數(1) (2)表示第(1)和第(2)條三元式的計算結果。9條件語句的三元式：If x y then z := x; else z := y + 1; , x , yBMZ , (1) , (5):= , Z , XBR , , (7)+ , Y , 1:= , Z , (5) : :其中：BMZ：是二元操作符，測試第二個域的值。若0，則按第3個域的地址轉移，若為正值則該指令作廢。BR：一元操作符，按第3個域作無條件轉移。z := y + 110 使用三元式也不便于代碼優化，因為優化要刪除一些三元式，或對某些三元式的位置要進行變更，由于三

7、元式的結果（表示為編號），可以是某個三元式的操作數，隨著三元式位置的變更也將作相應的修改，很費事！間接三元式：為了便于在三元式上作優化處理，可使用間接三元式。11例： A := B + C * D / E F := C * D用直接三元式表示為：(1) * , C , D(2) / , (1) , E(3) + , B ,(2) (4) := , A ,(3)(5) * , C , D (6) := , F , (5)(1) * , C , D(2) / , (1) , E(3) + , B ,(2) (4) := , A ,(3)(5) := , F , (1)優化12用間接三元式表示為：

8、操作 三元式 1. (1) (1) * , C , D 2. (2) (2) / , (1) , E 3. (3)(3) + , B ,(2) 4. (4) (4) := , A ,(3) 5. (1) (5) := , F , (1) 6. (5) 三元式的執行次序用另一張表表示，這樣在優化時（三元式位置的變更實際是執行順序的變化），三元式可以不變，而僅僅改變其執行順序表。將執行順序和三元式編號分離13四元式表示操作符 操作數1 操作數2 結果結果：通常是編譯時分配的臨時變量，可由編譯程序分配一個寄存器或主存單元。例: ( A + B ) * ( C + D ) - E+, A, B, T1

9、+, C, D, T2*, T1, T2, T3, T3, E, T4其中T1T4為臨時變量。用四元式優化比較方便148.3 抽象機代碼 許多Pascal編譯系統生成的中間代碼是一種稱為Pcode的抽象代碼。Pcode的“P”即“Pseudo”。 既然是“抽象機”，就是表示它并不是實際的物理目標機器而通常是虛擬的一臺“堆棧計算機”。該堆棧式計算機主要由若干寄存器、一個保存程序指令的儲存器和一個堆棧式數據及操作存儲組成。15寄存器有：1. PC 程序計數器。2. NP New指針，指向“堆”的頂部。“堆”用來存放由NEW生成的動態數據。3. SP 運行棧指針，存放所有可按源程序的數據聲明直接尋址

10、的數據。4. BP 基地址指針，即指向當前活動記錄的起始位置指針。5. 其他（如MP棧標志指針，EP極限棧指針等）16計算機的存儲大致情況如下：Pcode指令PC程序指令存儲器NPSPBP當前模塊活動記錄(數據段)棧底運行棧堆堆底常量區17 運行P code的抽象機沒有專門的運算器或累加器，所有的運算（操作）都在運行棧的棧頂進行，如要進行d := ( a + b ) * c的運算，生成P code序列為：棧底：運行棧a單元b單元c單元d單元ba棧頂：SP取a LOD a取b LOD b+ ADD取c LOD c* MUL送d STO dPcode實際上是波蘭表示形式的中間代碼。18 編譯程序生

11、成P code指令程序后，我們可以用一個解釋執行程序（interpreter）來解釋執行P code ，當然也可以把P code再變成某一機器的目標代碼。 顯然，生成抽象機P code的編譯程序是很容易移植的。作業：P175 1，2，419補充：中間代碼生成實例翻譯成后綴式begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;end20begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k :=

12、 i 2 j 2; i:= 0;end12345678910111213141516計算表達式值若值為零無條件轉移語句組1語句組2NY21begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;end123k100:=計算表達式值若值為零無條件轉移語句組1語句組2NY2212345678k100:=kij+begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;

13、endL標號計算表達式值若值為零無條件轉移語句組1語句組2NY2312345678910k100:=kij+?jezbegin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;end1abel1L標號計算表達式值若值為零無條件轉移語句組1語句組2NY2412345678910k100:=kij+0jezbegin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;endL

14、標號無法確定的地址先填入0。一旦地址確定 “回填”之！計算表達式值若值為零無條件轉移語句組1語句組2NY25123456789101112131415k100:=kij+0jezkk1-:=begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;endL標號計算表達式值若值為零無條件轉移語句組1語句組2NY2612345678910111213141516k100:=kij+0jezkk1-:=417jbegin k := 100;L: if k i + j then begi

15、n k := k 1; goto L; end else k := i 2 j 2; i:= 0;endL標號計算表達式值若值為零無條件轉移語句組1語句組2NY2712345678910111213141516k100:=kij+0jezkk1-:=4171819j?jbegin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;end1abel2計算表達式值若值為零無條件轉移語句組1語句組2NY2812345678910111213141516k100:=kij+20jezkk1-

16、:=4171819202122232425262728j0jki2j2-:=begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;end1abel1計算表達式值若值為零無條件轉移語句組1語句組2NY2912345678910111213141516k100:=kij+20jezkk1-:=417181920212223242526272829303132j29jki2j2-:=i0:=begin k := 100;L: if k i + j then begin k := k 1; goto L; end else k := i 2 j 2; i:= 0;end1