语法制导翻译和中间代码

第八章语法制导翻译和中间代码8.1属性文法8.2语法制导翻译概论8.3语法制导翻译8.4中间代码8.5一些语句的翻译属性文法属性文法(attributegrammar)是一个三元组:A=(G,V,F),其中G:是一个上下文无关文法V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,F:关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性

表达式文法E→T+T|TorT

T→n|bE→

T1+T2

{T1.type=int

T2.type=T1.type E.type:=int}E

→

T1orT2

{T1.type=bool

T2.type=T1.typeE.type:=bool}T→n{T.type:=int}T→b{T.type:=bool}一个简单台式计算器的语法制导定义语义规则

LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)

E.val:=E1.val+T.val

E.val:=T.val

T.val:=T1.valF.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval产生式综合属性val惟独digit只使用综合属性LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。生产式语义规则DTL

T

int

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)继承属性L.inRealid1,id2,id3DL.in=realL.in=realL.in=realT.type=realrealid2id1id3..生产式语义规则DTL

T

int

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)语法制导翻译概论在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。参见P.157-159对表达式2+3*5进行的分析中间代码的形成中间代码的常见形式：逆波兰记号三元式四元式树形表示逆波兰记号（后缀式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。逆波兰记号的扩充用途i--i@GotoLLjumpifEthenS1elseS2ES1S2￥A[n][m]nmAsubs复杂性：压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。逆波兰示例例：

把下述产生式定义的算术表达式映射到后缀波兰表示：

EE+TET

TTFTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a产生式 翻译成分确定输入a+aa的输出：(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)三元式和树形表示格式：

(算符,第一运算对象,第二运算对象)如：

a=b*c+b*d

(1) (*,b,c)

(2) (*,b,d)

(3) (+,(1),(2))

(4) (=,(3),a)=a+**bcbd四元式格式：

(算符,第一运算对象,第二运算对象,结果)如：

a=b*c+b*d

(1) (*,b,c,t1)

(2) (*,b,d,t2)

(3) (+,t1,t2,t3)

(4) (=,t3,-,a)四元式的特点类似于三地址指令利于优化和代码生成四元式的直观表示t1=b*c

t2=b*d

t3=t1+t2

a=t3(jump,-,-,L) gotoL(jrop,B,C,L) ifBropCgotoL简单赋值语句的翻译四元式形式:

t:=arg1oparg2语义属性：,E.place

函数：lookup();

过程：emit(t:=arg1oparg2);newtemp;

产生式和语义描述：(1)Sid:=E{P:=lookup();ifPnilthenemit(P“:=”E.place)elseerror}返回指向id的指针输出四元式生成临时变量E.place:值E的位置(2)EE1+E2

{E.place:=newtemp;

emit(E.place“:=”E1.place“+”E2.place)}(3)E-E1

{E.place:=newtemp;

emit(E.place“:=”“uminus”E1.place)}(4)E(E1)

{E.place:=E1.place}(5)Eid{E.place:=newtemp;

P:=lookup();

ifPnilthenE.place:=P

elseerror}E.false8.5控制语句中布尔表达式的翻译控制语句S®ifEthenS1

elseS2

E的代码

E.true

E.true:S1的代码

gotooutE.false:S2的代码out:1.

把条件转移的布尔表达式E翻译成仅含

条件真

转

和

无条件

转

的四元式

E：aropb

?ifaropbgotoE.true

gotoE.false如

：a<borc<dande<f

可

翻译成如下四元式：(1)ifa<bgotoE.true(2)

goto(3)(3)

ifc<dgoto(5)(4)

gotoE.false(5)

ife<fgotoE.true(6)

gotoE.false

(翻译不是最优)(1)

ifa<bgoto(E.true)(2)

goto(3)

(3)ifc<dgoto(5)(4)goto(E.false)(5)ife<fgoto(E.true)(6)goto(E.false)(E.true)(S1的四元式序列

……

……）(p)goto

(q)(E.false)(S2的四元式序列……(q-1)……）(q)自下而上分析中的一种翻译方案：(1)

E→E1

orE2{backpatch(E1.false,E2.Codebegin);

E.Codebegin:=E1.codebegin;

E.true:=merge(E1.true,E2.true)

E.false:=E2.false}(2)

E→E1

andE2{backpatch(E1.true,