编译原理第七章课件——张淑艳.ppt

1、程序设计语言编译原理,张 淑 艳 zhang_shu_,第七章 语义分析和中间代码的产生,紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。 静态语义检查通常包括： 类型检查。操作数和操作符类型一致 控制流检查。控制转移到合理的位置 一致性检查。变量只能被声明一次，同一case语句的标号不能相同，枚举类型的元素不能相同 相关名字检查。有时，同一名字必须出现两次以上,翻译为中间语言的好处,（1）便于进行与机器无关的代码优化； （2）使编译程序改变目标机更容易；易于编译器的移植 （3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。,主要

2、内容,中间语言的形式 后缀式，图表方法，三元式 编译过程中不同语言的翻译或处理方法 说明语句的翻译 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译,7.1中间语言,中间语言的形式： 逆波兰表示：后缀式 图表示法：DAG 和AST 三地址代码:四元式、三元式、间接三元式,7.1.1 后缀式,后缀式：把操作数写在前面，把算符写在后面。 后缀式的构造方法： （1）如果E是一个变量或常量，则E的后缀式是E自身。 （2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为 E1 E2op,这里E1 和E2分别为E1和E2的后缀式。 （3）如果E是(E1)形式的表达式，则E1的

3、后缀式就是E的后缀式。,后缀式的优点,便于计算机处理，因为在后缀式中，表达式的求值顺序与运算符出现的顺序一致，这样只要用一个栈就可以实现表达式的求值。,例：5+4*6 5 4 6 *+,将表达式翻译为后缀式的语义规则,E.code表示E的后缀式，op为二元操作符，“|”表示后缀形式的连接。,7.1.2 图表示法,图表示法包括DAG(有向无环图)与AST(抽象语法树)。 相同点：对于表达式中的每个子表达式，图中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。 不同点：在DAG图中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。,5+4*6的

4、DAG图,5,+,6,4,*,5+4*6+4*6 的DAG图,5,+,6,4,*,+,5+4*6+4*6 的AST图,5+4*6的AST图,5,+,6,4,*,a:=b*-c+b*-c的DAG图,a:=b*-c+b*-c的AST图,后缀式与抽象语法树的关系,通过对抽象语法树的不同形式的遍历可以形成不同形式的缀式表达式 前序遍历：前缀式 中序遍历：中缀式 后序遍历：后缀式,产生赋值语句抽象语法树的属性文法,赋值语句：a:=b*-c+b*-c,后续遍历得后缀式：a b c uminus * b c uminus * + assign,7.1.3 三地址代码,三地址代码是由下面一般形式的语句构成的序

5、列: x:=y op z 每条语句通常包含三个地址：两个操作数地址，一个操作结果地址,三地址码示例,t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ： t5,a:=b*-c+b*-c,三地址码示例,t1：-c t2 ： b* t1 t5：t2+t2 a：= t5,a:=b*-c+b*-c,三地址代码的具体表示,1四元式： op, arg1, arg2, result,a:=b*(-c)+b*(-c),t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ： t5,三地址代码:四元式、三元式、间

6、接三元式,三地址代码的具体表示,2.三元式: op, arg1, arg2,a:=b*(-c)+b*(-c),t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ： t5,三地址代码的具体表示,3.间接三元式: 间接码表+三元式表 目的：便于优化处理,a:=b*(-c)+b*(-c),t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ： t5,语义分析中各种语句的处理,说明语句的翻译 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译,7.2 说明语句的翻译,说明语句的处理方式：不生成可执行代码

7、，只涉及符号表的操作。 说明语句的处理:对每个局部名字，在符号表中建立相应的表项，填写有关的信息 如类型、嵌套深度、相对地址等。 相对地址：相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。,7.3 赋值语句的翻译1.简单算术表达式和赋值语句,S id := E P:=lookup () ; if Pnil then emit( P“:=”E.place) else error EE1+E2 E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place) EE1*E2 E.place:= newtemp; emit(E.p

8、lace“:=” E1.place“*”E2.place) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place) E( E1) E.place:= E1.place Eid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error,lookup：表示检查idname是否出现在符号表中，若在则返回一指向该登记项的指针，否则返回nil：,7.4 布尔表达式的翻译,布尔表达式: 用布尔运算符号（and，or，not）作用到布尔变量或关系表达式上而组

9、成。 布尔表达式的作用： 1. 用作计算逻辑值 2. 用作控制流语句如if-then，if-then-else和 while-do等之中的条件表达式,7.4 布尔表达式的翻译,计算布尔表达式值的方法 如同计算算术表达式，一步步计算 如：1 and (0 or 1) and not 0 =1 and 1 and 1 =1 and 1 =1 采取某种优化措施 如：A or B 若A为1，则不用计算B,可知结果为1 可以if-then-else来解释 A or B if A then true else B A and B if A then B else false not A if A then

10、 false else true,用1表示真，0表示假来实现布尔表达式的翻译 例如，布尔表达式：a or b and not c 翻译成三地址代码序列： 100 ： t1:=not c 101 ： t2:=b and t1 102 ： t3:=a or t1,7.4.1 数值表示法的翻译,关系表达式 ab 等价于 if ab then 1 else 0 翻译成三地址代码序列： 100 ： if ab goto l03 101 ： t：=0 102 ： goto l04 103 : t:=1 104：,7.4.1 数值表示法的翻译,E E1 or E2 E E1 and E2 E not E 注

11、意E的true和false属性均为继承属性。,7.4.2 作为条件控制语句的布尔表达式的翻译,E E1 and E2 E1.true=E2的第一条语句; E1.false=E.false E2.true=E.true； E2.false=E.false,E1.code,S1.code,E.true:,Goto s.next,E.false:,to E.false,to E.true,S2.code,s.next:,E2.code,to E.true,to E.false,7.4.2 作为条件控制语句的布尔表达式的翻译,一遍扫描的表达式翻译中存在的问题： 生成某些转移语句时，转移到的目标的标号是

12、未知的 解决方案：当目标语句的标号确定后，进行回填,7.4.2 作为条件控制语句的布尔表达式的翻译,我们假设实现三地址代码时采用四元式形式实现，并且假定： （jnz,a ,- , p) 表示 if a goto p (jrop,x,y, p) 表示 if x rop y goto p (j,-,-， p ) 表示 goto p,7.4.2 作为条件控制语句的布尔表达式的翻译,转移到的目标标号,Sif E then S1 的四元式序列 1.(j, E, -, 3) 2.(j, -, -, q) 3. S1的四元式序列 q. ,7.5 控制语句的翻译,2. Sif E then S1 else S

13、2 的四元式序列 1. (j, E, -, 3) 2. (j, -, -, p+1) 3. S1的四元式序列 p. (j,- , -, q) p+1. S2的四元式序列 q. ,7.5 控制语句的翻译,用四元式表示 1 : (j, a, b, ) 2 : (j, -, -, ) 3 : (+, a, 1, t1) 4 : (:=, t1, -, a) 5 : (j, -, -, ) 6 : (+, b, 1, t2) 7 : (:=, t2, -, b) 8 ： ,例： if ab then a := a + 1 else b := b + 1,7.4.2 作为条件控制语句的布尔表达式的翻译,

14、3,6,8,?,?,?,翻译为四元式,例： 将语句if ab or cd and ef then s1 else s2,1 (j,a,b,?) 2 (j,-,- ,? ),3 (j,c,d,?) 4 (j,-,- ? ),5 (j,e,f,?) 6 (j,-,-,? ),7 S1的四元式序列 p (j,-,- ,?),p+1 S2的四元式序列 ,q ,1 (j, a, b, 7) 2 (j, -, - , 3 ),3 (j, c, d, 5) 4 (j, -, -, p+1 ),5 (j, e, f, 7) 6 (j, -, -,p+1 ),7 S1的四元式序列 p (j, -, - , q)

15、,3. S while E do S1 的四元式序列 1. (j, E, -, 3) 2. (j, -, -, p+1) 3. S1的四元式序列 p. (j, -, - , 1) p+1. ,7.5 控制语句的翻译,例：考虑如下语句： while ab do if cd then x：= yz,100 (j, a, b,?) 101 (j,-, -,?),106 (j, - ,-,100),104 (+,y,z,T) 105 (:=,T,-,x),102 (j, c, d,?) 103 (j, -, - ,?),102 (j, c, d,104) 103 (j, -, -,?),102 (j,

16、 c, d,104) 103 (j, -, -,100),100 (j, a, b,102) 101 (j,- , - ,?),107 ,100 (j, a, b,102) 101 (j,- ,- ,107),例：写出下列语句的四元式： if x=y+1 then x：= x*y else while x0 do begin x:=x-1;y:=y+2 end,100 (+, y, 1,t1) (j=,x, t1,?) (j, -, - ,?),103 (*,x,y,t2) (:=,t2,-,x) (j, -, - ,?),106 (j , x, 0,?) 107 (j, -, - ,?),113 ,108 (-,x,1,t3) (:=,t3,-,x) (+,y,2,t4) (:=,t4,-,y) (j, -, - ,?),100 (+, y, 1,t1) (j=,x, t1,103) (j, -, - ,106),103 (*, x, y, t2) (:=,t2,-, x) (j, -,- ,113),106 (j , x, 0,108) 10