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

1、第第 1 12 2 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：赵建邦主讲教师：赵建邦 第四章第四章 语义分析和中间代码生成语义分析和中间代码生成l4.1 4.1 语义分析概述语义分析概述l4.2 4.2 属性文法属性文法l4.3 4.3 几种常见的中间语言几种常见的中间语言l4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l4.5 4.5 控制语句的翻译控制语句的翻译l4.6 4.6 数组元素的翻译数组元素的翻译l4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l4.8 4.8 说明语句的翻译说明语句的翻译l4.9 4.9 递归下降语法制导翻译

2、方法简介递归下降语法制导翻译方法简介u第四章第四章语义分析和中间代码生成语义分析和中间代码生成l4.6 4.6 数组元素的翻译数组元素的翻译l4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l4.8 4.8 说明语句的翻译说明语句的翻译u重点掌握重点掌握l二维数组赋值语句的翻译二维数组赋值语句的翻译本讲目标本讲目标 4.6 4.6 数组元素的翻译数组元素的翻译u关于数组关于数组l数组是用来存储一批同类型数据的数据结构，数组中的每一数组是用来存储一批同类型数据的数据结构，数组中的每一个元素具有同样长度的存储空间。个元素具有同样长度的存储空间。l如果在编译时就知道一个数组存储空间的

3、大小，则称其为如果在编译时就知道一个数组存储空间的大小，则称其为静静态数组态数组，否则为，否则为动态数组动态数组。 例：例： int a34; a21 = 5; void *malloc(unsigned int size); void *calloc(unsigned int num, unsigned int size);l我们主要讨论我们主要讨论静态数组元素静态数组元素的引用如何翻译。的引用如何翻译。4.6 4.6 数组元素的翻译数组元素的翻译u4.6.1 数组元素的地址计算及中间代码形式数组元素的地址计算及中间代码形式l数组元素的地址计算数组元素的地址计算 数组元素的存放方式决定了数组

4、元素的地址计算方法，地址数组元素的存放方式决定了数组元素的地址计算方法，地址计算方法决定了数组元素四元式的产生形式。计算方法决定了数组元素四元式的产生形式。 数组元素的存放方式：数组元素的存放方式：按行存放按行存放和和按列存放按列存放。l我们主要讨论按行存放的数组元素地址计算方法。我们主要讨论按行存放的数组元素地址计算方法。123456789A=A=1234567891472583694.6 4.6 数组元素的翻译数组元素的翻译4.6 4.6 数组元素的翻译数组元素的翻译4.6 4.6 数组元素的翻译数组元素的翻译l实现数组元素的地址计算时，将产生两组四元式序列：实现数组元素的地址计算时，将产

5、生两组四元式序列： 一组计算一组计算CONSPART，其值存放在临时变量，其值存放在临时变量T中；中； 另一组计算另一组计算VARPART，其值存放在临时变量，其值存放在临时变量T1中；中； 用用T T1(“基址基址”+“变址变址”)表示数组元素的地址。表示数组元素的地址。l对数组元素的赋值和引用就有如下两种不同的四元式：对数组元素的赋值和引用就有如下两种不同的四元式：(1) 变址存数变址存数：若有：若有T T1 =X，则可以用四元式，则可以用四元式 (=，X，_， TT1)表示。表示。(2) 变址取数变址取数：若有：若有X= T T1 ，则可用四元式，则可用四元式 (=， TT1 ，_，X)

6、表示。表示。4.6 4.6 数组元素的翻译数组元素的翻译u4.6.2 赋值语句中数组元素的翻译赋值语句中数组元素的翻译l为了便于语法制导翻译，我们定义一个含有数组元素的赋值为了便于语法制导翻译，我们定义一个含有数组元素的赋值语句文法语句文法GA如下：如下： GA: (1) AV=E(2) Vielist | i(3) elistelist,E | E(4) EE+E | (E) | V思考当前文法所能表达的语言？思考当前文法所能表达的语言？其中，其中，A代表赋值语句；代表赋值语句；V代表变量名；代表变量名；E代表算术表达式；代表算术表达式；elist代表由逗号分隔的表达式，它表示数组的一个下标

7、；代表由逗号分隔的表达式，它表示数组的一个下标；i代表简单变量名或数组名代表简单变量名或数组名。4.6 4.6 数组元素的翻译数组元素的翻译u4.6.2 赋值语句中数组元素的翻译赋值语句中数组元素的翻译l在用产生式在用产生式(2)、(3)进行归约时，为了能够及时计算数组元素进行归约时，为了能够及时计算数组元素的的VARPART，我们将产生式，我们将产生式(2)、(3)改写为：改写为：(2) Vielist | i(3) elistelist,E | E(2) Velist | i(3) elistelist,E | iE则数组元素赋值语句文法变为：则数组元素赋值语句文法变为： GA: (1)

8、AV=E(2) Velist | i (3) elistelist,E | iE(4) EE+E | (E) | V4.6 4.6 数组元素的翻译数组元素的翻译l关键非终结符之：关键非终结符之：使用使用GA规约如下句子：规约如下句子： x = A， A，=x可见，有可能是简单变量规约得到，也可能是数组元素规可见，有可能是简单变量规约得到，也可能是数组元素规约得到。因此，为设置两个语义值：约得到。因此，为设置两个语义值：.place和和V.offset。 GA: (1) AV=E(2) Velist | i (3) elistelist,E | iE(4) EE+E | (E) | V4.6 4

9、.6 数组元素的翻译数组元素的翻译l关键非终结符之：关键非终结符之： 如果如果V是一个简单变量名是一个简单变量名，V.place保存该变量的入口地址，保存该变量的入口地址，V.offset = null; 如果如果V是一个数组元素是一个数组元素，V.place保存该数组元素的保存该数组元素的CONSPART，V.offset 保存保存VARPART;4.6 4.6 数组元素的翻译数组元素的翻译l关键非终结符之关键非终结符之2：elist对于类似于如下形式的句子：对于类似于如下形式的句子： AE，E，E，E=x最终规约为最终规约为elist = x，继而，继而 V= x ； 可见，可见，elis

10、t负责规约数组元素中除了负责规约数组元素中除了之外的部分。对之外的部分。对elist设置设置三个属性：三个属性：elist.ARRAY，elist.DIM，elist.place。 GA: (1) AV=E(2) Velist | i (3) elistelist,E | iE(4) EE+E | (E) | V4.6 4.6 数组元素的翻译数组元素的翻译l非终结符之非终结符之2：elist(1)elist.ARRAY：表示数组名在符号表中的入口。例如：数组：表示数组名在符号表中的入口。例如：数组元素元素A3,4,6,3,2在规约过程中，所有在规约过程中，所有elist.ARRAY的值是；的值

11、是；(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归约的过程中，将逐步产生计算归约的过程

12、中，将逐步产生计算VARPART的四的四元式元式VARPART=(i1d2 + i2)d3 + i3)d4 + )+ in1)dn + in4.6 4.6 数组元素的翻译数组元素的翻译(1) AV=E if(V.offset=null) emit(=,E.place,_,V.place); /*V是简单变量是简单变量*/ else emit(=,E.place,_,V.placeV.offset); /*V是下标变量是下标变量*/ 含有数组元素含有数组元素的赋值语句对应的文法的赋值语句对应的文法GAGA及相应的语义子程序及相应的语义子程序如下如下( (省略语义检查，仅给出主要语义动作省略语义检

13、查，仅给出主要语义动作) )：CONSPARTVARPARTu4.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.6 数组元素的翻译数组元素的翻译(4) EV if (V.offset=null) E.place=V.place; /*V是简单变量是简单变量*/ else T=newtemp; /*V是下标变量是下标变量*/ emit(= ,V.

14、placeV.offset,_,T); E.place=T; 将数组元素的值赋给T4.6 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:

15、=1; elist.ARRAY=entry(i);(7) elistelist(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 + + in1dn)+in4.6 4.6 数组元素的翻译数组元素的翻译其它函数：其它函数： limit(ARRAY,k)计算

16、数组计算数组ARRAY的第的第k维长度维长度dk4.6 4.6 数组元素的翻译数组元素的翻译 4.6 4.6 数组元素的翻译数组元素的翻译例例4.9 已知已知A是一个是一个10 20的数组的数组(每维下界均为每维下界均为1)且按行存放，且按行存放，求：求：(1) 赋值语句赋值语句X = AI,J的四元式序列；的四元式序列； (2) 赋值语句赋值语句AI + 2，J + 1 = M + N的四元式序列的四元式序列要求给出语法制导翻译过程。要求给出语法制导翻译过程。解答解答 由于由于A是是10 20的数组，故的数组，故: d1 = 10，d2 = 20，C = l1 d2 + l2 = 21。(1

17、) 根据文法根据文法GA及对应的语义加工子程序，赋值语句及对应的语义加工子程序，赋值语句X=AI, J的语法制导翻译过程如图的语法制导翻译过程如图4-17所示。所示。图图4-17 X=AI,J的语法制导翻译过程的语法制导翻译过程104(=, T3, _, X)4.6 4.6 数组元素的翻译数组元素的翻译例例4.9 已知已知A是一个是一个10 20的数组的数组(每维下界均为每维下界均为1)且按行存放，且按行存放，求：求：(1) 赋值语句赋值语句X = AI,J的四元式序列的四元式序列: 100(*, I, 20, T1) /*d2=20*/101(+, J, T1, T1) /*得到得到20I+

18、J*/102(, A, 21, T2) /*得到得到A21*/103(= ,T2T1,_,T3) /*T2T1即为即为AI,J，即，即 T3=T21*/105(+，M，N，T5)4.6 4.6 数组元素的翻译数组元素的翻译例例4.9 已知已知A是一个是一个10 20的数组的数组(每维下界均为每维下界均为1)且按行存放，且按行存放，求：求：(2) 赋值语句赋值语句AI + 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，_，T4T3

19、) /*T4T3 = T5*/4.6 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=T3T2x:=T4C=( (l1*n2)+l2)*w4.6 4.6 数组元素的翻译数组元素的翻译VAR=( (i1*n2)+i2)*w4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译u4.7.

20、1 过程调用过程调用l1.定义和调用过程定义和调用过程(函数、方法等函数、方法等)是程序语言的主要特征之一。是程序语言的主要特征之一。主要功能有：主要功能有： (1) 是模块化程序设计的主要手段；是模块化程序设计的主要手段； (2) 节省程序代码；节省程序代码； (3) 扩充语言能力。扩充语言能力。l2.过程调用：实质是把程序控制转到子程序。过程调用：实质是把程序控制转到子程序。l3.过程调用中遇到的主要问题：过程调用中遇到的主要问题： (1) 如何进行参数传递；如何进行参数传递； (2) 子程序执行完之后如何回到主调程序；子程序执行完之后如何回到主调程序； (3) 子程序回到主调程序时，运行

21、环境的恢复。子程序回到主调程序时，运行环境的恢复。4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l在编译阶段对过程调用语句的翻译，所做的工作主要是在编译阶段对过程调用语句的翻译，所做的工作主要是参数参数传递传递。l1.参数：参数： (1) 实在参数：来自于主调过程实在参数：来自于主调过程 (2) 形式参数：存在于被调过程形式参数：存在于被调过程l2.传递方式：传递方式： (1) 传地址传地址(call by reference)：把实参的地址传给形参；：把实参的地址传给形参； (2) 传值传值(call by value)：把实参值的拷贝传给形参。：把实参值的拷贝传给形参。4

22、.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l如何传递实参地址？如何传递实参地址？ (1) 如果实参是一个变量（包括下标变量），则直接传递该变如果实参是一个变量（包括下标变量），则直接传递该变量的地址；量的地址； (2) 如果实参是一个常量或表达式如果实参是一个常量或表达式(如：如：2或者或者X+2)，现将它的，现将它的值计算出来并存放在临时变量值计算出来并存放在临时变量T中，然后传递中，然后传递T的地址。的地址。l被调过程执行的时候，会在栈中为其分配内存空间。被调过程执行的时候，会在栈中为其分配内存空间。 被调过程的每个形参都有一个单元被调过程的每个形参都有一个单元(称为称

23、为形式单元形式单元)，用来存放，用来存放对应实参的地址。对应实参的地址。 因此，在被调过程的内部语句执行之前，必须先把实参的地因此，在被调过程的内部语句执行之前，必须先把实参的地址取到对应的形参单元中。然后才能执行本过程中的语句。址取到对应的形参单元中。然后才能执行本过程中的语句。4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译u4.7.2 过程调用语句的翻译过程调用语句的翻译(传址传址)l1.文法：文法： GS: Scall i (elist) elist elist,E | EP() Q(x,y,z); Q(int a,int b,int c) call i(E(1),E(2),E(3);1.使用队列保存使用队列保存E(i);2.传递传递E(i)的地址的地址;3.call Q;4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l2.语义子程序：语义子程序：for (队列队列queue中的每个中的每个P) emit(par, _, _, P); emit(call, _, _, i.place);将将E.place加入到加入到queue的队尾的队尾 GS: Scall i (elist) elist elist,E elist E初始化初始化queue,仅包含仅包含E.place