編譯原理第八章

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

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

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

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

第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成

8．1屬性文法8．2語(yǔ)法制導(dǎo)翻譯概論

8．3中間代碼的形式

8．4簡(jiǎn)單賦值語(yǔ)句的翻譯

8．5布爾表達(dá)式的翻譯

8．6控制結(jié)構(gòu)的翻譯8．7說(shuō)明語(yǔ)句的翻譯

8．8數(shù)組和結(jié)構(gòu)的翻譯

8．1屬性文法

屬性文法：語(yǔ)法制導(dǎo)翻譯工具，說(shuō)明程序設(shè)計(jì)語(yǔ)言的意義。屬性文法構(gòu)成：上下文無(wú)關(guān)文法+語(yǔ)義規(guī)則語(yǔ)義規(guī)則附在文法的產(chǎn)生式上，在語(yǔ)法分析過(guò)程中，完成附加在所使用產(chǎn)生式上的語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。

定義：

一個(gè)屬性文法是一個(gè)三元組：

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

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

例如G：E→T1+T2|T1orT2

T→num|true|false

屬性文法記號(hào)中常使用N．t的形式表示與非終結(jié)符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}可進(jìn)行類型檢查的屬性文法（表達(dá)式）

對(duì)輸入串3+4的語(yǔ)法樹(shù)：

E{T1．t=T2．t}

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

4+

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

A為屬性文法例8.2

描述說(shuō)明語(yǔ)句中各種變量的類型信息的語(yǔ)義規(guī)則產(chǎn)生式語(yǔ)義規(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)要解決的問(wèn)題：紀(jì)錄標(biāo)識(shí)符的類型類型信息傳遞方法：用T.type記錄類型信息，并傳給L.inentryid的屬性：可以是它在符號(hào)表中的地址addtype在符號(hào)表中為變量填加類型信息8．2語(yǔ)法制導(dǎo)翻譯概論

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

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

例算術(shù)表達(dá)式求值的語(yǔ)義描述

（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,語(yǔ)義處理是計(jì)算表達(dá)式的值，采用LR分析法，LR分析表如下：

LR分析表如下?tīng)顟B(tài)ACITON（動(dòng)作）GOTO（轉(zhuǎn)換）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)棧語(yǔ)義棧（值棧）符號(hào)棧剩余輸入串歸約動(dòng)作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)棧語(yǔ)義棧（值棧）符號(hào)棧剩余輸入串歸約動(dòng)作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接受

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

8．3中間代碼的形式

中間代碼有多種形式，常見(jiàn)的有逆波蘭式三元式四元式

樹(shù)形表示

一、逆波蘭記號(hào)

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

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

如GOTOL寫(xiě)為L(zhǎng)jumpifEthenS1else

S2

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

二、三元式和樹(shù)形表示

組成：（OP，ARG1，ARG2）OP為算符，ARG1和ARG2分別為第一、第二運(yùn)算對(duì)象。

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

（1）

（*，b，c）（2）

（/，c，d）（3）

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

三元式中的（1）、（2）表示第一和第二個(gè)三元式的結(jié)果。

對(duì)一元運(yùn)算符，規(guī)定只用ARG1。

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

e1+e2+T1T2*T1T2-T1e1*e2

-e1二目運(yùn)算對(duì)應(yīng)二叉子樹(shù)，多目運(yùn)算對(duì)應(yīng)多叉子樹(shù)。

三、四元式

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

RESULT是運(yùn)算結(jié)果。

有時(shí)為了直觀，也把四元式的形式寫(xiě)成簡(jiǎn)單賦值形式，例如把上述四元式寫(xiě)成：

（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）

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

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

8．4簡(jiǎn)單賦值語(yǔ)句的翻譯

說(shuō)明：

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

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

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

（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}

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

帶類型轉(zhuǎn)換的語(yǔ)義處理如下：（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；}

語(yǔ)義值的設(shè)計(jì)是與語(yǔ)義處理的描述相關(guān)的，如非終結(jié)符E，有語(yǔ)義值E．place、E．type或E．kind（見(jiàn)PL/0編譯程序）

8．5布爾表達(dá)式的翻譯

在程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式的作用有兩個(gè)：一是用作邏輯賦值語(yǔ)句的邏輯運(yùn)算，二是用作控制語(yǔ)句中的條件表達(dá)式。

布爾表達(dá)式的形式為：E1ropE2，E1和E2是算術(shù)表達(dá)式，rop是關(guān)系符=、〈=、>=、〈、〉、≠。為簡(jiǎn)單起見(jiàn)，只考慮如下文法生成的布爾表達(dá)式：

E→EandE|EorE|notE|idropid|true|false布爾運(yùn)算符的優(yōu)先順序?yàn)椋簄ot、and、or，并且and和or服從左結(jié)合。一、布爾表達(dá)式的翻譯方法

計(jì)算布爾表達(dá)式的值有兩種辦法：

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

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

若按第一種方法計(jì)算布爾表達(dá)式，

aorbandnotc翻譯成四元式為：

（1）

t1：=notc（2）

t2：=bandt1（3）t3：=aort2

對(duì)于a〈b這樣的關(guān)系表達(dá)式，可看成等價(jià)的條件語(yǔ)句:ifa〈bthen1else0，翻譯成的四元式序列為：

（1）

ifa〈bgoto（4）（2）

t：=0（3）

goto（5）（4）

t：=1（5）…

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

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

nextstat：給出輸出序列中下一四元式序號(hào)；

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’）}二、控制語(yǔ)句中布爾表達(dá)式的翻譯討論出現(xiàn)在if-then；if–then-else和while-do等語(yǔ)句中的布爾表達(dá)式E的翻譯語(yǔ)法：

S→ifEthenS1|ifEthenS1elseS2

|whileEdoS1

begin：out：假假假真真真E的代碼E的代碼E的代碼S1的代碼S1的代碼S1的代碼S2的代碼jumpoutjumpbeginifEthenS1ifEthenS1elseS2whileEdoS1控制語(yǔ)句的代碼結(jié)構(gòu)

作為條件轉(zhuǎn)移的E，僅把E翻譯成條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移的四元式。翻譯的基本思路是：

對(duì)于E為aropb的形式，生成代碼為：

ifaropbgotoE.true和

gotoE.false對(duì)于E為E1orE2

的形式，若E1為真，則E為真，即E1的真出口和E的真出口一樣。若E1為假則需計(jì)算E2，E1的假出口應(yīng)是E2代碼的第一個(gè)四元式標(biāo)號(hào)，E2的真出口和假出口分別與E的真出口和假出口一樣。

E為E1andE2

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

對(duì)于notE1的翻譯，E的真假出口是E1的假真出口。

例8.3

布爾表達(dá)式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）是不需要的，這種問(wèn)題可在代碼優(yōu)化階段解決。

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

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

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

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

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

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

（10）…gotoE.true（20）…gotoE.true（30）…gotoE.true（10）…goto（0）（20）…goto（10）（30）…goto（20）其中鏈?zhǔn)诪椋?0），鏈尾為（10），0為鏈尾標(biāo)志。則鏈成:使用：E.true和E.false：分別表示“真”鏈和“假”鏈nextstat：下一四元式地址emit：輸出四元式merge（p1,p2）：合并p1、p2兩條鏈，即將p2的鏈尾鏈接到p1鏈?zhǔn)?，合并后p2為鏈?zhǔn)?。例：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所鏈接的每個(gè)四元式的第四區(qū)段都填為tE.codebegin：E的第一個(gè)四元式序號(hào)（語(yǔ)義值）

自下而上的分析中布爾表達(dá)式的一種翻譯方案，如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)生語(yǔ)法樹(shù)時(shí)的語(yǔ)義動(dòng)作結(jié)果“真”“假”鏈情況注釋在相應(yīng)結(jié)點(diǎ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過(guò)程：

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

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

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

E1.codebegin=100；

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

102：ifc〈dgoto—103：goto—

E2.true和E2.fa