《编译原理-算术表达式赋值句数组元素的引用布尔表达式》由会员分享，可在线阅读，更多相关《编译原理-算术表达式赋值句数组元素的引用布尔表达式（37页珍藏版）》请在金锄头文库上搜索。
1、1,上次课程内容回顾,参数传递（续） 引用调用、复写-恢复、名字调用 嵌套定义的过程中信息的存储 作用域信息的保存 过程的作用域(过程与程序块的区别) 过程嵌套的层次 符号表的组织与符号表中的作用域信息 语法制导翻译生成符号表 用栈保留各符号表节点信息 进入过程声明D之前构造符号表，分析D时填写符号表，退出D后在外层符号表中加入此过程条目,2,4.5 简单算术表达式与赋值句,简单算术表达式和赋值句，是指表达式和赋值句中变量是不可再分的简单变量。,讨论所基于的文法： A id:=E E E + E | E * E | - E | ( E ) | id,3,4.5.1 简单算术表达式的语法制导翻译
2、,属性.place： 存放E的变量地址(符号表中地址或临时变量的编码)； 过程emit(result := arg1 op arg2)： 生成“result:= arg1 op arg2”的三地址码。,(1) Aid:=E (2) EE1+E2 (3) EE1*E2 (4) E-E1 (5) E(E1) (6) Eid,E.place:=entry(id.name),E.place:=newtemp; emit(E.place := E1.place + E2.place),E.place:=newtemp; emit(E.place := E1.place * E2.place),E.pla
3、ce:=newtemp; emit(E.place := - E1.place),E.place:= E1.place,emit(entry(id.name) := E.place),4,4.5.2 变量的（内部）类型转换,强制（coercion）：按照一定的原则，将不同类型的变量在内部转换为相同的类型，然后进行同类型变量的计算。,运算的转换原则：,赋值的转换原则：,属性.type：取值int或real 表达式的类型判定树：,5,4.5.2 变量的（内部）类型转换（续1）,三地址码： T := itr E：将E从整型变为实型，结果存放T中 T := rti E：将E从实型变为整型，结果存放T中
4、,语义规则： A id := E, t_type:=entry(id.name).type; if t_type=E.type then emit(entry(id.name) := E.place); else T := newtemp; emit(entry(id.name) := T); end if; ,if t_type=int then emit(T := rti E.place); else emit(T := itr E.place); end if;,结果,6,4.5.2 变量的（内部）类型转换（续2）,EE1 op E2, T:=newtemp；E.type:=real;
5、if E1.type=int then else end if; E.place:=T; ,其他语义规则看教材P128129,if E2.type=int then emit(T := E1.place OPi E2.place); E.type := int; else U:=newtemp; emit(U := itr E1.place); emit(T := U OPr E2.place); end if;,if E2.type=int then U:=newtemp; emit(U := itr E2.place); emit(T := E1.place OPr U); else em
6、it(T := E1.place OPr E2.place); end if;,前页,7,4.5.2 变量的（内部）类型转换（续3）,例4.17 x:=-a*b+c的语法制导翻译，x、a、b是整型，c是实型。,序号 产生式 中间代码 (1) E1a (2) E2-E1 t1:=-a (3) E3b (4) E4E2*E3 t2:=t1*ib (5) E5c (6) E6E4*E5 t4:=itr t2 t3:=t4+rc (7) Ax:=E6 t5:=rti t3 x := t5,8,4.6 数组元素的引用,确定数组空间的存储分配： 以第一个元素地址为首地址，分配一个连续空间。 多维到一维存储
7、空间的映射方法： 以行为主，以列为主 考虑三行、三列的二维数组 a02, 24 ：,a0,2 a0,3 a0,4 a1,2 a1,3 a1,4 a2,2 a2,3 a2,4,以行为主存放时的元素排列：,a0,2 a0,3 a0,4,a1,2 a1,3 a1,4,a2,2 a2,3 a2,4,以列为主存放时的元素排列：,a0,2 a1,2 a2,2,a0,3 a1,3 a2,3,a0,4 a1,4 a2,4,确定数组元素地址的两个要素：首地址和相对首地址的偏移量,不同的映射方式，使得同一个数组元素相对首地址的偏移量不同 例如：a1,4，偏移量分别是5和7,9,确定映射方式的两种方法,1由声明时的
8、语法确定映射方式： a:arrayd1 of arrayd2of.arraydn of integer; 引用方式：ai1,i2, .,in或ai1i2.in 2由编译器确定映射方式： a : array d1, d2, ., dn of integer; 引用方式：ai1,i2, .,in,数组元素引用时地址的确定： 1根据映射方式求出计算公式； 2根据计算公式设计语义规则。,10,4.6.1 数组元素的地址计算,三个假设条件： 数组元素以行为主存放，推广到n维，就是数组的第i维中每个成员是di个n-i维的数组，其中di是第i维成员的个数； 数组每维的下界均为1； 每个元素仅占一个标准存贮单
9、元（可以认为是一个字或者一个字节）。 约定： 数组的声明： Ad1, d2, , dn 数组元素的引用： Ai1, i2, , in,11,一维数组元素的地址计算：,addr(Ai) = a + (i-1)*w,二维数组元素的地址计算： addr(Ai1,i2)=a+(i1-1)*d2+(i2-1)*w,跳过前i-1个单元,跳过前i1-1行,跳过前i2-1个单元,12,n维数组元素的地址计算,addr(Ai1，i2，.，in) =a+(i1-1)*d2*d3*.*dn+(i2-1)*d3*d4*.*dn+.+ (in-1)*w =a-(d2*d3*.*dn+d3*d4*.*dn+.+dn+1)
10、*w +(i1*d2*d3*.*dn+i2*d3*d4*.*dn+.+in-1*dn+in)*w =ac*w+v*w 根据假设条件w=1: addr(Ai1，i2，.，in)=ac+v 其中：,c = d2*d3*d4.*dn+d3*d4*d5.*dn+*d4*d5*d6.*dn.+dn+1 = (d2+1)*d3*.*dn+d4*d5.*dn+.+dn+1 =(d2+1)*d3+1)*d4*d5.*dn+.+dn+1 = (.(d2+1)*d3+1)*d4.+1)*dn+1,同理： v = (.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+in,13,n维数组元素的地址计算（
11、续1）,c=(.(d2+1)*d3+1)*d4.+1)*dn+1 v=(.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+in,令： v1 = i1 则： v2 = i1*d2+i2 = v1*d2+i2 v3 = (v1*d2+i2)*d3+i3 = v2*d3+i3 于是有： v1 = i1 vj = vj-1*dj+ij (j=2，3，., n) (4.4) 同理可得：c1 = 1 cj = cj-1*dj+1 (j=2，3，., n) (4.3),最终得到数组元素引用的地址计算公式： addr(Ai1，i2，.，in)=a-c+v=CONSPART+VARPART 注意：
12、如果w1,则c和v分别需要乘一个w，即： addr(Ai1，i2，.，in)=a-cw+vw=CONSPART+VARPART,14,4.6.2 数组元素引用的语法制导翻译,数组元素的寻址：CONSPARTVARPART，或者T1T 取值的三地址码：X:=T1T 赋值的三地址码：T1T:=X, 引入数组元素后的赋值句文法 A V := E V id | idEL (G4.4) EL E | EL ，E E E + E | ( E ) | V,引入了新的非终结符V，使得分析树增高。 例如ai, j:=x的分析树：,根据此文法进行语法制导翻译有困难，无法使用递推公式（因为dj需要知道数组名a）。,
13、15,4.6.2 （续）,修改文法以适应递推公式的同步计算： A V := E (1) V id (2) | EL (3) EL id E (4) | EL , E (5) E E + E (6) | ( E ) (7) | V (8),- 得到数组名和第一维下标和v1 - 递归计算第i维的vi,- 完成数组元素的分析和对v的计算,根据修改后的文法， ai, j:=x的分析树变为：,16, 属性和函数,属性.array：数组名在符号表中的入口和数组首地址a。 属性.dim：数组维数计数器，记录当前分析到的维数。 属性.place： 简单变量id：仍然表示简单变量的地址， 数组元素idEL：存放
14、不变部分，一般可以是一个临时变量， 下标列表EL：存放vj=vj-1*dj+ij (j=2，3，., n)的临时变量。 属性.offset：保存数组元素的可变部分， 简单变量的offset为空，可记为null。 函数limit(array, k)：计算并返回数组array中第k维成员个数dk。,17,语义规则, if V.offset=null then emit(V.place := E.place); else emit(V.placeV.offset := E.place); end if; V.place:=entry(id.name); V.offset:=null; V.place
15、:=newtemp; emit(V.place :=EL.array - c); V.offset:=newtemp;emit(V.offset:=EL.place * w); EL.place:=E.place; EL.dim :=1; EL.array:=entry(id.name); T:=newtemp; k:=EL1.dim+1; dk:=limit(EL1.array, k); emit(T :=EL1.place * dk); emit(T := T + E.place); EL.array:=EL1.array; EL.place:=T; EL.dim:=k;,- Vk-1*dk - T:=Vk-1*dk+ik,例子,(1) AV:=E (2) Vid (3) VEL (4) ELidE (5) ELEL1,E,18,语义规则（续1）, T:=newtemp; emit(T := E1.place + E2.place); E.place:=T; E.place:=E1.place; if V.offset=null; then E.place:=V.place; el
