小型編譯程序介紹第一頁，共五十八頁，2022年，8月28日9.1小型編譯程序結構 編譯程序的工作貫穿于從輸入源程序開始到輸出目標程序為止的整個過程，是非常復雜的。一般來說，整個過程可以劃分成五個階段：詞法分析、語法分析、中間代碼生成、優化和目標代碼生成。 第一階段為詞法分析。詞法分析的任務是輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個單詞符號，如保留字、標識符、常數、算符和界符等。第二頁，共五十八頁，2022年，8月28日 第二階段為語法分析。語法分析的任務是在詞法分析的基礎上，根據語言的語法規則(文法規則)把單詞符號串分解成各類語法單位(語法范疇)，如“短語”、“子句”、“句子”、“程序段”和“程序”。通過語法分析確定整個輸入串是否構成一個語法上正確的“程序”。 第三階段為中間代碼產生。按語言的語義將語法分析出來的語法單位翻譯成中間代碼。一般而言，中間代碼是一種獨立于具體硬件的記號系統，但它與計算機的指令形式有某種程度的接近，或者能夠比較容易地把它變換成計算機的機器指令。常用的中間代碼有四元式、三元式、間接三元式和逆波蘭記號等。第三頁，共五十八頁，2022年，8月28日圖9-1編譯程序結構示意第四頁，共五十八頁，2022年，8月28日 第四階段為優化。優化的任務在于對前階段產生的中間代碼進行加工變換，以期在最后階段能產生出更為高效(節省時間和空間)的目標代碼。 第五階段為目標代碼生成。這一階段的任務是把中間代碼(或經優化處理之后)變換成特定機器上的絕對指令代碼或可重新定位的指令代碼或匯編指令代碼。這一階段實現了最后的翻譯，它的工作有賴于硬件系統結構和機器指令含義。第五頁，共五十八頁，2022年，8月28日 上述編譯過程的五個階段是編譯程序工作時的動態特征，編譯程序的結構可以按照這五個階段的任務分模塊進行設計。編譯程序的結構示意如圖9-1所示。 我們設計的小型編譯程序包含除優化以外的其余各階段。第六頁，共五十八頁，2022年，8月28日9.2小型編譯程序關于高級語言的規定 高級語言程序具有四種基本結構：順序結構﹑選擇結構﹑循環結構和過程。為了便于掌握編譯的核心內容，突出重點，簡化編譯程序的結構，同時又涵蓋高級語言程序的基本結構，我們選取賦值語句﹑if語句和while語句作為前三種結構的代表，略去了過程結構。實際上，上述三種語句已經基本滿足了高級語言的程序設計。因此，我們僅考慮由下面產生式所定義的程序語句：

第七頁，共五十八頁，2022年，8月28日

S→ifBthenSelseS︱whileBdoS︱beginLend︱A L→S;L︱S A→i:=E B→B∧B︱B∨B︱?

B︱(B)︱iropi︱i E→E+E︱E*E︱(E)︱i第八頁，共五十八頁，2022年，8月28日 其中，各非終結符的含義如下：

S——語句；

L——語句串；

A——賦值句；

B——布爾表達式；

E——算術表達式。第九頁，共五十八頁，2022年，8月28日 各終結符的含義如下：

i?——整型變量或常數，布爾變量或常數；

rop?——六種關系運算符的代表；

;?——起語句分隔符作用；

:=?——賦值符號；

?

——邏輯非運算符“not”；∧?——邏輯與運算符“and”；第十頁，共五十八頁，2022年，8月28日 ∨?——邏輯或運算符“or”；

+?——算術加運算符； *?——算術乘運算符；

(?——左括號；

)?——右括號。 注意，六種關系運算符分別為

<：小于<=：小于等于<>：不等于

>：大于>=：大于等于=：等于第十一頁，共五十八頁，2022年，8月28日 關于表達式的運算，我們規定由高到低優先順序為算術運算、關系運算、布爾運算；并且服叢左結合規則。算術運算符優先級的順序依次為“()”﹑“*”﹑“+”；布爾運算符優先級的順序依次為“?

”﹑“∧”﹑“∨”；六個關系運算符優先級相同。 我們規定的程序是由一條語句或由begin和end嵌套起來的復合語句組成的，并且規定在語句末要加上“#~”表示程序結束。下面給出的是符合規定的程序示例：

begin A:=A+B*C; C:=A+2;第十二頁，共五十八頁，2022年，8月28日

whileA<CandB<DdowhileA>BdoifM=NthenC:=DelsewhileA<=DdoA:=D end#~第十三頁，共五十八頁，2022年，8月28日9.3小型編譯程序關于單詞的內部定義

由于我們規定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯誤的檢查，而將編譯程序的重點放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規定輸出的單詞符號格式為如下的二元式：

(單詞種別，單詞自身的值)

我們對常量，變量，臨時變量，保留關鍵字(if、while、begin、end、else、then、do等)，關系運算符，邏輯運算符，分號，括號等，規定其內部定義如表9-1所示。

第十四頁，共五十八頁，2022年，8月28日表9-1關于單詞的內部定義

第十五頁，共五十八頁，2022年，8月28日9.4小型編譯程序的LR分析表

1.算術表達式的LR分析表 算術表達式文法G[E]如下：

E->E+E︱E*E︱(E)︱I

將文法G[E]拓廣為文法G′[E]：(0)S′→E(1)E→E+E(2)E→E*E(3)E→(E)(4)E→i

由此得到算術表達式的SLR(1)分析表如表9-2所示。第十六頁，共五十八頁，2022年，8月28日表9-2算術表達式的SLR(1)分析表

第十七頁，共五十八頁，2022年，8月28日

2．

布爾表達式的LR分析表 布爾表達式的文法如下：

B->B∧B︱B∨B︱?

B︱iropi︱I

為了便于語法分析時的加工處理，我們將上述文法改寫為文法G[S]：

B→BAB︱BOB︱?

B︱(B)︱iropi︱iBA→B∧BO→B∨第十八頁，共五十八頁，2022年，8月28日 將文法G[S]拓廣為文法G[S′]：(0)S′→B ???(1)B→I ??(2)B→iropi?? ?(3)B→(B)??? (4)B→NOTB??? (5)A→BAND? ??(6)B→AB?? ?(7)O→BOR?? ?(8)B→OB

由此得到布爾表達式的SLR(1)分析表如表9-3所示。

第十九頁，共五十八頁，2022年，8月28日表9-3布爾表達式的SLR分析表

第二十頁，共五十八頁，2022年，8月28日

3.程序語句的LR分析表 程序語句的文法G[S]如下：

S→ifethenSelseS︱whileedoS︱beginLend︱aL→S;L︱S

由于在編譯程序設計與實現中，我們是將賦值語句與算術表達式歸為一類處理的，故在此將賦值語句僅看作為程序語句文法中的一個終結符a，將布爾表達式B也看作為終結符e。將文法G[S]拓廣為文法G[S′]：(0)S′→S第二十一頁，共五十八頁，2022年，8月28日

(1)S→ifethenSelseS(2)S→whileedoS(3)S→beginLend(4)S→a(5)L→S(6)L→S;L

由此得到程序語句的SLR(1)分析表如表9-4所示。第二十二頁，共五十八頁，2022年，8月28日表9-4程序語句的SLR分析表

第二十三頁，共五十八頁，2022年，8月28日9.5小型編譯程序執行過程 小型編譯程序執行分兩個階段：第一個階段，將高級語言源程序翻譯成四元式程序；第二個階段，將四元式程序翻譯成匯編語言目標程序。執行過程示意如圖9-2所示。

第二十四頁，共五十八頁，2022年，8月28日圖9-2執行過程示意

第二十五頁，共五十八頁，2022年，8月28日 下例為一個名為PAS.DAT的高級語言源程序經過PAS的編譯，產生名為PAS.MED的四元式(中間代碼)程序；PAS.MED經過COMPILER編譯生成8086/8088匯編語言目標程序PAS.ASM。

/*******************************************/ /*pas.dat*/ /*高級語言源程序?*/ /******************************************/第二十六頁，共五十八頁，2022年，8月28日

while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end # ~第二十七頁，共五十八頁，2022年，8月28日

/*******************************************/ /*pas.med*/ /*高級語言生成的四元式文件?*/ /******************************************/

100 (j> ,a ,b ,102 ) 101 (j , , ,117 ) 102 (j>= ,m ,n ,104 ) 103 (j , , ,107 ) 104 (+ ,a ,1 ,T1 )第二十八頁，共五十八頁，2022年，8月28日

105 (:= ,T1 , ,a )

106 (j , , ,112 )

107 (j= ,k ,h ,109 )

108 (j , , ,112 )

109 (+ ,x ,2 ,T2 )

110 (:= ,T2 , ,x ) 111 (j , , ,107 )第二十九頁，共五十八頁，2022年，8月28日

112 (+ ,m ,y ,T3 ) 113 (* ,x ,T3 ,T4 ) 114 (+ ,n ,T4 ,T5 ) 115 (:= ,T5 , ,m ) 116 (j , , ,100 )

/*******************************************/ /*pas.asm*/第三十頁，共五十八頁，2022年，8月28日

/*由四元式文件生成的匯編文件*/ /******************************************/

datasegment ;定義數據段

h DW k DW m DW n DW x DW y DW a DW b DW第三十一頁，共五十八頁，2022年，8月28日

dataends ;數據段定義結束

;************************************** codesegment ;定義代碼段

mainprocfar ;程序的執行部分

assumecs:code,ds:data start: ;為返回操作系統入棧

pushds subbx,bx pushbx第三十二頁，共五十八頁，2022年，8月28日

;設置DS段為當前數據段

movbx,data movds,bx 100: movAX,a ;把條件跳轉指令的第一操作數讀入寄存器

cmpAX,b ;把條件跳轉指令的第一操作數和第二操作數相減

jg102 ;大于則跳轉

101: jmp117 ;產生直接跳轉指令第三十三頁，共五十八頁，2022年，8月28日

102: movAX,m ;把條件跳轉指令的第一操作數讀入寄存器

cmpAX,n ;把條件跳轉指令的第一操作數和第二操作數相減

jge104 ;大于或等于則跳轉

103: jmp107;產生直接跳轉指令

104:

movAX,a ;把在存儲器中的被加數賦給結果寄存器

addAX,1D;把被加數和加數立即數相加第三十四頁，共五十八頁，2022年，8月28日

105: movBX,AX ;執行賦值語句，寄存器中的值賦給結果變量

mova,BX ;在跳出基本塊之前保存寄存器中已改變的變量

106: jmp112 ;產生直接跳轉指令

107: movAX,k ;把條件跳轉指令的第一操作數讀入寄存器

cmpAX,h ;把條件跳轉指令的第一操作數和第二操作數相減

je109 ;相等則跳轉第三十五頁，共五十八頁，2022年，8月28日

108: jmp112 ;產生直接跳轉指令

109: movAX,x ;把在存儲器中的被加數賦給結果寄存器

addAX,2D ;把被加數和加數立即數相加

110: movBX,AX ;執行賦值語句，寄存器中的值賦給結果變量

movx,BX ;在跳出基本塊之前保存寄存器中已改變的變量第三十六頁，共五十八頁，2022年，8月28日

111:jmp107 ;產生直接跳轉指令

112:movAX,m ;把在存儲器中的被加數賦給結果寄存器

addAX,y ;把被加數和在存儲器中的加數相加

113:mulx ;把被乘數和在存儲器中的乘數相乘第三十七頁，共五十八頁，2022年，8月28日

114: movBX,n ;把在存儲器中的被加數賦給結果寄存器

addBX,AX ;把被加數和在寄存器中的加數相加

115: movCX,BX ;執行賦值語句，寄存器中的值賦給結果變量

movm,CX ;在跳出基本塊之前保存寄存器中已改變的變量

116:jmp100 ;產生直接跳轉指令第三十八頁，共五十八頁，2022年，8月28日

117: ret mainendp codeends ;代碼段定義結束

endstart第三十九頁，共五十八頁，2022年，8月28日9.6小型編譯程序運行實例分析 我們以高級語言源程序到四元式的翻譯為例對其進行分析。待編譯的PAS.DAT源程序如下：

while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end#~第四十頁，共五十八頁，2022年，8月28日 經編譯程序運行后得到的輸出結果如下： *******詞法分析結果*******/*注釋：查單詞內部定義和下面的變量名表*/ 3 0/*(sy_while,0)*/ 48 0/*(″(″,0)*/ 56 0/*(變量,a)*/ 42 3/*(rop,″>″)*/ 561/*(變量,b)*/ 490/*(″)″,0)*/第四十一頁，共五十八頁，2022年，8月28日

5 0/*(sy_do,0)*/4 0/*(sy_begin,0)*/0 0/*(sy_if,0)*/56 2/*(變量,m)*/42 2/*(rop,″>=″)*/56 3/*(變量,n)*/1 0/*(sy_then,0)*/56 0/*(變量,a)*/第四十二頁，共五十八頁，2022年，8月28日

38 0/*(″:=″,0)*/56 0/*(變量,a)*/34 0/*(″+″,0)*/56 1/*(整常量,1)*/2 0/*(sy_else,0)*/3 0/*(sy_while,0)*/56 4/*(變量,k)*/第四十三頁，共五十八頁，2022年，8月28日

pressanykeytocontinue42 5/*(rop,″=″)*/56 5/*(變量,n)*/5 0/*(sy_do,0)*/56 6/*(變量,x)*/38 0/*(″:=″,0)*/56 6/*(變量,x)*/第四十四頁，共五十八頁，2022年，8月28日

34 0/*(″+″,0)*/57 2/*(整常量,2)*/8 0/*(″;″,0)*/56 2/*(變量,m)*/38 0/*(″:=″,0)*/56 3/*(變量,n)*/34 0/*(″+″,0)*/第四十五頁，共五十八頁，2022年，8月28日

56 6/*(變量,x)*/36 0/*(″*″,0)*/48 0/*(″c″,c)*/56 2/*(變量,m)*/34 0/*(″+″,0)*/56 7/*(變量,y)*/49 0/*(″)″,0)*/6 0/*(sy_end,0)*/10 0/*(″#″,0)*/第四十六頁，共五十八頁，2022年，8月28日

程序總共9行，產生了43個二元式！*****************變量名表*****************

0 a1

b2

m3

n4

k5

h6

x7

y第四十七頁，共五十八頁，2022年，8月28日 *********狀態棧分析過程及歸約順序***************

stack[0]=0 n=3 lr=3 stack[1]=3 n=9 lr=7 stack[2]=7 n=5 lr=11 stack[3]=11 n=4 lr=4 stack[4]=4 n=0 lr=2 stack[5]=2 n=9 lr=6 stack[6]=6 n=1 lr=10 stack[7]=10 n=7 lr=5第四十八頁，共五十八頁，2022年，8月28日

stack[8]=5 n=2 lr=104 s->a歸約

stack[7]=10 n=11 lr=14 stack[8]=14 n=2 lr=17 stack[9]=17 n=3 lr=3 stack[10]=3 n=9 lr=7 stack[11]=7 n=5 lr=11 stack[12]=11 n=7 lr=5 stack[13]=5 n=8 lr=104第四十九頁，共五十八頁，2022年，8月28日

s->a歸約

stack[12]=11 n=11 lr=15 stack[13]=15 n=8 lr=102 s->whileedos歸約

stack[9]=17 n=11 lr=18 stack[10]=18 n=8 lr=101第五十頁，共五十八頁，2022年，8月28日

s->ifethenselses歸約

stack[4]=4 n=11 lr=9 stack[5]=9 n=8 lr=13 stack[6]=13 n=7 lr=5 stack[7]=5 n=6 lr=104 s->a歸約

stack[6]=13 n=11 lr=9 stack[7]=9 n=6 lr=105第五十一頁，共五十八頁，2022年，8月28日

L->s歸約

stack[6]=13 n=12 lr=16 stack[7]=16 n=6 lr=106 L->S;L歸約

stack[4]=4 n=12 lr=8 stack[5]=8 n=6 lr=12 stack[6]=12 n=10 lr=103 s->beginLend歸約

stack[3]=11 n=11 lr=15 stack[4]=15 n=10 lr=102第五十二頁，共五十八頁，2022年，8月28日

s->whileedos歸約

stack[0]=0 n=11 lr=1 stack[1]=1 n=10 lr=-2

************四元式分析結果***************** ********************************************

100(j>, a, b, 102 ) 101(j, , , 117 )第五十三頁，共五十八頁，2022