程序设计语言编译原理(第三版)第7章.ppt

1,第七章语义分析和中间代码产生,一般情况下，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么，由语法分析程序直接调用相应的语义子程序进行语义处理；要么，首先生成语法树或该结构的某种表示，再进行语义处理。,2,语义处理分两步：1.静态语义分析，即验证语法结构合法的程序是否真正有意义。2.若静态语义正确，语义处理则要执行真正的翻译。即要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。,静态语义检查包括：（1）类型检查；（2）控制流检查；（3）一致性检查；（4）相关名字检查。,第七章语义分析和中间代码产生,3,中间代码：即中间语言，独立于机器的，复杂性介于源语言和机器语言之间的一种表示形式。,采用中间语言的好处：,第七章语义分析和中间代码产生,（1）便于进行与机器无关的代码优化工作；,（2）使编译程序改变目标机更容易；,（3）使编译程序的结构在逻辑上更为简单明确。,4,7.1 中间语言 7.2 说明语句 7.3 赋值语句的翻译 7.4 布尔表达式的翻译 7.5 控制语句的翻译 7.6 过程调用的处理（略）7.7 类型检查（略）,第七章语义分析和中间代码产生,5,7.中间语言,中间语言形式：后缀式三地址代码 图表示法,6,一、后缀式逆波兰式：,规则：,7.中间语言,(1)E常量变量：后缀式为E本身,(2)EE1 op E2：E1 E2 op,(3)E(E1)：(E1),(4)Eop E1：E1 op,7,7.中间语言,例子：,a*(b+c),(a+b)*(c+d),abc+*,x+yza0(8+z)3,ab+cd+*,xy+za08z+3,8,二、图表示法,1.DAG(无循环有向图)与抽象语法树对比 相同点:对表达式中的每个子表达式，它们都有一个结 点，一个内部结点代表一个操作符，它的孩子 代表操作数；不同点:在一个DAG中代表公共子表达式的结点具有多个 父结点，而在一棵抽象语法树中公共子表达式 被表示为重复的子树。,7.中间语言,9,例子：如图所示，为a+a*(b-c)+(b-c)*d的DAG,7.中间语言,10,2.抽象语法树,例子：(1)a:=b*-c+b*-c的图表示法,7.中间语言,11,(2)a:=b*-c+b*-c 的抽象语法树的两种表示法,012345678910,7.中间语言,12,三、三地址代码,1.三地址代码:下面一般形式的语句构成的序列:x:=y op zT1:=y*z,T2:=x+T1,称为三地址代码的原因:每条语句通常包含三个地址,两个用来表示操作数,一个用来存放结果。,7.中间语言,具体实现:用记录表示,其中包含运算符和操作数的域。,x,y,z:名字,常数,编译时产生的临时变量 op:运算符号(如定点运算符,浮点运算符,逻辑运算符等),13,2.四元式：带有四个域的记录结构,7.中间语言,(op，arg1，arg2，result),14,7.中间语言,例子:三地址语句a:=b*-c+b*-c的四元式表示,四元式表示,15,3.三元式：为了避免把临时变量填入符号表,可通过计算该临时变量值的语句的位置来引用该临时变量。,7.中间语言,（op，arg1，arg2）,16,7.中间语言,例子:三地址语句a:=b*-c+b*-c的三元式表示,17,4.间接三元式：便于代码优化处理方法：间接码表+三元式表,例:语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下所示:,三元式表,7.中间语言,18,7.2 说明语句,编译过程中,对“说明语句”要做的工作:,对一个过程或分程序的一系列说明语句,考察时:,(1)需要为局部于该过程的名字分配存储空间;,(2)对每个局部名字,都需在符号表中建立相应的表项,并填入有关的信息如类型、在存储器中的相对地址 等。,19,一、过程中的说明语句,1.产生“说明语句”的文法：,PDDD;DDid:T TintegerTrealTarraynum of T1TT1,7.2 说明语句,20,2.处理方式：处理第一条说明语句之前，先置offset为0，以后每次遇到一个新的名字，则:(1)将该名字填入符号表中,(2)置相对地址为当前offset之值，(3)使offset加上该名字所表示的数据对象的域宽。,7.2 说明语句,21,3.相应的翻译模式：,7.2 说明语句,PDDD;DDid:T TintegerTrealTarraynum of T1TT1,offset:=0,enter(id.name,T.type,offset);offset:=offset+t.width,T.type:=integer;T.width:=4,T.type:=real;T.width:=8,T.type:=array(num.val,T1.type);T.width:=num.valT1.width,T.type:=pointer(T1.type);T.width:=4,22,说明:(1)offset:全程变量,代表变量在过程数据区中的相对地址,用来跟踪下一个可用的相对地址的位置.,7.2 说明语句,(2)enter(name,type,offset):把名字name符号表,并给出此名字的类型type及在过程数据区中的相对地址offset.,(3)综合属性:T.type名字的类型;T.width名字的域宽(即该类型名字所占用 的存储单元个数),23,二、保留作用域信息,1.嵌套过程中的说明语句,7.2 说明语句,(1)相应的文法:PD DD;D|id:T|proc id;D;S,(2)程序举例:,24,7.2 说明语句,2.含嵌套说明的翻译模式：,PM D addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset),M t:=mktable(nil);push(t,tblptr);push(0,offset),D D1;D2,D proc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t),N t:=mktable(top(tblptr);push(t,tblptr);push(0,offset),D id:T enter(top(tblptr),id.name,T.type,top(offset);top(offset):=top(offset)+T.width,25,(1)语义规则中的操作:,7.2 说明语句,2.含嵌套说明的翻译模式：,Mktable(previous):创建一张新符号表,并返回指向新表的一个指针;,Enter(table,name,type,offset):在指针table指示的符号表中为名字name建立一个新顶,并把类型type、相对地址offset填入到该项中;,26,7.2 说明语句,(1)语义规则中的操作:,Enterproc(table,name,newtable):在指针table指示的符号表中为名字name的过程建立一个新顶。参数newtable指向过程name的符号表。,Addwidth(table,width):在指针table指示的符号表表头中记录下该表中所有名字占用的总宽度;,27,(2)栈:tblptr:存放指向符号表的指针,栈顶为指向当前正在处理过 程的符号表指针.offset:存放变量在数据区中的相对地址,栈顶为当前正在处 理过程的下一个变量的相对地址。,(3)top():取当前栈顶元素 push(a,B):将a推进B栈栈顶 pop(A):将A栈栈顶元素出栈,7.2 说明语句,28,7.3 赋值语句的翻译,一、简单算术表达式及赋值语句,1.产生“赋值语句”三地址代码的翻译模式:,Sid:=E p:=lookup(id.name);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-E1 E.place:=newtemp;emit(E.place:=uminusE1.place),E(E1)E.place:=E1.place,Eid p:=lookup(id.name);if pnil then E.place:=p else error,29,2.说明:id.nameid所代表的名字本身lookup(id.name)检查符号表中是否存在相应此名字的入口nil:返回一个该表项的指针=nil:未找到 emit()将生成的三地址语句发送到输出文件中E.place存放E值的名字newtemp产生“临时变量”,7.3 赋值语句的翻译,30,3.例题：写出下列代码段中表达式的翻译制导过 程及其所产生的四元式beginInteger：B、C、D、X;X:=-B*(C+D);end,符号表,四元式,7.3 赋值语句的翻译,31,已归约串PLACE输入串语义动作#X:=-B*(C+D)#X X:=-B*(C+D)#X:=X_-B*(C+D)#X:=-X_ B*(C+D)#X:=-B X_B*(C+D)#X:=-E X_B*(C+D)#E.place:=p=#X:=E1 X_T1*(C+D)#E1.place:=newtemp=T1;生成四元式(1)#X:=E*(C X_T1_C+D)#X:=E*(E1X_T1_C+D)#E1.place:=p=,32,已归约串 PLACE 输入串 语义动作#X:=E*(E1+D X_T1_C_D)#X:=E*(E1+E2 X_T1_C_D)#E2.place:=p=#X:=E*(E3X_T1_T2)#E3.place:=newtemp=T2;生成四元式(2)#X:=E*(E3)X_T1_T2_#X:=E*E4 X_T1_T2#E4.place=E3.place=T2#X:=E5X_T3#E5.place=T3;生成四元式(3)#S#p:=lookup(X.name);生成四元式(4),33,二、数组元素的引用,1.数组元素在存储器中的存放:,7.3 赋值语句的翻译,一维数组地址:,二维数组地址:,Ai 的地址=base+(i-low)*w=i*w+(base-low*w),Ai1,i2 的地址=base+(i1 low1)*n2+i1-low2)*w=(i1*n2)+i2)*w+(base(low1*n2)+low2)*w),34,7.3 赋值语句的翻译,1.数组元素在存储器中的存放:,二、数组元素的引用,k维数组地址:,C=(low1 n2+low2)n3+low3)nk+lowk)*w,变量部分：（(i1 n2+i2）n3+i3）)nm+i m e1=i1,em=em-1*n m+im,A i1,i2,ik 的地址=（i1 n2+i2）n3+i3）)nk+ik)*w+base(low1 n2+low2)n3+low3)nk+lowk)*w,35,改写产生式的原因：使我们在整个下标表达式串Elist的翻译过程中随时都能知道符号表中相应于数组名字id的符号表入口,从而随时能了解登记在符号表中的有关数组id的全部信息。,7.3 赋值语句的翻译,36,3.数组元素的翻译模式：A.文法:(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)ElistElist,E(8)Elistid E,7.3 赋值语句的翻译,37,B.说明:id.placeid的符号表入口.E.place存放E的名字/值.L.offset=null,L为简单名字;null,L为数组元素引用,存放临时变量的值.(变量部分的值)L.place L简单名字,则指向符号表中相应此名字表项的 指针,即此名字的符号表入口.L数组引用,则L.place存放临时变量的值.(常量部分的值),7.3 赋值语句的翻译,38,7.3 赋值语句的翻译,B.说明:Elist.array用来记录指向符号表中相应数组名字 表项的指针数组变量的符号表入口 Elist.place表示临时变量,用来临时存放由Elist中的 下标表达式计算出的值。Elist.ndim记录Elist中的下标表达式的个数,即 维数。Limit(array,j)返回nj,即由array所指示的数组的 第j维长度。,39,7.3 赋值语句的翻译,C.翻译模式,S L:=E if L.offset=null then emit(L.place:=E.place)else emit(L.place L.offset:=E.place),(2)E E1+E2 E.place:=newtemp;Emit(E.place:=E1.place+E2.place),(3)E(E1)E.place:=E1.place,40,7.3 赋值语句的翻译,(4)EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp;emit(E.place:=L.place L.offset)end,(5)L Elist L.place:=newtemp;emit(L.place:=Elist.array-C);L.offset:=newtemp;emit(L.offset:=w*Elist.place),(6)Lid L.place:=id.place;L.offset:=null,41,7.3 赋值语句的翻译,(7)Elist Elist1,E t:=newtemp;m:=Elist1.ndim+1;emit(t:=Elist1.place*limit(Elist1.array,m);emit(t:=t+t.place)Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m,(8)Elist id E Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place,42,4.举例已知:A为1020的数组,即n1=10,n2=20,设w=4,x:=A y,zx:=Ay,z 其相应的三地址语句序列如下:(1)T1:=y*20(2)T1:=T1+z(3)T2:=A-84(4)T3:=4*T1(5)T4:=T2T3(6)x:=T4,7.3 赋值语句的翻译,43,7.4 布尔表达式的翻译,前言:,2.布尔表达式的组成及形式 组成:布尔运算符号、布尔变量、关系表达式 and,or,not(,)形式:E1 relop E2,1.布尔表达式的两个基本作用(1)用来计算逻辑值(2)用作控制流语句的条件表达式,44,7.4 布尔表达式的翻译,3.产生布尔表达式的文法:EE or EEE and EEnot EE(E)Eid relop idEid,45,一、数值表示法,1.计算布尔表达式值的两种方法：,7.4 布尔表达式的翻译,(1)逐步计算(与算术表达式计算类似)例：1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1,(2)采取某种优化措施 A or B if A then T else B A and Bif A then B else F not A if A then F elseT,46,2.采取“逐步计算法”计算布尔表达式,7.4 布尔表达式的翻译,(2)关系式a b if ab then 1 else 0,分析:(1)布尔式a or b and not c,T1:=not c T2:=b and T1 T3:=a or T2,100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,47,3.布尔表达式“逐步计算法”的翻译模式：Emit():过程,将产生的三地址代码送到输出文件中.Nextstat:给出输出序列中下一条三地址语句的地址索引,每产生一条三地址语句后,过程emit将nextstat加1.,7.4 布尔表达式的翻译,48,关于布尔表达式的数值表示法的翻译模式:EE1 or E2 E.place:=newtemp;emit(E.place:=E1.placeorE2.place),EE1 and E2 E.place:=newtemp;emit(E.place:=E1.placeandE2.place),Enot E1 E.place:=newtemp;emit(E.place:=notE1.place),E(E)E.place:=E1.place,Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place gotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1);,Eid E.place:=id.place,49,4.举例：ab or cd and ef,7.4 布尔表达式的翻译,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,108:if ef goto 111 109:T3:=0 110:goto 112 111:T3:=1,112:T4:=T2 and T3 113:T5:=T1 or T4,50,二、作为条件控制的布尔式的翻译,1.以布尔式为条件控制的语句 S if E then S1|if E then S1 else S2|while E do S1,7.4 布尔表达式的翻译,51,7.4 布尔表达式的翻译,相应的代码结构:,52,注:这里的布尔式作用仅在于控制对S1和S2的选择,无须将E的值最终保留某个临时单元之中。设置两种出口:真出口E.true,假出口E.false,7.4 布尔表达式的翻译,53,2.初步分析E1 or E2 E1 and E2 E1.trueE.true E1.falseE.false E2.trueE.true E1.trueE.true E2.falseE.false E2.falseE.false,7.4 布尔表达式的翻译,54,例子:if ac or bd then S1 else S2,翻译如下:if ac goto L2goto L1 L1:if bd goto L2goto L3 L2:关于S1的三地址代码goto Lnext L3:关于S2的三地址代码 Lnext:,7.4 布尔表达式的翻译,55,3.产生布尔表达式三地址代码的语义规则 课本188页表7.7,注意：利用表7.7中的语义规则翻译的最容易方法是经过 两遍扫描。（1）为给定的输入串构造一颗语法树；（2）对语法树进行深度优先遍历，进行语义规则中 规定的翻译。,56,4.实现一遍扫描翻译(1)三地址代码表示 四元式(jnz,a,p)if a goto p(jrop,x,y,p)if x rop y goto p(j,p)goto p,(2)一遍扫描的主要问题：当生成某些转移语句时我们可能还不知道该语句将要转移到的标号究竟是什么？,问题的解决：在生成形式分支的跳转指令时暂时不确定跳转 目标，而建立一个链表，把转向这个目标的跳 转指令的标号键入这个链表。一旦目标确定之 后再把它填入有关的跳转指令中。回填技术,E.truelist-E.falselist:分别记录布尔表达式E所对应的四元式中需回填“真”、“假”出口的四元式标号所构成的链表。,57,变量nextquad指向下一条将要产生但尚未形成的四元式的 地址,初值为1,执行一次emit后,自动加1.,函数makelist(i)将创建一个仅含i的新链表，其中i是四元式 数组的一个下标，函数返回指向这个链的指针。,函数merge(p1,p2)把链首为p1和p2的两条链合并为一,作为 函数值,回送合并后的链首.,过程backpatch(p,t)功能是完成“回填”,把p所链接的每个 四元式的第四个区段都填为t.,（3）变量和过程,58,（4）翻译模式:课本190页,7.4 布尔表达式的翻译,(1)EE1 or M E2 backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist,(2)EE1 and M E2 backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist),(3)Enot E1 E.truelist:=E1.falselist;E.falselist:=E1.truelist,(4)E(E1)E.truelist:=E1.truelist;E.falselist:=E1.falselist,59,(5)Eid1 relop id2 E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place,id2.place,0);emit(j,-，-，0),7.4 布尔表达式的翻译,(6)Eid E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jnz,id.place,-,0);emit(j,-，-，0),(7)E M.quad:=nextquad;,60,5.例题：课本190页例题7.4 ab or cd and ef,7.4 布尔表达式的翻译,翻译结果：100(j,a,b,0)101(j,-,-,102)102(j,c,d,104)103(j,-,-,0)104(j,e,f,0)105(j,-,-,0),61,7.5 控制语句的翻译,一、控制流语句,相应的代码结构:,S if E then S1|if E then S1 else S2|while E do S1,62,7.5 控制语句的翻译,1.控制流语句翻译的一般规则,S.next继承属性，值为一个标号，指出继S的代码 之后将被执行的第一条三地址指令。表7.8控制流语句的属性文法,例1 if E1 then if E2 then S1 else S2 else S3 E1.codeE1.true:E2.code E2.true:S1.codegoto S.next E2.false:S2.codegoto S.next E1.falseS3.code,63,例2 while ab do if cd then x:=y+z else x:=y-z,7.5 控制语句的翻译,=L1:if ab goto L2 goto Lnext L2:if cd goto L3 goto L4 L3:T1:=y+z X:=T1 goto L1 L4:T2:=y-z X:=T2 goto L1 Lnext,64,7.5 控制语句的翻译,2.一遍扫描产生中间代码的翻译模式课本195-196,S if E then S if E then S else S while E do S begin L end A L L;SS,分析：L.nextlist指向一个转移指令链表 S.nextlist指向一个转移指令链表转移指令链表：未填写目标标号而在以后需要回填的转移指 令的链。,65,7.5 控制语句的翻译,（1）S if E then M1 S1 N else M2 S2 backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)N：产生跳过S2的无条件跳转指令。,（2）N N.nextlist:=makelist(nextquad);emit(j,)（3）M M.quad:=nextquad,(4)S if E then M S1 backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist),66,7.5 控制语句的翻译,S while M1 E do M2 S1 backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselist emit(j,，m1.quad),S begin L end S.nextlist:=L.nextlist(7)S A S.nextlist:=makelist()(8)L L1;M S backpatch(L1.nextlist,M.quad);L.nextlist:=S.nextlist(9)L S L.nextlist:=S.nextlist,67,7.5 控制语句的翻译,例7.6 按照上述的语义动作，加上前述关于赋值句和布尔表达式的翻译法，采用一遍扫描翻译语句.课本196页 While(ab)do if(cd)then x:=y+z；,翻译结果：100(j,a,b,102)101(j,-,-,0)False102(j,c,d,104)103(j,-,-,100)(+,y,z,T)105(:=,T,-,x)106(j,-,-,100),