语法制导翻译和中间代码的生成.ppt

共50页,Page1,编译程序的任务:是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。,第八章语法制导翻译和中间代码的生成,共50页,Page2,通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。,共50页,Page3,语义处理的两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。,共50页,Page4,1.属性文法2.语法制导翻译3.中间代码的形式4.简单的赋值语句的翻译5.布尔表达式的翻译(*),共50页,Page5,属性文法:一个属性文法是一个三元组A=(G，V，F)，(1)一个上下文无关文法G；(2)一个属性的有穷集V;(3)关于属性的断言或谓词的有穷集F。每个属性与文法的某个非终结符或终结符相联。每个断言与文法的某产生式相联。,8.1属性文法,共50页,Page6,如果对G中的某一输入串而言,句子A中的所有断言对该输入串的语法树结点的属性全为真，则该串A是语言中的句子,编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。,共50页,Page7,属性文法静态语义实例分析,GEET1T2|T1orT2Tnum|true|false输入串3+4,共50页,Page8,常使用N.t的形式表示与非终结符N相联的属性t,加入属性和断言GE：ET1T2T1.t=intANDT2.t=intET1orT2T1.t=boolANDT2.t=boolTnumT.t:=intTtrueT.t:=boolTfalseT.t:=bool,共50页,Page9,例8.1简单算术表达式求值的语义描述。产生式语义规则(0)LEprint(E.val)(1)EE1+TE.val:=E.valT.val(2)ETE.val:=T.val(3)TT1*FT.Val:=T1.val*F.val(4)TFT.val:=F.val(5)F(E)F.Val:=E.val(6)FdigitF.val=digitlexval,共50页,Page10,例8.2描述说明语句中各种变量的类型信息的语义规则。产生式语义规则(1)DTLL.in:=T.type(2)TintT.type：Integer(3)TrealT.type:=realL1.in:=L.in(4)LL1,idaddtype(id.entry,L.in)(5)Lidaddtype(id.entry，L.in),共50页,Page11,根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。两个主要任务:(1).简单算数术表达式计算它的值,(2).其它语法结构翻印成中间代码,82语法制导翻译概论,共50页,Page12,假定我们现在要分析的语法成分是简单算术表达式，所完成的语义处理不是将它翻译成中间代码或是目标代码，而是计算表达式的值.产生式语义规则(0)LEprint(E.val)(1)EE1+TE.val:=E.valT.val(2)ETE.val:=T.val(3)TT1*FT.Val:=T1.val*F.val(4)TFT.val:=F.val(5)F(E)F.Val:=E.val(6)FdigitF.val=digitlexval,共50页,Page13,共50页,Page14,1).逆波兰记号2).三元式3).树形表示4).四元式,8.3.中间代码的形式,共50页,Page15,表示规则：运算对象写在前面，运算符写在后面,1).逆波兰记号,共50页,Page16,最大的优点：易于用栈结构分析表达式，每碰到运算对象就把他推进栈，碰到运算符，若该运算符是二元的实施运算，并将结果代替这两个运算对象进栈,若是一元的，则对栈顶的元素运算，并将结果代替该运算对象进栈，最后结果留在栈顶。,共50页,Page17,例:将-B+C*D写成逆波兰记号，并分析的计算过程逆波兰记号：B-CD*+过程：1.B进栈2.对栈顶的元素实施一元运算，并将结果代替栈顶，即-B进栈3.C进栈4.D进栈5.栈顶两元素相乘CD出栈，相乘结果进栈6.栈顶两元素相加，两元素出栈，结果进栈即表达式结果在栈顶,实例分析,共50页,Page18,规则：（op,Arg1,Arg2）实例:a:=b*c+b*d表示为:(1).(*,b,c)(2).(*,b,d)(3).(+,(1),(2)(4).(:=,(3),a)注意：1).一目运算：（op,Arg1,）2).多目运算，用相继的多个三元式写成,2).三元式和树形表示,共50页,Page19,树形表示是三元式的翻译，使用二叉树结构表达实例:a:=b*c+b*d表示为:,3).树形表示,:=,a,+,*,*,b,b,c,d,共50页,Page20,1).对常量和变量的数就是常量和变量本身2).表达式e1和e2的树为T1,T2,特殊情况,共50页,Page21,规则：（op,Arg1,Arg2,Result）实例:a:=b*c+b*d表示为:(1).(*,b,c,t1)(2).(*,b,d,t2)(3).(+,t1,t2,t3)(4).(:=,t3,a),4).四元式,共50页,Page22,命令的四元式：gotoL写成：(jump,L)ifbropcgotoL写成：(jrop,b,c,L),共50页,Page23,id表示的单词;id.name单词属性，用做语义变量;Lookup(id.name)表示审查id.name是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil;语义过程emit表示输出四元式到输出文件;语义过程newtemp表示生成一临时变量，每调用一次，生成一新的临时变量;语义变量E.Place，表示存放E值的变量名在符号表的登录项或一整数码,8.4.简单的赋值语句的翻译,共50页,Page24,（1）Sid:=Ep:=lookup(id.name)；ifpnilthenemit(p:=Eplace)elseerror（2）EE1+E2E.place:=newtemp；emilt(E.place:=E1.place+E2.place（3）EE1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place)elseerror,赋值语句的翻译的属性文法,共50页,Page25,（4）E-E1E.place:=newtemp;emit(E.place:=uminusE1.place)（5）E(E1)E.place:=E1.place（6）Eidp:=lookup(id.name)ifpnilthenE.Place:=p；,共50页,Page26,1)E.type表示E的类型信息，E.type的值或为int或为real，2)整型加（乘）和实型加（乘),把十（*）分别写作十i(*i)和十r(*r).3)用一目算符itr表示将整型运算对象转换成实型。,赋值语句的翻译的属性文法(带数据类型),共50页,Page27,E.place:=newtemp;ifE1.type=intANDE2.type=intthenbeginemit(E.Place，:=，E1.Place，*,E2.Place)E.type:=intendelseifE1.type=realANDE2.type=realthenbeginemit(E.place，:=,E1.place,*r,E2.place)E.type:=realend,产生式EE1*E2的翻译,共50页,Page28,elselfE1.type=int/*andE2.type=real*/thenbegint:=newtemp;emit(t，:=,itr,E1.place);emit(E.Place,:=,t,*r,E2.Place)；E.type:=realendelse/*E1.typerealandE2.type=Int*/begint:=newremp；emit(t,:=;itr,E2.place)；emit(E.Place,:=,E1.Place,*r,t)；E.type:=realend；,共50页,Page29,布尔表达式的计算方法：1or(not0and0)or01).按算术表达式一样计算1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1,8.5.布尔表达式的翻译,共50页,Page30,2)采用优化方法：1or(not0and0)or0or中任意一项为真，表达式为真,(1)t1:=notc(2)t2:=bandt1(3)t3:=aort2,例.aorbandnotc按方法一的翻译,共50页,Page31,(1).ifabgoto(4)(2).t:=0(3).goto(5)(4).t:=1(5).,Ifabthen1else0的翻译,共50页,Page32,EE1orE2E.Place:=newtemp;emit(E.place:=E1.placeorE2.place)EE1andE2E.Place:=newtemp;emit(E.place:=E1.placeandE2.place)EnotE1E.Place:=newtemp;emit(E.place:=notE1.place)E(E1)emit(E.place:=E1.place),简单布尔表达式翻译的属性文法,共50页,Page33,Eid1relopid2E.Place:=newtemp;emit(ifid1.placerelopid2.placegotonextstat+3);emit(E.Place:=0);emit(gotonextstat+2);emit(E.Place:=1)EtrueE.Place:=newtemp;emit(E.Place:=1)EfalseE.Place:=newtemp;emit(E.Place:=0),共50页,Page34,SifEthenS1|ifEthenS1elseS2|whileEdoS1,控制语句的布尔表达式的翻译,共50页,Page35,E.ture表达式为真转向的目标语句E.false表达式为假转向的目标语句实例ifafthenS1elses2的布尔表达式的翻译：,共50页,Page36,(1).ifafgoto(7)(6)goto(p+1)(7)s1的四元式.(p)goto(q)P+1的四元式.(q),回填与拉链,产生四元时不知道,共50页,Page37,(10)gotoE.true(10).goto(0).(20)gotoE.true(20)goto(10).(30)gotoE.true(30)goto(20).(40)gotoE.true(40)goto(30),共50页,Page38,Nextstat指向下一四元式的地址Merge(p1,p2)把p1和p2为首的两条链合并成一条返回合并后的链首值，即将p2链尾第四区段改为p1,合并后的链首为P2backpatch(p,t)把p链第四区段填为tE.codebeginE的第一个四元式的地址,控制语句的布尔表达式的翻译文法,共50页,Page39,EE1orE2backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge(E1.true,E2.true)E.false:=E2.false,共50页,Page40,EE1andE2backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false)EnotE1E.true:=E1.trueE.codebegin:=E1.codebegin;E.false:=E1.true,共50页,Page41,E(E1)E.true:=E1.trueE.codebegin:=E1.codebegin;E.false:=E1.falseEid1relopid2E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(ifid1.placeropid2.placegoto-)emit(goto-);,共50页,Page42,EtrueE.true:=nextstat;E.codebegin:=nextstat;emit(goto-);EfalseE.false:=nextstat;E.codebegin:=nextstat;emit(goto-);,共50页,Page43,共50页,Page44,共50页,Page45,归约cd产生式102:ifcdgoto103:goto-,E1.codebegin=102E.true=102E.false=103,共50页,Page46,归约ef104:ifefgoto105:goto-,E2.codebegin=104E.true=104E.false=105,共50页,Page47,EE1andE2backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false),E2.codebegin=104E.true=104E.false=105,E1.codebegin=102E.true=102E.false=103,共50页,Page48,backpatch(E1.true,E2.codebegin)=backpatch(102,104)E.false:=merge(E1.false,E2.false)=merge(103,105)E.true=104100:ifabgoto101:goto-102:ifcdgoto104103:goto104:ifefgoto105:goto103,E.codebegin=102E.true=104E.false=103,105,共50页,Page49,EE1orE2backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge(E1.true,E2.true)E.false:=E2.false,E2.codebegin=102E.true=104E.false=103,105,E1.codebegin=100E.true=100E.false=101,共50页,Page50,