语义分析和中间代码生成.ppt

资源描述

《语义分析和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《语义分析和中间代码生成.ppt（157页珍藏版）》请在三一办公上搜索。

1、第七章语义分析和中间代码生成,本章内容介绍几种常用的中间表示：后缀表示、图形表示和三地址代码用语法制导定义和翻译方案的方法来说明程序设计语言的结构怎样被翻译成中间形式,7.1 中间语言,7.1.1 后缀式表达式E的后缀式可以如下递归定义如果E是变量或常数，那么E的后缀式就是E本身。,7.1 中间语言,7.1.1 后缀表示表达式E的后缀表示可以如下递归定义如果E是变量或常数，那么E的后缀表示就是E本身。如果E是形式为E1 opE2的表达式，那么E的后缀式是E1 E2 op，其中E1和E2分别是E1和E2的后缀式。,7.1 中间语言,7.1.1 后缀式表达式E的后缀式可以如下递

2、归定义如果E是变量或常数，那么E的后缀式就是E本身。如果E是形式为E1 opE2的表达式，那么E的后缀式是E1 E2 op，其中E1和E2分别是E1和E2的后缀式。如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的后缀式。,7.1 中间语言,后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法因此又称逆波兰表示法。这种表示法是把运算量（操作数）写在前面把算符写在后面（后缀）。,7.1 中间语言,把表达式翻译为后缀式的语义规则描述产生式语义规则EE1op E2 E.code:E1.code|E2.code|opE（E1）Eco

3、de:=E1.codeEid Ecode:id,7.1 中间语言,后缀式不需要括号(8 4)+2 的后缀表示是8 4 2+后缀式的最大优点是便于计算机处理表达式后缀式很容易拓广到含一元算符的表达式后缀式也可以拓广到表示赋值语句和控制语句，但很难用栈来描述它的计算,7.1 中间语言,图形表示图表示法包括DAG与抽象语法树语法树是一种图形化的中间表示,7.1 中间语言,图形表示语法树是一种图形化的中间表示有向无环图也是一种中间表示,7.1 中间语言,构造赋值语句语法树的语法制导定义,7.1 中间语言,7.1.3 三地址代码一般形式：x:=y op z表达式x+y

4、z翻译成的三地址语句序列是t1:=y z t2:=x+t1,7.1 中间语言,三地址代码是语法树或DAG的一种线性表示a:=(b+cd)+cd语法树的代码DAG的代码t1:=bt1:=bt2:=c dt2:=c dt3:=t1+t2t3:=t1+t2t4:=c dt4:=t3+t2t5:=t3+t4 a:=t4a:=t5,7.1 中间语言,本书常用的三地址语句赋值语句x:=y op z，x:=op y，x:=y无条件转移goto L条件转移if x relop y goto L过程调用param x 和call p,n过程返回 return y索引赋值x:=yi和 xi:=y地址和

5、指针赋值x:=&y，x:=y和x:=y,T1:y*zT2:xT1,T1:=c T1:=c T2:=b*T1 T2:=b*T1 T3:=c T5:=T2+T4 T4:=b*T3 a:=T5 T5:=T2+T4 a:=T5图7.5相应于图7.3的树和DAG的三地址代码（a）对于抽象语法树的代码；(b)对于DAG的代码,四元式、三元式、间接三元式,三地址语句可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。通常有三种表示方法：四元式、三元式、间接三元式。,a:b*cb*c,四元式三元式 op arg1 arg2 result op

6、arg1 arg2(0)uminus c T1(0)uminus c*b T1 T2(1)*b(0)(2)uminus c T3(2)uminus c(3)*b T3 T4(3)*b(2)(4)+T2 T4 T5(4)+(1)(3)(5):=T5 a(5)assign a(4),7.2 说明语句,为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息,7.2 说明语句,过程中的声明,7.2 说明语句,计算被声明名字的类型和相对地址P D offset:=0D D;D D id:T enter(id.name,T.type,offse

7、t);offset:=offset+T.width T integer T.type:=integer;T.width:=4 T real T.type:=real;T.width:=8 T array num of T1 T.type:=array(num.val,T1.type);T.width:=num.val T1.widthT T1 T.type:=pointer(T1.type);T.width:=4,7.2 说明语句,7.2.2 作用域信息的保存所讨论语言的文法P D SD D;D|id:T|proc id;D;S 语义动作用到的函数mktable(previous)ent

8、er(table,name,type,offset)addwidth(table,width)enterproc(table,name,newtable),7.2 说明语句,处理嵌套过程中的说明语句P M D addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t:=mktable(nil);push(t,tblprt);push(0,offset)D D1;D2D proc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);ent

9、erproc(top(tblptr),id.name,t)Did:T enter(top(tblptr),id.name,T.type,top(offset);top(offset):=top(offset)+T.width N t:=mktable(top(tblptr);push(t,tblptr);push(0,offset),（1）program sort(input,output)（2）var a:array0.10 of integer;（3）x:integer;（4）procedure readarray（5）var i:integer;（6）beginaendreadarray

10、（7）procedure exchange(i,j:integer);（8）begin（9）x:=ai;ai:=aj;aj:=x（10）end exchange;（11）procedure quicksort(m,n;integer);（12）var k,v:integer;（13）function partition(y,z:integer):integer;（14）var i,j:integer;（15）begina（16）v（17）exchange(i,j);（18）end partition;（19）begin end quicksort;（20）beginend sort.,7.2

11、说明语句,7.2 说明语句,记录的域名T record D endT record L D endT.type:=record(top(tblptr);T.width:=top(offset);pop(tblptr);pop(offset)L t:=mktable(nil);push(t,tblprt);push(0,offset),7.3 赋值语句,7.3.1 简单算术表达式及赋值语句S id:=E p:=lookup(id.name);if p nil thenemit(p，:=,E.place)else error E E1+E2E.place:=newtemp;emi

12、t(E.place,:=,E1.place,+,E2.place),7.3 赋值语句,7.3.1 简单算术表达式及赋值语句E E1 E.place:=newtemp;emit(E.place,:=,uminus,E1.place)E(E1)E.place:=E1.place E id p:=lookup(id.name);if p nil then E.place:=p else error,7.3 赋值语句,7.3.2数组元素的地址计算一维数组A的第i个元素的地址计算base+(i low)w,7.3 赋值语句,7.3.3 数组元素的地址计算一维数组A的第i个元素的地址计算

13、base+(i low)w 重写成i w+(base low w),7.3 赋值语句,二维数组列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3,7.3 赋值语句,二维数组列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3行为主A1,1,A1,2,A1,3,A2,1,A2,2,A2,3,7.3 赋值语句,二维数组列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3行为主A1,1,A1,2,A1,3,A2,1,A2,2,A2,3base+(i1 low1)n2+(i2 low2)w（其中n2=high2 low2+1）,7.3 赋值语

14、句,二维数组列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3行为主A1,1,A1,2,A1,3,A2,1,A2,2,A2,3base+(i1 low1)n2+(i2 low2)w（其中n2=high2 low2+1）(i1 n2)+i2)w+(base(low1 n2)+low2)w),7.3 赋值语句,多维数组Ai1,i2,.,ik 的地址表达式(i1 n2+i2)n3+i3)nk+ik)w+base(low1 n2+low2)n3+low3)nk+lowk)w,7.3 赋值语句,7.3.4 数组元素地址计算的翻译方案下标变量访问的产生式L id Elist|i

15、dElist Elist,E|E改成L Elist|idElist Elist,E|id E,7.3 赋值语句,所有产生式S L:=EE E+EE(E)E LL Elist L idElist Elist,EElist id E,7.3 赋值语句,L id L.place:=id.place;L.offset:=null,7.3 赋值语句,L id L.place:=id.place;L.offset:=null Elist id E Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place,7.3 赋值语句,L

16、id L.place:=id.place;L.offset:=null Elist id E Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place Elist Elist1,E t:=newtemp;m:=Elist1.ndim+1;emit(t,:=,Elist1.place,limit(Elist1.array,m);emit(t,:=,t,+,E.place);Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m,7.3 赋值语句,L id L.place:=id.p

17、lace;L.offset:=null Elist id E Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place Elist Elist1,E t:=newtemp;m:=Elist1.ndim+1;emit(t,:=,Elist1.place,limit(Elist1.array,m);emit(t,:=,t,+,E.place);Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=mL Elist L.place:=newtemp;emit(L.place,:=,base(E

18、list.array),C);/*C=invariant(Elist.array)*/L.offset:=newtemp;emit(L.offset,:=,Elist.place,w),7.3 赋值语句,E L if L.offset=null then/L是简单变量/E.place:=L.place else begin E.place:=newtemp;emit(E.place,:=,L.place,L.offset,)end,7.3 赋值语句,E Lif L.offset=null then/L是简单变量/E.place:=L.place else begin E.place

19、:=newtemp;emit(E.place,:=,L.place,L.offset,)end E E1+E2E.place:=newtemp;emit(E.place,:=,E1.place,+,E2.place),7.3 赋值语句,E Lif L.offset=null then/L是简单变量/E.place:=L.place else begin E.place:=newtemp;emit(E.place,:=,L.place,L.offset,)end E E1+E2E.place:=newtemp;emit(E.place,:=,E1.place,+,E2.place)E(E1

20、)E.place:=E1.place,7.3 赋值语句,E Lif L.offset=null then/L是简单变量/E.place:=L.place else begin E.place:=newtemp;emit(E.place,:=,L.place,L.offset,)end E E1+E2E.place:=newtemp;emit(E.place,:=,E1.place,+,E2.place)E(E1)E.place:=E1.place S L:=Eif L.offset=null then/L是简单变量/emit(L.place,:=,E.place)else emit(L.

21、place,L.offset,:=,E.place),7.3 赋值语句,7.3 赋值语句,t1:=y 20 t1:=t1+z,7.3 赋值语句,t1:=y 20 t1:=t1+z,t2:=A 84 t3:=4 t1,7.3 赋值语句,t1:=y 20 t1:=t1+z,t2:=A 84 t3:=4 t1,t4:=t2 t3,7.3 赋值语句,t1:=y 20 t1:=t1+z,t2:=A 84 t3:=4 t1,t4:=t2 t3,x:=t4,7.3 赋值语句,7.3.5 类型转换x:=y+i j（x和y的类型是real，i和j的类型是integer）中间代

22、码t1:=i int jt2:=inttoreal t1 t3:=y real+t2 x:=t3,7.3 赋值语句,E E1+E2E.place:=newtempif E1.type=integer and E2.type=integer then begin emit(E.place,:=,E1.place,int+,E2.place);E.type=integerendelse if E1.type=integer and E2.type=real then beginu:=newtemp;emit(u,:=,inttoreal,E1.place);emit(E.place,:=,u

23、,real+,E2.place);E.type:=realend.,7.4 布尔表达式的翻译,布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式,7.4 布尔表达式的翻译,布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算布尔表达式的“短路”计算E1 or E2 定义成 if E1 then true else E2E1 and E2 定义成 if E1 then E2 else false,7.4 布尔表达式的翻译,7.4.1 布尔表达式的翻译E E or E|E and E|not E|(E)|id relop id|true|falsea b的

24、翻译100:if a b goto 103101:t:=0102:goto 104103:t:=1104:,7.4 布尔表达式的翻译,E E1 or E2 E.place:=newtemp;emit(E.place,:=,E1.place,or E2.place)E id1 relop id2E.place:=newtemp;emit(if,id1.place,relop.op,id2.place,goto,nextstat+3);emit(E.place,:=,0);emit(goto,nextstat+2);emit(E.place,:=,1),7.4 布尔表达式的翻译,表达式a b or

25、 c d and e f的代码是：100 if a b goto 103 107 T2:=1101 T1:=0 108 if e f goto 111 102 goto 104 109 T3:=0103 T1:=1 110 goto 112 104 if c d goto 107 111 T3:=1105 T2:=0 112 T4:=T2 and T3 106 goto 108 113 T5:=T1 or T4,7.4 布尔表达式的翻译,E E1 or E2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;

26、E.code:=E1.code|gen(E1.false,:)|E2.code,7.4 布尔表达式的翻译,E E1 or E2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.false,:)|E2.code E not E1E1.true:=E.false;E1.false:=E.true;E.code:=E1.code,7.4 布尔表达式的翻译,E E1 and E2E1.true:=newlabel;E1.false:=E.false;E2.true:=E

27、.true;E2.false:=E.false;E.code:=E1.code|gen(E1.true,:)|E2.code,7.4 布尔表达式的翻译,E E1 and E2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.true,:)|E2.code E(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code,7.4 布尔表达式的翻译,E id1 relop id2E.code:=gen(if,id1.pl

28、ace,relop.op,id2.place,goto,E.true)|gen(goto,E.false),7.4 布尔表达式的翻译,E id1 relop id2E.code:=gen(if,id1.place,relop.op,id2.place,goto,E.true)|gen(goto,E.false)E trueE.code:=gen(goto,E.true)E falseE.code:=gen(goto,E.false),7.5 控制语句的翻译,7.5.1 控制流语句的翻译S if E then S1|if E then S1 else S2|while E do S1|S1;S2

30、de,7.5 控制语句的翻译,S while E do S1 S.begin:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin,:)|E.code|gen(E.true,:)|S1.code|gen(goto,S.begin),7.5 控制语句的翻译,S S1;S2S1.next:=newlabel;S2.next:=S.next;S.code:=S1.code|gen(S1.next,:)|S2.code,while ab do if cd then x:=y+z else x:=y

31、-z根据上述属性文法和赋值语句的翻译模式，将生成下列代码：,L1:if ab goto L2 goto Lnext L2:if cd goto L3 goto L4 L3:T1:=y+z x:=T1 goto L1 L4:T1:=y-z x:=T2 goto L1 Lnext:,100(j,a,b,102)while ab do 101(j,-,-,107)if cd then 102(j,c,d,104)x:=y+z103(j,-,-,100)104(+,y,z,T)105(:=,T,-,x)106(j,-,-,100)107,7.5 控制语句的翻译,7.5.2 布尔表达式的控制流翻译如果E

32、是a b的形式，那么代码是：if a b goto E.truegoto E.false,7.5 控制语句的翻译,7.5.3 开关语句的翻译switch Ebegincase V1:S1case V2:S2.case Vn-1:Sn 1default:Snend,7.5 控制语句的翻译,分支数较少时t:=E的代码|Ln-2:if t Vn-1 goto Ln-1 if t V1 goto L1|Sn-1的代码 S1的代码|goto nextgoto next|Ln-1:Sn的代码 L1:if t V2 goto L2|next:S2的代码goto nextL2:.,7.5 控制语句的翻译,分支

34、6 过程调用的处理,过程调用的翻译S call id(Elist)for 队列queue中的每一项p do emit（param p）；emit（callid.Place）Elist Elist,E 将E.Place加入到queeue的队尾 Elist E 初始化queue仅包含E.place,7.4 布尔表达式和控制流语句,过程调用id(E1,E2,En)的中间代码结构E1.place:=E1的代码E2.place:=E2的代码.En.place:=En的代码param E1.placeparam E2.place.param En.placecall id.place,n,7.4 布尔表达

35、式和控制流语句,S call id(Elist)为长度为n的队列中的每个E.place，emit(param,E.place);emit(call,id.plase,n)Elist Elist,E把E.place放入队列末尾Elist E将队列初始化，并让它仅含E.place,7.7 类型检查,静态检查中最典型的部分类型检查：类型系统、类型检查、多态函数、重载。忽略其它的静态检查：控制流检查、唯一性检查、关联名字检查。,7.7.1 类型系统变量的类型变量在程序执行期间的取值范围类型化语言变量都被给定类型的语言未类型化的语言不限制变量值范围的语言一个运算可以作用到任意的运算对象，其结果可能是一

36、个有意义的值、一个错误、一个异常或一个未做说明的结果。,类型系统的根本目的是防止程序运行时出现执行错误类型可靠的语言粗略地说，所有程序运行时都没有执行错误出现类型系统的形式化类型表达式、定型断言、定型规则、类型检查算法显式类型化的语言类型是语法的一部分隐式类型化的语言,执行错误和安全语言执行错误会被捕获的错误（trapped error）例：非法指令错误、非法内存访问、除数为零引起计算立即停止不会被捕获的错误（untrapped error）例：下标变量的访问越过数组末端的数据例：跳到一个错误的地址，该地址开始的内存正好代表一个指令序列,类型可靠的语言所有合法的程序都是良行为的又称为强检查

37、的语言未类型化语言通过彻底的运行时详细检查来排除所有的禁止错误，如LISP语言也可以通过静态检查来拒绝不良行为的程序类型系统就是用来支持这种静态检查的这种检查叫做类型检查这样的类型化语言，又称强类型化的语言,一些实际使用的语言是弱类型化语言Pascal语言无标志的变体记录类型函数型参数,一些实际使用的语言是弱类型化语言Pascal语言无标志的变体记录类型函数型参数C语言有很多不安全的并且被广泛使用的特征，如：指针算术运算类型强制参数个数可变,在语言设计的历史上，安全性考虑不足是出于效率上的原因,在语言设计的历史上，安全性考虑不足是出于效率上的原因在语言设计中的，安全性的位

38、置越来越重要 C的一些问题已经在C+中得以缓和更多一些问题在Java中已得到解决 ML是一个类型化的安全语言,类型化语言的优点从工程的观点看，类型化语言有下面一些优点开发的实惠较早发现错误类型信息还具有文档作用,类型化语言的优点从工程的观点看，类型化语言有下面一些优点开发的实惠较早发现错误类型信息还具有文档作用编译的实惠程序模块可以相互独立地编译,类型化语言的优点从工程的观点看，类型化语言有下面一些优点开发的实惠较早发现错误类型信息还具有文档作用编译的实惠程序模块可以相互独立地编译运行的实惠可得到更有效的空间安排和访问方式,类型检查器的规格说明,一个简单的语言P D;SD D;D

40、pe)T boolean T.type:=booleanT integer T.type:=integerT T1 T.type:=pointer(T1.type)T array num of T1 T.type:=array(num.val,T1.type),类型检查器的规格说明,类型检查声明语句D D;DD id:T addtype(id.entry,T.type)T boolean T.type:=booleanT integer T.type:=integerT T1 T.type:=pointer(T1.type)T array num of T1 T.type:=array(num

41、.val,T1.type)T T1 T2 T.type:=T1.type T2.type,类型检查器的规格说明,类型表达式的抽象语法基本类型 boolean,char,integer,real构造类型数组类型array(I,T)指针类型pointer(T)积类型T1 T2函数 T1 T2记录（例）record(address integer)(lexeme array(1.10,char)类型表达式中还可以出现类型名字和类型变量,类型检查器的规格说明,类型检查表达式E truthE.type:=boolean E numE.type:=integerE idE.type:=lookup(id.

42、entry),类型检查器的规格说明,类型检查表达式E truthE.type:=boolean E numE.type:=integerE idE.type:=lookup(id.entry)E E1 mod E2E.type:=if E1.type=integer and E2.type=integer then integer else type_error,类型检查器的规格说明,类型检查表达式E E1 E2 E.type:=if E2.type=integer and E1.type=array(s,t)then t else type_error,类型检查器的规格说明,类型检查表达式E

43、 E1 E2 E.type:=if E2.type=integer and E1.type=array(s,t)then t else type_error E E1 E.type:=if E1.type=pointer(t)then t else type_error,类型检查器的规格说明,类型检查表达式E E1 E2 E.type:=if E2.type=integer and E1.type=array(s,t)then t else type_error E E1 E.type:=if E1.type=pointer(t)then t else type_error E E1(E2)E

44、.type:=if E2.type=s and E1.type=s t then t else type_error,类型检查器的规格说明,类型检查语句S id:=E S.type:=if id.type=E.typethen void else type_error,类型检查器的规格说明,类型检查语句S id:=E S.type:=if id.type=E.typethen void else type_error S if E then S1 S.type:=if E.type=booleanthen S1.type else type_error,类型检查器的规格说明,类型检查语句S w

45、hile E do S1S.type:=if E.type=boolean then S1.type else type_error,类型检查器的规格说明,类型检查语句S while E do S1S.type:=if E.type=boolean then S1.type else type_error S S1;S2S.type:=if S1.type=void andS2.type=void then voidelse type_error,类型检查器的规格说明,类型检查程序P D;S P.type:=if S.type=void then voidelse type_error,类型检

46、查器的规格说明,类型转换E E1 op E2E.type:=if E1.type=integer and E2.type=integerthen integerelse if E1.type=integer and E2.type=realthen realelse if E1.type=real and E2.type=integerthen realelse if E1.type=real and E2.type=realthen realelse type_error,多态函数,7.7.3.1 为什么要使用多态函数例：用Pascal语言写不出求表长度的通用程序type link=cell

47、;cell=record info:integer;next:link end;,多态函数,function length(lptr:link):integer;var len:integer;beginlen:=0;while lptr nil do begin len:=len+1;lptr:=lptr.nextend;length:=lenend;,多态函数,用ML语言很容易写出求表长度的程序而不必管表元的类型。fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;,多态函数,用ML语言很容易写出求表长度的

48、程序而不必管表元的类型。fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;length(“sun”,“mon”,“tue”)length(10,9,8)都等于3,多态函数,多态函数允许变元有不同的类型,多态函数,多态函数允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）,多态函数,多态函数允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）多态算符用于以不同类型的变元执行的代码段,多态函数,多态函数允许变元有不同的类型体中的语句可以在变元类型不同

49、的情况下执行（区别于重载的特征）多态算符用于以不同类型的变元执行的代码段例如：数组索引,多态函数,多态函数允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）多态算符用于以不同类型的变元执行的代码段例如：数组索引、函数作用,多态函数,多态函数允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）多态算符用于以不同类型的变元执行的代码段例如：数组索引、函数作用、通过指针间接访问,多态函数,多态函数允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）多态算符用于以不同类型的变元执行的代码段例如：数组

展开阅读全文