《语义分析和中间代码产生(第十一周).ppt》由会员分享，可在线阅读，更多相关《语义分析和中间代码产生(第十一周).ppt（65页珍藏版）》请在三一办公上搜索。
1、第七章 语义分析和 中间代码产生,概述,静态语义检查类型检查控制流检查一致性检查 相关名字检查名字的作用域分析,语法分析器,中间代码产生器,静态检查器,中间代码,优化器,中间语言（复杂性界于源语言和目标语言之间）的好处：便于进行与机器无关的代码优化工作 易于移植使编译程序的结构在逻辑上更为简单明确,源语言程序,目标语言程序,中间语言程序,内容线索,中间语言说明语句 赋值语句的翻译布尔表达式的翻译控制语句的翻译过程调用的处理,中间语言,常用的中间语言后缀式，逆波兰表示图表示 DAG抽象语法树三地址代码三元式四元式间接三元式,后缀式,后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，
2、又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。3.如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。,把表达式翻译成后缀式的
3、语义规则描述,E.code表示E后缀形式op表示任意二元操作符“|”表示后缀形式的连接,数组POST存放后缀式：k为下标，初值为1上述语义动作可实现为：产生式程序段EE(1)op E(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1例：输入串a+b+c的分析和翻译POST：1 2 3 4 5,EE(1)op E(2)E.code:=E(1).code|E(2).code|opE(E(1)E.code:=E(1).codeEidE.code:=id,a,b,+,c,+,图表示法,DAG抽象语法树,DAG,有向无循环图(Directed Acyclic Graph
4、，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点,a+a*(b-c)+(b-c)*d的图表示法,+,a,*,-,b,d,c,*,+,后缀表达式：aabc-*+bc-d*+,抽象语法树,在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树(Abstract Syntax Tree),Sif B then S1 else S2,3*5+4,建立表达式的抽象语法树,mknode(op,left,right)建立一个运算符号结点，标号是op，
5、两个域left和right分别指向左子树和右子树。mkleaf(id,entry)建立一个标识符结点，标号为id，一个域entry指向标识符在符号表中的入口。mkleaf(num,val)建立一个数结点，标号为num，一个域val用于存放数的值。,建立抽象语法树的语义规则,产 生 式 语 义 规 则 EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr T(E)T.nptr:=E.nptr TidT.nptr:=mkleaf(id,id.entry)Tnum T.np
6、tr:=mkleaf(num,num.val),a4c的抽象语法树,E nptr,T nptr,E nptr,To entry for a,E,T nptr,id,-,T nptr,id,To entry for c,num,a:=b*(-c)+b*(-c)的图表示法,产生赋值语句抽象语法树的属性文法,产 生 式语义规则Sid:=ES.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)E-E1 E
7、.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrEid E.nptr:=mkleaf(id,id.place),三地址代码,三地址代码x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5,抽象语法树对应的代码：T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,a:=b*(-c)+b*(-c)的图表示法,三地址语句的种类,x:=y op z x:=op y x:=y goto L if x relop y
8、goto L或if a goto Lparam x和call p,n，以及返回语句return yx:=yi及xi:=y的索引赋值x:=&y,x:=*y和*x:=y的地址和指针赋值,x:=&y 把y的地址赋给x，其中y是一个名字，或者是一个临时变量，代表一个具有左值的表达式,x:=*y 把y所指示的地址单元里存放的内容赋给x，其中y是一个指针或者是一个其右值为地址的临时变量。,*x:=y 把y的右值赋给x所指向的对象的右值,x,y,地址,内容,左值,右值,地址,内容,左值,右值,x,y,地址,内容,左值,右值,地址,内容,左值,右值,地址,内容,左值,右值,x,y,地址,内容,左值,右值,地址
9、,内容,左值,右值,地址,内容,左值,右值,语句的三地址代码,生成三地址代码时，临时变量的名字对应抽象语法树的内部结点产生式E E1+E2 E的值放到一个新的临时变量T中赋值语句id:=E的三地址代码包括：（1）对表达式E求值并置于变量T中（2）进行赋值 id.place:=T,赋值语句的文法,非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：E.place表示存放E值的名字。E.code表示对E求值的三地址语句序列。函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,。gen表示生成三地址语句三地址语句序列往往是被存
10、放到一个输出文件中,产生式Sid:=EEE1+E2EE1*E2E-E1 E(E1)Eid,S-属性文法定义,产生式 语义规则Sid:=ES.code:=E.code|gen(id.place:=E.place)EE1+E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place*E2.place)E-E1 E.place:=newtemp;E.code:=E1.code|g
11、en(E.place:=uminus E1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEid E.place:=id.place;E.code=,三地址语句,四元式之间的联系通过临时变量实现。单目运算只用arg1域，转移语句将目标标号放入result域。arg1,arg2,result通常为指针，指向有关名字的符号表入口，且临时变量填入符号表。,op arg1arg2 result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a,四元式一个带有四个域的记录结构，这四个域分别称为
12、op,arg1,arg2及result,a:=b*(-c)+b*(-c),三地址语句,oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4),三元式 通过计算临时变量值的语句的位置来引用这个临时变量三个域：op、arg1和arg2,a:=b*(-c)+b*(-c),三地址语句,多目运算的三元式 例.xi:=y op arg1 arg2(0)=x i(1)assign(0)y 例.x:=yi op arg1 arg2(0)=y i(1)assign x(0),三地址语句,间接三元式 为了便于代码优化，用三元式表+
13、间接码表 表示中间代码间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。优点:方便优化，节省空间,例如，语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。,四元式、三元式和间接三元式比较,三元式中使用了指向三元式的指针，优化时修改较难。间接三元式优化只需要更改间接码表，并节省三元式表存储空间。修改四元式表也较容易，只是临时变量要填入符号表，占据一定存储空间。,内容线索,中间语言说明语句的翻译 赋值语句的翻译布尔表达式的翻译控制语句的翻译过程调用的处理,概述,说明部分中把定义性出现的标识符与类型等属性相关联,从而确定它们在计算机内部的表示法、取值范围
14、及可对其进行的运算。为了产生有效地可执行目标代码，对于说明部分的翻译，不仅仅把与标识符相关联的类型等属性填入符号表中，还必须考虑到标识符所标记的对象的存储分配问题。,常量定义的翻译,C+语言中有常量定义，以关键字const为标志，如 const float pi=3.1416，one=1.0对每个常量定义的处理应包括下列工作：（1）把等号右边的常量值登录入常量表中（若之前尚未登录）并回送常量表序号；（2）然后为等号左边的标识符建立符号表新条目，在该条目中填入常量标志、相应类型及常量表序号。,假定常量定义中不指明类型，类型直接由常量值本身确定，且等号右边仅整数或常量标识符。常量定义及相应翻译方案
15、CONSTEDFconst CDTCDT CDT，CDCDT CD CD id=num num.ord:=lookCT(num.lexval)id.ord:=num.ord;id.type:=integer;id.kind:=CONSTANT add(id.entry,id.kind,id.type,id.ord)CD id=id1 id.kind:=CONSTANT;id.type:=id1.type;id.ord:=id1.ord add(id.entry,id.kind,id.type,id.ord),lookCT(c)将在常量表中查找常量c，若查不到，则把给常量值登录入常量表。最终回送
16、常量c值在常量表中的序号,过程add是对过程addtype的扩充，它把种类、类型与序号三者填入符号表相应条目中,变量说明的翻译,变量说明部分由一组变量说明语句组成，这里假定每个变量说明语句中仅包含一个标识符。变量说明部分的语法定义 P D;D D;D D id:T T integer T real T arraynum of T1 T T1,变量说明部分的翻译 P D;offset:=0 D D;D D id:T enter(id.name,T.type,offset);offset:=offset+T.width T integer T.type:=integer;T.width:=4 T
17、real T.type:=real;T.width:=8 T arraynum of T1 T.type:=array(num.val,T1.type);T.width:=num.val*T1.width T T1 T.type=pointer(T1.type);T.width:=4,文法转换,P D;offset:=0 为了使得offset赋初值更明显 变更为 P offset:=0 D;也可采用增加非终结符号及产生式来实现 P M D M offset:=0,保留作用域信息,过程（函数）定义的语法 P D;D D;D D id:T D proc id;D;S过程及函数定义的翻译必然涉及标识
18、符作用域问题基本思想：每个过程有一张独立的符号表,T integerT realT arraynum of T1T T1,过程示例(1)Program sort(input,output)(2)var a:array0.10 of integer;(3)x:integer;(4)procedure readarray;(5)var i:integer;(6)begin a end readarray(7)procedure exchange(i,j:integer)(8)begin(9)x:=ai;ai:=aj;aj:=x(10)end exchange(11)procedure quicks
19、ort(m,n:integer);(12)var k,v:integer;(13)function partition(y,z:integer):integer;(14)var i,j:integer;(15)begin a(16)v(17)exchange(i,j);(18)end partition(19)begin end quicksort;(20)begin end sort.,语义规则中的操作mktable(previous)：创建一张新符号表，并返回指向新表的一个指针。参数previous指向一张先前创建的符号表，其值放在新符号表表头enter(table,name,type,o
20、ffset)：在指针table指示的符号表中为名字name建立一个新项，并把类型type、相对地址offset填入到该项中。addwidth(table,with)：指针table指示的符号表表头中记录下该表中所有名字占用的总宽度enterproc(table,name,newtable)：在指针table指示的符号表中为名字为name的过程建立一个新项。参数newtable指向过程name的符号表,翻译 P M D;addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t:=mktable(nil);push(t,tblptr);
21、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)D id:T enter(top(tblptr),id.name,T.type,top(offse);top(offset):=top(offset)+T.width N t:=mktable(top(tblptr);push(t,tblptr);push(0,offset),栈tblptr 保存各外层过程的符号表指针栈offset
22、存放各嵌套过程的当前相对地址栈顶元素为当前被处理过程的下一个名字的相对地址,tblptr,offset,0,sort,nil,a,0,x,44,sort,44,48,readarray,sort,readarray,0,i,0,4,4,readarray,(1)Program sort(input,output)(2)var a:array0.10 of integer;(3)x:integer;(4)procedure readarray;(5)var i:integer;(6)begin a end readarray,内容线索,中间语言说明语句的翻译 赋值语句的翻译布尔表达式的翻译控制语
23、句的翻译过程调用的处理,赋值语句的翻译,简单算术表达式及赋值语句简单算术表达式及赋值语句翻译为三地址代码的翻译模式属性id.name 表示id所代表的名字本身过程lookup(id.name)检查是否在符号表中存在相应此名字的入口。如果有，则返回一个指向该表项的指针，否则，返回nil表示没有找到过程emit将生成的三地址语句发送到输出文件中,产生赋值语句三地址代码的翻译模式,Sid:=E p:=lookup(id.name);if pnil thenemit(p:=E.place)else error EE1+E2 E.place:=newtemp;emit(E.place:=E1.place
24、+E2.place)EE1*E2 E.place:=newtemp;emit(E.place:=E 1.place*E 2.place),Sid:=E S.code:=E.code|gen(id.place:=E.place)EE1+E2 E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place+E2.place)EE1*E2 E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place*E2.place),E-E1 E.place:=newtemp;emit(E
25、.place:=uminusE 1.place)E(E1)E.place:=E1.placeEid p:=lookup(id.name);if pnil then E.place:=p else error,E-E1 E.place:=newtemp;E.code:=E1.code|gen(E.place:=uminus E1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEid E.place:=id.place;E.code=,类型转换,用E.type表示非终结符E的类型属性 对应产生式EE1 op E2的语义动作中关于E.type的语义规则可定义
26、为：if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real 进行类型转换的三地址代码 x:=inttoreal y算符区分为整型算符int op和实型算符real op，例.x:=yi*j 其中x、y为实型；i、j为整型。这个赋值句产生的三地址代码为：T1:=i int*j T3:=inttoreal T1 T2:=y real+T3 x:=T2,关于产生式EE1 E2 的语义动作,E.place:=newtemp;if E1.type=integer and E2.type=integer then b
27、egin emit(E.place:=E 1.place int+E 2.place);E.type:=integer end else if E1.type=real and E2.type=real then begin emit(E.place:=E 1.place real+E 2.place);E.type:=real end,else if E1.type=integer and E2.type=real then beginu:=newtemp;emit(u:=inttoreal E 1.place);emit(E.place:=u real+E 2.palce);E.type:
28、=realendelse if E1.type=real and E1.type=integer then beginu:=newtemp;emit(u:=inttoreal E 2.place);emit(E.place:=E 1.place real+u);E.type:=realend else E.type:=type_error,内容线索,中间语言说明语句的翻译 赋值语句的翻译布尔表达式的翻译控制语句的翻译过程调用的处理,布尔表达式的翻译,布尔表达式：用布尔运算符把布尔量、关系表达式联结起来的式子。布尔运算符：and,or,not；关系运算符,，,布尔表达式的两个基本作用:用于逻辑演
29、算,计算逻辑值;用于控制语句的条件式.产生布尔表达式的文法:EE or E|E andE|E|(E)|id rop id|id运算符优先级：布尔运算由高到低:not and or，同级左结合 关系运算符同级，且高于布尔运算符,计算布尔表达式通常采用两种方法:（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 true else B 把A and B解释成 if A then B else false 把 A解释成 if A t
30、hen false else true,对应的，有两种布尔表达式翻译方法,数值表示法,a or b and not c 翻译成T1:=not cT2:=b and T1T3:=a or T1ab的关系表达式可等价地写成if ab then 1 else 0，翻译成 100:if ab goto 103101:T:=0102:goto 104103:T:=1104:,数值表示法的翻译模式,过程emit将三地址代码送到输出文件中nextstat：给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程emit便把nextstat加1,数值表示法的翻译模式,EE1 or E2 E.pla
31、ce:=newtemp;emit(E.place:=E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place:=E 1.place and E2.place)Enot E1 E.place:=newtemp;emit(E.place:=not E 1.place)E(E1)E.place:=E1.place,数值表示法的翻译模式,Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place goto nextstat+3);emit(E.place:=
32、0);emit(goto nextstat+2);emit(E.place:=1)Eid E.place:=id.place,ab 翻译成100:if ab goto 103101:T:=0102:goto 104103:T:=1104:,布尔表达式ab or cd and ef的翻译结果,100:if ab goto 103101:T1:=0102:goto 104103:T1:=1104:if cd goto 107105:T2:=0106:goto 108107:T2:=1108:if ef goto 111109:T3:=0110:goto 112111:T3:=1112:T4:=T2
33、 and T3113:T5:=T1 or T4,Eid1 relop id2 E.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)Eid E.place:=id.place EE1 or E2 E.place:=newtemp;emit(E.place:=E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place:=E 1.plac
34、e and E2.place),作为条件控制的布尔式翻译,条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,E.true:,E.false:,例.把语句:if ac or b c goto L2goto L1L1:if bd goto L2goto L3 L2:(关于S1的三地址代码序列)goto LnextL3:(关于S2的三地址代码序列)Lnext:,“真”出口,“真”出口,“假”出口,产生布尔表达式三地址代码的语义规则,产生式语义规
35、则 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,每次调用函数newlabel后都返回一个新的符号标号,E.true是E为真时控制流转向的标号,E.false是E为假时控制流转向的标号,产生式 语义规则EE1 and E2 E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code|gen(E1.
36、true:)|E2.code,产生布尔表达式三地址代码的语义规则,产生式语义规则Enot E1 E1.true:=E.false;E1.false:=E.true;E.code:=E1.code E(E1)E1.true:=E.true;E1.false:=E.false;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),产生布尔表达式三地址代码的语义规则,考虑如下表达式：ab or cd and ef假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：,if ab goto Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto Lfalse,
