語法制導(dǎo)翻譯和中間代碼生成詳解演示文稿

語法制導(dǎo)翻譯和中間代碼生成詳解演示文稿第一頁，共二十五頁。（優(yōu)選）語法制導(dǎo)翻譯和中間代碼生成第二頁，共二十五頁。語法制導(dǎo)翻譯和中間代碼生成文法的語法制導(dǎo)定義(語義規(guī)則)和翻譯方案--語法制導(dǎo)定義-->語義分析做什么

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

第五頁，共二十五頁。7.1.2圖表示法圖表示法DAG-無循環(huán)有向圖抽象語法樹

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

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

請畫出語法樹和DAG

:=a+*b-cDAG:=a+*b-c抽象語法樹*b-c第九頁，共二十五頁。抽象語法樹對應(yīng)的代碼：t1=-c t2=b*t1

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

a=t5assigna+*buminusc抽象語法樹*buminusc第十頁，共二十五頁。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第十一頁，共二十五頁。作業(yè)：P2217.1第十二頁，共二十五頁。7.3中間代碼生成

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

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

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)分別是它們在三元式表中的位置。

■

第十五頁，共二十五頁。三地址代碼的形式：

三元式、四元式、間接三元式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)第十六頁，共二十五頁。屬性文法是在上下文無關(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)生第十七頁，共二十五頁。產(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)第十八頁，共二十五頁。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()}

分別生成三元式代碼、四元式代碼第十九頁，共二十五頁。.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的三元式三元式序列：第二十頁，共二十五頁。語義規(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)第二十一頁，共二十五頁。屬性文法是在上下文無關(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)生第二十二頁，共二十五頁。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。第二十三頁，共二十五頁。產(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地址指令。第二十四頁，共二十五頁。步驟棧內(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.pl