语义分析和中间代码的产生

野性酷女 2023-03-13 03:45 4阅读 0赞

### 文章目录 ###

*   *  赋值语句翻译
     *   *  算数表达式
         *  含数组引用的翻译
         *  类型转换
     *  总结赋值语句翻译

## 赋值语句翻译 ##

### 算数表达式 ###

属性文法略  
翻译模式：  
S→id:=E \{ p:=lookup(id.name);  
if p！=nil then emit(p ‘:=’ E.place)  
else error \}  
E→E1+E2 \{ E.place:=newtemp;  
emit(E.place ‘:=’ E1.place ‘+’ E2.place)\}  
E→E1*E2 \{ E.place:=newtemp;  
emit(E.place ‘:=’ E 1.place ‘*’ E 2.place)\}  
E→-E1 \{ E.place:=newtemp;  
emit(E.place‘:=’ ‘uminus’ E 1.place) \}  
E→(E1) \{ E.place:=E1.place \}  
E→id \{ p:=lookup(id.name);  
if p！=nil then E.place:=p  
else error \}  
E用来表示产生终结符。  
相关属性说明：  
place：综合属性，表示存放E值单元的名字或地址  
code：综合属性，三地址代码。  
相关函数说明：  
newtemp：产生一个中间临时变量，如T1，T2…  
emit：产生三地址代码（可能使用四元式形式表达，也可能是原始的三地址代码形式）  
lookup:在符号表中查找相应入口

观察此翻译模式得到如下结论：  
1、简单算数表达式的文法共6个产生式，**注意其中“-”为单目运算符，即表示求相反数，取负号，不是减法。**  
2、此翻译模式与自下而上语法分析（规范规约）相结合。即从输入串（算数表达式）开始，进行自下而上的规约。每次规约时都进行相应的语义动作。  
3、应该重点关注进行emit的语义动作。其中每次归约“-，+，\*”及：=时进行emit（此步骤与练习题答案密切相关）  
4、添加括号

例子：写出A:=B\*（-C+D)产生的三地址代码  
画出语法树（正常应该由规范归约产生，在规范归约过程中，一边产生语法树，一边进行翻译，但归约较麻烦，因此可以直接利用最左推导产生语法树，在利用语法树，判断归约过程）：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdoNzAx_size_16_color_FFFFFF_t_70_pic_center][]  
共进行了4次emit，根据归约顺序：  
T1:=@C  
T2:=T1+ T1  
T3：=B*T2  
A：=T3  
观察语法树得到如下特点：  
1、赋值号：=左边的终结符A未被归约成E，即A不是句柄，因为不存在E：=E这样的句型。  
2、赋值号右边的终结符都要先归约成E，在进行含“-，+，*”的产生式归约时，每次归约都要emit。

### 含数组引用的翻译 ###

**数组元素地址的计算**  
符号说明：low为数组下界，base为数组A的第一个元素的地址即A\[low\]的地址（可以用数组名来表示），w为每个数组元素宽度。  
1、一维数组：A\[i\]的地址为 base+（i-low）*w=i*w+（base-low*w）  
观察发现i*w随i变化，为可变部分，而base-low\*w只与数组本身有关，为不变部分。  
2、多维数组\*\*（按行存放）\*\*：A\[i1,i2,…,ik\]地址公式  
((…i1 n2+i2)n3+i3)…)nk+ik)×w +base-((…((low1 n2+low2)n3+low3)…)nk+lowk)×w  
同理可分为不变部分与可变部分。注意公式的递推性质：以不变部分为例，k（k>1)维不变部分为k-1维乘k维元素的维度加上k维，再乘w。不变部分即把i换成low，再用base减。

**翻译模式**  
添加产生式：  
L → id \[ Elist \] | id  
Elist → Elist,E | E  
为了便于处理，文法改写为  
L → Elist \] | id （即读到“\]”就说明产生了一个数组元素）。  
Elist → Elist, E | id \[ E （读到\[说明出现了数组元素，E表示最左下标，EList表示所有下标）  
翻译模式：  
1) S→L:=E  
\{ if L.offset=null then /*L是简单变量*/  
emit(L.place ‘:=’ E.place)  
else emit( L.place ‘ \[’ L.offset ‘\]’ ‘:=’ E.place)\}

(2) E→E1 +E2  
\{ E.place:=newtemp;  
emit(E.place ‘:=’ E 1.place ‘+’ E 2.place)\}  
(3) E→(E1) \{E.place:=E1.place\}

(4) E→L  
\{ if L.offset=null then /*L是简单变量*/  
E.place:=L.place  
else begin  
E.place:=newtemp;  
emit(E.place ‘:=’ L.place ‘\[’ L.offset ‘\]’ )  
end  
\}  
(5) L→Elist \]  
\{ L.place:=newtemp;  
emit(L.place ‘:=’ Elist.array ‘－’ C); **（数组名即为base）**  
L.offset:=newtemp;  
emit(L.offset ‘:=’ w ‘\*’ Elist.place) \}

(6) L→id \{ L.place:=id.place; L.offset:=null \}  
(7) Elist→ Elist1, E  
\{ t:=newtemp;  
m:=Elist1.ndim+1;  
emit(t ‘:=’ Elist1.place ‘\*’ limit(Elist1.array,m) );  
emit(t ‘:=’ t ‘+’ E.place);\*\*（此两条语义动作与之前描述的递归性相关）  
Elist.place:=t;  
Elist.ndim:=m  
Elist.array:= Elist1.array;  
\}  
(8) Elist→id \[ E  
\{ Elist.place:=E.place;  
Elist.ndim:=1;  
Elist.array:=id.place \}  
函数与属性说明：  
**Elist有三个综合属性**  
Elist.ndim: 下标个数计数器  
Elist.place: 保存临时变量的名字，存放已扫描的Elist中的下标计算出来的值(为了得到可变部分地址）  
Elist.array: 保存数组名，**数组名用来表示首元素地址。**  
limit(array，j) ：函数过程，它给出数组array的第j维的长度  
**L有两个综合属性**  
L.place  
若L为简单变量i, 指变量i的符号表入口  
若L为下标变量，指存放不变部分的临时变量的名字  
L.offset  
若L为简单变量，null  
若L为下标变量，指存放可变部分的临时变量的名字

将此文法与简单算数表达式对比：  
1、共8条产生式，后4条的意义是，L用来表示产生终结符id或者数组元素id\[Elist\]。如果将一个数组元素看成终结符的话，此处的L与之前的简单算数表达式文法中的id对应。  
2、8,7,5三条表达式是为了得到数组元素的可变地址与不可变地址，从8开始，利用7进行更新，5结束。  
3、表达式4是为了得到终结符的地址（将数组元素看成一个终结符），用不变\[可变\]表示数组元素地址。

### 类型转换 ###

增加综合属性E.type非终结符E的类型属性，只有integer和real两种取值。  
1、相同类型可以进行运算，不同类型运算前需转换。转换只能从integer变到real  
2、在运算符前添加real或integer。  
3、运算结果为integer但且仅当参与运算的元素都为integer。

## 总结赋值语句翻译 ##

1、翻译与自下而上的语法分析结合，每次用产生式归约时，进行相应的语义动作。  
2、给定待翻译赋值语句中含数组元素，普通终结符，运算符号，（）。在普通算数表达式中E产生id即终结符，再含数组元素时，L代替id的位置，L可能产生终结符或数组元素。注意赋值号左边的终结符在归约时的处理  
3、翻译时重点关注emit动作。  
4、数组元素主要针对二维数组。  
3、提到类型时要进行类型转换。

基于陈火旺主编国防科技大学编写的《程序设计语言编译原理》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdoNzAx_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/c7da2c1c55034a88a1e23e57091e340e.png