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

使用中間語(yǔ)言的好處：復(fù)雜性界于源語(yǔ)言和目標(biāo)語(yǔ)言之間便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作易于移植使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確源語(yǔ)言程序目標(biāo)語(yǔ)言程序中間語(yǔ)言程序CompilerFrontEndCompilerBackEnd---->編譯程序---->

輸入

輸出

第一頁(yè)，共二十六頁(yè)。語(yǔ)法制導(dǎo)翻譯和中間代碼生成文法的語(yǔ)法制導(dǎo)定義(語(yǔ)義規(guī)則)和翻譯方案--語(yǔ)法制導(dǎo)定義-->語(yǔ)義分析做什么

--翻譯方案-->中間代碼生成怎么做第二頁(yè)，共二十六頁(yè)。中間語(yǔ)言高級(jí)的：接近源語(yǔ)言。語(yǔ)法樹(shù)，適合完成靜態(tài)類型檢查。低級(jí)的：接近目標(biāo)語(yǔ)言。適合完成依賴于機(jī)器的任務(wù)。常用的中間語(yǔ)言：后綴式：逆波蘭表示圖表示：DAG、抽象語(yǔ)法樹(shù)三地址代碼三元式、四元式中間代碼的選擇可以是一種實(shí)際的語(yǔ)言也可以是編譯各階段共享的內(nèi)部數(shù)據(jù)結(jié)構(gòu)7.1中間語(yǔ)言第三頁(yè)，共二十六頁(yè)。P200后綴式定義寫(xiě)出3+4*5的后綴式寫(xiě)出b*(-c)+b*(-c)的后綴式后綴式表示：算術(shù)表達(dá)式、賦值語(yǔ)句、控制語(yǔ)句后綴式的計(jì)算用一個(gè)棧實(shí)現(xiàn)一般的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到運(yùn)算量（操作量）就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。7.1.1后綴式

第四頁(yè)，共二十六頁(yè)。7.1.2圖表示法圖表示法DAG-無(wú)循環(huán)有向圖抽象語(yǔ)法樹(shù)

第五頁(yè)，共二十六頁(yè)。7.1.2圖表示法無(wú)循環(huán)有向圖(簡(jiǎn)稱DAG)對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)第六頁(yè)，共二十六頁(yè)。7.1.3三地址代碼三地址代碼x=yopz三地址代碼可以看成是抽象語(yǔ)法樹(shù)或DAG的一種線性表示樹(shù)與其他中間代碼的關(guān)系第七頁(yè)，共二十六頁(yè)。

a:=b*(-c)+b*(-c)的圖表示法

請(qǐng)畫(huà)出語(yǔ)法樹(shù)和DAG

:=a+*b-cDAG:=a+*b-c抽象語(yǔ)法樹(shù)*b-c第八頁(yè)，共二十六頁(yè)。抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：t1=-c t2=b*t1

t3=-c t4=b*t3 t5=t2+t4

a=t5assigna+*buminusc抽象語(yǔ)法樹(shù)*buminusc第九頁(yè)，共二十六頁(yè)。DAG對(duì)應(yīng)的代碼：

t1=-ct2=b*t1t5=t2+t2a=t5assigna+*buminuscDAG抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：t1=-c t2=b*t1

t3=-c t4=b*t3 t5=t2+t4

a=t5第十頁(yè)，共二十六頁(yè)。作業(yè)：P2217.1第十一頁(yè)，共二十六頁(yè)。7.3中間代碼生成

----賦值語(yǔ)句翻譯成三地址代碼

產(chǎn)生三地址代碼賦值語(yǔ)句翻譯方案填查符號(hào)表詞法分析發(fā)布出錯(cuò)信息第十二頁(yè)，共二十六頁(yè)。語(yǔ)法制導(dǎo)翻譯第十三頁(yè)，共二十六頁(yè)。三地址代碼的形式：

1.三元式、2.四元式、3.間接三元式1、三元式

三元式：(i)(op,arg1,arg2)

三地址碼：(i):=arg1oparg2例4.5

表達(dá)式x:=a+b*c的三元式：

(1)(*，b，c) (2)(+，a，(1)) (3)(:=，x，(2))

標(biāo)識(shí)符a，b，c，x分別表示它們的存儲(chǔ)位置，序號(hào)(1)、(2)、(3)分別是它們?cè)谌奖碇械奈恢谩?/p>

■

第十四頁(yè)，共二十六頁(yè)。三地址代碼的形式：

三元式、四元式、間接三元式2、四元式四元式：(i)(op,arg1,arg2，result)

四地址碼：result

:=arg1oparg2例4.5

表達(dá)式x:=a+b*c的四元式：

(1)(*，b，c,T1) (2)(+，a，T1,T2) (3)(:=，x，T2)第十五頁(yè)，共二十六頁(yè)。屬性文法是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)配備若干相關(guān)的“值”，稱為屬性，屬性與變量一樣可以進(jìn)行計(jì)算和傳遞，屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。對(duì)文法的每個(gè)產(chǎn)生式配備的一組屬性的計(jì)算規(guī)則，叫語(yǔ)義規(guī)則，語(yǔ)義分析和中間代碼的產(chǎn)生就是根據(jù)該規(guī)則進(jìn)行的，在自上而下或自下而上語(yǔ)法分析過(guò)程中，在適當(dāng)?shù)臅r(shí)候進(jìn)行屬性的計(jì)算，或其它語(yǔ)義動(dòng)作（如查填符號(hào)表、產(chǎn)生中間代碼、發(fā)布出錯(cuò)信息）就可進(jìn)行語(yǔ)法制導(dǎo)翻譯得到中間代碼，這就是語(yǔ)法制導(dǎo)翻譯的基本思想。語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生第十六頁(yè)，共二十六頁(yè)。產(chǎn)生賦值語(yǔ)句抽象語(yǔ)法樹(shù)的屬性文法產(chǎn)生式 語(yǔ)義規(guī)則S→id:=E S.nptr:=mknode(‘a(chǎn)ssign’,

mkleaf(id,id.place),E.nptr)E→E1+E2

E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2

E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E→-E1

E.nptr:=mknode(‘uminus’,E1.nptr)E→(E1) E.nptr:=E1.nptrE→id E.nptr:=mkleaf(id,id.place)第十七頁(yè)，共二十六頁(yè)。LR分析翻譯方案產(chǎn)生式與翻譯方案A(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=trip(:=，entry()，E.code)}{E.code:=trip(+，E1.code，E2.code)}{E.code:=trip(*，E1.code，E2.code)}{E.code:=E1.code}{E.code:=trip(@，E1.code，)}{E.code:=entry()}

產(chǎn)生式與翻譯方案B

(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=newtemp;emit(:=，entry(),E.code,A.code)}{E.code:=newtemp;emit(+，E1.code,E2.code,E.code)}{E.code:=newtemp;emit(*，E1.code,E2.code,E.code)}{E.code:=E1.code}{E.code:=newtemp;emit(@,E1.code,,E.code)}{E.code:=entry()}

分別生成三元式代碼、四元式代碼第十八頁(yè)，共二十六頁(yè)。.code=a

.code=b

.code=c.code=(1)(*,b,c)

.code=(3)(:=,x,(2)).code=(2)(+,a,(1))

(1)(*,b,c)(2)(+,a,(1))(3)(:=,x,(2))產(chǎn)生式與語(yǔ)義規(guī)則A：(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=trip(:=，entry()，E.code)}{E.code:=trip(+，E1.code，E2.code)}{E.code:=trip(*，E1.code，E2.code)}{E.code:=E1.code}{E.code:=trip(@，E1.code，)}{E.code:=entry()}

例生成x:=a+b*c的三元式三元式序列：第十九頁(yè)，共二十六頁(yè)。語(yǔ)義規(guī)則B(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=newtemp;emit(:=，entry(),E.code,A.code)}{E.code:=newtemp;emit(+，E1.code,E2.code,E.code)}{E.code:=newtemp;emit(*，E1.code,E2.code,E.code)}{E.code:=E1.code}{E.code:=newtemp;emit(@,E1.code,,E.code)}{E.code:=entry()}

例生成x:=a+b*c的四元式.code=a

.code=b

.code=c.code=(1)(*,b,c)

.code=(3)(:=,x,(2)).code=(2)(+,a,(1))

(1)(*,b,c)(2)(+,a,(1))(3)(:=,x,(2))三元式序列：四元式序列：

(*,b,c，T1)(+,a,T1,T2)(:=,x,T2,T3)第二十頁(yè)，共二十六頁(yè)。屬性文法是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)配備若干相關(guān)的“值”，稱為屬性，屬性與變量一樣可以進(jìn)行計(jì)算和傳遞，屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。對(duì)文法的每個(gè)產(chǎn)生式配備的一組屬性的計(jì)算規(guī)則，叫語(yǔ)義規(guī)則，語(yǔ)義分析和中間代碼的產(chǎn)生就是根據(jù)該規(guī)則進(jìn)行的，在自上而下或自下而上語(yǔ)法分析過(guò)程中，在適當(dāng)?shù)臅r(shí)候進(jìn)行屬性的計(jì)算，或其它語(yǔ)義動(dòng)作（如查填符號(hào)表、產(chǎn)生中間代碼、發(fā)布出錯(cuò)信息）就可進(jìn)行語(yǔ)法制導(dǎo)翻譯得到中間代碼，這就是語(yǔ)法制導(dǎo)翻譯的基本思想。語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生第二十一頁(yè)，共二十六頁(yè)。LR分析翻譯方案的設(shè)計(jì)

LR分析中的語(yǔ)法制導(dǎo)翻譯實(shí)質(zhì)上是對(duì)LR語(yǔ)法分析的擴(kuò)充：<1>擴(kuò)充LR分析器的功能：當(dāng)執(zhí)行歸約產(chǎn)生式的動(dòng)作時(shí)，也執(zhí)行產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。<2>擴(kuò)充分析棧：增加一個(gè)與分析棧并列的語(yǔ)義棧，用于存放分析棧中文法符號(hào)所對(duì)應(yīng)的屬性值。例：E→E1+E2

val[top]:=val[top]+val[top+2];

對(duì)于表達(dá)式：5+3當(dāng)歸約為左部E時(shí)，同時(shí)也得到了值8。第二十二頁(yè)，共二十六頁(yè)。產(chǎn)生式算術(shù)表達(dá)式（語(yǔ)義規(guī)則）翻譯方案-三地址碼-P208(1)S→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{p=lookup(id.lexeme);if(p!-nil)emit(p,’=’

，E.place)elseerror}{E.place=newtemp();emit(E.place,’=’，E1.place,’+’，E2.place)}{E.place=newtemp();emit(E.place,’=’，E1.place,’*’，E2.place)}{……}{……}{……}

屬性.place： 表示存放運(yùn)算結(jié)果的變量；函數(shù)newtemp()：返回一個(gè)新的臨時(shí)變量，如t1，t2，...等；過(guò)程emit(result，’=’，arg1，op，arg2)：

生成一個(gè)3地址指令。第二十三頁(yè)，共二十六頁(yè)。步驟棧內(nèi)容當(dāng)前輸入移進(jìn)-規(guī)約動(dòng)作翻譯動(dòng)作（語(yǔ)義規(guī)則具體化）A1#0i1*i2+i3#移進(jìn)：s52#0i15*i2+i3#規(guī)約：r6（F→i）F.place=porF.place=entry()3#0F3*i2+i3#規(guī)約：r4（T→F）T.place=F.place4#0T2*i2+i3#移進(jìn)：s75#0T2*7i2+i3#移進(jìn)：s56#0T2*7i25+i3#規(guī)約：r6（F→i）F.place=porF.place=entry()7#0T2*7F10+i3#規(guī)約r3（T→T*F）T.place=newtemp(),emit(T.place,’=’，T.place,’*’，F(xiàn).place8#0T2+i3#規(guī)約：r2（E→T）E.place:=T.place9#0E1+i3#移進(jìn)：s610#0E1+6i3#移進(jìn)：s511#0E1+6i35#規(guī)約：r6（F→i）F.place=porF.place=entry()12#0E1+6F3#規(guī)約：r4（T→F）T.place=F.place13#0E1+6T9#規(guī)約：r1（E→E+T）E.place=newtemp();emit(E.place,’=’,E.place,’+’，T.place)}14#0E1#acc（1）t1=i1翻譯動(dòng)作（2）t1=t1（3）t2=i2（4）t3,t3=t1*t2（5）t3=t3（6）t4=i3

（7）t4=t4

（8）t5,t5=t3+t4P208,P113,P6（1）t1=i1三地址代碼（2）t1=t1（3）t2=i2（4）t3,t3=t1*t2（5）t3=t3（6）t4=i3

（7）t4=t4

（8）t5,t5=t3+t4第二十四頁(yè)，共二十六頁(yè)。步驟棧內(nèi)容當(dāng)前輸入移進(jìn)-規(guī)約動(dòng)作翻譯動(dòng)作B1#0i1*i2+i3#移進(jìn)：s52#0i15*i2+i3#規(guī)約：r6（F→i）F.code:=entry()3#0F3*i2+i3#規(guī)約：r4（T→F）T.code:=F.code4#0T2*i2+i3#移進(jìn)：s75#0T2*7i2+i3#移進(jìn)：s56#0T2*7i25+i3#規(guī)約：r6（F→i）F.code:=entry()7#0T2*7F10+i3#規(guī)約：r3（T→T*F）T.code:=newtemp,emit(*,T.code,F.code,T.code)8#0T2+i3#規(guī)約：r2（E→T）E.code:=T.code9#0E1+i3#移進(jìn)：s610#0E1+6i3#移進(jìn)：s511#0E1+6i35#規(guī)約：r6（F