语义分析和中间代码生成课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 语义分析和中间代码的产生,紧接在词法分析和语法分析之后，编译程序要做的工作是进行,静态语义检查,和,翻译,。,静态语义检查通常包括：,类型检查。操作数和操作符类型一致,控制流检查。控制转移到合理的位置,一致性检查。变量只能被声明一次，同一,case,语句的标号不能相同，枚举类型的元素不能相同,相关名字检查。同一名字必须出现两次以上,翻译为中间语言的好处,（1）便于进行与机器无关的代码优化；,（2）使编译程序改变目标机更容易；易于编译器的移植,（3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。,主要内容,中间语言的形式,后缀式，图表方法，三元式,编译过程中不同语言的翻译或处理方法,说明语句的翻译,赋值语句的翻译,布尔表达式的翻译,控制语句的翻译,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的后缀式就是E的后缀式。,后缀式的优点,便于计算机处理,，因为在后缀式中，表达式的求值顺序与运算符出现的顺序一致，这样只要用一个栈就可以实现表达式的求值。,实现过程：自左向右扫描后缀表达式；遇到运算对象入栈，遇到N元运算符，就从栈顶取出N个运算对象进行计算，再将结果入栈；当全部后缀表达式扫描结束，则栈顶的值即为表达式结果。,后缀式特点：,无括号,运算对象的顺序与中缀式一致,根据操作符（运算符）的优先级和结合性进行相关的处理,例： 5+4*6,5 4 6 *+,7.1.2 图表示法,图表示法包括DAG与AST(抽象语法树)。,有向无环图（Directed Acyclic Graph , 简称 DAG ).,与抽象语法树一样，对于表达式中的每个子表达式，DAG图中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。,两者不同的是，在DAG图中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。,例：,5+4*6的DAG图,5,+,6,4,*,5+4*6+4*6 的DAG图,5,+,6,4,*,+,5+4*6+4*6 的AST图,5,+,6,4,*,+,6,4,*,后缀式与抽象语法树的关系,后缀式是抽象语法树的线性表示：每个结点都是在它的所有子节点之后立即出现的。,通过对抽象语法树的不同形式的遍历可以形成不同形式的缀式表达式,前序遍历：前缀式,中序遍历：中缀式,后序遍历：后缀式,5,+,6,4,*,+,6,4,*,产生赋值语句抽象语法树的属性文法,S.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr),E.nptr:=mknode(+,E1.nptr,E2.nptr),E.nptr:=mknode(*,E1.nptr,E2.nptr),mkleaf(id,id.place),Sid:=E,EE1+E2,EE1*E2,E-id,产生式,语义规则,S.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr),E.nptr:=mknode(+,E1.nptr,E2.nptr),E.nptr:=mknode(*, E1.nptr, E2.nptr),E.nptr:=mkleaf(id,id.place),mkleaf(id,id.place),Sid:=E,EE1+E2,EE1*E2,E-id,a:=b+c,a,b,c,+,:=,抽象语法树的存储表示,二叉树的形式,：算术运算通常都是二元运算,树中每个节点包含三个域：,数组的形式表示,：每一个数组元素形式如下：,节点类型 | 操作数1 | 操作数2,节点类型 | 操作数1 | 操作数2,*,uminus,id,c,id,b,赋值语句：a:=b*-c+b*-c,后缀式：a b c uminus * b c uminus * + assign,assign,+,*,uminus,id,a,id,c,id,b,id b,id c,unimus,1,* 0 2,id b,id c,unimus,5,* 4 6,+ 3 7,id a,assign,9 8,.,7.1.3 三地址代码,三地址代码是由下面一般形式的语句构成的序列:,X:=y op z,其中，x、y、z为名字、常数或编译时产生的,临时变量,（存放中间结果，对应于语法树的内部节点）；,op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。,每个语句的右边只能有一个运算符,。,每条语句通常包含三个地址：两个操作数地址，一个操作结果地址,三地址码示例,t1 ： -c,t2 ： b* t1,t3 ： -c,t4 ： b* t3,t5 ： t2+t4,a ： t5,assign,a,+,*,b,c,uminus,*,uminus,c,b,a:=b*-c+b*-c,三地址码示例（2）,assign,a,+,*,b,c,uminus,t1：-c,t2 ： b* t1,t5：t2+t2,a：= t5,a:=b*-c+b*-c,三地址代码的具体表示,1四元式： op, arg1, arg2, result,(0),(1),(2),(3),(4),(5),uminus,*,uminus,*,+,assign,c,b,c,b,t2,t5,arg1,t1,t3,t4,arg2,result,t1,t2,t3,t4,t5,a,op,t1 ： -c,t2 ： b* t1,t3 ： -c,t4 ： b* t3,t5 ： t2+t4,a ： t5,a:=b*(-c)+b*(-c),三地址代码的具体表示,2.三元式: op, arg1, arg2,(0),(1),(2),(3),(4),(5),uminus,*,uminus,*,+,assign,c,b,c,b,（1）,a,arg1,(0),(2),(3),(4),arg2,op,t1 ： -c,t2 ： b* t1,t3 ： -c,t4 ： b* t3,t5 ： t2+t4,a ： t5,a:=b*(-c)+b*(-c),三地址代码的具体表示,3.间接三元式: 间接码表+三元式表,目的：便于优化处理,t1 ： -c,t2 ： b* t1,t3 ： -c,t4 ： b* t3,t5 ： t2+t4,a ： t5,(1),(2),(3),(4),uminus,*,+,assign,c,b,（2）,a,arg1,(1),(2),(3),arg2,op,间接代码表,(1),(2),(1),(2),(3),(4),a:=b*(-c)+b*(-c),t1 ： a+b,t2 ： t1*c,X ： t2,t3 ： a+b,t4 ： dt3,Y ： t4,(1),(2),(3),(4),(5),+,*,:=,:=,a,(1),x,d,Y,arg1,b,c,(2),(1),(4),arg2,op,间接代码表,(1),(2),(3),(1),(4),(5),X：=(a+b)*c,Y:=d(a+b),语义分析中各种语句的处理,说明语句的翻译,赋值语句的翻译,布尔表达式的翻译,控制语句的翻译,7.2 说明语句的翻译,说明语句的处理方式：不生成可执行代码，只涉及符号表的操作。,说明语句的处理:,对每个局部名字，在符号表中建立相应的表项，填写有关的信息 如类型、嵌套深度、相对地址等。,相对地址：,相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。,因为,每进入一次过程需分配一次内存,，因此在处理过程内的说明语句时，要分配每个标识符的相对地址。设变量offset用来记录相对地址，每次进入一个过程，先将offset置为0。每次遇到一个新名字，则把名字同offset的当前值一起录入符号表，然后offset的值增加，其增加的值由该名字的数据类型所决定，称为数据对象的宽度，用属性width表示。假设integer型对象宽度为4，real型对象宽度为8，则下表为过程中说明语句的翻译方案。,过程中的说明语句的翻译,PD,offset：0,DD; D,Did ：T,enter（id.name，T.type，offset）； offset:=offsetT.width,Tinteger,T.type ：=integer; T.width：= 4,Treal,T.type：real; T.width ：8,Tarraynumof T1,T.type:array（num.val, T1.type ）； T.width： num.val *T1.width,T T1,T.type:pointer（T1type）；,T.width ：= 4,7.3 赋值语句的翻译,在本节中赋值语句中的表达式的类型可以是整型、实型、数组和记录。,作为翻译赋值语句为三地址代码的一部分,我们将主要讨论:,简单赋值语句的翻译,7.3.1 简单算术表达式及赋值语句的翻译,所讨论的简单赋值语句不包含对数组元素、记录元素的引用，仅包含对简单变量的算术表达式的引用。并且假定赋值语句中所有变量均为同一类型，不必考虑类型转换的问题。,简单赋值语句的文法Gs如下：,Sid:=E,E E+T|T,T T*F|F,F (E)|id,分析文法GS，可以看到文法中包含两类不同语义操作的产生式，一类含有运算符操作，一类仅含有传值操作。因此，要使语义分析后能产生三地址语句中间代码，应该对这两类不同的产生式进行不同的处理，含有运算符操作的产生式的语义动作应该产生相应的三地址语句，而仅含有传值操作的产生式则只进行传值的语义处理。根据这种思想，可以构造出各产生式的语义子程序如下表所示。,产生赋值语句三地址代码的翻译模式,Sid:=E p:=looku);,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.place:=E1.place*E2.place),E -E,E.place:=newtemp,;,emit(E.place := uminusE1.place,E(E1) E.place:=E1.place,Eid p:=looku);,if pnil then E.place:=p else error,有关说明：(1)语义变量Eplace：表示存放E值的变量名在符号表的位置或一整数码(若此变量是一个临时变量)；,(2)语义变量idname：表示单词id的名字；,(3)语义过程newtemp:表示生成一个临时变量,每调用一次,生成一新的临时变量；,(4)语义过程,lookup,：表示检查idname是否出现在符号表中，若在则返回一指向该登记项的指针，否则返回nil：,(5)语义过程emit：表示产生三地址语句并输出到文件上。,t1 ： -c,t2 ： b* t1,t3 ： -c,t4 ： b* t3,t5 ： t2+t4,a ： t5,assign,a,+,*,b,c,uminus,*,uminus,c,b,a:=b*-c+b*-c,产生赋值语句三地址代码的翻译模式,Sid:=E p:=looku);,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.place:=E1.place*E2.place),E -E ,E.place:=newtemp,;,emit(E.place := uminusE1.place,E(E1) E.place:=E1.place,Eid p:=looku);,if pnil then E.place:=p else error,7.4 布尔表达式的翻译,布尔表达式:,用布尔运算符号（and，or，not）作用到布尔变量或关系表达式上而组成。,布尔表达式的作用：,1. 用作计算逻辑值,2. 用作控制流语句如if-then，if-then-else和 while-do等之中的条件表达式,一个布尔表达式的值的计算,方法一,：用数值表示真和假，从而对布尔表达式的求值，可以象对算术表达式的求值那样一步一步地来计算,方法二,：优化的方法。,A or B,解释成,if A then true else B,A and B,解释成,if A then B else false,not A,解释成,if A then false else true,7.4.1 数值表示法的翻译 （用作计算逻辑值）,用1表示真，0表示假来实现布尔表达式的翻译,例如，布尔表达式,：a or b and not c,翻译成三地址代码序列：,100 ： t1:=not c,101 ： t2:=b and t1,102 ： t3:=a or t1,or,a,and,b,c,not,关系表达式,：,ab,等价于,if ab then 1 else 0,翻译成三地址代码序列：,100,：,if a,b,goto,l03,101,：,t,：,=0,102,：,goto,l04,103 : t:=1,104,：,关于布尔表达式的数值表示法的翻译模式,EE1 or E2,E.place:=newtemp; emit(E.place := E1.place or E2.place),EE1 and E2,E.place:=newtemp;,emit(E.place:=E1.placeand E2.place),Enot E1,E.place:=newtemp;,emit(E.place:= not E1.place),Eid1 relop id2,注：,relop,是关系运算符, E.place:=newtemp;,emit(if id1.place relop.op id2.place goto nextstat+3);,emit(E.place:=0);,emit(gotonextstat,+2,);,emit(E.place:= 1),Eture,E.place:=newtemp; emit(E.place:= 1),Efalse,E.place:=newtemp; emit(E.place:= 0),ab 的翻译：,100 ： if ab goto,l03,101 ： t：=0,102 ： goto l04,103 : t:=1,104：,例： 考虑如下语句：,X=a,b and cd or ef,a, b,E,and,C d,E,or,e f,E,E,E,100:if ab goto 103,101:,t1=0,102:goto 104,103:,t1=1,104:if cd goto 107,105:,t2=0,106:goto 108,107:,t2=1,109:if ef goto 112,110:,t4=0,111:goto 113,112:,t4=1,X =,S,108：,T3,=t1 and t2,113：T5=t3 or t4,114：x:=t5,7.4.2 作为条件控制语句的布尔表达式的翻译,(采用简化的方法进行布尔表达式的计算),文法： if E then S1 else S2,E.code,S1.code,E.true:,Goto s.next,E.false:,to E.true,to E.false,生成的代码结构：,S2.code,S.next:,控制语句中的条件表达式翻译的基本思想,给控制语句中的条件表达式设两个属性：E.true,和E.false，记录控制语句所转向的两个语句的标号。对条件表达式的翻译如下：,E: ab, 生成如下的代码,If ab goto E.true,Goto E.false,E.code,S1.code,E.true:,Goto s.next,E.false:,to E.true,to E.false,S2.code,s.next:,控制语句中的条件表达式翻译的基本思想,假定E形如E1 or E2。若E1为真，则立即可知E为真，于是E1.true与E.true是相同的。若El为false则必须对E2求值，因此我们置E1.false：为E2的代码的第一条指令的标号。而E2的真、假出口可以分别与E的真、假出口相同。类似可考虑形如E1 and E2的E的翻译。至于形如not E1的布尔表达式E不必生成新的代码，只要把E1的假、真出口作为E的真、假出口即可。按此方式可以写出布尔表达式译成三地址代码的语义规则。,注意E的true和false属性均为继承属性。,E: E1 or E2,E1.true=E.true, E1.false=E2的第一条代码,E2.true=E.true, E2.false=E.false,控制语句中的条件表达式翻译的基本思想,E: E1 or E2,E1.true=E.true,E1.false=E2的第一条代码,E2.true=E.true,E2.false=E.false,E1.code,S1.code,E.true:,Goto s.next,E.false:,to E.true,to E.false,S2.code,s.next:,E2.code,to E.true,to E.false,控制语句中的条件表达式翻译的基本思想,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.true,to E.false,S2.code,s.next:,E2.code,to E.true,to E.false,产生式,语义规则,EE1 or E2,E1.true:=E.true;,E1.false:=newlabel;,E2.true:=E.true;,E2.false:=E.false,E.code:=E1.code|,gen(E1.false:)|E2.code,产生式,语义规则,EE1 and E2,E1.true:= newlabel;,E1.false:= E.false;,E2.true:=E.true;,E2.false:=E.false;,E.code:=E1.code,gen(E1.true:) E2.code,Enot E1,E1.true:= E.false;,E1.false:= E.true;,E.code:=E1.code,产生式,语义规则,Eid1 relop,id2,E.code:=gen(if id1.place,relop.op id2.place,goto E.true)|,gen(goto E.false),Etrue,E.code:=gen(goto E.true),Efalse,E.code:=gen(goto E.false),E的true和false属性都是继承属性，E.code是综合属性。因此该语义规则的不能通过一遍扫描完成。,E(E1),E1.true:= E.true;,E1.false:= E.false;,E.code:=E1.code,例： 考虑如下语句：,ab or cd and ef,假定整个表达式的真假出口分别置为,Ltrue,和,Lfalse,a, b,E,or,C d,E,and,e f,E,E,E,if ab goto E.,true,goto,E.false,if cd goto E.true goto,E.false,if ef goto,E.true,goto E.,false,if cd goto,E.true,goto,E.false,L2,:if ef goto,E.true,goto E.,false,if ab goto E.,true,goto,E.false,L1,:,if cd goto E.true goto,E.false,L2,:if ef goto,E.true,goto E.,false,例： 考虑如下语句：,ab or cd and ef,假定整个表达式的真假出口分别置为,Ltrue,和,Lfalse,a, b,E,or,C d,E,and,e f,E,E,E,if cd goto,L2,goto,Lfalse,L2,:if ef goto,Ltrue,goto L,false,if ab goto,Ltrue,goto,L1,L1,:,if cd goto L2 goto,Lfalse,L2,:if ef goto,Ltrue,goto,Lfalse,L1:,L2:,if ab goto E.,true,goto,E.false,if cd goto E.true goto,E.false,if ef goto,E.true,goto E.,false,例： 考虑如下语句：,a,b and cd or ef,a, b,E,and,C d,E,or,e f,E,E,E,if ab goto E.,true,goto,E.false,if cd goto,E.true,goto,E.false,if ef goto,E.true,goto E.,false,if ab goto,E.true,goto,E.false,L1,:if cd goto,E.true,goto,E.false,if ab goto,E.true,goto,E.false,l1,:,if cd goto,E.true,goto,E.false,l2,:if ef goto,E.true,goto E.false,L1:,L2:,例： 考虑如下语句：,a,b and cd or ef,a, b,E,and,C d,E,or,e f,E,E,E,if ab goto,E.true,goto,E.false,L1,:,if cd goto,E.true,goto,E.false,L2,:if ef goto,E.true,goto E.false,L1:,L2:,if ab goto,L1,goto,E.false,L1,:,if cd goto,E.true,goto,L2,L2,:if ef goto,E.true,goto E.false,我们假设实现三地址代码时采用四元式形式实现，并且假定：,（jnz,a ,- , p) 表示 if a goto p,(jrop,x,y, p) 表示 if x rop y goto p,(j,-,-， p ) 表示 goto p,控制语句中布尔表达式的翻译模式,一遍扫描的,表达式翻译中存在的问题：,生成某些转移语句时，转移到的目标的标号是未知的,解决方案：当目标语句的标号确定后，进行,回填,用四元式表示,1,: (j,a,b,3,),2,: (j,-,-,6,),3 : (+,a,1,t1),4 :,(:=,t1,-,a),5 :,(j,-,-,8,),6 : (+,b,1,t2),7 :,(:=,t2,-,b),8 ： ,例： if ab then a:=a+1 else b:=b+1,7.5 控制语句的翻译,任何程序都可有顺序结构、选择结构和while循环结构表示，这三类结构可用如下的文法描述：,（1）Sif E then S,（2） | if E then S else S,（3） | while E do S,（4） | begin L end,（5） | A,（6）LL；S,（7） |S,S,表示语句,E,为一个布尔表达式,L,表示语句块,A,为赋值语句,控制流语句的翻译模式,：,S,if E then S,1,的四元式序列,1.(j,E,-,3),2.(j,-,-,q),3.,q.,S1的四元式序列,2. S,if E then,S1 else S2,的四元式序列,1. (j,E,-,3),2. (j,-,-,p+1),3.,p.,(j,-,-,q,),p+1.,q. ,S1的四元式序列,S2的四元式序列,3. S,while E do S1,的四元式序列,1. (j,E,-,3),2. (j,-,-,p+1),3.,p.,(j,-,-,1,),p+1. ,S1的四元式序列,（4） S,begin L end,（5） S,A,（6） LL；S,（7） S,S 1,语句块L的四元式序列,赋值语句A的四元式序列,语句块L的四元式序列,语句S的四元式序列,语句S1的四元式序列,翻译为四元式,例： 将语句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,),例： 考虑如下语句：,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, 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),107 (j, -, - ,113),108 (-,x,1,t3),(:=,t3,-,x),(+,y,2,t4),(:=,t4,-,y),(j, -, - ,106),本章小结,中间代码形式：逆波兰式、图形表示、三元式、间接三元式、四元式,语句翻译：说明语句的翻译、赋值语句的翻译、布尔表达式的翻译、控制语句的翻译,习题,一、多项选择,A C,B D,A B C D,A,A,二、判断题,三、解答题,1、把下列语句翻译为四元式序列,100 (j, A, C,?),(j, -, - ,?),102 (j, B, D,?),103 (j, -, - ,?),104 (j=, A, 1,?),105 (j, -, - ,?),114 (j, -, - ,?),(+,C,1,t1),(:=,t1,-,C),(j, -, - ,?),(j, A, D,?),(j, -, - ,?),111 (+,A,2,t2),112 (:=,t2,-,A),113 (j, -, - ,?),115 ,100 (j, A, C,102),(j, -, - ,115),102 (j, B, D,104),103 (j, -, - ,115),104 (j=, A, 1,106),105 (j, -, - ,109),(+,C,1,t1),(:=,t1,-,C),(j, -, - ,100),(j=, A, D,111),(j, -, - ,100),111 (+,A,2,t2),112 (:=,t2,-,A),113 (j, -, - ,109),114 (j, -, - ,100),2、把下列表达式翻译为逆波兰式、三元式、间接三元式、四元式。,a=(b+c)*e+(b+c)/f,解:,(1),逆波兰式：bc+e*bc+f/+,(2)三元式:,(3),间接三元式:,(4)四元式:,课后练习,P217-1，3,P218-6,7,