第8章 语法制导翻译和中间代码(4学时).ppt

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 Li

4、d, L.in := T.type , T.type := char , 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; e

5、lse error(); , E.type:=T.type; E.val:=T.val , getType(F.type, id.entry); F.val:=id.lexval; ,语法制导翻译的实质： 根据每个产生式所对应的语义规则，随语法分析的每一步（推导或归约），执行相应的语义动作。 语法制导翻译的过程： 对单词符号串进行语法分析，构造语法分析树； 然后根据需要构造属性依赖图，遍历语法树，并在语法树的各结点处按语义规则进行计算。,8.2 语法制导翻译概论,使用“依赖图”，从依赖图的拓扑排序中得到计算语义规则的顺序，再依照顺序对输入串进行语义分析。 依赖图 一个有向图，用于描述分析树中的

6、属性和属性之间的相互依赖关系。 构造依赖图举例：参见P172 图8.4 属性计算方法 树遍历：事先建立语法树，（深度优先）遍历直至计算出所有属性值。 一遍扫描：在语法分析的同时计算属性值。,计算语义规则,属性： 综合属性：可以在分析输入串的同时，自下而上地来计算。如：val 继承属性：一个结点的继承属性值是由此结点的父结点和（或）兄弟结点的某些属性来决定的。如：L.in 属性文法： S-属性文法：L-属性文法的一个特例 L-属性文法：例1就是一个L-属性文法 属性文法的计算：可以是普通意义上的数学运算，也可以是打印输出等动作。,属性文法的类型和计算,S-属性文法：是L-属性文法的一个特例，只含

7、有综合属性。例2是一个S-属性文法。 S-属性文法翻译器：可以借助LR分析器实现。 实现原理：LR分析器中增加一个栈（语义值栈）用来存放综合属性的值，进行归约的同时，栈中正在归约的产生式右部符号的综合属性值弹栈，并调用相应语义子程序进行相应计算（完成属性文法中的语义规则），产生的新值入语义值栈。 举例：参见P174 图8.7,S-属性文法和自下而上翻译,L-属性文法：对于文法中的每个产生式AX1X2Xn，其每个语义规则中的每个属性要么是综合属性，要么是Xj(1jn)的一个继承属性且该继承属性仅依赖于：产生式中X1,X2,Xj-1的属性和A的继承属性。 L-属性文法优点：允许一次遍历就计算出所有

8、属性值。,L-属性文法,L-属性文法翻译器：可以借助LL分析器实现。 实现原理：在自顶向下分析的过程中，每应用一个产生式进行推导，同时完成该产生式上属性文法的计算。 LL(1)分析方法的语义描述：语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。这样的语义描述称为翻译模式。 举例：P174 例8.3 例8.4,L-属性文法在自上而下分析中的实现,翻译模式：语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。 翻译模式是适合语法知道翻译的另一种描述形式。 翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表现出来。,翻译模式,何时将属性文法改写成翻译模式？ 消除左递归时，原属性

9、文法将被改成翻译模式。 如何将属性文法改写成翻译模式？ 原文法：AA1YA.a=g(A1.a,Y.y) AXA.a=f(X.x) 翻译模式：AXR.i=f(X.x)RA.a=R.s RYR1.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)(=

11、,(3),a),四元式,四元式的格式：(算符, 第一运算对象, 第二运算对象, 结果) 如：a=b*c+b*d 的四元式表示如下,特点：利于代码优化和目标代码生成 特例：goto L 的四元式为（jump,-,-,L） if B rop C goto L的四元式为(jrop,B,C,L),8.4 简单赋值语句的翻译,说明： 1） 表示id所表示的单词，用作语义变量 2）lookup() 审查是否出现在符号表 是：返回指向该登录项的指针 否：返回 nil 3）emit 将四元式输出到中间文件（或目标文件）上 4）newtemp 生成一临时变量 5）E.p

12、lace 存放 E值的变量名在符号表的登录项 若变量为临时变量，则直接存放一整数码,8.4 简单赋值语句的翻译,例3 将赋值语句翻译成四元式的语义描述： S id := E E E1 + E2 E E1 * E2 E -E1 E (E1) E id,S id := EP:=lookup () ;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:= new

13、temp; 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) Eid p:=lookup(); if (p!=nil) E.place=p; else error();,8.5 布尔表达式的翻译,1、布尔表达式的作用： 计算逻辑值 （返回真 / 假 ） 控制流语句中的条件表达式 if() then while() 2、布尔表达

14、式的文法 EE and E EE or E Enot E Eid rop id Etrue Efalse,3、布尔表达式的计算方法： 一步一步计算出式中各部分真假，最终算出整个表达式的值 采用优化措施，只计算部分表达式值即可 例如： a and b/a为0时，b无论是什么表达式的值都为0 a or b/a为1时，b无论是什么表达式的值都为1,8.5 布尔表达式的翻译,例如 a or b and not c 对应的四元式 (1) (not,c,-,t1) (2) (and,b,t1,t2) (3) (or,a,t2,t3),布尔表达式的翻译,Enot E1 E.true := E1.false;

15、 E.codebegin := E1.codebegin; E.false := E1.true; ,(2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.codebegin := E1.codebegin; E.true := E2.true; E.false := merge(E1.false, E2.false);,(3) EE1 or E2 backpatch(E1.false, E2.codebegin); E.codebegin := E1.codebegin; E.true := merge(E1.true, E2.true); E

16、.false := E2.false;,布尔表达式译为四元式的语义描述：,(4) E(E1) E.true := E1.true; E.codebegin := E1.codebegin; E.false := E1.false; ,(5) Eid1 rop id2 E.true := nextstat; E.codebegin := nextstat; E.false := nextstat + 1; emit(if,id1.place,rop,id2.place,goto,); emit(goto,-);,(6) Eid E.true := nextstat; E.codebegin :=

17、 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 对应的四元式,For循环语句的翻译,I:=1 got

18、o (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) (-,