编译原理 - 陈火旺版 - 第七章

1编译方法中国人民大学信息学院陈文萍2第7章语义分析和中间代码生成中间语言一些语法成分的翻译说明语句赋值语句布尔表达式控制语句过程调用类型检查3语义分析概述静态语义检查类型控制流一致性名字的匹配翻译生成中间语言：逻辑清楚，易于优化，移植性好，中间语言的形式：后缀式，三元式，四元式，间接三元式，图4后缀式后缀式（逆波兰式）表达式E的后缀形式E’的写法：•若E是变量或常量，则E’=E•若E=E1opE2,则E’=E1’E2’op•若E=(E1)，则E’=E1表达式变为后缀形式的语义规则E→E1opE2{E.CODE:=E1.CODE||E2.CODE||op}E→(E1){E.CODE:=E1.CODE}E→i{E.CODE:=i}例如：a*(b+c)后缀形式：abc+*5后缀式特点：•运算对象(操作数）的出现顺序与中缀表示相同•运算符按实际计算的顺序从左到右排序，且每一运算符总是紧跟在它的运算对象之后，无须括号•计值易于在计算机上实现例如，后缀式ab＋c*的计值过程•1，把a压入栈•2，把b压入栈•3，弹出栈顶两项，相加之和压入栈•4，把c压入栈•5，弹出栈顶两项，相乘之积压入栈推广到表达式外的范围•例如a:=b*c+b*d后缀形式：abc*bd*+:=6图抽象语法树内部结点表示运算符，后代表示运算对象无循环有向图（DAG）与抽象语法树•相同之处：内部结点表示运算符，后代表示运算对象•不同之处：考虑到公共子表达式（不只一个父结点），更加紧凑高效实现途径：记录指针7三地址代码三地址代码的一般形式：x:=yopzy,z:操作数x：结果op：操作符例：x＋y*z的三地址形式序列：T1:=y*zT2:=x+T1三地址代码的具体实现四元式三元式间接三元式8四元式是一个带有四个域的记录结构（操作符，左操作数，右操作数，结果）当是一元运算时，无右操作数；当是零元运算时无左、右操作数在按语法制导翻译产生的四元式中，操作符用一整数码表示，用于表示运算符的种属，及其他语义信息，如数据类型，运算方式及运算精度等。另三个量通常是指向符号表有关名字的入口例如：对于赋值语句A:=－B*(C+D),四元式表示为•(－,B,,T1)•(+,C,D,T2)•(*,T1,T2,T3)•(:=,T3,,A)9三元式三个域:(操作符，左操作数，右操作数)三元式编号代表运算结果例如：赋值语句A:=－B*(C+D)，写成三元式①(－，B，)②(+，C，D)③(*,①,②)④(:=,A,③)同四元式指向符号表指针或指向三元式的指针10间接三元式三元式序列所需存储空间少（不需临时变量），但不便于优化处理解决方法：建立两个表：三元式表：存放各三元式本身间接码表：按运算先后顺序列出三元式在三元式表中的位置例如，对以下赋值语句X:=(A+B)*CB:=A+BY:=C*(A+B)若用三元式表示，可写成(1)(+,A,B)(2)(*,(1),C)(3)(:=,X,(2))(4)(:=,B,(1))(5)(+,A,B)(6)(*,C,(5))(7)(:=,Y,(6))其中，三元式（1）和（5）形式完全一致，但却不能将（5）省去；对于（2）、（6）来说，也应当说是一致的（因为乘法满足交换律)，同样不能将（6）省去（为什么？）。然而，若按间接三元式表示，则可写成：间接码表三元式表（1）（1）（+，A，B）（2）（2）（*,（1），C）（3）（3）（:＝，X，（2））（4）（4）（:＝，B，（1））（1）（5）（:＝，Y，（2））（2）（5）11三种三地址表示形式的比较三元式优点：节省空间缺点：不利于优化四元式与间接三元式缺点：占用存储空间相对较大优点：代码调整时改动少12课堂练习求下列各式的逆波兰表示？1，-a-(b*c/(c-d)+(-b)*a)2，-A+B*C↑(D/E)/F3，写出A+B*(C-D)-E/F↑G的三元组表示和四元组表示13课堂练习1，-a-(b*c/(c-d)+(-b)*a)的逆波兰表示：a-bc*cd-/b-a*+-2，-A+B*C↑(D/E)/F的逆波兰表示:A-BCDE/↑*F/+3，A+B*(C-D)-E/F↑G的三元组表示：(1)（－，C,D)(2)(*,B,(1))(3)(+,A,(2))(4)(↑,F,G)(5)(/,E,(4))(6)(-,(3),(5))四元组表示(1)（－，C,D,T1)(2)(*,B,T1,T2)(3)(+,A,T2,T3)(4)(↑,F,G,T4)(5)(/,E,T4,T5)(6)(-,T3,T5,T6)14说明语句的翻译说明语句定义局部于该过程的数据对象（以标识符标识）为数据对象分配空间，在符号表中登记数据对象的名字，类型，分配的存储地址有过程嵌套的，表示出嵌套关系15说明语句的翻译简单的说明语句的翻译模式P→MDM→εD→D;DD→i:TT→integerT→realT→array[num]ofT1T→↑T1{offset:=0}{enter(i.name,T.type,offset);offset:=offset+T.width}{T.type:=integer;T.width:=4}{T.type:=real;T.width:=8}{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}{T.type:=pointer(T1.type);T,width:=4}16说明语句的翻译嵌套的过程声明中声明语句翻译模式增加一个嵌套过程的文法：D→proci;D1;S•i：过程名，该过程局部于它的外围过程•创建过程i的符号表，登记过程i中说明的名字•过程i的外围过程的名字在过程i中可用，过程i有指针指向它的外围过程符号表符号表的组织•例：见书P17617说明语句的翻译嵌套过程声明的翻译模式P→MDM→εD→D;DD→i:TD→proci;ND1;SN→ε......{addwidth(top(tblptr),top(offset));//在符号表表头中记录所有名字总长度pop(tblptr);pop(offset)}{t:=mktable(nil);push(t,tblptr);push(0,offset)}//tblptr：保存外层过程的符号表指针{enter(top(tblptr),i.name,T.type,top(offset);top(offset):=top(offset)+T.width}//为数据对象分配存储空间{t:=top(tblptr);//嵌套过程符号表指针Addwidth(t,top(offset);//嵌套过程符号表长度pop(tblptr);pop(offset)//弹出嵌套过程的符号表指针enterproc(top(tblptr),i.name,t)}//外围过程中设置一新项指向嵌套过程符号表{t:=mktable(top(tblptr));//创建新符号表，有指针指向外围过程符号表push(t,tblptr);push(0,offset)}//初始化嵌套过程符号表……18说明语句的翻译记录类型的声明文法：T→recordLDend为记录创建一个符号表记录域名（由D表示）T→recordLDendL→ε......{T.type:=record(top(tblptr));T.width:=top(offset);//记录的长度pop(tblptr);pop(offset)}{t:=mktable(nil);//为记录创建符号表push(t,tblptr);push(0,offset)}……19赋值语句的翻译只含简单算术表达式的赋值语句约定算符优先性，结合性翻译模式S→i:=EE→E1opE2E→-E1E→(E1)E→i{P:=lookup(i.name);//查找符号表，看变量i是否说明ifPnilthenemit(P,‘:=’,E.place)//生成三地址语句elseerror}{E.place:=newtemp;//结果指向临时变量emit(E.place,‘:=’,E1.place,‘op’,E2.place)}{E.place:=newtemp;emit(E.place,‘:=’,‘unimus’,E1.place)}{E.place:=E1.place}{P:=lookup(i.name);ifPnilthenE.place:=Pelseerror}20赋值语句的翻译例：a:=-b*c+d按上述方案的语法制导翻译过程。按归约次序依次为1）E→b，i.name为b，设E.place为b；2）E→-E1,设newtemp为t1，emit生成三地址语句t1:=uminusb;3)E→c，i.name为c，设E.place为c；4)E→E1*E2,设newtemp为t2，此时E1.place为t1，E2.place为c，emit生成三地址语句t2:=t1*c;5)E→d，i.name为d，设E.place为d；6)E→E1+E2,设newtemp为t3，此时E1.place为t2，E2.place为d，emit生成三地址语句t3:=t2+d;7)S→a:=E,i.name为a，此时E.place为t3，emit生成三地址语句a:=t3；21赋值语句的翻译类型转换许多语言允许混合类型运算，但在运算前须转换为相同类型引入类型转换功能的三地址语句t:=itrx，将整型变量x转换为实型变量t对于产生式E-E1opE2,语义子程序可写成t:=newtemp;ifE1.TYPE=integerandE2.TYPE=integerthenbeginemit(t,‘:=‘,E1.place,’op’,E2.PLACE);E.TYPE:=integerendelseifE1.TYPE=realandE2.TYPE=realthenbeginemit(t,‘:=‘,E1.place,’op’,E2.PLACE);E.TYPE:=realendelseifE1.TYPE=intergerthenbegint1:=newtemp;emit(t1,‘:=‘,itr,E1.PLACE);emit(t,‘:=‘,t1,’op’,E2.PLACE);E.TYPE:=realendelsebegint1:=newtemp;emit(t1,‘:=‘,itr,E2.PLACE);emit(t,‘:=‘,E1.PLACE,’op’,t1);E.TYPE:=realendE.place:=t22赋值语句的翻译含数组元素的赋值语句数组元素（下标变量）地址的计算•n维数组定义,如：A[l1:u1,l2:u2,……,ln:un]:integer•对下标变量的翻译的核心问题是计算其地址。计算机中按一定顺序存贮数组的各元素（按行/按列存贮），这里按行计算•n维数组元素的下标表中，第k维是dk进制的，dk=uk-lk+1,因此n维数组元组A[i1,i2,…,in]的存储地址D为：D=a+(i1-l1)*d2*d3*…*dn+(i2-l2)*d3*…*dn+…+(in-1-ln-1)*dn+(in-ln)=a-[(…(l1*d2+l2)*d3+l3)*d4+…+ln-1)*dn+ln]+[(…(i1*d2+i2)*d3+i3)*d4+…+in-1)*dn+in]令C=[(…(l1*d2+l2)*d3+l3)*d4+…+ln-1)*dn+ln]CONSPART=a–CVARPART=[(…(i1*d2+i2)*d3+i3)*d4+…+in-1)*dn+in]23赋值语句的翻译•CONSPART与元素下标无关，每个数组只计算一次•a为数组元素的首地址•为数组创建内情向量表：记录CONSPART,lk,uk,界差dk24赋值语句的翻译含下标变量的赋值语句的翻译文法描述：S-L:=EL-Elis