《语法制导翻译和中间代码(8学时).ppt》由会员分享,可在线阅读,更多相关《语法制导翻译和中间代码(8学时).ppt(41页珍藏版)》请在三一办公上搜索。
1、第8章 语法制导翻译和中间代码,属性文法语法制导翻译中间代码的形式逆波兰式、三元式、树形表示、四元式一些语句的翻译 赋值语句 布尔表达式 控制语句中的布尔表达式 For循环语句,8.1 属性文法,预备知识源程序与目标程序,语法结构完全不同,但语义相同,所以表达的结果完全相同。语义分析的2种处理方法:1)语法分析之后,直接调用相应的“语义子程序”进行语义处理2)语法分析之后,先生成“语法树”或其他形式,再进行语义处理语义分析的处理结果:1)目标代码2)中间代码:复杂性介于源程序语言和机器语言之间,静态语义分析:审查语法结构的静态语义 确定标识符的数据类型 类型检查和转换:检查运算对象的数据类型是
2、否合法,必要时进行类型转换 一致性检查:一个对象只能被声明一次 作用域检查 控制流检查:控制语句转到合法的地方继续执行翻译(若静态语义分析正确后才翻译),语义处理的任务和功能,常用的语义分析方法语法制导翻译语法制导翻译:首先,使用属性文法为工具,描述程序设计语言的语义规则。在语法分析时,每应用一个产生式(推导或归约),同时完成该产生式上所附的语义规则描述的动作,从而完成语义处理。,语义分析的方法,用于描述语义规则的文法。对文法的每个符号引入一些属性,这些属性代表与文法符号相关的信息,例如:类型、值、代码序列、符号表内容等。属性值可以在语法分析过程中进行计算和传递。属性的加工过程就是语义的处理过
3、程。,属性文法(attribute grammar),属性文法的组成:一个上下文无关文法 一系列语义规则(附在文法的每个产生式上)属性文法的形式:三元组 A=(G,V,F)G:是一个上下文无关文法V:有穷属性集,每个属性与文法的一个终结符或非终结符关联F:关于属性的断言或谓词集.每个断言与一个产生式关联.而此断言只引用该产生式的终结符或非终结符相关联的属性,属性文法(attribute grammar),属性文法 举例,例1 说明语句中各种变量的类型信息的语义规则:产生式语义规则 DTL Tchar Tint Tfloat LL1,id Lid,L.in:=T.type,T.type:=cha
4、r,T.type:=int,T.type:=float,L1.in:=L.in addtype(id.entry,L.in),addtype(id.entry,L.in),属性文法 举例,例2 表达式类型检查和求值的语义规则:假设:类型不同的两个变量进行运算则语义错误。产生式语义规则 LE EE1+T ET TT1*F TF F(E)Fid,print(E.val);,if(E1.type=T.type)E.type:=E1.type;E.val:=E1.val+T.val;else error();,E.type:=T.type;E.val:=T.val,getType(F.type,id.
5、entry);F.val:=id.lexval;,语法制导翻译的实质:根据每个产生式所对应的语义规则,随语法分析的每一步(推导或归约),执行相应的语义动作。语法制导翻译的过程:对单词符号串进行语法分析,构造语法分析树;然后根据需要构造属性依赖图,遍历语法树,并在语法树的各结点处按语义规则进行计算。,8.2 语法制导翻译概论,使用“依赖图”,从依赖图的拓扑排序中得到计算语义规则的顺序,再依照顺序对输入串进行语义分析。依赖图一个有向图,用于描述分析树中的属性和属性之间的相互依赖关系。构造依赖图举例:参见P172 图8.4属性计算方法 树遍历:事先建立语法树,(深度优先)遍历直至计算出所有属性值。一
6、遍扫描:在语法分析的同时计算属性值。,计算语义规则,属性:综合属性:可以在分析输入串的同时,自下而上地来计算。如:val继承属性:一个结点的继承属性值是由此结点的父结点和(或)兄弟结点的某些属性来决定的。如:L.in属性文法:S-属性文法:L-属性文法的一个特例L-属性文法:例1就是一个L-属性文法属性文法的计算:可以是普通意义上的数学运算,也可以是打印输出等动作。,属性文法的类型和计算,S-属性文法:是L-属性文法的一个特例,只含有综合属性。例2是一个S-属性文法。S-属性文法翻译器:可以借助LR分析器实现。实现原理:LR分析器中增加一个栈(语义值栈)用来存放综合属性的值,进行归约的同时,栈
7、中正在归约的产生式右部符号的综合属性值弹栈,并调用相应语义子程序进行相应计算(完成属性文法中的语义规则),产生的新值入语义值栈。举例:参见P174 图8.7,S-属性文法和自下而上翻译,L-属性文法:对于文法中的每个产生式AX1X2Xn,其每个语义规则中的每个属性要么是综合属性,要么是Xj(1jn)的一个继承属性且该继承属性仅依赖于:产生式中X1,X2,Xj-1的属性和A的继承属性。L-属性文法优点:允许一次遍历就计算出所有属性值。,L-属性文法,L-属性文法翻译器:可以借助LL分析器实现。实现原理:在自顶向下分析的过程中,每应用一个产生式进行推导,同时完成该产生式上属性文法的计算。LL(1)
8、分析方法的语义描述:语义动作不是附在产生式右部的末尾,而是嵌在两个符号之间。这样的语义描述称为翻译模式。举例:P174 例8.3 例8.4,L-属性文法在自上而下分析中的实现,翻译模式:语义动作不是附在产生式右部的末尾,而是嵌在两个符号之间。翻译模式是适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序,可把某些实现细节表现出来。,翻译模式,何时将属性文法改写成翻译模式?消除左递归时,原属性文法将被改成翻译模式。如何将属性文法改写成翻译模式?原文法:AA1YA.a=g(A1.a,Y.y)AXA.a=f(X.x)翻译模式:AXR.i=f(X.x)RA.a=R.s RYR1.
9、i=g(R.i,Y.y)R1 R.s=R1.s RR.s=R.i,改写成翻译模式,L-属性文法中,如何实现自下而上计算继承属性?方法1:去掉翻译模式中嵌入在产生式中间的动作。方法2:改变原文法或重新构造文法,用综合属性代替继承属性。自学(P176,177),L-属性文法在自下而上分析中的实现,8.3 中间代码的形式,中间代码的常见形式:逆波兰记号三元式树形表示四元式,逆波兰记号(后缀式),特点:将运算对象写在前面,把运算符号写在后面标识符顺序与表达式中的一致 运算符顺序与计算顺序一致 无括号,为什么要使用逆波兰式?更易于计算机处理,表示简洁、计算方便。,逆波兰记号的扩充用途,逆波兰式的复杂性:
10、压栈的可能是地址(如变量赋值),不是值;栈中不一定产生结果。,逆波兰式的计算机处理方法:自左向右扫描逆波兰式,遇到运算对象入栈,遇到算符则将相应数目的运算对象出栈计算后结果入栈。,三元式和树形表示,三元式的格式:(算符,第一运算对象,第二运算对象)如:a=b*c+b*d 的三元式和树形表示(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2)(4)(=,(3),a),四元式,四元式的格式:(算符,第一运算对象,第二运算对象,结果)如:a=b*c+b*d 的四元式表示如下,特点:利于代码优化和目标代码生成 特例:goto L 的四元式为(jump,-,-,L)if B rop C g
11、oto L的四元式为(jrop,B,C,L),8.4 简单赋值语句的翻译,说明:1)id.name 表示id所表示的单词,用作语义变量2)lookup(id.name)审查id.name是否出现在符号表是:返回指向该登录项的指针否:返回 nil3)emit 将四元式输出到中间文件(或目标文件)上4)newtemp 生成一临时变量5)E.place 存放 E值的变量名在符号表的登录项 若变量为临时变量,则直接存放一整数码,8.4 简单赋值语句的翻译,例3 将赋值语句翻译成四元式的语义描述:S id:=E E E1+E2E E1*E2E-E1E(E1)E id,S id:=EP:=lookup(i
12、d.name);if Pnil then emit(P,“:=”,E.place);elseerror();,(2)EE1+E2 E.place:=newtemp;emit(E.place,“:=”,E1.place,“+”,E2.place);,(3)EE1*E2 E.place:=newtemp;emit(E.place,“:=”,E1.place,“*”,E2.place);,(4)E-E1 E.place=newtemp;emit(E.place,:=,-,E1.place);(5)E(E1)E.place=newtemp;emit(E.place,:=,E1.place);(6)Ei
13、d p:=lookup(id.name);if(p!=nil)E.place=p;else error();,8.5 布尔表达式的翻译,1、布尔表达式的作用:计算逻辑值(返回真/假)控制流语句中的条件表达式 if()thenwhile()2、布尔表达式的文法 EE and E EE or EEnot EEid rop idEtrueEfalse,3、布尔表达式的计算方法:一步一步计算出式中各部分真假,最终算出整个表达式的值采用优化措施,只计算部分表达式值即可 例如:a and b/a为0时,b无论是什么表达式的值都为0a or b/a为1时,b无论是什么表达式的值都为1,8.5 布尔表达式的翻
14、译,例如 a or b and not c 对应的四元式(1)(not,c,-,t1)(2)(and,b,t1,t2)(3)(or,a,t2,t3),布尔表达式的翻译,Enot E1E.true:=E1.false;E.codebegin:=E1.codebegin;E.false:=E1.true;,(2)EE1 and E2backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false);,(3)EE1 or E2backpatch(E1.f
15、alse,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge(E1.true,E2.true);E.false:=E2.false;,布尔表达式译为四元式的语义描述:,(4)E(E1)E.true:=E1.true;E.codebegin:=E1.codebegin;E.false:=E1.false;,(5)Eid1 rop id2E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(if,id1.place,rop,id2.place,goto,);emit(g
16、oto,-);,(6)EidE.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(if,id1.place,goto,);emit(goto,-);,控制语句 S if E then S1 else S2,控制语句中布尔表达式的翻译,举例 将下列控制语句翻译成四元式if af then S1 else S2,控制语句中布尔表达式的翻译,if af goto(i+1)关于S2的四元式(i)goto(n)/n是S1的出口(i+1)关于S1的四元式(n),例 for I:=1 step 1 until N do M:=M+I
17、对应的四元式,For循环语句的翻译,I:=1 goto(4)I:=I+1 if I=N goto(6)goto(9)T:=M+I M:=T goto(3),课堂练习1(1)(2)(5)(6)(7)2 逆波兰式、三元式、四元式序列3 5 6 7,课后 1(1)a*(-b+c)abc+*(2)A(CD)ACD(5)-a+b*(-c+d)abcd+*+(6)(AB)(CDE)ABCDE(7)if(x+y)*z=0 then s:=(a+b)*c else s:=a*b*c,三元式序列(+,a,b)(-,(1),-)(+,c,d)(*,(2),(3)(+,a,b)(+,(5),c)(-,(4),(6),课后 2 逆波兰式、三元式、四元式序列逆波兰式:ab+cd+*ab+c+-,四元式序列(+,a,b,t1)t1:=a+b(-,t1,-,t2)t2:=-t1(+,c,d,t3)t3:=c+d(*,t2,t3,t4)t4:=t2*t3(+,a,b,t5)t5:=a+b(+,t5,c,t6)t6:=t5+c(-,t4,t6,t7)t7:=t4-t6,课后 3 步骤1:求LR分析表步骤2:增加一个语义栈,利用分析表,对句子进行语法分析的同时完成语义分析。,课后 5,课后6(2)写出“类型转换”和“后缀表达式的输出”的语义规则,