編譯原理第八章

第八章語法制導翻譯和中間代碼生成源程序的結構分析詞法分析ch4語法分析ch5、ch6、ch7語義分析由語法分析程序直接調(diào)用相應的語義子程序首先生成語法樹（或該結構的某種表示），再進行語義處理生成中間代碼編譯中的邏輯階段源語言程序代碼優(yōu)化目標代碼（匯編或機器碼）詞法分析語義分析語法分析中間代碼生成目標代碼生成前端處理后端處理語義處理語義處理的任務：靜態(tài)語義檢查靜態(tài)語義：語法結構

靜態(tài)語義檢查：審查靜態(tài)語義動態(tài)語義處理動態(tài)語義：程序單元執(zhí)行的操作

動態(tài)語義處理：生成(中間/目標)代碼語義處理的實現(xiàn)：屬性文法：描述語義規(guī)則。--工具語法制導翻譯：在語法分析的同時，執(zhí)行語義規(guī)則描述的動作：檢查靜態(tài)語義生成中間代碼/目標代碼語義處理的環(huán)境：符號表為語義分析提供類型、作用域等信息。為代碼生成提供類型、作用域、存儲類別、存儲（相對）位置等信息。

本章引入屬性文法和語法制導翻譯方法的基本思想，介紹幾種典型的中間代碼形式，最后討論一些語法成分的翻譯工作。

第8章語法制導翻譯和中間代碼生成

8．1屬性文法8．2語法制導翻譯概論

8．3中間代碼的形式

8．4簡單賦值語句的翻譯

8．5布爾表達式的翻譯

8．6控制結構的翻譯8．7說明語句的翻譯

8．8數(shù)組和結構的翻譯

8．1屬性文法

屬性文法：語法制導翻譯工具，說明程序設計語言的意義。屬性文法構成：上下文無關文法+語義規(guī)則語義規(guī)則附在文法的產(chǎn)生式上，在語法分析過程中，完成附加在所使用產(chǎn)生式上的語義規(guī)則描述的動作，從而實現(xiàn)語義處理。

定義：

一個屬性文法是一個三元組：

A=（G，V，F(xiàn)）其中:G：上下文無關文法V：屬性的有窮集。每個屬性與文法的某個非終結符或終結符相聯(lián)F：關于屬性的斷言或謂詞的有窮集。

--屬性的計算規(guī)則每個斷言與文法的某產(chǎn)生式相聯(lián)。

例如G：E→T1+T2|T1orT2

T→num|true|false

屬性文法記號中常使用N．t的形式表示與非終結符N相聯(lián)的屬性。E→T1+T2{T1．t=intANDT2．t=int}E→T1orT2{T1．t=boolANDT2．t=bool}T→num{T．t=int}T→true{T．t=bool}T→false{T．t=bool}可進行類型檢查的屬性文法（表達式）

對輸入串3+4的語法樹：

E{T1．t=T2．t}

{T1．=int}TT{T2．=int}3

4+

如果對G中的某一輸入串而言，A中的所有斷言對該輸入串的語法樹的結點的屬性全為真，則該串也是A語言中的句子。編譯程序的靜態(tài)語義審查工作就是驗證關于所編譯的程序的斷言是否全部為真。

A為屬性文法例8.2

描述說明語句中各種變量的類型信息的語義規(guī)則產(chǎn)生式語義規(guī)則(1)DTLL.in:=T.type(2)TintT.type:=integer(3)TrealT.type:=real(4)LL1,idL1.in:=L.in;addtype(id.entry,L.in)(5)Lidaddtype(id.entry,L.in)要解決的問題：紀錄標識符的類型類型信息傳遞方法：用T.type記錄類型信息，并傳給L.inentryid的屬性：可以是它在符號表中的地址addtype在符號表中為變量填加類型信息8．2語法制導翻譯概論

語法制導翻譯：首先，使用屬性文法為工具，描述程序設計語言的語義規(guī)則。在語法分析時，每應用一個產(chǎn)生式（推導或歸約），同時完成該產(chǎn)生式上所附的語義規(guī)則描述的動作，從而完成語義處理。在進行語法分析的同時，完成相應的語義處理

語法制導翻譯的具體實現(xiàn)途徑不難。如有一個LR分析器，擴充它的分析棧，使得每個文法符號都跟有語義值。同時擴充LR分析器功能，使它不僅執(zhí)行語法分析任務，且能在用某個產(chǎn)生式進行歸約的同時調(diào)用相應語義子程序。

例算術表達式求值的語義描述

（0）L→Eprint（E.val)（1）E→E1+T

E.val:=E1.val+T.val（2）E→TE.val:=T.val（3）T→T1*FT.val:=T1.val*F.val（4）T→FT.val:=F.val（5）F→（E）F.val:=E.val（6）F→digitF.val:=digit.lexval

輸入串2+3*5,語義處理是計算表達式的值，采用LR分析法，LR分析表如下：

LR分析表如下狀態(tài)ACITON（動作）GOTO（轉換）d+*（）#ETF0S5

S4

1231

S6

acc

2

r2S7

r2r2

3

r4r4

r4r4

4S5

S4

8235

r6r6

r6r6

6S5

S4

937S5

S4

108

S6

S11

9

r1S7

r1r1

10

r3r3

r3r3

11

r5r5

r5r5

LR分析輸入串2+3*5步驟狀態(tài)棧語義棧（值棧）符號棧剩余輸入串歸約動作10-#2+3*5#205--#2+3*5#303-2#F+3*5#

r6402-2#T+3*5#r4501-2#E+3*5#r26016-2-#E+3*5#70165-2--#E+3*5#

步驟狀態(tài)棧語義棧（值棧）符號棧剩余輸入串歸約動作80163-2-3#E+F*5#r690169-2-3#E+T*5#r41001697-2-3-#E+T*5#11016975-2-3--#E+T*5#1201697（10）-2-3-5#E+T*F#r6130169-2-（15）#E+T#r31401-（17）

#E#

r115接受

按照上述實現(xiàn)辦法，若把語義子程序改為產(chǎn)生中間代碼的動作，則可在語法制導下生成中間代碼。（選作實驗）

8．3中間代碼的形式

中間代碼有多種形式，常見的有逆波蘭式三元式四元式

樹形表示

一、逆波蘭記號

最簡單的一種中間代碼形式。將運算對象寫在前面，運算符號寫在后面如a+b寫成ab+，也稱后綴式。后綴表示法表示表達式的最大優(yōu)點是計算機處理表達式方便。如B@CD*+（@表示一元減，中綴表示為-B+C*D）

逆波蘭表示很容易擴充到表達式以外的范圍，只要遵守運算對象后直接跟它們的運算符這條規(guī)則即可。

如GOTOL寫為LjumpifEthenS1else

S2

表示為ES1S2￥，把if-then-else看成三目運算符，用￥表示。但要注意，要對新添加的運算符的含義正確處理。

二、三元式和樹形表示

組成：（OP，ARG1，ARG2）OP為算符，ARG1和ARG2分別為第一、第二運算對象。

如：a：=b*c+c/d表示為：

（1）

（*，b，c）（2）

（/，c，d）（3）

（+，（1），（2））（4）（：=，（3），a）

三元式中的（1）、（2）表示第一和第二個三元式的結果。

對一元運算符，規(guī)定只用ARG1。

樹形表示是三元式的翻版。表達式的樹形表示很容易實現(xiàn)：簡單變量或常數(shù)的樹是自身，如果表達式e1和e2的樹分別為T1和T2，那么e1+e2、e1*e2，-e1的樹為：

e1+e2+T1T2*T1T2-T1e1*e2

-e1二目運算對應二叉子樹，多目運算對應多叉子樹。

三、四元式

普遍采用的一種中間代碼形式。組成：（OP，ARG1，ARG2，RESULT）其中:OP，ARG1，ARG2的含義同三元式

RESULT是運算結果。

有時為了直觀，也把四元式的形式寫成簡單賦值形式，例如把上述四元式寫成：

（1）t1：=b*c（2）t2：=c/d（3）t3：=t1+t2（4）a：=t3

如，a：=b*c+c/d的四元式表示如下：

（1）（*，b，c，t1）（2）（/，c，d，t2）（3）（+，t1，t2，t3）（4）（：=，t3，-，a）

四元式和三元式的主要不同在于：四元式對中間結果的引用必須通過給定的名字，三元式是通過產(chǎn)生中間結果的三元式編號。

四元式表示類似于三地址指令，有時也把這種表示稱為三地址代碼，它對代碼優(yōu)化和目標代碼生成都較有利。

8．4簡單賦值語句的翻譯

說明：

在實際實現(xiàn)中，四元式的ARG1和ARG2、RESULT，或者是一個指針，指向符號表的某一登錄項；或者是一個臨時變量的整數(shù)碼。

語義變量id．name：id表示的單詞的一屬性語義變量E．place：表示存放E值的變量名在符號表的登錄項或一整數(shù)碼語義過程emit：表示輸出四元式到輸出文件上語義過程newtemp：表示生成一臨時變量。函數(shù)Lookup（id．name）：查id．name是否在符號表中，如在，則返回指向該登錄項指針，否則返回nil。

下面列出了翻譯賦值語句到四元式的語義描述，這里的語義工作包括對變量進行“先定義后使用”的檢查。

（1）S→id：=E{p：=Lookup（id．name）；

ifｐ≠nil

then

emit（p‘：＝’E．place）

elseerror}四元式采用賦值形式，即result：=arg1oparg2（2）E→E1+E2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘+’E2.place）

}（3）E→E1*E2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘*’E2.place）

}（4）E→-E1{E.place:=newtemp；

emit（E.place‘:=’‘uminus’E1.place）

}（5）E→（E1）

{E.place:=E1.place}（6）E→id{p:=Lookup（）；

ifp≠nil

then

E.place:=pelseerror}

編譯程序還可對表達式中的運算對象進行類型檢查、類型轉換。約定：當兩個不同類型的量進行運算時，先將整型量轉換為實型量，并增加E.type表示E的類型信息，值為int或real，用+i（*i）、+r（*r）區(qū)別整型加和實型加。

帶類型轉換的語義處理如下：（E→E1*E2）

E→E1*E2

{E.place:=newtemp；

ifE1.type=intANDE2.type=intthenbeginemit(E.place,‘:=’,E1.place,‘*i’,E2.place);

E.type:=intendelseifE1.type=realANDE2.type=realthen

beginemit(E.place,‘:=’,E1.place,‘*r’,E2.place);E.type:=realend

elseifE1．type=int/*E2．type=real*/thenbegint:=newtemp；

emit（t,‘:=’，itr，E1.place）；

emit（E.place,‘:=’，t,‘*r’,E2.place）；

E．type:=realendelse/*E1.type=realANDE2.type=int*/begint:=newtemp；

emit（t,‘:=’，itr，E2.place）

emit（E.place,‘:=’，E1.place,‘*r’，t）；

E.type:=realend；}

語義值的設計是與語義處理的描述相關的，如非終結符E，有語義值E．place、E．type或E．kind（見PL/0編譯程序）

8．5布爾表達式的翻譯

在程序設計語言中，布爾表達式的作用有兩個：一是用作邏輯賦值語句的邏輯運算，二是用作控制語句中的條件表達式。

布爾表達式的形式為：E1ropE2，E1和E2是算術表達式，rop是關系符=、〈=、>=、〈、〉、≠。為簡單起見，只考慮如下文法生成的布爾表達式：

E→EandE|EorE|notE|idropid|true|false布爾運算符的優(yōu)先順序為：not、and、or，并且and和or服從左結合。一、布爾表達式的翻譯方法

計算布爾表達式的值有兩種辦法：

第一種：同算術表達式的計算一樣，按步計算各部分的真假值，最后計算整個表達式的值。例如：1or（not0and0）or0=1or（1and0）or0=1or0or0=1or0=1采取哪種方法取決于程序設計語言的語義。

第二種：采取某種優(yōu)化措施，只計算部分表達式，如AorB，若A的值為1，則無需計算B，整個布爾表達式的值為1。同理，對于AandB，若A為0，則整個布爾表達式值為0，無需計算B。

若按第一種方法計算布爾表達式，

aorbandnotc翻譯成四元式為：

（1）

t1：=notc（2）

t2：=bandt1（3）t3：=aort2

對于a〈b這樣的關系表達式，可看成等價的條件語句:ifa〈bthen1else0，翻譯成的四元式序列為：

（1）

ifa〈bgoto（4）（2）

t：=0（3）

goto（5）（4）

t：=1（5）…

用t存放a〈b的值，（5）為后繼的四元式序號。

p182圖8.14給出了按第一種辦法計算布爾表達式的值。其中：

nextstat：給出輸出序列中下一四元式序號；

emit：輸出四元式，每調(diào)用一次，nextstat

增加1。

E→E1orE2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘or’E2.place）}E→E1andE2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘a(chǎn)nd’E2.place）}E→notE1

{E.place:=newtemp；

emit（E.place‘:=’‘not’E1.place）}E→（E1

）

{E.place:=E1.place}

E→id1relopid2

{E.place:=newtemp；

emit（‘if’id1.placerelopid2.place‘goto’nextstat+3）；

emit（E.place‘:=’‘0’）；

emit（‘goto’nextstat+2）；

emit（E.place‘:=’‘1’）；}E→true{E.place:=newtemp；

emit（E.place‘:=’‘1’）}E→false{E.place:=newtemp；

emit（E.place‘:=’‘0’）}二、控制語句中布爾表達式的翻譯討論出現(xiàn)在if-then；if–then-else和while-do等語句中的布爾表達式E的翻譯語法：

S→ifEthenS1|ifEthenS1elseS2

|whileEdoS1

begin：out：假假假真真真E的代碼E的代碼E的代碼S1的代碼S1的代碼S1的代碼S2的代碼jumpoutjumpbeginifEthenS1ifEthenS1elseS2whileEdoS1控制語句的代碼結構

作為條件轉移的E，僅把E翻譯成條件轉移和無條件轉移的四元式。翻譯的基本思路是：

對于E為aropb的形式，生成代碼為：

ifaropbgotoE.true和

gotoE.false對于E為E1orE2

的形式，若E1為真，則E為真，即E1的真出口和E的真出口一樣。若E1為假則需計算E2，E1的假出口應是E2代碼的第一個四元式標號，E2的真出口和假出口分別與E的真出口和假出口一樣。

E為E1andE2

的形式，與2)類似，只需調(diào)換E1的真假出口即可

對于notE1的翻譯，E的真假出口是E1的假真出口。

例8.3

布爾表達式a〈b

or

c〈dande〉f

翻譯成如下四元式序列：

（1）

ifa〈bgotoE.ture（2）

goto3（3）

ifc〈dgoto5（4）

gotoE.false（5）

ife〉fgotoE.true（6）gotoE.false

上述四元式（2）是不需要的，這種問題可在代碼優(yōu)化階段解決。

不是最優(yōu)語句ifa<borc<dande<fthenS1elseS2的四元式(1)ifa<bgoto(7)

//轉移至(E.true)(2)goto(3)

(3)ifc<dgoto(5)(4)goto(p+1)//轉移至(E.false)(5)ife<fgoto(7)(6)goto(p+1)(7)(S1的四元式

……(p-1)……）(p)goto

(q)(p+1)(S2的四元式……(q-1)……）(q)//轉移至(E.true)//轉移至(E.false)//(E.false)入口//(E.true)入口E.true和E.false的值不能在產(chǎn)生四元式的同時就知道，要在整個布爾表達式（或語句）的四元式產(chǎn)生完畢之后才得知，因此要回填這個地址。

為了記錄需回填地址的四元式，常采用一種拉鏈的辦法：把需回填E.true的四元式拉成一鏈，稱為“真”鏈，把需回填E.false的四元式拉成一鏈，稱為“假”鏈。若有四元式序列：

（10）…gotoE.true（20）…gotoE.true（30）…gotoE.true（10）…goto（0）（20）…goto（10）（30）…goto（20）其中鏈首為（30），鏈尾為（10），0為鏈尾標志。則鏈成:使用：E.true和E.false：分別表示“真”鏈和“假”鏈nextstat：下一四元式地址emit：輸出四元式merge（p1,p2）：合并p1、p2兩條鏈，即將p2的鏈尾鏈接到p1鏈首，合并后p2為鏈首。例：merge(p1,p2)(p10)goto(0)

……

p1鏈(p100)goto(p10)……`(p1)goto(p100)(p20)goto(0)(p1)……

p2鏈(p200)goto(p20)……(p2)goto(p200)backpatch（p，t）：把p所鏈接的每個四元式的第四區(qū)段都填為tE.codebegin：E的第一個四元式序號（語義值）

自下而上的分析中布爾表達式的一種翻譯方案，如p167圖8.13所示

（1）E→E1orE2

{backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge（E1.true,E2.true）;E.false:=E2.false；

}（2）E→E1andE2

{backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge（E1.false,E2.false）；

}

（3）E→notE1

{

E.true:=E1.false;E.codebegin:=E1.codebegin;E.false:=E1.true;}（4）E→(E1){

E.true:=E1.true;

E.codebegin:=E1.codebegin;E.false:=E1.false;}（5）E→id1relopid2

{E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(‘if’id1.place‘rop’id2.place‘goto’_);emit(‘goto’_)；

}

（6）E→true{E.true:=nextstat;E.codebegin:=nextstat;emit(‘goto’_)；

}（7）E→false{E.false:=nextstat;E.codebegin:=nextstat;emit(‘goto’_)；

}以a〈borc〈dande〈f

為例，將分析產(chǎn)生語法樹時的語義動作結果“真”“假”鏈情況注釋在相應結點處

anda〈borEE.true={104，100}E.false={105，103}E1

E.true={100}E.false={101}E4

E.true={104}E.false={105，103}E2

E.true={102}E.false={103}E3

E.true={104}E.false={105}c〈d

e〈f過程：

1）歸約a〈b到E1時，產(chǎn)生兩個四元式：

100：ifa〈bgoto—101：goto—（假定nextstat初值為100）

E1.true和E1.false分別為{100}、{101}，

E1.codebegin=100；

2）歸約c〈d到E2時，產(chǎn)生兩個四元式：

102：ifc〈dgoto—103：goto—

E2.true和E2.fa