第八章 语法制导翻译与中间代码生成

第8章语法制导翻译和中间代码生成提纲：属性文法翻译模式中间代码语句翻译语法制导翻译：在语法分析的同时，完成相应的语义处理语义分析的任务：检查静态语义：类型、越界、维数、运算翻译(生成)中间(目标)代码：变量的存储分配、表达式的求值、语句的翻译8.1属性文法语义：语法成份的语义可以用文法符号的属性来表示，通过属性的计算来完成翻译属性文法：在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的属性及一些附在产生式上的语义规则。属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等属性可以进行计算和传递语义规则：对于文法的每个产生式都配备了一组属性的计算规则属性文法的形式化定义：属性文法A是一个三元组:A=(G,V,F)G:是一个上下文无关文法V:有穷的属性集F:关于属性的语义规则属性的设定：根据文法符号的语义，为文法符号设置属性例如：根据实际需要设置属性表达式E：E.typeE.val属性文法的例子：文法语义规则EE1+E2E.val:=E1.val+E2.valE(E1)E.val:=E1.valEnE.val:=n.lex属性文法的主要思想：首先对每个文法符号引进相关的属性符号；其次对每个产生式写出属性值计算的规则。说明：属性有不同的类型，可以象变量一样地被赋值.例：E.val:=E1.val+E2.val赋值过程就是语义处理过程.例：在推导语法树的时候，诸属性的值被计算并通过赋值规则层层传递.语法推导树最后完成时，就得到开始符号的属性值.也就是整个程序的语义.属性的分类：综合属性：“自下而上”传递信息继承属性：“自上而下”传递信息在一个属性文法中，对应于每个产生式A→都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,…,ck)这里，f是一个函数，c1,c2,…,ck是产生式文法符号或A的属性b为A的综合属性：如果b是A的一个属性，并且c1,c2,…,ck是产生式右边文法符号的属性或者A的其他属性。b是文法符号X的继承属性：如果b是产生式右边某个文法符号X的一个属性，c1,c2,…,ck

是A或产生式右边任何文法符号的属性。两种情况下，属性b都依赖于属性c1,c2,…,ck。说明：终结符属性为综合属性，由词法分析器给出非终结符既可以有综合属性，也可以有继承属性

产生式

L→E E→E1+T E→T T→T1*F T→F F→(E) F→digit语义规则print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexvalE、T、F的Val属性是？综合属性例：简单算术表达式求值的语义描述（属性文法）

产生式

语义规则

D→TL L.in:=T.type T→int T.type:=integer T→real T.type:=real L→L1,id L1.in:=L.in

addtype(id.entry,L.in)

L→id addtype(id.entry,L.in)T.type是综合属性L.in是继承属性例：说明语句中各种变量的类型信息的语义规则（属性文法）综合属性在语法树中，一个结点的综合属性的值由其子结点的属性值确定。使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值3*5+4的带语义信息的语法树digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19L

产生式语义规则

L→Eprint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.valT→F T.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval继承属性在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定句子realid1，id2，id3的带语义信息的语法树id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real产生式

语义规则

D→TLL.in:=T.typeT→int T.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→id addtype(id.entry,L.in)8.2语法制导翻译概论基于属性文法的处理方法过程（一般情况）：对单词符号串进行语法分析，构造语法分析树构造属性依赖图获得语义规则的计算顺序翻译结果（语义规则的计算）产生代码在符号表中存放信息给出错误信息执行任何其它动作对输入符号串的翻译也就是根据语义规则进行计算的结果。8.2.1计算语义规则在一棵语法树中，结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,…,ck)

的形式依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。E→E1＋E2 E.val:=E1.val+E2.valE1+E2Evalvalval语义规则的计算次序一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序基于属性文法的翻译是很精确的基础文法用于建立输入符号串的语法分析树根据语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序输入串语法树依赖图语义规则计算次序属性计算1）树遍历通过树遍历的方法计算属性的值假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性以某种次序遍历语法树，直至计算出所有属性深度优先，从左到右的遍历属性计算2）一遍扫描的处理方法是在语法分析的同时计算属性值所采用的语法分析方法属性的计算次序8.2.2S-属性文法和自下而上翻译S-属性文法：只含有综合属性S－属性文法适合于一遍扫描的自下而上分析综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。在分析栈中使用一个附加的域来存放综合属性值假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式A→XYZ的表达式文法的SLR（1）分析表ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法

0:L→E 1:E→E+T2:E→T 3:T→T*F4:T→F5:F→(E)6:F→i

产生式

L→E E→E1+T E→T T→T1*F T→F F→(E) F→digit语义规则print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval3*5+4的分析和值计算过程输入 state sym val 用到的产生式

3*5+4#0 # -

*5+4#05 #3 --

*5+4#03 #F -3 F→digit*5+4#02 #T -3 T→F5+4#027 #T* -3-

+4#0275 #T*5 -3-- ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法

0:L→E 1:E→E+T2:E→T 3:T→T*F4:T→F5:F→(E)6:F→i3*5+4的分析和值计算过程输入state sym val 用到的产生式+4#0275 #T*5 -3-- +4#02710 #T*F -3-5 F→digitACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法

0:L→E 1:E→E+T2:E→T 3:T→T*F4:T→F5:F→(E)6:F→i3*5+4的分析和值计算过程输入state sym val 用到的产生式+4#0275 #T*5 -3-- +4#02710 #T*F -3-5 F→digit+4#02#T -15 T→T*F+4#01 #E -15 E→T4#016 #E+ -15-

#0165 #E+4 -15-4

ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法

0:L→E 1:E→E+T2:E→T 3:T→T*F4:T→F5:F→(E)6:F→i3*5+4的分析和值计算过程输入 state symval 用到的产生式

#0165 #E+4 -15--

#0163#E+F -15-4 F→digit#0169#E+T -15-4 T→F#01 #E-19 E→E+T #L -19 L→EACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法

0:L→E 1:E→E+T2:E→T 3:T→T*F4:T→F5:F→(E)6:F→i8.2.3L-属性文法和自顶向下翻译一个属性文法称为L-属性文法，如果对于每个产生式A→X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于：(1)产生式Xj的左边符号X1，X2，…，Xj-1的属性；(2)A的继承属性。S-属性文法一定是L-属性文法不是L-属性文法

产生式

语义规则

A→LM M.i:=m(L.s) A→QR Q.i:=q(R.s)

A.s:=f(Q.s)例：将中缀表达式翻译成后缀表达式的属性文法E->EaddopTprint(addop.lexeme)|TT->numprint(num.val)其中，addop为+或-是L-属性文法如果用LR分析，很容易实现在语法分析时进行翻译例：将2+3-5转换成中缀表达式2Tprint2E3Tprint++ETprint--E5print5说明语义动作的语法树print3例：将2+3-5转换成中缀表达式LR分析8.2.3L-属性文法和自顶向下翻译对L-属性文法进行自顶向下翻译LL(1)文法适合自顶向下分析LL(1)文法不包含左递归文法：E->EaddopTprint(addop.lexeme)|TT->numprint(num.val)此文法含有左递归为了利用LL(1)方法分析，必须去除左递归E→TRR→addopT{print(addop.lexeme)}R1|

T→num{print(num.val)}

例：9-5+2语义动作的语法树-ETR9{print(‘9’)}TR5{print(‘5’)}{print(‘-’)}+T2{print(‘2’)}R{print(‘+’)}改写后：E->EaddopTprint(addop.lexeme)|TT->numprint(num.val)这种语义处理的描述形式称为翻译模式8.2.3L-属性文法和自顶向下翻译翻译模式：是适合语法制导翻译的另一种描述形式，给出了使用语义规则进行计算的次序在翻译模式中，和文法符号相关的属性和语义规则用花括号{}括起来，插入到产生式右部的合适位置上设计翻译模式的原则设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。当消除一个翻译模式的基本文法的左递归时同时考虑属性

8.2.4L-属性文法的自下而上的翻译方法：1）从翻译模式中去掉嵌入在产生式中间的动作，把所有的语义动作都放在产生式的末尾2）用综合属性代替继承属性1）转换方法：加入新的产生式M→把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M→的末尾翻译模式

E→TRR→＋T{print(‘＋’)}R|－T{print(‘－’)}R|T→num{print(num.val)}转换为

E→TRR→＋TMR|－TNR|T→num{print(num.val)}M→{print(‘＋’)}N→{print(‘－’)}8.3中间代码的形式中间代码：是源程序的一种内部表示，复杂性介于源语言和目标机语言之间中间代码的作用：使编译程序的逻辑结构更加简单明确利于进行与目标机无关的优化利于在不同目标机上实现同一种语言中间代码的形式：逆波兰式、四元式、三元式、树8.3.1逆波兰式逆波兰表示法：一种表示表达式的方法，又称后缀式表示法。4+5*2-3后缀式：452*+3-后缀式的计算要知道每个算符的目数用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。8.3.1逆波兰式可将逆波兰表示扩充到表达式以外的范围例如：赋值语句a:=b*c+b*d表示：abc*bd*+:=条件语句ifEthenS1elseS2表示：ES1S2♂♂为三目运算符8.3.2三元式和树形表示三元式通过计算临时变量值的语句的位置来引用这个临时变量三个域：op（运算符）、arg1(运算对象)和arg2（运算对象）

op arg1 arg2(0) - c (1) * b (0)(2) - c (3) * b (2)(4) + (1) (3)(5) ：= a (4)例如：a:=b*(-c)+b*(-c)例如，语句X:=(A+B)*C;Y:=D↑(A+B)的三元式表示如下表所示。三元式也可以表示成树：=a+*b-c*b-c例如

a:=b*(-c)+b*(-c)的树表示法8.3.3四元式四元式(普遍采用的中间代码形式)一个带有四个域的记录结构，这四个域分别称为op,arg1,arg2及result op arg1 arg2 result(0) - c T1(1) * b T1 T2(2) - c T3(3) * b T3 T4(4) + T2 T4 T5(5) := T5 a

例如：a:=b*(-c)+b*(-c)8.3.3四元式为了更直观，也把四元式的形式写成简单赋值形式(1)T1:=-c(2)T2:=b*T1(3)T3:=-c(4)T4:=b*T3(5)T5:=T2+T4(6)a:=T5把（jump,-,-,L）写成gotoL把(jrop,B,C,L)写成ifBropCgotoL例如：a:=b*(-c)+b*(-c)8.4简单赋值语句的翻译在上面的四元式中，使用变量名字本身表示运算对象在实际实现中，它们是指针：指向符号表的某一登陆项或临时变量的整数码翻译的一般要求：充分了解各种语法成分的语义目标语言的语义简单赋值语句的翻译：翻译成四元式下面为翻译中用到的信息：语义属性：E.place：存储位置或整数码lookup()：子程序，在符号表中查找emit(t:=arg1oparg2)：子程序，生成四元式newtemp：产生新的临时变量产生赋值语句的四元式翻译模式S→id:=E {p:=lookup(); ifpnilthen emit(p‘:=’E.place) elseerror}E→E1+E2{E.place:=newtemp; emit(E.place‘:=’E1.place‘+’E2.place)}E→E1*E2{E.place:=newtemp; emit(E.place‘:=’E1.place‘*’E2.place)}产生赋值语句的四元式翻译模式（续）E→-E1 {E.place:=newtemp; emit(E.place‘:=’

‘-’E1.place)}E→(E1) {E.place:=E1.place}E→id{p:=lookup(); ifpnilthen E.place:=p elseerror}例如：将x:=y+i*j翻译成四元式S→id:=E {p:=lookup(); ifpnilthenemit(p‘:=’E.place)elseerror}E→E1+E2{E.place:=newtemp; emit(E.place‘:=’E1.place‘+’E2.place)}E→E1*E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘*’E2.place)}E→-E1 {E.place:=newtemp;emit(E.place‘:=’‘-’E1.place)}E→(E1){E.place:=E1.place}E→id{p:=lookup(); ifpnilthenE.place:=pelseerror}在翻译中有时需要类型转换用E.type表示非终结符E的类型属性假设只有整型和实型，对应产生式EE1opE2的语义动作中关于E.type的语义规则可定义为：

{ifE1.type=integerandE2.type=integer E.type:=integer elseE.type:=real}算符区分为整型算符intop和实型算符realopx:=y＋i*j

其中x、y为实型；i、j为整型。这个赋值句产生的四元式代码（简写）为：

T1:=iint*j T3:=inttorealT1 T2:=yreal+T3 x:=T2关于产生式E→E1

＋E2的语义动作{E.place:=newtemp;

ifE1.type=integerandE2.type=integerthenbegin emit(E.place‘:=’E1.place‘int+’E2.place); E.type:=integerendelseifE1.type=realandE2.type=realthenbegin emit(E.place‘:=’E1.place‘real+’E2.place); E.type:=realendelseifE1.type=integerandE2.type=realthenbegin u:=newtemp; emit(u‘:=’

‘inttoreal’E1.place); emit(E.place‘:=’u‘real+’E2.palce); E.type:=realendelseifE1.type=realandE1.type=integerthenbegin u:=newtemp; emit(u‘:=’

‘inttoreal’E2.place); emit(E.place‘:=’E1.place‘real+’u); E.type:=realendelseE.type:=type_error}8.5布尔表达式的翻译布尔表达式的两个基本作用:计算逻辑值：a&&b||c(C语言)控制语句的条件表达式：(C语言)if(a<b)thena=a+2;while(t>5)t--;产生布尔表达式的文法E→Eor

E|Eand

E|notE|(E)|irop

i|true|false约定布尔算符的优先顺序从高到低为not,and,or，并且and和or服从左结合8.5.1布尔表达式的翻译方法通常计算布尔表达式的值有两种方法:1.如同计算算术表达式一样，一步步算（计算值）

1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采用某种优化措施（控制语句中的条件表达式）计算AorB，若A为1，可以不计算B

8.5.1布尔表达式的翻译方法若按第一种办法计算布尔表达式，则aorbandnotc翻译成的四元式序列为： （1）t1:=notc

（2）t2:=bandt1

（3）t3:=aort2对于关系表达式a<b可看成等价的条件语句

ifa<bthen1else0翻译成的四元式序列为： （1）ifa<bgoto（4）（2）t:=0

（3）goto（5） （4）t:=1

（5）关于布尔表达式的翻译模式过程emit生成四元式nextstat给出输出序列中下一个四元式的地址aorbandnotc翻译成的四元式序列为：

（1）t1:=notc

生成四元式（1）之后，nextstat的值为2

（2）t2:=bandt1

（3）t3:=aort2每产生一个四元式后，过程emit便把nextstat加1

布尔表达式的翻译模式E→E1orE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘and’E2.place)}E→notE1{E.place:=newtemp; emit(E.place‘:=’‘not’E1.place)}E→(E1) {E.place:=E1.place}Eid1ropid2{E.place:=newtemp;

emit(‘if’id1.placeropid2.place‘goto’nextstat+3);

emit(E.place‘:=’‘0’);

emit(‘goto’nextstat+2);

emit(E.place‘:=’‘1’)}E→true {E.place:=newtemp;E.place=1;}E→false {E.place:=newtemp;E.place=0;}对于关系表达式a<b可看成等价的条件语句

ifa<bthen1else0翻译成的四元式序列为： （1）ifa<bgoto（4）（2）t:=0

（3）goto（5） （4）t:=1

（5）产生布尔表达式的文法

E→Eor

E|Eand

E|notE|(E)|irop

i|true|false

约定布尔算符的优先顺序从高到低为not,and,or，并且and和or服从左结合

给出布尔表达式a<borc<dande<f的语法树（根据算符优先关系，采用自下向上分析）a<bEc<dEe<fEandEorE布尔表达式a<borc<dande<f的翻译结果

（假设nextstat从0开始）0: ifa<bgoto31: T1:=0 2: goto43: T1:=14: ifc<dgoto75: T2:=0 6: goto87: T2:=18:ife<fgoto119:T3:=010:goto1211:T3:=112:T4:=T2andT313:T5:=T1orT4E→E1orE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘and’E2.place)}E→notE1{E.place:=newtemp; emit(E.place‘:=’‘not’E1.place)}E→(E1) {E.place:=E1.place}Eid1ropid2{E.place:=newtemp;

emit(‘if’id1.placeropid2.place‘goto’nextstat+3);

emit(E.place‘:=’‘0’);

emit(‘goto’nextstat+2);