【编译原理系列】布尔表达式及控制语句翻译

心已赠人 2023-01-10 11:53 130阅读 0赞

# 布尔表达式 #

从高到低：`not and or`

**短路计算**可以回避指针为空时对ptr^.data=x的判断，从而

## 直接计算的语法制导翻译 ##

(1)E→E1 or E2  { E.place := newtemp; 
    		    emit(E.place ':=' E1.place 'or' E2.place);}
    (2)  |E1 and E2 { E.place := newtemp; 
    		    emit(E.place ':=' E1.place 'and' E2.place);}
    (3)  |not E1{ E.place := newtemp; 
    		    emit(E.place ':=' 'not' E1.place);}
    (4)  |(E1)  { E.place := E1.place;}
    (5)  |id1 relop id2
    (6)  |id    { E.place:=entry(id.name);}
    (7)  |true { E.place:=newtemp; emit(E.place ':=' '1');}
    (8)  |false { E.place:=newtemp; emit(E.place ':=''0');}

## 语法制导翻译 ##

1.  属性 .true：表达式的真出口，它指向表达式为真时的转向
2.  属性 .false：表达式的假出口，它指向表达式为假时的转向；
3.  函数 newlable：与newtemp相似，但它产生的是一个**标号**而**不是一个临时变量**

这里`.code`是综合属性，`.true`和`.false`是继承属性

(1)E→E1 or E2  
    	{ E1.true:= E.true; E1.false:=newlabel;
    	  E2.true:= E.true; E2.false:=E.false; 
    	  E.code := E1.code||emit(E1.false ':')||E2.code;}
    (2)  |E1 and E2
    	 { E1.false:= E.false; E1.true:=newlabel;
             E2.false:= E.false; E2.true:=E.true; 
             E.code  := E1.code||emit(E1.true':')||E2.code;} 
    (3)  |not E1 { E1.false:=E.true;   E1.true:=E.false;}
    (4)  |(E1)   { E1.false:=E.false;  E1.true:=E.true;} 
    (5)  |id1 relop id2 
           { E.code := emit
    	      ('if'id1.place relop.op id2.place'goto'E.true)
               || emit('goto' E.false);
           }
    (6)  |id    { E.code := emit('if' id.place 'goto' E.true)
                      || emit('goto' E.false);}
    (7)  |true  { E.code := emit('goto' E.true);}
    (8)  |false { E.code := emit('goto' E.false);}

## 拉链与回填 ##

拉链与回填的基本思想：

*  当三地址码中的**转向不确定时**，将所有转向**同一地址**的三地址码**拉成一个链**
 *  一旦所**转向的地址被确定**，则**沿此链将所有的三地址码中回填**入此地址

新增函数与属性：

1.  属性.tc：真出口链，链接所有转向**真出口（true）** 的三地址码
2.  属性.fc：假出口链，链接所有转向**假出口（false）** 的三地址码
3.  属性.stat：记录当前**第一个可用三地址码的序号**
4.  函数mkchain(i)：为序号是i的三地址码**构造一个新链**，且返回指向该链的指针
5.  函数merg(P1，P2)：**合并链P1和P2**，且P2成为合并后的链头，并返回链头指针
6.  过程backpatch(P，i)：将**P链中相应域中的所有链域**均回填为i值

由于需要增加拉链回填这个语义规则，所以我们在产生式右部引入一个非终结符来实现；
    同时，为其增加一个新的属性.stat，记录当前第一个可用三地址码的序号
    
    (1)M→ε					{M.stat:=nextstat;} 
    (2)E→E1 or M E2 
    {backpatch(E1.fc, M.stat);
    E.tc:=merge(E1.tc, E2.tc); 
     E.fc:=E2.fc;} 
     
    (3)  |E1 and M E2		
    {backpatch(E1.tc, M.stat);
    E.tc:=merge(E1.fc, E2.fc); 
     E.tc:=E2.tc;} 
     
    (4)  |not E1			{E.tc:=E1.fc; E.fc:=E1.tc;}
    (5)  |(E1) 				{E.tc:=E1.tc; E.fc:=E1.fc;}
    
    (6) E→id1 relop id2				--这里直接写如a<b，而不用写id1 relop id2，然后再画线了
     { E.tc:=mkchain(nextstat); 
     E.fc:=mkchain(nextstat+1);
     emit('if' id1.place relop.op id2.place 'goto -');
     emit('goto -');
     } 
    (7)   |id { E.tc:=mkchain(nextstat);
    	 	E.fc:=mkchain(nextstat+1);
          	emit('if' id.place 'goto -');
          	emit('goto -'); }
    (8)   |true {E.tc:=mkchain(nextstat); emit('goto -');}
    (9)   |false{E.fc:=mkchain(nextstat); emit('goto -');}

# 控制语句 #

四类控制语句：

*  无条件转移：goto （转向某标号所在位置），exit、break（退出某个范围）
    
     *  两个要素
        
         *  标号所标记的位置和goto所转向的标号
         *  起**标记位置作用**的标号被称为标号的**定义出现**
         *  用于**goto转向的标号**被称为标号的**引用出现**
         *  在一定的作用域内，**标号仅可以定义一次，而可以引用多次**
         *  当标号定义出现时，将有关信息填写进符号表中
         *  而当标号引用出现时，根据符号表中的信息生成正确转移的三地址码
         *  但在有些情况下标号的引用先于标号的定义。解决的方法是借助于符号表的拉链与回填

*  条件转移： if\_then\_else，while\_do：判断布尔表达式
 *  循环： for\_loop：设定下限、上限与循环步长
 *  分支： case、switch：根据不同的取值执行不同的分支

## 无条件转移 ##

在符号表中为标号设置以下信息域：

1.  type：记录标识符的类型，如‘标号’或‘未知’
2.  def： 若是标号，记录是否已定义，如‘未定义’或‘已定义’
3.  addr：标号定义前作为链头，标号定义后作为此标号对应三地址码的序号

**定义过程：fill(entry(id.name), a, b, c)**，将a, b, c分别填写到符号表中标识符id的.type、.def、.addr域中

(1)S→goto id
       { if   entry(id.name).type='未知'       -- 标识符第一次出现
         then fill(entry(id.name),'标号', '未定义', nextstat);
              emit('goto -');
         else if   entry(id.name).type ='标号'   -- 已出现且是标号
              then emit('goto', entry(id).addr)；
                   if    entry(id.name).def=‘未定义’ -- 尚未定义，拉链
                   then  fill(entry(id.name),'标号','未定义',nextstat-1);
                   end if;
              else  error；  -- 标识符已出现且类型不是标号，出错
              end if;
         end if;
       }
    (2)S  →LAB S { -- 略（根据S是何种语句，进行相应的翻译）}
    (3) LAB→id '：'
        { if   entry(id.name).type='未知'   -- 标识符第一次出现
          then fill(entry(id.name), '标号', '已定义', nextstat);
          else if    entry(id.name).type='标号'  
                     and entry(id.name).def='未定义' -- 还未定义出现
               then q:=entry(id.name).addr;  
                    fill(entry(id.name), '标号', '已定义', nextstat);
                    backpatch(q, nextstat);
               else error;         -- 其它情况均出错
               end if;
          end if;
        }

## 条件转移 ##

1.  属性.begin：语句S开始的三地址码序号
2.  属性.next： 语句S结束后的三地址码 序号

(1) S→if E then S1
    {	E.true:=newlabel; E.false:=S.next; S1.next:=S.next;
    S.code:=E.code||emit(E.true':')||S1.code;
    
    } 
    (2) S→if E then S1 else S2
    { E.true :=newlabel;   E.false:=newlabel;
     S1.next:=S.next; 	S2.next:=S.next;
     S.code := E.code 
    	|| emit(E.true ':') || S1.code
          || emit('goto' S.next)
    	|| emit(E.false ':') || S2.code; 
    
    }
    
    (3) S→while E do S1
    { S.begin := newlabel; E.true := newlabel;
    E.false := S.next;   S1.next := S.begin;
    S.code :=   emit(S.begin ':') || E.code
    	   || emit(E.true ':')  || S1.code 
    	   || emit('goto' S.begin)
    	   || emit(E.false ':');
    }

**当有嵌套等控制流的问题的时候：通过拉链回填的方法**

1.  属性.nc：语句结束后的转向；未确定时拉链，确定后回填
2.  属性.begin：语句(如while)的三地址码序列首地址

(1)M→ε 		{M.stat:=nextstat;}
    (2)S→if E then M S1		{backpatch(E.tc,M.stat);S.nc:= merge(E.fc,S1.nc);}
    (3)N→ε		{N.nc:= mkchain(nextstat); emit('goto -');}
    (4)S→if E then M1 S1 N else M2 S2
    {backpatch(E.tc,M1.stat); backpatch(E.fc,M2.stat);
     S.nc:=merge(S1.nc,merge(N.nc,S2.nc));} 
    (5)S→while M1 E do M2 S1
    {backpatch(S1.nc,M1.stat); backpatch(E.tc,M2.stat);
     S.nc:=E.fc; emit('goto' M1.stat);} 
    (6)S→A		{S.nc := mkchain();}