编译原理第7章

19.11.7copyright/1陕西理工学院计算机系《编译原理》1第7章语义分析和中间代码产生7.1中间语言7.2说明语句7.3赋值语句的翻译7.4布尔表达式的翻译7.5控制语句的翻译第7章语义分析和中间代码产生19.11.7copyright/2陕西理工学院计算机系《编译原理》2语义分析的任务•静态语义检查–例：类型检查、控制流检查、一致性检查、相关名字检查•动态语义处理——翻译–对程序意义的解释，执行真正的翻译–例：变量的存储分配–例：表达式的求值–例：语句的翻译（中间代码的生成）总目标生成等价的中间代码19.11.7copyright/3陕西理工学院计算机系《编译原理》3编译中的语义分析•描述方法–利用属性文法描述如何将各种语句和表达式翻译成中间代码–为每个文法符号赋予相应属性，对应每一个产生式编制一个语义子程序•工作方式——语法制导翻译–当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译–每识别出一个语法结构时，完成相应的语义检查与中间代码生成19.11.7copyright/4陕西理工学院计算机系《编译原理》47.1中间语言(Intermediatelanguage/code/representation)•独立于机器的、复杂性界于源语言和机器语言之间语言•源程序的一种内部表示——中间代码序列（中间语言的语句）•用中间语言过渡的好处–便于进行与机器无关的优化工作–使编译程序改变目标机容易，便于移植–使编译程序的结构在逻辑上更为简单明确7.1中间语言19.11.7copyright/5陕西理工学院计算机系《编译原理》5•表示形式：•后缀式（逆波兰式）•图表示法：抽象语法树、DAG图•三地址代码：三元式、四元式、间接三元式特点：•形式简单、语义明确、便于翻译•独立于目标语言7.1中间语言19.11.7copyright/6陕西理工学院计算机系《编译原理》67.1.1后缀式（逆波兰式）•是表达式的一种表示形式•把运算符写在运算量(操作数)后面•定义设E是表达式，那么–若E是变量或常量，E的后缀式为E自身–E1OPE2==E1’E2’OP，其中E1’和E2’分别为E1和E2的后缀式–(E)==E’•中缀式(a+b)*c后缀式ab+c*(a+b)*(c+d)ab+cd+*not(AorB)ABornot7.1中间语言19.11.7copyright/7陕西理工学院计算机系《编译原理》7中缀式改写成后缀式课堂练习•中缀式1.-a+b*c2.a+b*(c-d)+e/(c-d)↑n对应后缀式后缀式特点1.运算量的顺序与中缀式相同2.运算符的先后顺序即为运算的先后顺序3.有利于表达式运算的实现1.a@bc*+2.abcd-*+ecd-n↑/+7.1中间语言19.11.7copyright/8陕西理工学院计算机系《编译原理》8后缀式翻译的语义规则产生式语义规则E→E1opE2E.code:=E1.code||E2.code||opE→(E1)E.code:=E1.codeE→idE.code:=id功能：完成中缀表达式到后缀表达式的翻译例如：id1+id2+id3后缀式：E.codeEE+EE+Eid2id1id3数组postid1id2+id3E1E2+7.1中间语言19.11.7copyright/9陕西理工学院计算机系《编译原理》9语句的后缀式表示•赋值语句X:=A-B/(C+D)后缀式XABCD+/-:=控制语句ifx-y!=0thenx+1elsey+1xy-p1BZx1+p2BRy1+p1p2p1p2可改写后缀式：e’pBZ——当e’=0时，将控制转移至post[p]pBR——无条件转移到post[p]7.1中间语言19.11.7copyright/11陕西理工学院计算机系《编译原理》117.1.2图表示法——抽象语法树•在抽象语法树中，操作符和关键字作为内部结点出现，它们的孩子代表操作数，是叶子结点•我们通过为每一个运算符号都建立一个结点来为子表达式建立子树抽象语法树是在语法树中去掉对翻译不必要的信息，从而获得更有效的源程序的中间表示例：表达式3*5+4的抽象语法树*35+47.1中间语言19.11.7copyright/12陕西理工学院计算机系《编译原理》12例：表达式(A-12)*B+6的抽象语法树A12-B*6+7.1中间语言19.11.7copyright/17陕西理工学院计算机系《编译原理》177.1.3三地址代码一般形式x:=yopz操作数运算符操作数结果三个地址,xyz,为变量名、常数或编译产生的临时变量每条语句的右边只能有一个运算符op表达式x+y*z的三地址代码(1)T1:=y*z(2)T2:=x+T1赋值语句a:=b*-c+b*-c的三地址代码(1)T1:=-c(2)T2:=b*T1(3)T3:=-c(4)T4:=b*T3(5)T5:=T2+T4(6)a:=T57.1中间语言19.11.7copyright/18陕西理工学院计算机系《编译原理》18种类：x:=yopz双目运算x:=opy单目运算x:=y赋值gotoL无条件转移ifxrelopygotoL条件转移paramx实在参数callp,n(n是参数个数)过程调用returnx过程返回x:=y[i]数组运算(取数)x[i]:=y(存数)x:=&y地址和指针运算x:=*y*x=y7.1中间语言19.11.7copyright/19陕西理工学院计算机系《编译原理》19赋值语句生成三地址代码的属性文法定义非终结符的综合属性：•S.code表示赋值语句S的三地址代码•E.place表示存放E值的名字•E.code表示对E求值的三地址代码序列函数•newtemp每次调用将返回一个不同临时变量名字，如T1,T2,…•gen(x‘:=’y‘+’z)表示生成三地址代码语句x:=y+z赋值语句文法：S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id7.1中间语言19.11.7copyright/20陕西理工学院计算机系《编译原理》20对赋值语句产生三地址代码的属性文法S→id:=ES.code:=E.code||gen(id.place':='E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code||E2.code||gen(E.place':='E1.place'+'E2.place)E→E1*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':=''@'E1.place)E→(E1)E.place:=E1.place;E.code:=E1.codeE→idE.place:=id.place;E.code:=‘’产生式语义规则19.11.7copyright/21陕西理工学院计算机系《编译原理》211.四元式•表示方法：四个域(op，arg1，arg2，result)例：a+b*coparg1arg2result(0)*bcT1(1)+aT1T2运算操作数操作符结果操作数arg1，arg2和result是指向有关名字符号表的指针，可以是常量，变量或临时变量等7.1中间语言19.11.7copyright/22陕西理工学院计算机系《编译原理》22课堂练习•赋值语句A:=-B*(C+D)•对应的四元式序列(@,B,_,T1)此操作数为空用下划线表示(+,C,D,T2)(*,T1,T2,T3)(:=,T3,_,A)7.1中间语言19.11.7copyright/23陕西理工学院计算机系《编译原理》232.三元式•表示方法：三个域(op，arg1，arg2)例：a+b*coparg1arg2(0)*bc(1)+a(0)arg1，arg2：或者是指向符号表的指针，或者是指向三元式表的指针i运算操作数操作符三元式编号存运算结果7.1中间语言19.11.7copyright/24陕西理工学院计算机系《编译原理》24课堂练习•赋值语句A:=-B*(C+D)•对应的三元式序列①(@,B,_)此操作数为空，用下划线表示②(+,C,D)③(*,①,②)④(:=,A，③)可以看出：三元式是按相应表达式的实际运算顺序出现的三元式间的相互引用非常频繁，而这些引用又是通过编号来实现的在优化时，要删除或挪动三元式会造成大量修改的局面7.1中间语言19.11.7copyright/25陕西理工学院计算机系《编译原理》253.间接三元式•建立两个与三元式相关的表格三元式表——用来存放各三元式本身执行表(间接码表)——按各三元式执行顺序列出相应三元式在三元式表中的位置•例子：X:=(A+B)*C;Y:=D↑(A+B);三元式表oparg1arg2(1)+AB(2)*(1)C(3):=X(2)(4)↑D(1)(5):=Y(4)间接代码(1)(2)(3)(1)(4)(5)7.1中间语言19.11.7copyright/26陕西理工学院计算机系《编译原理》26间接三元式优点•需要调整运算顺序时，只需重新安排间接码表，无需改变三元式表•相同的三元式无需重复填进三元式表中，节省三元式空间7.1中间语言19.11.7copyright/27陕西理工学院计算机系《编译原理》27课堂练习•赋值语句X:=(A+B)*CB:=A+BY:=C*(A+B)对应的间接三元式为：间接码表（1）（2）（3）（1）（4）（1）（2）（5）三元式表(1)(+,A,B)(2)(*,1,C)(3)(:=,X,2)(4)(:=,B,1)(5)(:=,Y,2)三元式代码(1)(+,A,B)(2)(*,1,C)(3)(:=,X,2)(4)(+,A,B)(5)(:=,B,4)(6)(+,A,B)(7)(*,C,6)(8)(:=,Y,7)7.1中间语言19.11.7copyright/28陕西理工学院计算机系《编译原理》287.2说明语句•翻译工作–确定变量类型–分配地址空间——相对地址•地址空间的分配方式–有一个全局变量offset，记录了当前可用的空间的开始地址，初值为0–每次分配一个变量的空间，将offset增加相应的值7.2说明语句19.11.7copyright/29陕西理工学院计算机系《编译原理》29例：存储布局设整数类型域宽为4实数类型域宽为8•说明语句x:array[8]ofreal;i:integer;j:real;•名字类型相对地址0offset63x6467i6875j76xarray(8,real)0iinteger64jreal687.2说明语句19.11.7copyright/30陕西理工学院计算机系《编译原理》30说明语句的翻译•在符号表中填写变量的属性–类型、相对地址、作用域等•相对地址–全局变量表示为静态数据区的偏移值–局部变量表示为局部数据域(活动记录的部分）的偏移值7.2说明语句19.11.7copyright/31陕西理工学院计算机系《编译原理》31设计翻译模式•类型描述符T的属性–type类型–width占用的字节数•语义过程–enter(name,type,offset)在符号表中设置变量name的类型type和地址offset–array(num,type)描述数组类型–pointer(type)描述指针类型•全局量–offset跟踪下一个可用的相对地址的位置7.2说明语句19.11.7copyright/32陕西理工学院计算机系《编译原理》32说明语句的翻译模式P→DD→D;DD→id:TT→integerT→realT→array[num]ofT1T→↑T1说明段说明语句序列说明变量id类型为T数组指针{offset:=0}{}{enter(id.name,T.type,offset);offset:=off