《语法制导翻译和中间代码的生成.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码的生成.ppt（50页珍藏版）》请在三一办公上搜索。
1、50页,Page1,编译程序的任务:是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。,第八章 语法制导翻译和中间代码的生成,50页,Page2,通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。,50页,Page3,语义处理的两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行
2、真正的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。,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是语言中的句子,编译程
3、序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。,50页,Page7,属性文法静态语义实例分析,GE ET1 T2|T1 or T2 Tnum|true|false 输入串3+4,50页,Page8,常使用N.t的形式表示与非终结符N相联的属性t,加入属性和断言GE：ET1T2T1.t=int AND T2.t=int ET1 or T2 T1.t=bool AND T2.t=boolTnum T.t:=intTtrueT.t:=boolTfalseT.t:=bool,50页,Page9,例8.1 简单算术表达式求值的语义描述。产生式 语义规则(0)LE print(E.val
4、)(1)EE1+T E.val:=E.valT.val(2)ET E.val:=T.val(3)TT1*F T.Val:=T1.val*F.val(4)TF T.val:=F.val(5)F(E)F.Val:=E.val(6)Fdigit F.val=digitlexval,50页,Page10,例8.2 描述说明语句中各种变量的类型信息 的语义规则。产生式 语义规则(1)DTL L.in:=T.type(2)Tint T.type：Integer(3)Treal T.type:=real L1.in:=L.in(4)LL1,id addtype(id.entry,L.in)(5)Lid ad
5、dtype(id.entry，L.in),50页,Page11,根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。两个主要任务:(1).简单算数术表达式计算它的值,(2).其它语法结构翻印成中间代码,82 语法制导翻译概论,50页,Page12,假定我们现在要分析的语法成分是简单算术表达式，所完成的语义处理不是将它翻译成中间代码或是目标代码，而是计算表达式的值.产生式 语义规则(0)LE print(E.val)(1)EE1+T E.val:=E.valT.val(2)ET E.val:=T.val(3)TT1*F T.Val:=T1.val*F.va
6、l(4)TF T.val:=F.val(5)F(E)F.Val:=E.val(6)Fdigit F.val=digitlexval,50页,Page13,50页,Page14,1).逆波兰记号 2).三元式 3).树形表示 4).四元式,8.3.中间代码的形式,50页,Page15,表示规则：运算对象写在前面，运算符写在后面,1).逆波兰记号,50页,Page16,最大的优点：易于用栈结构分析表达式，每碰到运算对象就把他推进栈，碰到运算符，若该运算符是二元的实施运算，并将结果代替这两个运算对象进栈,若是一元的，则对栈顶的元素运算，并将结果代替该运算对象进栈，最后结果留在栈顶。,50页,Page
7、17,例:将-B+C*D写成逆波兰记号，并分析的计算过程逆波兰记号：B-CD*+过程：1.B进栈 2.对栈顶的元素实施一元运算，并将 结果代替栈顶，即-B进栈 3.C进栈 4.D进栈 5.栈顶两元素相乘C D出栈，相乘结果进栈 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
8、页,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,命令的四元式：goto L 写成：(jump,L)if b rop c goto
9、L写成：(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:=E p:=lookup(id.name)；if pnil then emit(p:=Eplace)els
10、e error（2）EE1+E2 E.place:=newtemp；emilt(E.place:=E1.place+E2.place（3）EE1*E2 E.place:=newtemp;emit(E.place:=E1.place*E2.place)else error,赋值语句的翻译的属性文法,50页,Page25,（4）E-E1 E.place:=newtemp;emit(E.place:=uminus E1.place)（5）E(E1)E.place:=E1.place（6）Eid p:=lookup(id.name)if p nil then E.Place:=p；,50页,Page2
11、6,1)E.type表示E的类型信息，E.type的值或为int 或为real，2)整型加（乘）和实型加（乘),把十（*）分别 写作十i(*i)和十r(*r).3)用一目算符 itr表示将整型运算对象转换成实 型。,赋值语句的翻译的属性文法(带数据类型),50页,Page27,E.place:=newtemp;if E1.type=int AND E2.type=int then begin emit(E.Place，:=，E1.Place，*,E2.Place)E.type:=int end else if E1.type=real AND E2.type=real then begin e
12、mit(E.place，:=,E1.place,*r,E2.place)E.type:=real end,产生式 EE1*E2的翻译,50页,Page28,else lf E1.type=int/*and E2.type=real*/then begin t:=newtemp;emit(t，:=,itr,E1.place);emit(E.Place,:=,t,*r,E2.Place)；E.type:=realendelse/*E1.typereal and E2.type=Int*/begin t:=newremp；emit(t,:=;itr,E2.place)；emit(E.Place,:=
13、,E1.Place,*r,t)；E.type:=realend；,50页,Page29,布尔表达式的计算方法：1 or(not 0 and 0)or 01).按算术表达式一样计算 1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1,8.5.布尔表达式的翻译,50页,Page30,2)采用优化方法：1 or(not 0 and 0)or 0 or中任意一项为真，表达式为真,(1)t1:=not c(2)t2:=b and t1(3)t3:=a or t2,例.a or b and not c按方法一的翻译,50页,Page31
14、,(1).if ab goto(4)(2).t:=0(3).goto(5)(4).t:=1(5).,If ab then 1 else 0 的翻译,50页,Page32,EE1 or E2 E.Place:=newtemp;emit(E.place:=E1.place or E2.place)EE1 and E2 E.Place:=newtemp;emit(E.place:=E1.place and E2.place)Enot E1 E.Place:=newtemp;emit(E.place:=not E1.place)E(E1)emit(E.place:=E1.place),简单布尔表达式翻
15、译的属性文法,50页,Page33,Eid1 relop id2 E.Place:=newtemp;emit(if id1.place relop id2.place goto nextstat+3);emit(E.Place:=0);emit(goto nextstat+2);emit(E.Place:=1)Etrue E.Place:=newtemp;emit(E.Place:=1)Efalse E.Place:=newtemp;emit(E.Place:=0),50页,Page34,S if E then S1|if E then S1 else S2|while E do S1,控制语
16、句的布尔表达式的翻译,50页,Page35,E.ture 表达式为真转向的目标语句 E.false表达式为假转向的目标语句实例if af then S1 else s2的布尔表达式的翻译：,50页,Page36,(1).if af goto(7)(6)goto(p+1)(7)s1的四元式.(p)goto(q)P+1的四元式.(q),回填与拉链,产生四元时不知道,50页,Page37,(10)goto E.true(10).goto(0).(20)goto E.true(20)goto(10).(30)goto E.true(30)goto(20).(40)goto E.true(40)goto
17、(30),50页,Page38,Nextstat指向下一四元式的地址Merge(p1,p2)把p1和p2为首的两条链合并成一条 返回合并后的链首值，即将p2链尾第四区段 改为p1,合并后的链首为P2backpatch(p,t)把p链第四区段填为tE.codebegin E的第一个四元式的地址,控制语句的布尔表达式的翻译文法,50页,Page39,EE1 or E2 backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge(E1.true,E2.true)E.false:=E2.false,50页,Page4
18、0,EE1 and E2backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false)E not E1E.true:=E1.true E.codebegin:=E1.codebegin;E.false:=E1.true,50页,Page41,E(E1)E.true:=E1.true E.codebegin:=E1.codebegin;E.false:=E1.falseEid1 relop id2E.true:=nextstat;E.codebe
19、gin:=nextstat;E.false:=nextstat+1;emit(if id1.place rop id2.place goto-)emit(goto-);,50页,Page42,Etrue E.true:=nextstat;E.codebegin:=nextstat;emit(goto-);Efalse E.false:=nextstat;E.codebegin:=nextstat;emit(goto-);,50页,Page43,50页,Page44,50页,Page45,归约cd 产生式102:if cd goto 103:goto-,E1.codebegin=102E.tru
20、e=102E.false=103,50页,Page46,归约ef104:if ef goto 105:goto-,E2.codebegin=104E.true=104E.false=105,50页,Page47,EE1 and E2backpatch(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,
21、50页,Page48,backpatch(E1.true,E2.codebegin)=backpatch(102,104)E.false:=merge(E1.false,E2.false)=merge(103,105)E.true=104100:if ab goto 101:goto-102:if cd goto 104103:goto 104:if ef goto 105:goto 103,E.codebegin=102E.true=104E.false=103,105,50页,Page49,EE1 or E2 backpatch(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,
