【编译原理系列】算术表达式与数组元素翻译

灰太狼 2023-01-10 13:08 122阅读 0赞

# 简单算术表达式与赋值句 #

简单算术表达式和赋值句，是指**表达式和赋值句中变量**是不可再分的**简单变量**

## 语法制导翻译 ##

1.  属性.place：存放E的**变量地址**(符号表中地址或临时变量的编码)
2.  过程emit(result ‘:=’ arg1 ‘op’ arg2)：**生成**“result:= arg1 op arg2”的**三地址码**

产生式：					语义规则：
    (1) A→id:=E		{emit(entry(id.name) ':=' E.place)} 
    (2) E→E1+E2		{E.place:=newtemp； 
     emit(E.place ':=' E1.place '+' E2.place)} 
    (3) E→E1*E2		{E.place:=newtemp； 
     emit(E.place ':=' E1.place '*' E2.place)} 
    (4) E→-E1		{E.place:=newtemp； 
     emit(E.place ':=' '-' E1.place)} 
    (5) E→(E1)		{E.place:= E1.place} 
    (6) E→id 		{E.place:=entry(id.name)}

## 内部类型转换 ##

**强制（coercion）：** 按照一定的原则，将不同类型的变量在内部转换为相同的类型，然后进行同类型变量的计算

三地址码：

*  T := itr E：将E从整型变为实型，结果存放T中
 *  T := rti E：将E从实型变为整型，结果存放T中

1. A->id:=E
    { tmode:=entry(id.name).mode;
      if   tmode=E.mode
      then emit(entry(id.name) ':=' E.place);
      else T := newtemp;
            if   tmode=int 
            then emit(T  ':=' rti E.place); 
            else emit(T  ':=' itr E.place);
            end if;
            emit(entry(id.name) ':=' T);
      end if;
    }

2. E→E1 op E2
    { T:=newtemp；E.mode:=real;
      if   E1.mode=int
      then  if   E2.mode=int
            then emit(T ':=' E1.place OPi E2.place);
                 E.mode := int;
            else U:=newtemp; 
                 emit(U ':=' itr E1.place);
                 emit(T ':=' U OPr E2.place);
            end if;
      else 	if   E2.mode=int
            then U:=newtemp;
                 emit(U ':=' itr E2.place);
                 emit(T ':=' E1.place OPr U);
            else emit(T ':=' E1.place OPr E2.place);
            end if;
      end if;
      E.place:=T;
    }

# 数组元素的引用 #

确定数组元素地址的两个要素：

*  **首地址**和**相对首地址的偏移量**
 *  不同的映射方式（行or列），使得同一个数组元素相对首地址的**偏移量不同**

确定映射方式的两种方法：

*  由声明时的语法确定映射方式
 *  由编译器确定映射方式

三个假设条件：

*  数组元素以**行**为主存放，推广到n维，就是数组的第i维是di个n-i维的数组(每个成员是一个n-i维的数组) ，其中di是第i维成员的个数
 *  数组每维的**下界均为1**
 *  每个**元素**仅占**一个标准存贮单元**（可以认为是一个字或者一个字节）。

约定：

*  数组的声明： `A[d1, d2, .., dn]`
 *  数组元素的引用：`A[i1, i2, .., in]`

n 维数组元素的地址计算

addr(A[i1，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)*w
       +(i1*d2*d3*...*dn+i2*d3*d4*...*dn+...+in-1*dn+in)*w
    =a–c*w+v*w
    
    根据假设条件③w=1:  addr(A[i1，i2，...，in])=a–c+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 
    
    令： v1 = i1
    则： v2 = i1*d2+i2 = v1*d2+i2
         v3 = (v1*d2+i2)*d3+i3 = v2*d3+i3
    	......
    于是有：  v1 = i1	
              vj = v{j-1}*dj+ij (j=2，3，..., n)		(4.4)
    同理可得：c1 = 1	
              cj = c{j-1}*dj+1 (j=2，3，..., n)	
    最终得到数组元素引用的地址计算公式：
    addr(A[i1，i2，...，in])=a-c+v=CONSPART+VARPART 
    注意：如果w≠1,则c和v分别需要乘一个w，即：
    addr(A[i1，i2，...，in])=a-cw+vw=CONSPART+VARPART

注意这里计算的时候，最后 i n i\_n in也要减一；同时如果所求的不是起始地址，而是存储地址的时候，则要求写范围，即`起始地址-起始地址+w-1`

## 语法制导翻译 ##

数组元素的寻址：

*  CONSPART\[VARPART\]，或者T1\[T\]  
    取值的三地址码：
 *  X:=T1\[T\] 赋值的三地址码：T1\[T\]:=X

1.  属性.array：数组名在符号表中的入口和数组**首地址a**
2.  属性.dim：数组**维数计数器**，记录当前分析到的维数
3.  属性.place：
    
     *  **下标列表EL：** 存放vj=vj-1\*dj+ij (j=2，3，…, n)的临时变量，
     *  **简单变量id：** 仍然表示简单变量的地址，
     *  **数组元素id\[EL\]：** 存放不变部分，一般可以是一个临时变量
4.  属性.offset：保存数组元素的可变部分（简单变量的offset为空，可记为null）
5.  函数limit(array, k)：计算并返回数组array中**第k维成员个数dk**

(1) A→V:=E 
    	{if  V.offset=null
    	 then emit(V.place ':=' E.place);
    	 else emit(V.place'['V.offset']' ':=' E.place);
    	 end if;} 
    (2) V→id { V.place:=entry(id.name); V.offset:=null;} 
    (3) V→EL]
        {V.place:=newtemp; emit(V.place ':=' EL.array '-' c);
         V.offset:=newtemp;emit(V.offset ':=' EL.place '*' w);}
     (4) EL→id[E  { EL.place:=E.place;  EL.dim :=1; 
                    EL.array:=entry(id.name);}
    (5) EL→EL1,E 
    	{ T:=newtemp; k:=EL1.dim+1;
    	  dk:=limit(EL1.array, k);
    	  emit(T ':='EL1.place '*' dk);	-- Vk-1*dk
    	  emit(T ':=' T '+' E.place);  	-- T:=Vk-1*dk+ik
    	  EL.array:=EL1.array; EL.place:=T; EL.dim:=k;} 
    (6) E→E1+E2
    	{ T:=newtemp;
    	  emit(T ':=' E1.place '+' E2.place);
    	  E.place:=T;} 
    (7) E→(E1){ E.place:=E1.place;}
    (8) E→V  { if   V.offset=null;
                then E.place:=V.place;
    		else T:=newtemp;
      		     emit(T ':=' V.place '['V.offset']')；
    		     E.place:=T;
    		end if;}