编译原理(4)语义-4(数组元素、过程、说明语句的翻译)

第12讲编译原理西北农林科技大学本科教程

主讲教师：赵建邦第四章语义分析和中间代码生成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数组元素的翻译关于数组数组是用来存储一批同类型数据的数据结构，数组中的每一个元素具有同样长度的存储空间。如果在编译时就知道一个数组存储空间的大小，则称其为静态数组，否则为动态数组。

例：inta[3][4];a[2][1]=5;

void*malloc(unsignedintsize);void*calloc(unsignedintnum,

unsignedintsize);我们主要讨论静态数组元素的引用如何翻译。关键问题：1.数组元素的地址计算方法2.数组元素的表示4.6数组元素的翻译4.6.1数组元素的地址计算及中间代码形式数组元素的地址计算

数组元素的存放方式决定了数组元素的地址计算方法，地址计算方法决定了数组元素四元式的产生形式。

数组元素的存放方式：按行存放和按列存放。我们主要讨论按行存放的数组元素地址计算方法。123456789A=1234567891472583694.6数组元素的翻译1(a)234i1A:l1u1关键问题：的地址是什么？4.6数组元素的翻译123456789101112A=A[3,3]的地址：1+(3-1)*4+(3-1)=114.6数组元素的翻译4.6数组元素的翻译4.6数组元素的翻译实现数组元素的地址计算时，将产生两组四元式序列：

一组计算CONSPART，其值存放在临时变量T中；

另一组计算VARPART，其值存放在临时变量T1中；关键问题2：数组元素的表示

用T[T1](“基址”+“变址”)表示数组元素的地址。对数组元素的赋值和引用就有如下两种不同的四元式：(1)

变址存数：若有T[T1]=X，则可以用四元式

([ ]=，X，_，

T[T1])表示。(2)变址取数：若有X=T[T1]，则可用四元式

(=[ ]，

T[T1]，_，X)表示。4.6数组元素的翻译4.6.2赋值语句中数组元素的翻译为了便于语法制导翻译，我们定义一个含有数组元素的赋值语句文法G[A]如下：G[A]:

(1)

A→V=E

(2)

V→i[elist]|i

(3)

elist→elist,E|E

(4)

E→E+E|(E)|V思考当前文法所能表达的语言？其中，A代表赋值语句；V代表变量名；E代表算术表达式；elist代表由逗号分隔的表达式，它表示数组的一个下标；i代表简单变量名或数组名。4.6数组元素的翻译4.6.2赋值语句中数组元素的翻译在用产生式(2)、(3)进行归约时，为了能够及时计算数组元素的VARPART，我们将产生式(2)、(3)改写为：(2)

V→i[elist]|i

(3)

elist→elist,E|E(2')

V→elist]|i

(3')

elist→elist,E|i[E则数组元素赋值语句文法变为：G[A]:

(1)

A→V=E

(2')

V→elist]|i

(3')

elist→elist,E|i[E

(4)

E→E+E|(E)|V4.6数组元素的翻译关键非终结符之１：Ｖ使用G[A]规约如下句子：

x=A［２，３］

A［２，３］=

x可见，Ｖ有可能是简单变量规约得到，也可能是数组元素规约得到。因此，为Ｖ设置两个语义值：Ｖ.place和V.offset。

G[A]:

(1)

A→V=E

(2')

V→elist]|i

(3')

elist→elist,E|i[E

(4)

E→E+E|(E)|V4.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。

G[A]:

(1)

A→V=E

(2')

V→elist]|i

(3')

elist→elist,E|i[E

(4)

E→E+E|(E)|V4.6数组元素的翻译非终结符之2：elist

(1)elist.ARRAY：表示数组名在符号表中的入口。例如：数组元素A[3,4,6,3,2]在规约过程中，所有elist.ARRAY的值是Ａ；

(2)elist.DIM：数组维数的计数器。例如：

A[3,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=((…((i1d2

+

i2)d3

+

i3)d4

+

…

)+

in−1)dn

+

in4.6数组元素的翻译(1)

A→V=E{if(V.offset==null)

emit(=,E.place,_,V.place);/*V是简单变量*/

else

emit([]=,E.place,_,V.place[V.offset]);

/*V是下标变量*/

}含有数组元素的赋值语句对应的文法G[A]及相应的语义子程序如下(省略语义检查，仅给出主要语义动作)：CONSPARTVARPART4.6.2赋值语句中数组元素的翻译(语义子程序)(2)

E→E(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)

E→V{if(V.offset==null)

E.place=V.place;/*V是简单变量*/

else{T=newtemp;/*V是下标变量*/

emit(=[],V.place[V.offset],_,T);

E.place=T;

}

}将数组元素的值赋给T4.6数组元素的翻译(5)

V→elist]{T=newtemp;

emit(−，elist.ARRAY,C,T);

V.place=T;V.offset=elist.place;}

/*假定通过数组名的符号表入口不仅能获得地址a而且也能得到常数C(CONSPART=a-C)*/(6)

V→i{V.place=entry(i);V.offset=null;}(8)

elist→i[E{elist.place=E.place;elist.DIM:=1;

elist.ARRAY=

entry(i);}(7)

elist→elist(1),E{T=newtemp;k=elist(1).DIM+1;

dk=limit(elist(1).ARRAY,k);

emit(*,elist(1).place,dk,T);

emit(+,E.place,T,T);

elist.ARRAY=elist(1).ARRAY;

elist.place=T;elist.DIM=k;}

VARPART=(…((i1d2

+

i2)d3

+

i3)d4

+

…

+

in−1dn)+in

4.6数组元素的翻译其它函数：

limit(ARRAY,k)计算数组ARRAY的第k维长度dk4.6数组元素的翻译4.6数组元素的翻译例4.10

已知A是一个10

×

20的数组(每维下界均为1)且按行存放，求：

(1)赋值语句X

=

A[I,J]的四元式序列；

(2)赋值语句A[I

+

2，J

+

1]

=

M

+

N的四元式序列

要求给出语法制导翻译过程。[解答]

由于A是10

×

20的数组，故:

d1

=

10，d2

=

20，C

=

l1d2

+

l2

=

21。

(1)根据文法G[A]及对应的语义加工子程序，赋值语句X=A[I,

J]的语法制导翻译过程如图4-17所示。104(=,T3,_,X)4.6数组元素的翻译例4.10

已知A是一个10

×

20的数组(每维下界均为1)且按行存放，求：

(1)赋值语句X

=

A[I,J]的四元式序列:

100(*,I,20,T1) /*d2=20*/

101(+,J,T1,T1) /*得到20I+J*/102(−,A,21,T2) /*得到A−21*/103(=[

],T2[T1],_,T3)/*T2[T1]即为A[I,J]，即

T3=T2[1]*/105(+，M，N，T5)4.6数组元素的翻译例4.9

已知A是一个10

×

20的数组(每维下界均为1)且按行存放，求：

(2)赋值语句A[I

+

2，J

+

1]

=

M

+

N的四元式序列:

100(+，I，2，T1)

101(+，J，1，T2)

102(*，T1，20，T3)

103(+，T2，T3，T3)104(−，A，21，T4)106([

]=，T5，_，T4[T3]) /*T4[T3]

=

T5*/4.6数组元素的翻译例.设A为一个10*20的数组，即n1=10,n2=20,并设w=4.对赋值语句x:=A[y,z]翻译成四元式。注意：数组下界为1应该生成的三地址序列为：T1:=y*20T1:=T1+zT2:=4*T1T3:=A-84T4=T3[T2]

x:=T4C=((l1*n2)+l2)*w4.6数组元素的翻译VAR=((i1*n2)+i2)*w4.7过程或函数调用语句的翻译4.7.1过程调用1.定义和调用过程(函数、方法等)是程序语言的主要特征之一。主要功能有：

(1)是模块化程序设计的主要手段；

(2)节省程序代码；

(3)扩充语言能力。2.过程调用：实质是把程序控制转到子程序。3.过程调用中遇到的主要问题：

(1)如何进行参数传递；

(2)子程序执行完之后如何回到主调程序；

(3)子程序回到主调程序时，运行环境的恢复。4.7过程或函数调用语句的翻译在编译阶段对过程调用语句的翻译，所做的工作主要是参数传递。1.参数：

(1)实在参数：来自于主调过程

(2)形式参数：存在于被调过程2.传递方式：

(1)传地址(callbyreference)：把实参的地址传给形参；

(2)传值(callbyvalue)：把实参值的拷贝传给形参。4.7过程或函数调用语句的翻译如何传递实参地址？

(1)如果实参是一个变量（包括下标变量），则直接传递该变量的地址；

(2)如果实参是一个常量或表达式(如：2或者X+2)，现将它的值计算出来并存放在临时变量T中，然后传递T的地址。被调过程执行的时候，会在栈中为其分配内存空间。

被调过程的每个形参都有一个单元(称为形式单元)，用来存放对应实参的地址。

因此，在被调过程的内部语句执行之前，必须先把实参的地址取到对应的形参单元中。然后才能执行本过程中的语句。4.7过程或函数调用语句的翻译4.7.2过程调用语句的翻译(传址)1.文法：

G[S]:S→calli(elist)

elist→elist,E|EP(){…Q(x,y,z);…}Q(inta,intb,intc){……}calli(E(1),E(2),E(3));1.使用队列保存E(i);2.传递E(i)的地址;3.callQ;4.7过程或函数调用语句的翻译2.语义子程序：{for(队列queue中的每个P)

emit(par,_,_,P);

emit(call,_,_,i.place);}{将E.place加入到queue的队尾}

G[S]:S→calli(elist)elist→elist,Eelist→E{初始化queue,仅包含E.place}例如：callQ(A+B,Z)被翻译为：(100)(+,A,B,T)(101)(par,_,_,T)(102)(par,_,_,Z)(103)(call,_,_,Q)4.8说明语句的翻译4.8.1变量说明的翻译说明语句的功能是说明源程序中每一个名字及其性质。文法1：文法2：

G[D]:D→intnamelist|floatnamelistnamelist→namelist,i|i

G'[D]:D→D,i|inti|floati(1)D→inti{fill(i,int);D.att=int;}缺点：变量列表先规约成namelist,最后才能确定变量的类型优点：每扫描一个变量，就