第讲-语法制导翻译和中间代码生成

第七讲

语法制导翻译和中间代码7.1属性文法7.2语法制导翻译概论7.3中间代码7.4一些语句的翻译第1页，共36页。属性文法属性文法(attributegrammar)是一个三元组:A=(G,V,F)F：关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性V：有穷的属性集，每个属性与文法的一个终结符或非终结符相连G：是一个上下文无关文法第2页，共36页。表达式文法E→T+T|TorT

T→n|true|falseE→

T1+T2

{T1.type=intANDT2.type=T1.typeE.type:=int}E→

T1orT2

{T1.type=boolANDT2.type=T1.typeE.type:=bool}T→n{T.type:=int}T→true{T.type:=bool}T→false{T.type:=bool}类型检查的属性文法：第3页，共36页。语义规则

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

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

E.val:=T.val

T.val:=T1.val

F.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval产生式综合属性val综合属性在分析树中，如果一个结点的某一个属性由其子结点的属性确定，则称这种属性为该结点的综合属性。产生副作用的语义规则，如打印一个值、向符号表中插入信息或更新一个全程变量等。语义规则函数都不具有副作用的语法制导定义称为属性文法。第4页，共36页。在语法制导定义中，一条语义规则完成一个计算属性值的动作。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的带注释的分析树如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S属性定义。通常采用自底向上的方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个节点的属性值。第5页，共36页。继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。生产式语义规则D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)继承属性L.in第6页，共36页。语句：

realid1，id2，id3

的分析树，采用自上而下的分析方法产生式语义规则D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)DL.in=realL.in=realL.in=realT.type=realrealid2id1id3..，，第7页，共36页。type#idA:=-B*(C+D)#true:将下列语句翻译成后缀式：{T1.true)(1)G：是一个上下文无关文法查看语意义子程序4~6type:=bool}#idA:=ET1*(ET2)#Sub2(+，C，D，T2）T=F(3)ifc<dgoto(5)place:=E1.语法制导翻译概论在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。参见P.157-159对表达式2+3*5进行的分析第8页，共36页。中间代码的形成中间代码的常见形式：逆波兰记号三元式（树形表示）间接三元式四元式第9页，共36页。逆波兰记号（后缀式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。第10页，共36页。逆波兰记号的扩充用途-ii@GotoLLjumpifEthenS1elseS2ES1S2￥A[n][m]nmAsubs复杂性：压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。第11页，共36页。逆波兰示例把下述产生式定义的算术表达式映射到后缀式表示：

EE+TET

TTFTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a产生式 翻译成分第12页，共36页。确定输入a+a

a的输出：(E,E)(E+T，ET+)

(T+T，TT+)(F+T，FT+)(a+T，aT+)(a+TF，aTF+)(a+FF，aFF+)(a+aF，aaF+)(a+aa，aaa+)

EE+TET

TTFTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a产生式 翻译成分第13页，共36页。将下列语句翻译成后缀式：

ifx>ytheny=y+zelsex=x+z错误的翻译：（ifEthenS1elseS2翻译成：ES1S2￥）xyyz>y+=z+xx=￥正确的翻译：xyyz>y+=z+xx=……L1JzL2Jmp

L1L2……第14页，共36页。三元式和树形表示格式：

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

a:=b*c+b*d

(1) (*，b，c)

(2) (*，b，d)

(3) (+，(1)，(2))

(4) (:=，(3)，a):=a+**bcbd三元式表示树形表示第15页，共36页。间接三元式执行表三元式表第16页，共36页。例如：x:=(a+b)*c

b:=a+b

y:=c*(a+b)三元式：(+，a，b)(*，(1)，c)(:=，(2)，x)(+，a，b)(:=，(4)，b)(+，a，b)(*，c，(6))(:=，(7)，y)间接三元式：

三元式表执行表(+，a，b)(1)(*，(1)，c)(2)(:=，(2)，x)(3)(:=，(1)，b)(1)(:=，(2)，y)(4)

(1)

(2)

(5)第17页，共36页。四元式格式：

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

a:=b*c+b*d

(1) (*，b，c，t1)

(2) (*，b，d，t2)

(3) (+，t1，t2，t3)

(4) (:=，t3，，a)第18页，共36页。四元式的特点类似于三地址指令利于优化和代码生成第19页，共36页。四元式的直观表示t1:=b*c

t2:=b*d

t3:=t1+t2

a:=t3(jump，，，L) gotoL(jrop，B，C，L) ifBropCgotoL第20页，共36页。E.(1)（@，B，，T1）type=real*/thenplace“:=”“uminus”E1.E.p10(5)E(E1)true:=merge(E而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性place“:=”E1.type:=int}第七讲语法制导翻译和中间代码三元式表执行表简单赋值语句的翻译四元式形式:

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

函数：lookup();

过程：emit(t:=arg1oparg2);

newtemp;返回指向id的指针输出四元式生成临时变量E.place:值E的位置第21页，共36页。产生式和语义描述：(1)S

id:=E{P:=lookup();ifP

nilthenemit(P“:=”E.place)elseerror}(2)E

E1+E2

{E.place:=newtemp;emit(E.place“:=”E1.place“+”E2.place)}(3)E

E1*E2

{E.place:=newtemp;emit(E.place“:=”E1.place“*”E2.place)}返回第22页，共36页。(4)E

-E1

{E.place:=newtemp;emit(E.place“:=”“uminus”E1.place)}(5)E

(E1){E.place:=E1.place}(6)E

id{P:=lookup();ifP

nilthenE.place:=Pelseerror}返回第23页，共36页。例：将下列语句翻译成四元式形式：A:=-B*(C+D)#A:=-B*(C+D)#查看语意义子程序1~3查看语意义子程序4~6

栈余留输入字符语意义动作产生的四元式#idA:=-B*(C+D)##idA:=-B*(C+D)##idA:=-B*(C+D)##idA:=-idB*(C+D)##idA:=-EB*(C+D)#Sub6#idA:=ET1*(C+D)#Sub4(@，B，，T1）#idA:=ET1*(C+D)##idA:=ET1*(C+D)##idA:=ET1*(idC+D)##idA:=ET1

*(EC+D)#Sub6#idA:=ET1*(EC+D)#第24页，共36页。查看语意义子程序1~3查看语意义子程序4~6栈余留输入字符语意义动作产生的四元式#idA:=ET1*(EC+D)##idA:=ET1*(EC+idD)##idA:=ET1*(EC+ED)#Sub6#idA:=ET1*(ET2)#Sub2(+，C，D，T2）#idA:=ET1*(ET2)##idA:=ET1*ET2#Sub5#idA:=ET3#Sub3(*，T1，T2，T3）#S

#Sub1(:=，T3，，A）第25页，共36页。语句A:=-B*(C+D)翻译成四元式形式为：(1)（@，B，，T1）(2)（+，C，D，T2）(3)（*，T1，T2，T3）(4)（:=，T3，，A）第26页，共36页。类型转换的语义处理E

E1*E2{E.place:=newtemp;ifE1.type=intANDE2.type=intthenBeginemit(E.place,‘:=’,E1.place,‘*i’,E2.place,)；E.type=int；EndelseifE1.type=realANDE2.type=realthenBeginemit(E.place,‘:=’,E1.place,‘*r’,E2.place,)；E.type=real；EndelseifE1.type=int/*E2.type=real*/thenBegint:=newtemp;emit(t,‘:=’,‘irt’,E1.place,)；emit(E.place,‘:=’,t,‘*r’,E2.place,)；E.type=real；Endelse/*E1.type=

real

AND

E2.type=int

*/

Begint:=newtemp;emit(t,‘:=’,‘irt’,E2.place)；emit(E.place,‘:=’,E1.place,‘*r’,t)；E.type=real；End}第27页，共36页。E.false控制语句中布尔表达式的翻译控制语句S®ifEthenS1

elseS2

E的代码

E.true

E.true:S1的代码

gotooutE.false:S2的代码out:……第28页，共36页。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

(翻译不是最优)第29页，共36页。2．拉链返填

……（10）

gotoL（10）goto0

……

……

链尾

（10）（20）

gotoL（20）goto10

……

……（30）

gotoL

(30)goto20

……

……

链头（30）（40）L：……

（40）L:?第30页，共36页。语句ifa<borc<dande<fthenS1

elseS2的四元式(1)

ifa<bgoto(7)

(E.true)(1)和(5）(2)goto(3)

拉链（真）(3)ifc<dgoto(5)(4)goto(p+1)(E.false)(4)和(6)(5)ife<fgoto(7)拉链（假）(6)goto(p+1)(7)(S1的四元式

……(p-1)……）(p)goto

(q)(p+1)(S2的四元式……(q-1)……）(q)第31页，共36页。(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)第32页，共36页。语义描述使用的变量和过程：

E.true：

“真”链，

E.false：

“假”链

。

E.codebegin：

E的第一个四元式

Nextstat：

下一四元式地址

过程：

emit()

输出一条四元式

merge(p1,p2)把p1的链头填在p2的链尾例：

merge(p1,p2)(p10)0……

p1链(p100)

p10……`(p1)p100(p20)0……p2链(p200)