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

编译原理,第七章 语义分析和中间代码产生,静态语义检查类型检查控制流检查一致性检查 相关名字检查名字的作用域分析,语法分析器,中间代码产生器,静态检查器,中间代码,优化器,编译原理,中间语言(复杂性界于源语言和目标语言之间)的好处：便于进行与机器无关的代码优化工作 易于移植使编译程序的结构在逻辑上更为简单明确,源语言程序,目标语言程序,中间语言程序,编译原理,常用的中间语言：后缀式，逆波兰表示图表示： DAG、抽象语法树三地址代码三元式四元式间接三元式,7.1 中间语言,编译原理,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的后缀式。,编译原理,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。,编译原理,把表达式翻译成后缀式的语义规则描述,产生式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表示任意二元操作符“|”表示后缀形式的连接。,编译原理,数组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,+,编译原理,7.1.2 图表示法,图表示法DAG抽象语法树,编译原理,7.1.2 图表示法,无循环有向图(Directed Acyclic Graph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点,编译原理,a:=b*(-c)+b*(-c)的图表示法,编译原理,抽象语法树对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,编译原理,DAG对应的代码： T1:=-cT2:=b*T1T5:=T2+T2a:=T5,抽象语法树对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,编译原理,产生赋值语句抽象语法树的属性文法,产 生 式语义规则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),编译原理,7.1.3 三地址代码,三地址代码x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,编译原理,a:=b*(-c)+b*(-c)的图表示法,编译原理,T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5对于抽象语法树的代码对于DAG的代码,编译原理,三地址语句的种类,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的地址和指针赋值,编译原理,生成三地址代码时，临时变量的名字对应抽象语法树的内部结点id:=E对表达式E求值并置于变量T中值id.place:=T,编译原理,从赋值语句生成三地址代码的S-属性文法,非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：E.place表示存放E值的名字。E.code表示对E求值的三地址语句序列。函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,。,编译原理,为赋值语句生成三地址代码的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= ,编译原理,三地址语句,四元式一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a,编译原理,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量三个域：op、arg1和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4),编译原理,三地址语句,xi:=y op arg1 arg2 (0) = x i (1) yx:=yiop arg1 arg2(0) = y i(1) assign x (0),编译原理,三地址语句,间接三元式 为了便于优化，用 三元式表+间接码表 表示中间代码间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。优点: 方便优化，节省空间,编译原理,例如，语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。,编译原理,7.2 说明语句,编译原理,7.3 赋值语句的翻译,7.3.1 简单算术表达式及赋值语句,编译原理,为赋值语句生成三地址代码的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= ,编译原理,产生赋值语句三地址代码的翻译模式,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),编译原理,产生赋值语句三地址代码的翻译模式,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= ,编译原理,7.3.2 数组元素的引用,数组元素地址的计算：,编译原理,设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,编译原理,id出现的地方也允许下面产生式中的L出现 L id Elist | idElistElist,E | E 为了便于处理，文法改写为 LElist | id ElistElist, E | id E,编译原理,引入下列语义变量或语义过程:Elist.ndim ：下标个数计数器Elist.place ：表示临时变量，用来临时存放已形成的Elist中的下标表达式计算出来的值 limit(array，j) ：函数过程，它给出数组array的第j维的长度,编译原理,每个代表变量的非终结符L有两项语义值L.place：若L为简单变量i, 指变量i的符号表入口 若L为下标变量，指存放CONSPART的 临时变量的整数码 L.offset ：若L为简单变量，null，若L为下标变量，指存放VARPART的临时变量的整数码,编译原理,(1) SL:=E(2) EE+E(3) E(E)(4) EL(5) LElist (6) Lid(7) Elist Elist, E(8) Elistid E,编译原理,(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),编译原理,(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 ,编译原理,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 ,编译原理,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 ,编译原理,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 ,编译原理,类型转换,用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，,编译原理,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 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,编译原理,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,编译原理,7.3.3 记录中域的引用,符号表表项之中保存记录中的域的类型和相对地址信息,编译原理,7.4 布尔表达式的翻译,布尔表达式的两个基本作用:用于逻辑演算,计算逻辑值;用于控制语句的条件式.产生布尔表达式的文法: EE or E | E andE | E | (E) | i rop i | i,编译原理,计算布尔表达式通常采用两种方法:1. 如同计算算术表达式一样,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =12. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true,编译原理,两种不同的翻译方法:第一种翻译法： A or B and C=D翻译成(1) (=, C, D, T1)(2) (and, B, T1, T2)(3) (or, A, T2, T3)第二种翻译法适合于作为条件表达式的布尔表达式使用.,编译原理,7.4.1 数值表示法,a or b and not c 翻译成T1:=not cT2:=b and T1T3:=a or T1a<b的关系表达式可等价地写成if a<b then 1 else 0 ，翻译成 100:if a<b goto 103101:T:=0102:goto 104103:T:=1104:,编译原理,关于布尔表达式的数值表示法的翻译模式,过程emit将三地址代码送到输出文件中nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程emit便把nextstat加1,编译原理,关于布尔表达式的数值表示法的翻译模式,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.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 := 0);emit(goto nextstat+2);emit(E.place:= 1) Eid E.place:=id.place ,a<b 翻译成100:if a<b goto 103101:T:=0102:goto 104103:T:=1104:,编译原理,布尔表达式a<b or c<d and e<f的翻译结果,100:if a<b goto 103101:T1:=0102:goto 104103:T1:=1104:if c<d goto 107105:T2:=0106:goto 108107: T2:=1108: if e<f goto 111109: T3:=0110: goto 112111: T3:=1112: T4:=T2 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.place and E2.place) ,编译原理,7.4.2 作为条件控制的布尔式翻译,条件语句 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 a>c or b c goto L2 “真”出口 goto L1L1:if b<d goto L2 “真”出口 goto L3 “假”出口 L2:(关于S1的三地址代码序列)goto LnextL3:(关于S2的三地址代码序列)Lnext:,编译原理,每次调用函数newlabel后都返回一个新的符号标号对于一个布尔表达式E，引用两个标号E.true是E为真时控制流转向的标号E.false是E为假时控制流转向的标号,编译原理,产生布尔表达式三地址代码的语义规则,产生式语义规则 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.fasle; E.code:=E1.code | gen(E1.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),编译原理,考虑如下表达式： a<b or c<d and e<f假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：,if a<b goto Ltruegoto L1L1:if c<d goto L2goto LfalseL2:if e<f goto Ltruegoto Lfalse,编译原理,布尔表达式的翻译,两遍扫描为给定的输入串构造一棵语法树；对语法树进行深度优先遍历，进行语义规则中规定的翻译。一遍扫描,编译原理,一遍扫描实现布尔表达式的翻译,采用四元式形式把四元式存入一个数组中，数组下标就代表四元式的标号约定 四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p)表示 if x rop y goto p四元式(j, -, -, p) 表示 goto p,编译原理,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机"回填"。,编译原理,为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填"真"出口的p，q，r三个四元式，则E.truelist为下列链:(p) (x， x，x，0)(q) (x，x，x，p)(r) (x，x，x，q),链尾,E. truelist =r,编译原理,为了处理E.truelist和E.falselist ，引入下列语义变量和过程:变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。,编译原理,布尔表达式的文法,(1) EE1 or M E2(2) | E1 and M E2(3)| not E1(4)| (E1)(5)| id1 relop id2(6)| id(7)M,编译原理,布尔表达式的翻译模式,(7) M M.quad:=nextquad ,编译原理,布尔表达式的翻译模式,(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,编译原理,布尔表达式的翻译模式,(5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) ,编译原理,布尔表达式的翻译模式,作为整个布尔表达式的"真""假"出口(转移目标)仍待回填.,编译原理,a<b or c<d and e<f,100(j<, a, b, 0)101(j, -, -, 102)102(j<, c, d, 104)103(j, -, -, 0)104(j<, e, f, 100) truelist105(j, -, -, 103) falselist,编译原理,计算布尔表达式通常采用两种方法:1. 如同计算算术表达式一样,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =12. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true,回顾：布尔表达式的翻译,编译原理,关于布尔表达式的数值表示法的翻译模式,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.place and E2.place) ,编译原理,回顾：布尔表达式的翻译,作为条件控制的布尔式翻译一遍扫描实现布尔表达式的翻译,编译原理,7.4.2 作为条件控制的布尔式翻译,条件语句 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:,编译原理,产生布尔表达式三地址代码的语义规则,