xd329Chapt7.ppt

国防科技大学计算机系602教研室,第七章 语义分析和中间代码产生,静态语义检查类型检查控制流检查一致性检查 相关名字检查名字的作用域分析,语法分析器,中间代码产生器,静态检查器,中间代码,优化器,国防科技大学计算机系602教研室,中间语言(复杂性界于源语言和目标语言之间)的好处：便于进行与机器无关的代码优化工作 易于移植使编译程序的结构在逻辑上更为简单明确,源语言程序,目标语言程序,中间语言程序,国防科技大学计算机系602教研室,常用的中间语言：后缀式，逆波兰表示图表示：DAG、抽象语法树三地址代码三元式四元式间接三元式,7.1 中间语言,国防科技大学计算机系602教研室,7.1.1 后缀式,后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。3.如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。,国防科技大学计算机系602教研室,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。,国防科技大学计算机系602教研室,把表达式翻译成后缀式的语义规则描述,产生式EE(1)op E(2)E(E(1)Eid,语义动作E.code:=E(1).code|E(2).code|opE.code:=E(1).codeE.code:=id,E.code表示E后缀形式op表示任意二元操作符“|”表示后缀形式的连接。,国防科技大学计算机系602教研室,数组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,+,国防科技大学计算机系602教研室,7.1.2 图表示法,图表示法DAG抽象语法树,国防科技大学计算机系602教研室,7.1.2 图表示法,无循环有向图(Directed Acyclic Graph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点,国防科技大学计算机系602教研室,a:=b*(-c)+b*(-c)的图表示法,国防科技大学计算机系602教研室,抽象语法树对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,国防科技大学计算机系602教研室,DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5,抽象语法树对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,国防科技大学计算机系602教研室,产生赋值语句抽象语法树的属性文法,产 生 式语义规则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.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrEid E.nptr:=mkleaf(id,id.place),国防科技大学计算机系602教研室,7.1.3 三地址代码,三地址代码x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,国防科技大学计算机系602教研室,a:=b*(-c)+b*(-c)的图表示法,国防科技大学计算机系602教研室,T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5对于抽象语法树的代码对于DAG的代码,国防科技大学计算机系602教研室,三地址语句的种类,x:=y op z x:=op y x:=y goto L if x relop y goto L或if a goto Lparam x和call p,n，以及返回语句return yx:=yi及xi:=y的索引赋值x:=&y,x:=*y和*x:=y的地址和指针赋值,国防科技大学计算机系602教研室,生成三地址代码时，临时变量的名字对应抽象语法树的内部结点id:=E对表达式E求值并置于变量T中值id.place:=T,国防科技大学计算机系602教研室,从赋值语句生成三地址代码的S-属性文法,非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：E.place表示存放E值的名字。E.code表示对E求值的三地址语句序列。函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,。,国防科技大学计算机系602教研室,为赋值语句生成三地址代码的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-E1E.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=,国防科技大学计算机系602教研室,三地址语句,四元式一个带有四个域的记录结构，这四个域分别称为op,arg1,arg2及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a,国防科技大学计算机系602教研室,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量三个域：op、arg1和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4),国防科技大学计算机系602教研室,三地址语句,xi:=y op arg1 arg2(0)=x i(1)yx:=yiop arg1 arg2(0)=y i(1)assign x(0),国防科技大学计算机系602教研室,三地址语句,间接三元式 为了便于优化，用 三元式表+间接码表 表示中间代码间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。优点:方便优化，节省空间,国防科技大学计算机系602教研室,例如，语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。,国防科技大学计算机系602教研室,7.2 说明语句,国防科技大学计算机系602教研室,7.3 赋值语句的翻译,7.3.1 简单算术表达式及赋值语句,国防科技大学计算机系602教研室,为赋值语句生成三地址代码的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-E1E.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=,国防科技大学计算机系602教研室,产生赋值语句三地址代码的翻译模式,Sid:=E p:=lookup(id.name);if pnil thenemit(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:=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),国防科技大学计算机系602教研室,产生赋值语句三地址代码的翻译模式,E-E1 E.place:=newtemp;emit(E.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=,国防科技大学计算机系602教研室,7.3.2 数组元素的引用,数组元素地址的计算：,国防科技大学计算机系602教研室,设A为n维数组，每个元素宽度为w，lowi 为第i维 的下界，ni 是为第i维 可取值的个数,base为A的第一个元素相对地址 元素Ai1,i2,ik相对地址公式(i1 n2+i2)n3+i3)nk+ik)w+base-(low1 n2+low2)n3+low3)nk+lowk)w C=base-(low1 n2+low2)n3+low3)nk+lowk)w,国防科技大学计算机系602教研室,id出现的地方也允许下面产生式中的L出现 L id Elist|idElistElist,E|E 为了便于处理，文法改写为 LElist|id ElistElist,E|id E,国防科技大学计算机系602教研室,引入下列语义变量或语义过程:Elist.ndim：下标个数计数器Elist.place：表示临时变量，用来临时存放已形成的Elist中的下标表达式计算出来的值 limit(array，j)：函数过程，它给出数组array的第j维的长度,国防科技大学计算机系602教研室,每个代表变量的非终结符L有两项语义值L.place：若L为简单变量i,指变量i的符号表入口 若L为下标变量，指存放CONSPART的 临时变量的整数码 L.offset：若L为简单变量，null，若L为下标变量，指存放VARPART的临时变量的整数码,国防科技大学计算机系602教研室,(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)Elist Elist,E(8)Elistid E,国防科技大学计算机系602教研室,(1)SL:=E if L.offset=null then/*L是简单变量*/emit(L.place:=E.place)else emit(L.place L.offset:=E.place)(2)EE1+E2 E.place:=newtemp;emit(E.place:=E 1.place+E 2.place),国防科技大学计算机系602教研室,(3)E(E1)E.place:=E1.place(4)EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp;emit(E.place:=L.place L.offset)end,国防科技大学计算机系602教研室,Ai1,i2,ik(i1 n2+i2)n3+i3)nk+ik)w+base-(low1 n2+low2)n3+low3)nk+lowk)w,(8)Elistid E Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place,国防科技大学计算机系602教研室,A i1,i2,ik(i1 n2+i2)n3+i3)nk+ik)w+base-(low1 n2+low2)n3+low3)nk+lowk)w,(7)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,国防科技大学计算机系602教研室,Ai1,i2,ik(i1 n2+i2)n3+i3)nk+ik)w+base-(low1 n2+low2)n3+low3)nk+lowk)w,(5)LElist 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,国防科技大学计算机系602教研室,类型转换,用E.type表示非终结符E的类型属性 对应产生式EE1 op E2的语义动作中关于E.type的语义规则可定义为：if E1.type=integer andE2.type=integer E.type:=integer else E.type:=real 算符区分为整型算符int op和实型算符real op，,国防科技大学计算机系602教研室,x:=yi*j 其中x、y为实型；i、j为整型。这个赋值句产生的三地址代码为：T1:=i int*j T3:=inttoreal T1 T2:=y real+T3 x:=T2,国防科技大学计算机系602教研室,关于产生式EE1 E2 的语义动作,E.place:=newtemp;if E1.type=integer and E2.type=integer then begin 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,国防科技大学计算机系602教研室,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:=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,国防科技大学计算机系602教研室,7.3.3 记录中域的引用,符号表表项之中保存记录中的域的类型和相对地址信息,