语法制导翻译技术和中间代码生成080602

第5章语法制导翻译技术和中间代码生成Sunday,December10,2023Sunday,December10,2023本章学习的主要内容本章我们将主要讨论语法制导翻译的根本思想及其在在中间代码生成中的应用。主要包括：属性文法、各种常见中间语言形式、赋值语句的翻译，布尔表达式的翻译，控制语句的翻译、说明语句的翻译等。通过本章的学习，要求掌握语法制导翻译的根本思想和翻译方案。Sunday,December10,2023Sunday,December10,2023语义处理程序的两个功能第一，审查每个语法结构的静态语义，即检查语法结构合法的程序是否真正有意义。也称静态语义分析。〔类型检查、控制流的检查、一致性检查、相关名字的检查〕第二，如果静态语义正确，语义处理那么要执行真正的翻译，要么生成中间代码，要么生成实际的目标代码。〔说明性语句：填符号表；可执行性语句：生成中间代码〕Sunday,December10,2023Sunday,December10,2023属性文法属性文法主要用来描述和说明程序设计语言语义的。属性：一般用来描述客观存在的事物或人的特征，编译技术中用属性来描述计算机要处理的对象的特征。属性文法：为每个上下文无关文法中的文法符号，配以相关联的属性，属性的处理过程也就是语义的处理过程，为文法的每条规那么配以相关联的语义规那么构成的文法称为属性文法。Sunday,December10,2023Sunday,December10,2023属性文法属性文法的形式定义：AG：AG=〔G，V，E〕G:上下文无关文法;V:属性的有穷集合;每一个属性与某一个文法符号相关联；用文法符号·属性表示E:表示属性的断言或谓词的有穷集合(语义规那么);每一个断言与文法的某个产生式相关联)属性:综合属性(自下而上传递信息)、继承属性〔自上而下传递信息)Sunday,December10,2023Sunday,December10,2023语法制导翻译的根本思想对文法中的每个产生式都附加一个语义动作或语义子程序,在执行语法分析的过程中，每当使用一条产生式进行推导或规约时，就执行相应产生式的语义动作。这些动作不仅指明了该产生式所生成的符号串的意义,而且还根据这种意义规定了对应的加工动作.〔如查填各类表格、改变编译程序的某些变量之值、打印各种错误信息以及生成中间代码等〕从而完成预定的工作。Sunday,December10,2023Sunday,December10,2023语法制导翻译概念在语法分析过程中,随着分析的步步进展,根据每个产生式所对应的语义子程序(或语义规那么描述的语义动作)进行翻译的方法称为语法制导翻译。Sunday,December10,2023Sunday,December10,2023算术表达式求值语法分析分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。Sunday,December10,2023Sunday,December10,2023算术表达式的属性文法简单算术表达式求值的语义描述。产生式语义规那么(0)L→EPrint(E.val)(1)E→E1+TE.val=E1val+T.val(2)E→TE.val=T.val(3)T→T1*FT.val=T1.val*F.val(4)T→FT.val=F.val(5)F→(E)F.val=E.val(6)F→digitF.val=Lex.digit〔0~9〕Sunday,December10,2023Sunday,December10,2023翻译步骤首先，为文法的每条规那么设计相应的语义子程序；增加一个语义信息栈；在语法分析的同时做语义处理：即在用某一个产生式进行规约的同时，调用相应的语义子程序完成所用规那么的语义动作，并将每次动作后的值保存在语义栈中Sunday,December10,2023Sunday,December10,2023计算表达式2+3*5Sunday,December10,2023Sunday,December10,2023状态ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5G[E]：1E→E+T2E→T3T→T*F4T→F5F→(E)6F→ii+i*iSunday,December10,2023Sunday,December10,2023表达式2+3*5的归约过程步骤状态栈语义栈符号栈输入串动作00_$2+3*5$S5105__$2+3*5$r6203_2$F+3*5$r4302_2$T+3*5$r2401_2$E+3*5$S65016_2_$E+3*5$S560165_2__$E+3*5$r6Sunday,December10,2023Sunday,December10,2023步骤状态栈语义栈符号栈输入串动作70163_2_3$E+F*5$r480169_2_3$E+T*5$S7901697_2_3_$E+T*5$S510016975_2_3__$E+T*5$r61101697(10)_2_3_5$E+T*F$r3120169_2_15$E+T$r11301_17$E$accSunday,December10,2023Sunday,December10,2023注意句柄归约在先，语义动作调用在后归约时，栈内句柄各符号的语义信息与句柄及同时出栈，整个句柄所表示的语义信息那么赋给相应产生式左部非终结符号的语义变量，并让该非终结符号及语义信息同时入栈Sunday,December10,2023Sunday,December10,2023中间代码中间代码是介于源程序和目标程序之间,用来表述源程序并与之等效的一种编码方式.生成中间代码的作用(1)中间代码与具体机器无关,便于语法分析和语义加工,便于编译程序移植.(更容易改变目标机)(2)易于对中间语言进行优化,有利于提高中间代码的质量.(3)可使编译前端和编译后端接口更清晰,编译程序的逻辑结构更为简单明确.Sunday,December10,2023Sunday,December10,2023常见的中间代码常用的中间代码形式:逆波兰式、三元式、四元式、树代码等Sunday,December10,2023Sunday,December10,2023逆波兰表示法〔后缀式〕特点：运算符直接写在其运算对象之后。不再有括号运算对象出现的次序未变求值过程简单，宜于用栈实现例：a+bab+a*b+cab*c+a*(b+c/d)abcd/+*a*b+c*dab*cd*+a:=b*c+d*eabc*de*+:=Sunday,December10,2023Sunday,December10,2023逆波兰表示法〔后缀式〕后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。Sunday,December10,2023Sunday,December10,2023三元式一般形式：(编号〕〈运算符〉〈运算对象1〉〈运算对象2〉ioparg1arg2出现的次序是对应语法成分的计算次序无需引进临时工作变量，用三元式的编号代替之，节省了存贮空间其中的编号代表某个三元式的位置编号和代表某个三元式的值语句之间的联系靠编号进行，因此，三元式的移动较困难，不便于优化Sunday,December10,2023Sunday,December10,2023表达式a+(-b)*c的三元式

(1)(@,b,_);单目运算，运算对象2为空(2)(*,(1),c)(3)(+,a,(2))Sunday,December10,2023Sunday,December10,2023三元式X=a+b*cY=d-b*c三元式表(1)(*,b,c)(2)(+,a,(1))(3)(=,x,(2))(4)(_,d,(1))(5)(=,y,(4))Sunday,December10,2023Sunday,December10,2023四元式(三地址代码〕一般形式：〈运算符〉〈运算对象1〉〈运算对象2〉〈结果〉(op,arg1,arg2,result)例：X=a*b+c*d的四元式序列三地址代码(1)(*,a,b,T1)(1)T1=a*b(2)(*,c,d,T2)(2)T2=c*d(3)(+,T1,T2,T3)(3)T3=T1+T2(4)(=,T3,_,X)(4)X=T3Sunday,December10,2023Sunday,December10,2023

图表示法无循环有向图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点Sunday,December10,2023Sunday,December10,2023

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

assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminuscSunday,December10,2023Sunday,December10,2023抽象语法树对应的代码：T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象语法树*buminuscSunday,December10,2023Sunday,December10,2023DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5Sunday,December10,2023Sunday,December10,2023

属性翻译文法的应用

综合属性与自下而上定值

每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定的。继承属性和自上而下定值

非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。Sunday,December10,2023Sunday,December10,2023自底向上的语法制导翻译自底向上的语法制导翻译方法是在自底向上的语法分析过程中逐步实现语义规那么的翻译方法。在实现时注意以下几点：〔1〕自底向上的翻译的特点，栈的操作，对产生式的要求等〔2〕各种程序语句的目标结构〔3〕从源结构到目标结构的变换方法〔包括对产生式的改造等〕Sunday,December10,2023Sunday,December10,2023算术表达式和赋值语句的翻译翻译步骤：〔1〕分析文法的特点；〔2〕设计一系列的语义变量、定义语义过程、语义函数；〔3〕设计每一条规那么的语义子程序；〔4〕增加一个语义信息栈，构造LR分析表;(5)语法分析同时语义处理.Sunday,December10,2023Sunday,December10,2023例：有文法G[A]：1.A→i:=E2.E→E+T∣T3.T→T*F∣F4.F→－P5.P→i∣(E)简单算术表达式的计值顺序与四元式出现的顺序相同,因此目标代码的顺序(结构)为:(1)先生成E的代码(一系列顺序执行的四元式)(2)把E的值赋给变量i(表达式的结果赋给赋值语句的左变量)Sunday,December10,2023Sunday,December10,2023引入语义变量,语义过程和语义函数(1)语义变量E.place:表示存放E值的变量名在符号表中的入口地址或临时变量的整数码.(2)语义函数newtemp():申请一个临时单元,存放中间结果;(3)语义过程emit(T=arg1oparg2):产生一条四元式,并添入四元式表中;(4)语义过程lookup():审查是否出现在符号表中,在:返回地址,不在:返回NULL;(5)语义函数entry(i):回送标识符i在符号表中的入口地址.Sunday,December10,2023Sunday,December10,2023表达式的语义动作设计1.A→i:=E{emit(entry(i)=E.place}2.E→E1+T{E.place=newtemp(),emit(E.place)=E1.place+T.place}3.E→T{E.place=newtemp(),emit(E.place=T.place)}4.T→T1*F{T.place=newtemp(),emit(T.place)=T1.place*F.place}5.T→F{T.place=newtemp(),emit(T.place=F.place)}Sunday,December10,2023Sunday,December10,20236.F→_P{F.place=newtemp(),emit(F.place)=@P.place}7.P→(E){P.place=newtemp(),emit(P.place=E.place)}8.P→i{P.place=newtemp(),emit(P.place=Entry(i))}Sunday,December10,2023Sunday,December10,2023例如:表达式X:=a+b*(c-d)的翻译K+1:T1:=c-dK+2:T2=b*T1K+3:T3:=a+T2K+4:X:=T3(-,c,d,T1)(*,b,T1,T2)(+,a,T2,T3)(:=,T3,_,X)Sunday,December10,2023Sunday,December10,2023布尔表达式的翻译布尔表达式是由布尔运算符(and,or,not)作用于布尔变量(或常数)或关系表达式而形成的。布尔表达式的作用：用作控制语句中的条件：if-then、while、repeat等逻辑赋值句中的逻辑运算Sunday,December10,2023Sunday,December10,2023布尔表达式到四元式的翻译

文法：EEEEEE(E)idEropE其中，(and)、(or)、(not)为布尔〔逻辑〕运算符；rop为关系运算符〔>，≥，，≤，=，≠〕；id为布尔〔逻辑〕变量或布尔〔逻辑〕常数；EropE为关系表达式。布尔表达式的求值方法：①通过逐步计算出各局部的值来计算整个表达式。②利用布尔运算符的性质计算其值Sunday,December10,2023Sunday,December10,2023布尔表达式作为控制语句中的条件式作用是用于选择下一个执行点whileEdoS1E的作用是选择S1执行,还是跳过S1语句,执行S1后面的语句E有两个出口:真:S1语句假:S1后面的语句Sunday,December10,2023Sunday,December10,2023While语句的目标结构

假E的代码真

whilleS1的代码

doJMPW.headW.headSunday,December10,2023Sunday,December10,2023布尔初等量(布尔变量和关系表达式)的目标结构

由两个转移四元式构成,一个表示真出口Li,另一个表示假出口Lj,设E是一布尔变量,它的目标结构为:(1)ifEgotoLi(jumpt,E,_,Li)

(jnz,A,_,Li)(2)ifE1ropE2gotoLi(jumpθ,E1,E2,Li)

(jrop,E1,E2,Li)例:(j<,a,b,p)(3)gotoLj(jumpLj)(j,_,_,Lj)Sunday,December10,2023Sunday,December10,2023举例:ifa<bthenA:=x+y的四元式序列ifa<bgotoLi(真出口)gotoLj(假出口)Li:S的第一个四元式…S的最后一个四元式Lj:S后面的语句(1)ifa<bgoto(3)(2)goto(5)(3)T1:=x+y(4)A:=T1(5)Sunday,December10,2023Sunday,December10,2023

多因子组成的布尔表达式的翻译例:ifa<b∨cthenS1elseS2分析结果如下:当a<b为真,执行S1,不需要计算c的值当a<b为假,计算c的值,c为真:执行S1,为假:执行S2当a<b与c分别为真时,程序转向一致,真出口相同(S1)当a<b与c分别为假时,程序转向一致,假出口相同(S2)Sunday,December10,2023Sunday,December10,2023ifa<b∨cthenS1elseS2的四元式序列(1)ifa<bgotoS1的第一条语句(5)(2)goto(3)(3)ifcgotoS1的第一条语句(5)(4)gotoS2的第一条语句(p+1(5)关于S1的四元式序列…(p)Gotoq(p+1)关于S2的四元式序列…(q)后继四元式目标结构E的代码TFS1的代码JUMPSS2的代码S〔后继语句〕Sunday,December10,2023Sunday,December10,2023ifEthenS1elseS2

的四元式序列(1)ifEgoto(3)(2)goto(S2的第一个四元式)(p+1)(3)关于S1的四元式序列……(p)gotor(执行完S1后转出)(p+1)关于S2的四元式序列……(r)后继四元式Sunday,December10,2023Sunday,December10,2023whileEdoS1的四元式序列(1)ifEgoto(3)(2)goto(S1后面的语句)(p+1)(3)关于S1的四元式序列……(p)goto(1)(p+1)后继四元式Sunday,December10,2023Sunday,December10,2023真出口链、假出口链、回填〔Backparch)在多个因子组成的布尔表达式中，可能有多个因子的真出口或假出口的转移去向相同，但又不能立刻知道具体转向位置。把转移方向相同的四元式链在一起，一旦发现具体转移目标，就回填。真出口用Etrue来表示。假出口用Efalse来表示。回填Backparch〔g,t)将t填入由g所指向的四元式的结果局部Sunday,December10,2023Sunday,December10,2023ifa<b∨cthenS1elseS2

的真假出口回填描述(1)ifa<bgoto0/E的真出口Etrue有待回填(2)goto(3)/*回填E的第一个假出口(3)ifcgoto(1)/*〔3〕是E的真出口链(4)goto0/*E的假出口Efalse有待回填(5)关于S1的四元式序列/*此时回填真出口Etrue…(p)goto0/*有待回填q的位置(p+1)关于S2的四元式序列/*此时回填假出口Efalse…(q)后继四元式/*此时回填qSunday,December10,2023Sunday,December10,2023语法制导翻译中使用的公共变量、过程和函数guad:四元式指针(表示四元式的编号或地址)GEN(X):生成一条四元式,把它放到四元式表的尾部,(和前面介绍的emit功能相同)Nextguad:指向下一个即将形成的四元式的编号,其初值为1,执行一次GEN(X),Nextguad自动加1;merg〔p1,p2)函数将以p1,p2为链首的两个四元式合并为一,返回合并后的链首Sunday,December10,2023Sunday,December10,2023条件语句的翻译

根本思路：①先对定义它的文法进行改造，以便能在相应处添加上语义子程序；②根据它的语义，设计出相应语义子程序的动作。Sunday,December10,2023Sunday,December10,2023

if语句的文法S→ifEthenS1S→ifEthenS1elseS2(E是转移条件)对ifEthenS1elseS2,其Etrue直到扫描到then,产生S1的第一个四元式序号时,才能将该标号作为E的真链填入到Etrue,而Efalse直到扫描到else,产生S2的第一个四元式序号时,才得到Efalse的值。Sunday,December10,2023Sunday,December10,2023if语句文法的改造(1)C→ifEthen(2)T→CS1else(3)S→TS2(4)S→CS1目标结构如右图T.chainS1.chainE.true

E.falseelseIfthenS1的代码JUMP0E的代码C.chainS2.chainS2的代码S.chainSunday,December10,2023Sunday,December10,2023if语句的语义动作(1)C→ifEthen{backpatch(Etrue,

Nextguad),C.chain=Efalse}

当用产生式ifEthen进行归约时,生成了条件E的代码,E的假出口不能回填,通过非终结符C向后传递,所以引入C.chain链.Sunday,December10,2023Sunday,December10,2023if语句的语义动作(2)T→CS1else{q:=

Nextguad,emit(goto0)Backpatch(C.chain,Nextguad),T.chain=merg(S1.chain,q)}当用产生式T→CS1else归约时,S1的代码已经形成,回填E的假出口即C.chain。此时S2的代码尚未形成,S1的转出链和JMP转向相同,合并为一,通过T向后传递.Sunday,December10,2023Sunday,December10,2023if语句的语义动作(3)S→TS2{S.chain:=merg(T.chain,S2.chain)}(4)S→CS1{S.chain:=merg(C.chain,S1.chain)Sunday,December10,2023Sunday,December10,2023IfA∧B∧C＞DthenifA＜BthenF:=1elseF:=0elseG:=G+1采用then与else的最近匹配原那么(三地址指令)(1)ifAgoto(3)(2)goto0(13)(3)ifBgoto(5)(4)goto(2)(13)(5)ifC＞Dgoto(7)(6)goto(4)(13)(7)ifA＜Bgoto(9)(8)goto0(11)(9)F:=1(10)goto0(15)(11)F:=0(12)goto(10)(15)(13)T:=G+1(14)G:=T(15)Sunday,December10,2023Sunday,December10,2023IfA∧B∧C＞DthenifA＜BthenF:=1elseF:=0elseG:=G+1四元式形式代码(1)(jnz,A,_,(3))(2)(j,_,_,0)(13)(3)(jnz,B,_,(5)(4)(j,_,_,(2))(13)(5)(j>,C,D,(7))(6)(j,_,_,(4))(13)(7)(j<,A,B,(9))(8)(j,_,_,0)(11)(9)(:=,1,_,F)(10)(j,_,_,0)(15)(11)(:=,0,_,F)(12)(j,_,_,(10))(15)(13)(+,G,1,T)(14)(:=,T,_,G)(15)Sunday,December10,2023Sunday,December10,2023While语句的翻译文法:G[S]S→whileEdoS文法改造为:S→CS1C→WEdoW→while

Etrue

S1chainEfalse

do

假E的代码

真whilleS1的代码JMPW.headW.headC.chainSunday,December10,2023Sunday,December10,2023While语句的语义动作〔1〕W→while{W.head:=Nextguad;}当用W→while归约时,Nextguad记下E的第一个四元式的位置,保存在Wguad中。〔2〕C→WEdo{backpatch(Etrue,Nextguad,C.chain=Efalse,C.head=W.head}当使用C→WEdo进行归约时,E的代码已经生成有两个出口Etrue和Efalse,扫描完do后,可以回填Etrue,而Efalse要到S1语句全部生成后才能回填,因此为待填信息,由C向后传递。Sunday,December10,2023Sunday,December10,2023While语句的语义动作〔3〕SCS1 {Backpatch(S1chain,C.head);S.chain:=C.chain;GEN(goto,W.head);当用上式进行归约时，S1语句全部产生，while语句结束应返回，因此产生四元式〔gotow.head),同时回填EfalseSunday,December10,2023Sunday,December10,2023whilea>0∧b>0do

ifx>ythenb:=b-1elsea:=a-1

假设四元式序列从100开始编号100〔j>,a,0,102)101(j,_,_,0)(112)102(j>,b,0,104)103(j,_,_,101)(112)104(j>,x,y,106)105(j,_,_,0)(109)106(-,b,1,T1)107(:=,T1,_,b)108(j,_,_,100)109(j,a,1,T2)110(:=,T2,_.a)111(j,_,_,100)112Sunday,December10,2023Sunday,December10,2023文法G[S]:S→SaA︱AA→AbB︱BB→cSd︱e(1)证明AacAbcBaAdbed是文法的一个句型.(2)请写出该句型的所有短语、素短语及句柄。〔3〕为文法G[S]的产生式构造相应的翻译子程序，使句型AacAbcBaAdbed经该翻译方案翻译后，输出为。Sunday,December10,2023Sunday,December10,2023文法及相应的翻译方案如下:S→bTc{print〞1〞}S→a{print〞2〞}T→R{print〞3〞}R→R/S{print〞4〞}R→S{print〞5〞}对于输入符号串bR/bTc/bSc/ac,该符号串的输出是什么?输出为1453142431归约的次序为:(1)S→bTc(1)(2)R→R/S(4)(3)R→S(5)(4)T→R(3)(5)S→bTc(1)(6)R→R/S(4)(7)S→a(2)(8)R→R/S(4)(9)T→R(3)(10)S→bTc(1)