资源描述
,第二级,第三级,第四级,第五级,第 1,2,讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第四章 语义分析和中间代码生成,4.1,语义分析概述,4.2,属性文法,4.3,几种常见的中间语言,4.4,表达式及赋值语句的翻译,4.5,控制语句的翻译,4.6,数组元素的翻译,4.7,过程或函数调用语句的翻译,4.8,说明语句的翻译,4.9,递归下降语法制导翻译方法简介,第四章,语义分析和中间代码生成,4.6,数组元素的翻译,4.7,过程或函数调用语句的翻译,4.8,说明语句的翻译,重点掌握,二维数组赋值语句的翻译,本讲目标,4.6,数组元素的翻译,关于数组,数组是用来存储一批同类型数据的数据结构，数组中的每一个元素具有同样长度的存储空间。,如果在编译时就知道一个数组存储空间的大小，则称其为,静态数组,，否则为,动态数组,。,例：,int a34;a21=5;,void*,malloc,(unsigned int size);,void*,calloc,(unsigned int num,unsigned int size);,我们主要讨论,静态数组元素,的引用如何翻译。关键问题：,1.,数组元素的地址计算方法,2.,数组元素的表示,4.6,数组元素的翻译,4.6.1,数组元素的地址计算及中间代码形式,数组元素的地址计算,数组元素的存放方式决定了数组元素的地址计算方法，地址计算方法决定了数组元素四元式的产生形式。,数组元素的存放方式：,按行存放,和,按列存放,。,我们主要讨论按行存放的数组元素地址计算方法。,1,2,3,4,5,6,7,8,9,A=,1,2,3,4,5,6,7,8,9,1,4,7,2,5,8,3,6,9,4.6,数组元素的翻译,1(a),2,3,4,i,1,A:,l,1,u,1,关键问题：,的地址是什么？,4.6,数组元素的翻译,1,2,3,4,5,6,7,8,9,10,11,12,A=,A3,3,的地址：,1+(,3,-1)*4+(,3,-1)=11,4.6,数组元素的翻译,4.6,数组元素的翻译,4.6,数组元素的翻译,实现数组元素的地址计算时，将产生两组四元式序列：,一组计算,CONSPART,，其值存放在临时变量,T,中；,另一组计算,VARPART,，其值存放在临时变量,T,1,中；,关键问题,2,：数组元素的表示,用,T T,1,(“,基址,”,+“,变址,”,),表示数组元素的地址。,对数组元素的赋值和引用就有如下两种不同的四元式：,(1),变址存数,：若有,T T,1,=X,，则可以用四元式,(=,，,X,，,_,，,TT,1,),表示。,(2),变址取数,：若有,X=T T1,，则可用四元式,(=,，,TT1,，,_,，,X),表示。,4.6,数组元素的翻译,4.6.2,赋值语句中数组元素的翻译,为了便于语法制导翻译，我们定义一个含有数组元素的赋值语句文法,GA,如下：,GA:,(1),AV=E,(2),Vielist|i,(3),elistelist,E|E,(4),EE+E|(E)|V,思考当前文法所能表达的语言？,其中，,A,代表赋值语句；,V,代表变量名；,E,代表算术表达式；,elist,代表由逗号分隔的表达式，它表示数组的一个下标；,i,代表简单变量名或数组名,。,4.6,数组元素的翻译,4.6.2,赋值语句中数组元素的翻译,在用产生式,(2),、,(3),进行归约时，为了能够及时计算数组元素的,VARPART,，我们将产生式,(2),、,(3),改写为：,(2),Vielist|i(3),elistelist,E|E,(2),Velist|i(3),elistelist,E|iE,则数组元素赋值语句文法变为：,GA:,(1),AV=E,(2),Velist|i (3),elistelist,E|iE,(4),EE+E|(E)|V,4.6,数组元素的翻译,关键非终结符之：,使用,GA,规约如下句子：,x=A,，,A,，,=,x,可见，有可能是简单变量规约得到，也可能是数组元素规约得到。因此，为设置两个语义值：,.place,和,V.offset,。,GA:,(1),AV=E,(2),Velist|i (3),elistelist,E|iE,(4),EE+E|(E)|V,4.6,数组元素的翻译,关键非终结符之：,如果,V,是一个简单变量名,，,V.place,保存该变量的入口地址，,V.offset=null;,如果,V,是一个数组元素,，,V.place,保存该数组元素的,CONSPART,，,V.offset,保存,VARPART;,4.6,数组元素的翻译,关键非终结符之,2,：,elist,对于类似于如下形式的句子：,A,E,，,E,，,E,，,，,E,=,x,最终规约为,elist=x,，继而,V=x,；,可见，,elist,负责规约数组元素中除了,之外的部分。对,elist,设置三个属性：,elist.ARRAY,，,elist.DIM,，,elist.place,。,GA:,(1),AV=E,(2),Velist|i (3),elistelist,E|iE,(4),EE+E|(E)|V,4.6,数组元素的翻译,非终结符之,2,：,elist,(1)elist.ARRAY,：表示数组名在符号表中的入口。例如：数组元素,A3,4,6,3,2,在规约过程中，所有,elist.ARRAY,的值是；,(2)elist.DIM,：数组维数的计数器。例如：,A3,4,6,3,2,规约为,elist,4,6,3,2,，,elist.DIM=1,；,elist,4,6,3,2,规约为,elist,6,3,2,，,elist.DIM=2,；,最终规约为,elist,，则,elist=5;,(3)elist.place,：登录已生成,VARPART,中间结果的单元名字在符号表中的存放位置，或是一个临时变量的整数码。因此，在逐次对,elist,归约的过程中，将逐步产生计算,VARPART,的四元式,VARPART=,(,(i,1,d,2,+,i,2,)d,3,+,i,3,)d,4,+,),+,i,n1,),d,n,+,i,n,4.6,数组元素的翻译,(1),AV=E,if(V.offset=null),emit(=,E.place,_,V.place);/*V,是简单变量*,/,else emit(=,E.place,_,V.placeV.offset);/*V,是下标变量*,/,含有数组元素,的赋值语句对应的文法,GA,及相应的语义子程序如下,(,省略语义检查，仅给出主要语义动作,),：,CONSPART,VARPART,4.6.2,赋值语句中数组元素的翻译,(,语义子程序,),(2),EE,(1),+E,(2,),T=newtemp;emit(+,E,(1),.place,E,(2),.place,T);E.place=T;(3),E(E,(1),),E.place=E,(1),.place;,4.6,数组元素的翻译,(4),EV,if(V.offset=null),E.place=V.place;/*V,是简单变量*,/,else T=newtemp;/*V,是下标变量*,/,emit(=,V.placeV.offset,_,T);,E.place=T;,将数组元素的值赋给,T,4.6,数组元素的翻译,(5),Velist,T=newtemp;emit(,，,elist.ARRAY,C,T);,V.place=T;V.offset=elist.place;/*,假定通过数组名的符号表入口不仅能获得地址,a,而且也能得到常数,C(CONSPART=a-C),*/,(6),Vi,V.place=entry(i);V.offset=null;,(8),elistiE,elist.place=E.place;elist.DIM:=1;elist.ARRAY=,entry(i);,(7),elistelist,(1),E,T=newtemp;k=elist,(1),.DIM+1;,d,k,=limit(elist,(1),.ARRAY,k);emit(*,elist,(1),.place,d,k,T);,emit(+,E.place,T,T);elist.ARRAY=elist,(1),.ARRAY;,elist.place=T;elist.DIM=k;,VARPART=,(,i,1,d,2,+,i,2,)d,3,+,i,3,)d,4,+,+,i,n1,d,n,)+i,n,4.6,数组元素的翻译,其它函数：,limit(ARRAY,k),计算数组,ARRAY,的第,k,维长度,d,k,4.6,数组元素的翻译,4.6,数组元素的翻译,例,4.10,已知,A,是一个,10,20,的数组,(,每维下界均为,1),且按行存放，求：,(1),赋值语句,X,=,AI,J,的四元式序列；,(2),赋值语句,AI,+,2,，,J,+,1,=,M,+,N,的四元式序列要求给出语法制导翻译过程。,解答,由于,A,是,10,20,的数组，故,:,d,1,=,10,，,d,2,=,20,，,C,=,l,1,d,2,+,l,2,=,21,。,(1),根据文法,GA,及对应的语义加工子程序，赋值语句,X=AI,J,的语法制导翻译过程如图,4-17,所示。,104(=,T,3,_,X),4.6,数组元素的翻译,例,4.10,已知,A,是一个,10,20,的数组,(,每维下界均为,1),且按行存放，求：,(1),赋值语句,X,=,AI,J,的四元式序列,:,100(*,I,20,T,1,),/*d,2,=20*/,101(+,J,T,1,T,1,),/*,得到,20I+J*/,102(,A,21,T,2,),/*,得到,A21*/,103(=,T,2,T,1,_,T,3,),/*T,2,T,1,即为,AI,J,，即,T,3,=T,2,1*/,105(+,，,M,，,N,，,T,5,),4.6,数组元素的翻译,例,4.9,已知,A,是一个,10,20,的数组,(,每维下界均为,1),且按行存放，求：,(2),赋值语句,AI,+,2,，,J,+,1,=,M,+,N,的四元式序列,:,100(+,，,I,，,2,，,T,1,),101(+,，,J,，,1,，,T,2,),102(*,，,T,1,，,20,，,T,3,),103(+,，,T,2,，,T,3,，,T,3,),104(,，,A,，,21,，,T,4,),106(,=,，,T,5,，,_,，,T,4,T,3,)/*T,4,T,3,=,T,5,*/,4.6,数组元素的翻译,例,.,设,A,为一个,10*20,的数组，即,n1=10,n2=20,并设,w=4.,对赋值语句,x:=A y,z,翻译成四元式。,注意：数组下界为,1,应该生成的三地址序列为：,T1:=y*20,T1:=T1+z,T2:=4*T1,T3:=A-84,T4=T3T2x:=T4,C,=(,l,1,*n2)+,l,2,)*w,4.6,数组元素的翻译,VAR,=(,i,1,*n2)+,i,2,)*w,4.7,过程或函数调用语句的翻译,4.7.1,过程调用,1.,定义和调用过程,(,函数、方法等,),是程序语言的主要特征之一。主要功能有：,(1),是模块化程序设计的主要手段；,(2),节省程序代码；,(3),扩充语言能力。,2.,过程调用：实质是把程序控制转到子程序。,3.,过程调用中遇到的主要问题：,(1),如何进行参数传递；,(2),子程序执行完之后如何回到主调程序；,(3),子程序回到主调程序时，运行环境的恢复。,4.7,过程或函数调用语句的翻译,在编译阶段对过程调用语句的翻译，所做的工作主要是,参数传递,。,1.,参数：,(1),实在参数：来自于主调过程,(2),形式参数：存在于被调过程,2.,传递方式：,(1),传地址,(call by reference),：把实参的地址传给形参；
展开阅读全文