第9章-小型編譯程序介紹課件

第九章

小型編譯程序介紹

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

9.2小型編譯程序關(guān)于高級語言的規(guī)定 高級語言程序具有7 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 S→ifBthenSelseS︱while8 其中，各非終結(jié)符的含義如下： S——語句； L——語句串； A——賦值句； B——布爾表達式； E——算術(shù)表達式。 其中，各非終結(jié)符的含義如下：9 各終結(jié)符的含義如下： i?——整型變量或常數(shù)，布爾變量或常數(shù)； rop?——六種關(guān)系運算符的代表；;?——起語句分隔符作用；:=?——賦值符號；

??——邏輯非運算符“not”；∧?——邏輯與運算符“and”； 各終結(jié)符的含義如下：10 ∨?——邏輯或運算符“or”； +?——算術(shù)加運算符； *?——算術(shù)乘運算符； (?——左括號； )?——右括號。 注意，六種關(guān)系運算符分別為 <：小于<=：小于等于<>：不等于 >：大于>=：大于等于=：等于 ∨?——邏輯或運算符“or”；11 關(guān)于表達式的運算，我們規(guī)定由高到低優(yōu)先順序為算術(shù)運算、關(guān)系運算、布爾運算；并且服叢左結(jié)合規(guī)則。算術(shù)運算符優(yōu)先級的順序依次為“()”﹑“*”﹑“+”；布爾運算符優(yōu)先級的順序依次為“??”﹑“∧”﹑“∨”；六個關(guān)系運算符優(yōu)先級相同。 我們規(guī)定的程序是由一條語句或由begin和end嵌套起來的復(fù)合語句組成的，并且規(guī)定在語句末要加上“#~”表示程序結(jié)束。下面給出的是符合規(guī)定的程序示例： begin A:=A+B*C; C:=A+2; 關(guān)于表達式的運算，我們規(guī)定由高到低優(yōu)先順序為算術(shù)運算、關(guān)12 whileA<CandB<DdowhileA>BdoifM=NthenC:=DelsewhileA<=DdoA:=D end#~ whileA<CandB<Ddo139.3小型編譯程序關(guān)于單詞的內(nèi)部定義

由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯誤的檢查，而將編譯程序的重點放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規(guī)定輸出的單詞符號格式為如下的二元式： (單詞種別，單詞自身的值) 我們對常量，變量，臨時變量，保留關(guān)鍵字(if、while、begin、end、else、then、do等)，關(guān)系運算符，邏輯運算符，分號，括號等，規(guī)定其內(nèi)部定義如表9-1所示。

9.3小型編譯程序關(guān)于單詞的內(nèi)部定義 由于我們規(guī)定的程14表9-1關(guān)于單詞的內(nèi)部定義

表9-1關(guān)于單詞的內(nèi)部定義159.4小型編譯程序的LR分析表

1.算術(shù)表達式的LR分析表 算術(shù)表達式文法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 由此得到算術(shù)表達式的SLR(1)分析表如表9-2所示。9.4小型編譯程序的LR分析表 1.算術(shù)表達式的LR16表9-2算術(shù)表達式的SLR(1)分析表

表9-2算術(shù)表達式的SLR(1)分析表17 2．

布爾表達式的LR分析表 布爾表達式的文法如下：B->B∧B︱B∨B︱??B︱iropi︱I 為了便于語法分析時的加工處理，我們將上述文法改寫為文法G[S]：B→BAB︱BOB︱??B︱(B)︱iropi︱iBA→B∧BO→B∨ 2．布爾表達式的LR分析表18 將文法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所示。

將文法G[S]拓廣為文法G[S′]：(0)S′→B19表9-3布爾表達式的SLR分析表

表9-3布爾表達式的SLR分析表20 3.程序語句的LR分析表 程序語句的文法G[S]如下：S→ifethenSelseS︱whileedoS︱beginLend︱aL→S;L︱S 由于在編譯程序設(shè)計與實現(xiàn)中，我們是將賦值語句與算術(shù)表達式歸為一類處理的，故在此將賦值語句僅看作為程序語句文法中的一個終結(jié)符a，將布爾表達式B也看作為終結(jié)符e。將文法G[S]拓廣為文法G[S′]：(0)S′→S 3.程序語句的LR分析表21 (1)S→ifethenSelseS(2)S→whileedoS(3)S→beginLend(4)S→a(5)L→S(6)L→S;L 由此得到程序語句的SLR(1)分析表如表9-4所示。 (1)S→ifethenSelseS22表9-4程序語句的SLR分析表

表9-4程序語句的SLR分析表239.5小型編譯程序執(zhí)行過程 小型編譯程序執(zhí)行分兩個階段：第一個階段，將高級語言源程序翻譯成四元式程序；第二個階段，將四元式程序翻譯成匯編語言目標(biāo)程序。執(zhí)行過程示意如圖9-2所示。

9.5小型編譯程序執(zhí)行過程 小型編譯程序執(zhí)行分兩個階段：24圖9-2執(zhí)行過程示意

圖9-2執(zhí)行過程示意25 下例為一個名為PAS.DAT的高級語言源程序經(jīng)過PAS的編譯，產(chǎn)生名為PAS.MED的四元式(中間代碼)程序；PAS.MED經(jīng)過COMPILER編譯生成8086/8088匯編語言目標(biāo)程序PAS.ASM。 /*******************************************/ /*pas.dat*/ /*高級語言源程序?*/ /******************************************/ 下例為一個名為PAS.DAT的高級語言源程序經(jīng)過PAS的26 while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end # ~ while(a>b)do27 /*******************************************/ /*pas.med*/ /*高級語言生成的四元式文件?*/ /******************************************/

100 (j> ,a ,b ,102 ) 101 (j , , ,117 ) 102 (j>= ,m ,n ,104 ) 103 (j , , ,107 ) 104 (+ ,a ,1 ,T1 ) /***************************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 ) 105 (:= ,T1 , ,a )29 112 (+ ,m ,y ,T3 ) 113 (* ,x ,T3 ,T4 ) 114 (+ ,n ,T4 ,T5 ) 115 (:= ,T5 , ,m ) 116 (j , , ,100 )

/*******************************************/ /*pas.asm*/ 112 (+ ,m ,y ,T3 )30

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

datasegment ;定義數(shù)據(jù)段 h DW k DW m DW n DW x DW y DW a DW b DW /*由四元式文件生成的匯編文件31 dataends ;數(shù)據(jù)段定義結(jié)束 ;************************************** codesegment ;定義代碼段 mainprocfar ;程序的執(zhí)行部分assumecs:code,ds:data start: ;為返回操作系統(tǒng)入棧 pushds subbx,bx pushbx dataends ;數(shù)據(jù)段定義結(jié)束32

;設(shè)置DS段為當(dāng)前數(shù)據(jù)段 movbx,data movds,bx 100: movAX,a ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器 cmpAX,b ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減 jg102 ;大于則跳轉(zhuǎn) 101: jmp117 ;產(chǎn)生直接跳轉(zhuǎn)指令 ;設(shè)置DS段為當(dāng)前數(shù)據(jù)段33 102: movAX,m ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器 cmpAX,n ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減 jge104 ;大于或等于則跳轉(zhuǎn) 103: jmp107;產(chǎn)生直接跳轉(zhuǎn)指令

104:

movAX,a ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器

addAX,1D;把被加數(shù)和加數(shù)立即數(shù)相加 102:34 105: movBX,AX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量 mova,BX ;在跳出基本塊之前保存寄存器中已改變的變量 106: jmp112 ;產(chǎn)生直接跳轉(zhuǎn)指令 107: movAX,k ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器 cmpAX,h ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減 je109 ;相等則跳轉(zhuǎn) 105:35 108: jmp112 ;產(chǎn)生直接跳轉(zhuǎn)指令 109: movAX,x ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器 addAX,2D ;把被加數(shù)和加數(shù)立即數(shù)相加 110: movBX,AX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量 movx,BX ;在跳出基本塊之前保存寄存器中已改變的變量 108: 36 111:jmp107 ;產(chǎn)生直接跳轉(zhuǎn)指令 112:movAX,m ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器addAX,y ;把被加數(shù)和在存儲器中的加數(shù)相加 113:mulx ;把被乘數(shù)和在存儲器中的乘數(shù)相乘 111:37 114: movBX,n ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器addBX,AX ;把被加數(shù)和在寄存器中的加數(shù)相加 115: movCX,BX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量 movm,CX ;在跳出基本塊之前保存寄存器中已改變的變量 116:jmp100 ;產(chǎn)生直接跳轉(zhuǎn)指令 114:38 117: ret mainendp codeends ;代碼段定義結(jié)束 endstart 117:399.6小型編譯程序運行實例分析 我們以高級語言源程序到四元式的翻譯為例對其進行分析。待編譯的PAS.DAT源程序如下： while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end#~9.6小型編譯程序運行實例分析 我們以高級語言源程序到40 經(jīng)編譯程序運行后得到的輸出結(jié)果如下： *******詞法分析結(jié)果*******/*注釋：查單詞內(nèi)部定義和下面的變量名表*/ 3 0/*(sy_while,0)*/ 48 0/*(″(″,0)*/ 56 0/*(變量,a)*/ 42 3/*(rop,″>″)*/ 561/*(變量,b)*/ 490/*(″)″,0)*/ 經(jīng)編譯程序運行后得到的輸出結(jié)果如下：41 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)*/ 5 042 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)*/ 38 043 pressanykeytocontinue42 5/*(rop,″=″)*/56 5/*(變量,n)*/5 0/*(sy_do,0)*/56 6/*(變量,x)*/38 0/*(″:=″,0)*/56 6/*(變量,x)*/ pressanykeytocontinue44 34 0/*(″+″,0)*/57 2/*(整常量,2)*/8 0/*(″;″,0)*/56 2/*(變量,m)*/38 0/*(″:=″,0)*/56 3/*(變量,n)*/34 0/*(″+″,0)*/ 34 045 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)*/ 56 646

程序總共9行，產(chǎn)生了43個二元式！*****************變量名表*****************0 a1

b2

m3

n4

k5

h6

x7

y 程序總共9行，產(chǎn)生了43個二元式！47 *********狀態(tài)棧分析過程及歸約順序***************

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 *********狀態(tài)棧分析過程及歸約順序********48 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 stack[8]=5 n=249 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 s->a歸約50 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 s->ifethenselses歸約51 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 L->s歸約52 s->whileedos歸約 stack[0]=0 n=11 lr=1 stack[1]=1 n=10 lr=-2

************四元式分析結(jié)果***************** ******************************************** 100(j>, a, b, 102 ) 101(j, , , 117 ) s->whileedos歸約53 102(j>=, m, n, 104 ) 103(j, , , 107 ) 104(+, a, 1, T1 ) 105(:=, T1, , a ) 106(j, , , 112 ) 107(j=, k, h, 109 ) 108(j, , , 112 ) 109(+, x, 2, T2 ) 102(j>=, m,54 110(:=, T2, , x ) 111(j, , , 107 ) 112(+, m, y, T3 ) 113(*, x, T3, T4 ) 114(+, n, T4, T5 ) 115(:=, T5, , m ) 116(j, , , 100 ) ******************************************** 110(:=, T2,55 程序運行結(jié)束！ 注意，狀態(tài)棧分析過程及歸約順序顯示所給出的是程序語句分析使用狀態(tài)棧STACK加工分析的過程，而對算術(shù)表達式和布爾表達式使用的狀態(tài)棧STACK的加工分析過程則沒有顯示(主要是考慮顯示的內(nèi)容過多)。因此，在程序語句分析中，當(dāng)處理到賦值語句(它與算術(shù)表達式一同處理)和布爾表達式時，其處理過程是不顯示的，它在程序語句分析中只顯示出已加工處理后的終結(jié)符號a(代表賦值語句)和e(代表布爾表達式)。 程序運行結(jié)束！56 在狀態(tài)棧分析過程及歸約順序顯示中，STACK棧由棧底到當(dāng)前棧頂顯示了根據(jù)程序語句LR分析表(見表9-4)加工分析的所有狀態(tài)，而LR欄則是根據(jù)當(dāng)前掃描的單詞符號(由n所指)在分析表對應(yīng)的下一狀態(tài)(小于100為移進狀態(tài)，大于等于100為歸約狀態(tài))。我們?nèi)园碙R分析表控制下的翻譯格式給出狀態(tài)棧STACK信息所對應(yīng)的符號棧內(nèi)容，這些符號棧內(nèi)容可以由狀態(tài)棧STACK中的信息和LR分析表分析推出。分析的結(jié)果見表9-5(狀態(tài)棧STACK內(nèi)容由豎向改為橫向)。 在狀態(tài)棧分析過程及歸約順序顯示中，STACK棧由棧底到當(dāng)57表9-5狀態(tài)棧分析加工過程表9-5狀態(tài)棧分析加工過程58第九章

小型編譯程序介紹

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

9.2小型編譯程序關(guān)于高級語言的規(guī)定 高級語言程序具有65 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 S→ifBthenSelseS︱while66 其中，各非終結(jié)符的含義如下： S——語句； L——語句串； A——賦值句； B——布爾表達式； E——算術(shù)表達式。 其中，各非終結(jié)符的含義如下：67 各終結(jié)符的含義如下： i?——整型變量或常數(shù)，布爾變量或常數(shù)； rop?——六種關(guān)系運算符的代表；;?——起語句分隔符作用；:=?——賦值符號；

??——邏輯非運算符“not”；∧?——邏輯與運算符“and”； 各終結(jié)符的含義如下：68 ∨?——邏輯或運算符“or”； +?——算術(shù)加運算符； *?——算術(shù)乘運算符； (?——左括號； )?——右括號。 注意，六種關(guān)系運算符分別為 <：小于<=：小于等于<>：不等于 >：大于>=：大于等于=：等于 ∨?——邏輯或運算符“or”；69 關(guān)于表達式的運算，我們規(guī)定由高到低優(yōu)先順序為算術(shù)運算、關(guān)系運算、布爾運算；并且服叢左結(jié)合規(guī)則。算術(shù)運算符優(yōu)先級的順序依次為“()”﹑“*”﹑“+”；布爾運算符優(yōu)先級的順序依次為“??”﹑“∧”﹑“∨”；六個關(guān)系運算符優(yōu)先級相同。 我們規(guī)定的程序是由一條語句或由begin和end嵌套起來的復(fù)合語句組成的，并且規(guī)定在語句末要加上“#~”表示程序結(jié)束。下面給出的是符合規(guī)定的程序示例： begin A:=A+B*C; C:=A+2; 關(guān)于表達式的運算，我們規(guī)定由高到低優(yōu)先順序為算術(shù)運算、關(guān)70 whileA<CandB<DdowhileA>BdoifM=NthenC:=DelsewhileA<=DdoA:=D end#~ whileA<CandB<Ddo719.3小型編譯程序關(guān)于單詞的內(nèi)部定義

由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯誤的檢查，而將編譯程序的重點放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規(guī)定輸出的單詞符號格式為如下的二元式： (單詞種別，單詞自身的值) 我們對常量，變量，臨時變量，保留關(guān)鍵字(if、while、begin、end、else、then、do等)，關(guān)系運算符，邏輯運算符，分號，括號等，規(guī)定其內(nèi)部定義如表9-1所示。

9.3小型編譯程序關(guān)于單詞的內(nèi)部定義 由于我們規(guī)定的程72表9-1關(guān)于單詞的內(nèi)部定義

表9-1關(guān)于單詞的內(nèi)部定義739.4小型編譯程序的LR分析表

1.算術(shù)表達式的LR分析表 算術(shù)表達式文法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 由此得到算術(shù)表達式的SLR(1)分析表如表9-2所示。9.4小型編譯程序的LR分析表 1.算術(shù)表達式的LR74表9-2算術(shù)表達式的SLR(1)分析表

表9-2算術(shù)表達式的SLR(1)分析表75 2．

布爾表達式的LR分析表 布爾表達式的文法如下：B->B∧B︱B∨B︱??B︱iropi︱I 為了便于語法分析時的加工處理，我們將上述文法改寫為文法G[S]：B→BAB︱BOB︱??B︱(B)︱iropi︱iBA→B∧BO→B∨ 2．布爾表達式的LR分析表76 將文法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所示。

將文法G[S]拓廣為文法G[S′]：(0)S′→B77表9-3布爾表達式的SLR分析表

表9-3布爾表達式的SLR分析表78 3.程序語句的LR分析表 程序語句的文法G[S]如下：S→ifethenSelseS︱whileedoS︱beginLend︱aL→S;L︱S 由于在編譯程序設(shè)計與實現(xiàn)中，我們是將賦值語句與算術(shù)表達式歸為一類處理的，故在此將賦值語句僅看作為程序語句文法中的一個終結(jié)符a，將布爾表達式B也看作為終結(jié)符e。將文法G[S]拓廣為文法G[S′]：(0)S′→S 3.程序語句的LR分析表79 (1)S→ifethenSelseS(2)S→whileedoS(3)S→beginLend(4)S→a(5)L→S(6)L→S;L 由此得到程序語句的SLR(1)分析表如表9-4所示。 (1)S→ifethenSelseS80表9-4程序語句的SLR分析表

表9-4程序語句的SLR分析表819.5小型編譯程序執(zhí)行過程 小型編譯程序執(zhí)行分兩個階段：第一個階段，將高級語言源程序翻譯成四元式程序；第二個階段，將四元式程序翻譯成匯編語言目標(biāo)程序。執(zhí)行過程示意如圖9-2所示。

9.5小型編譯程序執(zhí)行過程 小型編譯程序執(zhí)行分兩個階段：82圖9-2執(zhí)行過程示意

圖9-2執(zhí)行過程示意83 下例為一個名為PAS.DAT的高級語言源程序經(jīng)過PAS的編譯，產(chǎn)生名為PAS.MED的四元式(中間代碼)程序；PAS.MED經(jīng)過COMPILER編譯生成8086/8088匯編語言目標(biāo)程序PAS.ASM。 /*******************************************/ /*pas.dat*/ /*高級語言源程序?*/ /******************************************/ 下例為一個名為PAS.DAT的高級語言源程序經(jīng)過PAS的84 while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end # ~ while(a>b)do85 /*******************************************/ /*pas.med*/ /*高級語言生成的四元式文件?*/ /******************************************/

100 (j> ,a ,b ,102 ) 101 (j , , ,117 ) 102 (j>= ,m ,n ,104 ) 103 (j , , ,107 ) 104 (+ ,a ,1 ,T1 ) /***************************86 105 (:= ,T1 , ,a )

106 (j , , ,112 )

107 (j= ,k ,h ,109 )

108 (j , , ,112 )

109 (+ ,x ,2 ,T2 )

110 (:= ,T2 , ,x ) 111 (j , , ,107 ) 105 (:= ,T1 , ,a )87 112 (+ ,m ,y ,T3 ) 113 (* ,x ,T3 ,T4 ) 114 (+ ,n ,T4 ,T5 ) 115 (:= ,T5 , ,m ) 116 (j , , ,100 )

/*******************************************/ /*pas.asm*/ 112 (+ ,m ,y ,T3 )88

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

datasegment ;定義數(shù)據(jù)段 h DW k DW m DW n DW x DW y DW a DW b DW /*由四元式文件生成的匯編文件89 dataends ;數(shù)據(jù)段定義結(jié)束 ;************************************** codesegment ;定義代碼段 mainprocfar ;程序的執(zhí)行部分assumecs:code,ds:data start: ;為返回操作系統(tǒng)入棧 pushds subbx,bx pushbx dataends ;數(shù)據(jù)段定義結(jié)束90

;設(shè)置DS段為當(dāng)前數(shù)據(jù)段 movbx,data movds,bx 100: movAX,a ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器 cmpAX,b ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減 jg102 ;大于則跳轉(zhuǎn) 101: jmp117 ;產(chǎn)生直接跳轉(zhuǎn)指令 ;設(shè)置DS段為當(dāng)前數(shù)據(jù)段91 102: movAX,m ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器 cmpAX,n ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減 jge104 ;大于或等于則跳轉(zhuǎn) 103: jmp107;產(chǎn)生直接跳轉(zhuǎn)指令

104:

movAX,a ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器

addAX,1D;把被加數(shù)和加數(shù)立即數(shù)相加 102:92 105: movBX,AX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量 mova,BX ;在跳出基本塊之前保存寄存器中已改變的變量 106: jmp112 ;產(chǎn)生直接跳轉(zhuǎn)指令 107: movAX,k ;把條件跳轉(zhuǎn)指令的第一操作數(shù)讀入寄存器 cmpAX,h ;把條件跳轉(zhuǎn)指令的第一操作數(shù)和第二操作數(shù)相減 je109 ;相等則跳轉(zhuǎn) 105:93 108: jmp112 ;產(chǎn)生直接跳轉(zhuǎn)指令 109: movAX,x ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器 addAX,2D ;把被加數(shù)和加數(shù)立即數(shù)相加 110: movBX,AX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量 movx,BX ;在跳出基本塊之前保存寄存器中已改變的變量 108: 94 111:jmp107 ;產(chǎn)生直接跳轉(zhuǎn)指令 112:movAX,m ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器addAX,y ;把被加數(shù)和在存儲器中的加數(shù)相加 113:mulx ;把被乘數(shù)和在存儲器中的乘數(shù)相乘 111:95 114: movBX,n ;把在存儲器中的被加數(shù)賦給結(jié)果寄存器addBX,AX ;把被加數(shù)和在寄存器中的加數(shù)相加 115: movCX,BX ;執(zhí)行賦值語句，寄存器中的值賦給結(jié)果變量 movm,CX ;在跳出基本塊之前保存寄存器中已改變的變量 116:jmp100 ;產(chǎn)生直接跳轉(zhuǎn)指令 114:96 117: ret mainendp codeends ;代碼段定義結(jié)束 endstart 117:979.6小型編譯程序運行實例分析 我們以高級語言源程序到四元式的翻譯為例對其進行分析。待編譯的PAS.DAT源程序如下： while(a>b)do begin ifm>=nthena:=a+1 else whilek=hdox:=x+2; m:=n+x*(m+y) end#~9.6小型編譯程序運行實例分析 我們以高級語言源程序到98 經(jīng)編譯程序運行后得到的輸出結(jié)果如下： *******詞法分析結(jié)果*******/*注釋：查單詞內(nèi)部定義和下面的變量名表*/ 3 0/*(sy_while,0)*/ 48 0/*(″(″,0)*/ 56 0/*(變量,a)*/ 42 3/*(rop,″>″)*/ 561/*(變量,b)*/ 490/*(″)″,0)*/ 經(jīng)編譯程序運行后得到的輸出結(jié)果如下：99 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)*/ 5 0100 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)*/ 38 0101 pressanykeytocontinue42 5/*(rop,″=″)*/56 5/*(變量,n)*/5 0/*(sy_do,0)*/56 6/*(變量,x)*/38 0/*(″:=″,0)*/56 6/*(變量,x)*/ pressanykeytocontinue102 34 0/*(″+″,0)*/57 2/*(整常量,2)*/8 0/*(″;″,0)*/56 2/*(變量,m)*/38 0/*(″:=″,0)*/56 3/*(變量,n)*/34 0/*(″+″,0)*/ 34 0103 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)*/ 56 6104

程序總共9行，產(chǎn)生了43個二元式！*****************變量名表*****************0 a1

b2

m3

n4

k5

h6

x7

y 程序總共9行，產(chǎn)生了43