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

語法制導(dǎo)翻譯和中間代碼生成第1頁，課件共27頁，創(chuàng)作于2023年2月使用中間語言的好處：復(fù)雜性界于源語言和目標(biāo)語言之間便于進行與機器無關(guān)的代碼優(yōu)化工作易于移植使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確源語言程序目標(biāo)語言程序中間語言程序CompilerFrontEndCompilerBackEnd---->編譯程序---->

輸入

輸出

第2頁，課件共27頁，創(chuàng)作于2023年2月語法制導(dǎo)翻譯和中間代碼生成文法的語法制導(dǎo)定義(語義規(guī)則)和翻譯方案--語法制導(dǎo)定義-->語義分析做什么

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

第5頁，課件共27頁，創(chuàng)作于2023年2月7.1.2圖表示法圖表示法DAG-無循環(huán)有向圖抽象語法樹

第6頁，課件共27頁，創(chuàng)作于2023年2月7.1.2圖表示法無循環(huán)有向圖(簡稱DAG)對表達式中的每個子表達式，DAG中都有一個結(jié)點一個內(nèi)部結(jié)點代表一個操作符，它的孩子代表操作數(shù)在一個DAG中代表公共子表達式的結(jié)點具有多個父結(jié)點第7頁，課件共27頁，創(chuàng)作于2023年2月7.1.3三地址代碼三地址代碼x=yopz三地址代碼可以看成是抽象語法樹或DAG的一種線性表示樹與其他中間代碼的關(guān)系第8頁，課件共27頁，創(chuàng)作于2023年2月

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

請畫出語法樹和DAG

:=a+*b-cDAG:=a+*b-c抽象語法樹*b-c第9頁，課件共27頁，創(chuàng)作于2023年2月抽象語法樹對應(yīng)的代碼：t1=-c t2=b*t1

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

a=t5assigna+*buminusc抽象語法樹*buminusc第10頁，課件共27頁，創(chuàng)作于2023年2月DAG對應(yīng)的代碼：

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

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

a=t5第11頁，課件共27頁，創(chuàng)作于2023年2月作業(yè)：P2217.1第12頁，課件共27頁，創(chuàng)作于2023年2月7.3中間代碼生成

----賦值語句翻譯成三地址代碼

產(chǎn)生三地址代碼賦值語句翻譯方案填查符號表詞法分析發(fā)布出錯信息第13頁，課件共27頁，創(chuàng)作于2023年2月語法制導(dǎo)翻譯第14頁，課件共27頁，創(chuàng)作于2023年2月三地址代碼的形式：

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

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

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

表達式x:=a+b*c的三元式：

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

標(biāo)識符a，b，c，x分別表示它們的存儲位置，序號(1)、(2)、(3)分別是它們在三元式表中的位置。

■

第15頁，課件共27頁，創(chuàng)作于2023年2月三地址代碼的形式：

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

四地址碼：result

:=arg1oparg2例4.5表達式x:=a+b*c的四元式：

(1)(*，b，c,T1) (2)(+，a，T1,T2) (3)(:=，x，T2)第16頁，課件共27頁，創(chuàng)作于2023年2月屬性文法是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號配備若干相關(guān)的“值”，稱為屬性，屬性與變量一樣可以進行計算和傳遞，屬性加工的過程即是語義處理的過程。對文法的每個產(chǎn)生式配備的一組屬性的計算規(guī)則，叫語義規(guī)則，語義分析和中間代碼的產(chǎn)生就是根據(jù)該規(guī)則進行的，在自上而下或自下而上語法分析過程中，在適當(dāng)?shù)臅r候進行屬性的計算，或其它語義動作（如查填符號表、產(chǎn)生中間代碼、發(fā)布出錯信息）就可進行語法制導(dǎo)翻譯得到中間代碼，這就是語法制導(dǎo)翻譯的基本思想。語法制導(dǎo)翻譯和中間代碼產(chǎn)生第17頁，課件共27頁，創(chuàng)作于2023年2月產(chǎn)生賦值語句抽象語法樹的屬性文法產(chǎn)生式 語義規(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)第18頁，課件共27頁，創(chuàng)作于2023年2月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()}

分別生成三元式代碼、四元式代碼第19頁，課件共27頁，創(chuàng)作于2023年2月.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)生式與語義規(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的三元式三元式序列：第20頁，課件共27頁，創(chuàng)作于2023年2月語義規(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)第21頁，課件共27頁，創(chuàng)作于2023年2月屬性文法是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號配備若干相關(guān)的“值”，稱為屬性，屬性與變量一樣可以進行計算和傳遞，屬性加工的過程即是語義處理的過程。對文法的每個產(chǎn)生式配備的一組屬性的計算規(guī)則，叫語義規(guī)則，語義分析和中間代碼的產(chǎn)生就是根據(jù)該規(guī)則進行的，在自上而下或自下而上語法分析過程中，在適當(dāng)?shù)臅r候進行屬性的計算，或其它語義動作（如查填符號表、產(chǎn)生中間代碼、發(fā)布出錯信息）就可進行語法制導(dǎo)翻譯得到中間代碼，這就是語法制導(dǎo)翻譯的基本思想。語法制導(dǎo)翻譯和中間代碼產(chǎn)生第22頁，課件共27頁，創(chuàng)作于2023年2月LR分析翻譯方案的設(shè)計

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

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

對于表達式：5+3當(dāng)歸約為左部E時，同時也得到了值8。第23頁，課件共27頁，創(chuàng)作于2023年2月產(chǎn)生式算術(shù)表達式（語義規(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： 表示存放運算結(jié)果的變量；函數(shù)newtemp()：返回一個新的臨時變量，如t1，t2，...等；過程emit(result，’=’，arg1，op，arg2)：

生成一個3地址指令。第24頁，課件共27頁，創(chuàng)作于2023年2月步驟棧內(nèi)容當(dāng)前輸入移進-規(guī)約動作翻譯動作（語義規(guī)則具體化）A1#0i1*i2+i3#移進：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#移進：s75#0T2*7i2+i3#移進：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#移進：s610#0E1+6i3#移進：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翻譯動作（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第25頁，課件共27頁，創(chuàng)作于2023年2月步驟棧內(nèi)容當(dāng)前輸入移進-規(guī)約動作翻譯動作B1#0i1*i2+i3#移進：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#移進：s75#0T2*7i2+i3#移進：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#移進：s610#0E1+6i3#移進：s511#0E1