語法制導翻譯和中間代碼生成語法制導翻譯和中間代碼生成文法得語法制導定義(語義規則)和翻譯方案--語法制導定義-->語義分析

做什么

--翻譯方案-->中間代碼生成怎么做中間語言高級得:接近源語言。語法樹,適合完成靜態類型檢查。低級得:接近目標語言。適合完成依賴于機器得任務。常用得中間語言:后綴式:逆波蘭表示圖表示:DAG、抽象語法樹三地址代碼三元式、四元式中間代碼得選擇可以就是一種實際得語言也可以就是編譯各階段共享得內部數據結構7、1中間語言P200后綴式定義寫出3+4*5得后綴式寫出b*(-c)+b*(-c)得后綴式后綴式表示:算術表達式、賦值語句、控制語句后綴式得計算用一個棧實現一般得計算過程就是:自左至右掃描后綴式,每碰到運算量(操作量)就把她推進棧。每碰到k目運算符就把她作用于棧頂得k個項,并用運算結果代替這k個項。7、1、1后綴式

7、1、2圖表示法圖表示法DAG-無循環有向圖抽象語法樹

7、1、2圖表示法無循環有向圖(簡稱DAG)對表達式中得每個子表達式,DAG中都有一個結點一個內部結點代表一個操作符,她得孩子代表操作數在一個DAG中代表公共子表達式得結點具有多個父結點7、1、3三地址代碼三地址代碼x=yopz三地址代碼可以看成就是抽象語法樹或DAG得一種線性表示樹與其她中間代碼得關系

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

請畫出語法樹和DAG

:=a+*b-cDAG:=a+*b-c抽象語法樹*b-c抽象語法樹對應得代碼:t1=-c t2=b*t1

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

a=t5assigna+*buminusc抽象語法樹*buminuscDAG對應得代碼:

t1=-ct2=b*t1t5=t2+t2a=t5assigna+*buminuscDAG抽象語法樹對應得代碼:t1=-c t2=b*t1

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

a=t5作業:P2217、1大家學習辛苦了，還是要堅持繼續保持安靜7、3中間代碼生成

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

產生三地址代碼賦值語句翻譯方案填查符號表詞法分析發布出錯信息語法制導翻譯三地址代碼得形式:

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))

標識符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)屬性文法就是在上下文無關文法得基礎上,為每個文法符號配備若干相關得“值”,稱為屬性,屬性與變量一樣可以進行計算和傳遞,屬性加工得過程即就是語義處理得過程。對文法得每個產生式配備得一組屬性得計算規則,叫語義規則,語義分析和中間代碼得產生就就是根據該規則進行得,在自上而下或自下而上語法分析過程中,在適當得時候進行屬性得計算,或其她語義動作(如查填符號表、產生中間代碼、發布出錯信息)就可進行語法制導翻譯得到中間代碼,這就就是語法制導翻譯得基本思想。語法制導翻譯和中間代碼產生產生賦值語句抽象語法樹得屬性文法產生式 語義規則S→id:=E S、nptr:=mknode(‘assign’, 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分析翻譯方案產生式與翻譯方案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(:=,entr),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:=entr)}

產生式與翻譯方案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(:=,entr),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:=entr)}

分別生成三元式代碼、四元式代碼、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))產生式與語義規則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(:=,entr),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:=entr)}

例生成x:=a+b*c得三元式三元式序列:語義規則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(:=,entr),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:=entr)}

例生成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)屬性文法就是在上下文無關文法得基礎上,為每個文法符號配備若干相關得“值”,稱為屬性,屬性與變量一樣可以進行計算和傳遞,屬性加工得過程即就是語義處理得過程。對文法得每個產生式配備得一組屬性得計算規則,叫語義規則,語義分析和中間代碼得產生就就是根據該規則進行得,在自上而下或自下而上語法分析過程中,在適當得時候進行屬性得計算,或其她語義動作(如查填符號表、產生中間代碼、發布出錯信息)就可進行語法制導翻譯得到中間代碼,這就就是語法制導翻譯得基本思想。語法制導翻譯和中間代碼產生LR分析翻譯方案得設計

LR分析中得語法制導翻譯實質上就是對LR語法分析得擴充:<1>擴充LR分析器得功能:當執行歸約產生式得動作時,也執行產生式對應得語義動作。<2>擴充分析棧:增加一個與分析棧并列得語義棧,用于存放分析棧中文法符號所對應得屬性值。例:E→E1+E2val[top]:=val[top]+val[top+2];

對于表達式:5+3當歸約為左部E時,同時也得到了值8。產生式算術表達式(語義規則)翻譯方案-三地址碼-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,’+’