编译原理教程_8 静态语义分析和中间代码生成

心已赠人 2023-01-21 11:18 9阅读 0赞

> 文章原稿  
> https://gitee.com/fakerlove/fundamentals-of-compiling

### 文章目录 ###

*  8. 静态语义分析和中间代码生成
 *   *  8.1 中间语言
     *   *  8.1.1 概述
         *  8.1.2 逆波兰式(后缀式)
         *   *  1) 定义
             *  2) 计算方式
             *  3) 表达式 => 后缀式
         *  8.1.3 图表示法
         *   *  1) 有向无环图
             *  2) 举例
         *  8.1.4 三地址代码
         *   *  1) 概述
             *  2) 四元式
             *  3) 三元式
             *  4) 间接三元式
     *  8.2 赋值语句的翻译
     *   *  8.2.1 赋值语句的属性文法
         *   *  1) 概述
             *  2) 语义规则
         *  8.2.2 赋值语句的翻译模式
     *  8.3 数组元素引用的翻译
     *   *  8.3.1 数组元素地址计算
         *   *  1) 计算公式
             *  2) 产生式 / 属性定义
         *  8.3.2 带数组元素引用的赋值语句翻译模式
         *   *  1) 赋值语句类别
             *  2) 赋值语句翻译
         *  8.3.3 类型转换
     *  8.4 布尔表达式的翻译
     *   *  8.4.1 布尔表达式概述
         *   *  1) 文法 & 用途
             *  2) 布尔表达式两种计算方法
         *  8.4.2 按数值表示法翻译
         *   *  1) 数值表示法
             *  2) 翻译模式
         *  8.4.3 带优化的翻译
         *  8.4.4 布尔表达式的属性文法
         *   *  1) 属性
             *  2) 文法
         *  8.4.5 布尔表达式的一遍扫描翻译模式
         *   *  1) 定义引入
             *  2) 布尔表达式翻译模式
     *  8.5 控制语句的翻译
     *   *  8.5.1 控制语句的属性文法
         *   *  1) 基础定义
             *  2) 三遍扫描示例
         *  8.5.2 控制语句的属性文法
         *   *  1) if 语句的翻译模式
             *  2) while-do 语句的翻译模式
             *  3) 复合语句的翻译模式
             *  4) 一遍扫描示例
             *  5) for循环语句翻译
             *  6) 数组的翻译

# 8. 静态语义分析和中间代码生成 #

## 8.1 中间语言 ##

### 8.1.1 概述 ###

「特点」

*  独立于机器
 *  复杂性界于源语言和目标语言之间

「优点」

*  使编译程序的结构在逻辑上更为简单明确
 *  便于进行与机器无关的代码优化工作
 *  易于移植

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BSVEH68f-1597798561017)(media/15892705115957.jpg)\]][img-BSVEH68f-1597798561017_media_15892705115957.jpg]

「常用的中间语言」

*  后缀式：逆波兰表示
 *  图表示：抽象语法树（AST）、有向无环图（DAG）
 *  三地址代码：四元式、三元式、间接三元式

### 8.1.2 逆波兰式(后缀式) ###

#### 1) 定义 ####

![\[\]][2fdbe6824e05169adfd7c537e1a0190b.png]

逆波兰表示法即为**后缀表示法**，而默认我们使用的表达式是**中缀表示法**

<table> 
 <thead> 
  <tr> 
   <th>程序设计语言中的表示</th> 
   <th>-----逆波兰表示-----</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a+ba+b</td> 
   <td>ab+ab+</td> 
  </tr> 
  <tr> 
   <td>−a−a</td> 
   <td>a@a@</td> 
  </tr> 
  <tr> 
   <td>a+b∗ca+b∗c</td> 
   <td>abc∗+abc∗+</td> 
  </tr> 
  <tr> 
   <td>(a+b)∗c(a+b)∗c</td> 
   <td>ab+c∗ab+c∗</td> 
  </tr> 
  <tr> 
   <td>a:=b∗c+b∗da:=b∗c+b∗d</td> 
   <td>abc∗bd∗+:=abc∗bd∗+:=</td> 
  </tr> 
  <tr> 
   <td>a:=b∗(c+b)∗(−d)a:=b∗(c+b)∗(−d)</td> 
   <td>bcb+∗d@∗:=bcb+∗d@∗:=</td> 
  </tr> 
 </tbody> 
</table>

**逆波兰式的使用**：需使用额外的标识符栈。顺序扫描逆波兰表达式的时候，遇到**标识符**直接入栈。

遇到运算符时：

1.  根据运算符目数，从栈顶取出相应数目的标识符做运算，并把运算结果压栈
2.  运算结束时，标识符栈应该只剩下一个元素，且为运算结果

#### 2) 计算方式 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B9AvWI33-1597798561024)(media/15892707198504.jpg)\]][img-B9AvWI33-1597798561024_media_15892707198504.jpg]

#### 3) 表达式 => 后缀式 ####

*  表达式 => 后缀式的属性文法  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BF2UFws7-1597798561026)(media/15892707992936.jpg)\]][img-BF2UFws7-1597798561026_media_15892707992936.jpg]
 *  中缀表达式 => 后缀式  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-clcholFF-1597798561030)(media/15892708615183.jpg)\]][img-clcholFF-1597798561030_media_15892708615183.jpg]

### 8.1.3 图表示法 ###

#### 1) 有向无环图 ####

*  对表达式中的每个子表达式，DAG中都有一个结点
 *  一个内部结点代表一个操作符，它的孩子代表操作数
 *  在一个 DAG 中代表公共子表达式的结点具有多个父节点

树形表示和三元式表示非常相似，如a:=b∗c+b∗da:=b∗c+b∗d表示为：  
![img][]  
注意赋值表达式中被赋值对象在树的左孩子节点位置

单目运算−T1−T1直接表示成：

![img][img 1]

#### 2) 举例 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VWoROP0I-1597798561032)(media/15892710452917.jpg)\]][img-VWoROP0I-1597798561032_media_15892710452917.jpg]

### 8.1.4 三地址代码 ###

#### 1) 概述 ####

*  「形式」x : = y o p z x:=y\\ op \\ z*x*:=*y* *o\*\*p* *z*
 *  「理解」三地址代码可以看成是抽象语法树或有向无环图的一种线性表示
 *  「抽象语法树 vs. 三地址代码」  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UhTzo3xn-1597798561032)(media/15892711766376.jpg)\]][img-UhTzo3xn-1597798561032_media_15892711766376.jpg]
 *  「有向无环图 vs. 三地址代码」  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3CdouyC3-1597798561033)(media/15892712462704.jpg)\]][img-3CdouyC3-1597798561033_media_15892712462704.jpg]
 *  「三地址语句的种类」  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0BOT8lpL-1597798561034)(media/15892712864654.jpg)\]][img-0BOT8lpL-1597798561034_media_15892712864654.jpg]

#### 2) 四元式 ####

四元式(op,A1,A2,R)(op,A1,A2,R)

opop为运算符  
A1A1为第一运算对象  
A2A2为第二运算对象  
RR为运算结果

例如a:=b∗c+b∗da:=b∗c+b∗d的四元式表示：  
(1)(∗,b,c,t1)(1)(∗,b,c,t1)  
(2)(∗,b,d,t2)(2)(∗,b,d,t2)  
(3)(+,t1,t2,t3)(3)(+,t1,t2,t3)  
(4)(:=,t3,−,a)(4)(:=,t3,−,a)

和三元式的差别在于，四元式对中间结果的引用必须通过**给定的名字(临时变量)**

它的三地址码写法为：  
t1:=b∗ct1:=b∗c  
t2:=b∗dt2:=b∗d  
t3:=t1∗t2t3:=t1∗t2  
a:=t3a:=t3

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZlY4IvLA-1597798561035)(media/15892713218084.jpg)\]][img-ZlY4IvLA-1597798561035_media_15892713218084.jpg]

#### 3) 三元式 ####

在四元式基础上优化，用编号代表结果。

三元式(op,A1,A2)(op,A1,A2)

opop为运算符  
A1A1为第一运算对象  
A2A2为第二运算对象

例如a:=b∗c+b∗da:=b∗c+b∗d表示为：  
(1)(∗,b,c)(1)(∗,b,c)  
(2)(∗,b,d)(2)(∗,b,d)  
(3)(+,(1),(2))(3)(+,(1),(2)) 这里用(1)和(2)来表示**中间计算结果**的显式引用  
(4)(:=,(3),a)(4)(:=,(3),a) 这里相当于a:=(3)a:=(3)

而单目运算的−b−b可以表示成(−,b,/)(−,b,/)

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-awrSinJF-1597798561036)(media/15892713623197.jpg)\]][img-awrSinJF-1597798561036_media_15892713623197.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kfBHhYsY-1597798561036)(media/15892713765293.jpg)\]][img-kfBHhYsY-1597798561036_media_15892713765293.jpg]

#### 4) 间接三元式 ####

在三元式的基础上再度优化，使得式子发生变化时，可变性更强。

*  「定义」间接三元式 = 三元式表 + 间接码表
    
     *  间接码表：一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置
 *  「优点」方便优化，节省空间

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RCjxoYhl-1597798561037)(media/15892715368455.jpg)\]][img-RCjxoYhl-1597798561037_media_15892715368455.jpg]

## 8.2 赋值语句的翻译 ##

### 8.2.1 赋值语句的属性文法 ###

#### 1) 概述 ####

*  「赋值语句形式」$i d : = E $
 *  「赋值语句意义」
    
     *  对表达式 E 求值并置于变量 T 中
     *   i d . p l a c e : = T id.place:=T id.place:=T
 *  「赋值语句 => 三地址代码的 S-属性文法」  
    ![在这里插入图片描述][40a3719a9aa795c914adafb822c1c01b.png]

#### 2) 语义规则 ####

*  赋值语句生成三地址代码的 S-属性文法
 *  g e n ( ) 函数用于生成语句的三地址代码

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V4qonaeu-1597798561039)(media/15892747439561.jpg)\]][img-V4qonaeu-1597798561039_media_15892747439561.jpg]

### 8.2.2 赋值语句的翻译模式 ###

*  产生赋值语句三地址代码的翻译模式

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZEQKeOlb-1597798561039)(media/15892815565683.jpg)\]][img-ZEQKeOlb-1597798561039_media_15892815565683.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-erKog688-1597798561041)(media/15892816045157.jpg)\]][img-erKog688-1597798561041_media_15892816045157.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NzEI982e-1597798561042)(media/15892816187764.jpg)\]][img-NzEI982e-1597798561042_media_15892816187764.jpg]

## 8.3 数组元素引用的翻译 ##

### 8.3.1 数组元素地址计算 ###

#### 1) 计算公式 ####

*  设A为n维数组，按行存放，每个元素宽度为w
    
     *  $l o w\_i $为第 i 维的下界
     *   u p i u p\_i upi为第 i维的上界
     *   n i n\_i ni为第 i i*i* 维可取值的个数 ( n i = u p i − l o w i + 1 ) (n\_i=up\_i-low\_i+1) (ni=upi−lowi\+1)
     *  base为 A 的第一个元素相对地址
 *  元素
    
     A \[ i 1 , i 2 , . . . , i k \] A\[i\_1,i\_2,...,i\_k\] A\[i1,i2,...,ik\]相对地址公式
    
     *  可变部分  V = ( ( . . . ( ( i 1 n 2 + i 2 ) n 3 + i 3 ) . . . ) n k + i k ) ∗ w V=((...((i\_1n\_2+i\_2)n\_3+i\_3)...)n\_k+i\_k)\*w V=((...((i1n2\+i2)n3\+i3)...)nk\+ik)∗w
     *  不变部分 C = b a s e − ( ( . . . ( ( l o w 1 n 2 + l o w 2 ) n 3 + l o w 3 ) . . . ) n k + l o w k ) ∗ w C=base-((...((low\_1n\_2+low\_2)n\_3+low\_3)...)n\_k+low\_k)\*w C=base−((...((low1n2\+low2)n3\+low3)...)nk\+lowk)∗w
     *  相对地址 = V + C  
        ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iDkBoLQw-1597798561043)(media/15892831180039.jpg)\]][img-iDkBoLQw-1597798561043_media_15892831180039.jpg]

#### 2) 产生式 / 属性定义 ####

*  产生式  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2GclgfSI-1597798561043)(media/15892831082623.jpg)\]][img-2GclgfSI-1597798561043_media_15892831082623.jpg]
 *  属性定义  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u5Sysj5x-1597798561044)(media/15892831618853.jpg)\]][img-u5Sysj5x-1597798561044_media_15892831618853.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0v1nYIhS-1597798561045)(media/15892831864980.jpg)\]][img-0v1nYIhS-1597798561045_media_15892831864980.jpg]

### 8.3.2 带数组元素引用的赋值语句翻译模式 ###

此翻译模式与自下而上的语法分析方法结合在一起，可以一遍扫描就完成语法分析和翻译。

#### 1) 赋值语句类别 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VgvbmjZT-1597798561045)(media/15892854553256.jpg)\]][img-VgvbmjZT-1597798561045_media_15892854553256.jpg]

#### 2) 赋值语句翻译 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IzMua23j-1597798561046)(media/15892854993398.jpg)\]][img-IzMua23j-1597798561046_media_15892854993398.jpg]

![在这里插入图片描述][2be39366a804a2af6dbee8737f644c75.png]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G8uprSlz-1597798561047)(media/15892855289679.jpg)\]][img-G8uprSlz-1597798561047_media_15892855289679.jpg]

![在这里插入图片描述][87275208adb092acd89e7f53b4f53a42.png]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V2Q1MN1p-1597798561049)(media/15892855163621.jpg)\]][img-V2Q1MN1p-1597798561049_media_15892855163621.jpg]

### 8.3.3 类型转换 ###

「类型转换的三个功能」

*  检查操作数类型
 *  确定结果的类型
 *  如果有必要，将整型转变为实型

「类型转换的三地址代码举例」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nbLipJeQ-1597798561049)(media/15892860534181.jpg)\]][img-nbLipJeQ-1597798561049_media_15892860534181.jpg]

「类型转换属性文法」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qlQOJvrW-1597798561050)(media/15892860844077.jpg)\]][img-qlQOJvrW-1597798561050_media_15892860844077.jpg]

「类型转换的语义动作举例」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0YhwLse8-1597798561051)(media/15892861297840.jpg)\]][img-0YhwLse8-1597798561051_media_15892861297840.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oQInwVSG-1597798561051)(media/15892861405335.jpg)\]][img-oQInwVSG-1597798561051_media_15892861405335.jpg]

## 8.4 布尔表达式的翻译 ##

### 8.4.1 布尔表达式概述 ###

#### 1) 文法 & 用途 ####

「文法」

*  rop 为关系运算符，包含 \[>, >=, <, <=, <>, ==\]
 *  i 表示单个布尔变量
 *  运算优先级：括号 > 条件表达式 > not > and > or

「用途」

*  用于逻辑演算，计算逻辑值
 *  用于控制语句的条件式

#### 2) 布尔表达式两种计算方法 ####

「数值表示法」

*  如同计算算术表达式一样，一步步算
 *  举例  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vYpZXmw3-1597798561052)(media/15895214921645.jpg)\]][img-vYpZXmw3-1597798561052_media_15895214921645.jpg]

「带优化的翻译法」

*  相比数值表示法，可以减少很多冗余计算，效率更高
 *  适合于作为条件表达式的布尔表达式使用
 *  举例  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6VJAXXOg-1597798561053)(media/15895215805246.jpg)\]][img-6VJAXXOg-1597798561053_media_15895215805246.jpg]

### 8.4.2 按数值表示法翻译 ###

#### 1) 数值表示法 ####

「a or b and not c」

*   T 1 : = n o t   c T\_1:=not\\ c T1:=not c
 *  $ T\_2:=b \\ and\\ T\_1$
 *   T 3 : = a   o r   T 2 T\_3:=a\\ or\\ T\_2 T3:=a or T2

「a < b」

*  等价于「if a < b then 1 else 0」，进行如下翻译
 *   100 : i f   a < b   g o t o   103 100:if\\ a<b\\ goto\\ 103 100:if a<b goto 103
 *   101 : T   : =   0 101:T\\ :=\\ 0 101:T := 0
 *   102 : g o t o   104 102:goto\\ 104 102:goto 104
 *   103 : T   : =   1 103:T\\ :=\\ 1 103:T := 1
 *  104 :

#### 2) 翻译模式 ####

「基础说明」

*  过程 emit 将三地址代码送到输出文件中
 *  nextstat: 输出序列中下一条三地址语句的地址索引
 *  过程 emit 每产生一条指令，nextstat 加 1
 *  举例  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1GWbJBo2-1597798561053)(media/15895245708896.jpg)\]][img-1GWbJBo2-1597798561053_media_15895245708896.jpg]

「布尔表达式翻译模式」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MQ4uCTKD-1597798561054)(media/15895246972230.jpg)\]][img-MQ4uCTKD-1597798561054_media_15895246972230.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v4T6dVwG-1597798561054)(media/15895247113214.jpg)\]][img-v4T6dVwG-1597798561054_media_15895247113214.jpg]

「布尔表达式 a<b or c<d and e<f 翻译举例」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wScHMfBx-1597798561055)(media/15895247751816.jpg)\]][img-wScHMfBx-1597798561055_media_15895247751816.jpg]

### 8.4.3 带优化的翻译 ###

「核心思想」从左到右判断，当结果已经得出时，退出。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qDoM8d4i-1597798561056)(media/15895272342148.jpg)\]][img-qDoM8d4i-1597798561056_media_15895272342148.jpg]

「举例」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MROs5sKt-1597798561057)(media/15895272538033.jpg)\]][img-MROs5sKt-1597798561057_media_15895272538033.jpg]

### 8.4.4 布尔表达式的属性文法 ###

#### 1) 属性 ####

*  语义函数 newlabel，返回一个新的符号标号
 *  对于一个布尔表达式 E，设置两个继承属性
    
     *  E.true 是 E 为 ‘真’ 时控制流转向的标号
     *  E.false 是 E 为 ‘假’ 时控制流转向的标号
 *  E.code 记录 E 生成的三地址代码序列

#### 2) 文法 ####

*  产生布尔表达式三地址代码的属性文法

E → E 1   o r   E 2 E\\rightarrow E\_1 \\ or\\ E\_2 E→E1 or E2  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wCHRazN1-1597798561058)(media/15895283837288.jpg)\]][img-wCHRazN1-1597798561058_media_15895283837288.jpg]

$ E\\rightarrow E\_1 \\ and\\ E\_2$  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZpTB6Xz9-1597798561058)(media/15895284369692.jpg)\]][img-ZpTB6Xz9-1597798561058_media_15895284369692.jpg]

E → n o t   E 1 , E → ( E 1 ) E\\rightarrow not\\ E\_1,E\\to (E\_1) E→not E1,E→(E1)  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ovjLZPdS-1597798561059)(media/15895284931410.jpg)\]][img-ovjLZPdS-1597798561059_media_15895284931410.jpg]

E → i d 1   r e l o p   i d 2 E\\rightarrow id\_1\\ relop\\ id\_2 E→id1 relop id2  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ps4cfmWY-1597798561059)(media/15895285537911.jpg)\]][img-Ps4cfmWY-1597798561059_media_15895285537911.jpg]

*  举例

「布尔表达式：a < b or c < d and e < f」

**「翻译流程：第一遍扫描 — 构建语法树」**

*  整个表达式的真假出口分别置为 Ltrue、Lfalse

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lnAaZtx1-1597798561060)(media/15895307056494.jpg)\]][img-lnAaZtx1-1597798561060_media_15895307056494.jpg]

**「翻译流程：第二遍扫描 — 自上而下求出继承属性」**  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m4RxGJzb-1597798561060)(media/15895307711290.jpg)\]][img-m4RxGJzb-1597798561060_media_15895307711290.jpg]

**「翻译流程：第三遍扫描 — 自上而下求出综合属性 E.code」**

E.code: (red)
        if a < b goto Ltrue
        goto L1
    E.code: (blue)
        if c < d goto L2
        goto Lfalse
    E.code: (green)
        if e < f goto Ltrue
        goto Lfalse
    
    E.code: (purple)
        if c < d goto L2
        goto Lfalse
    L2: if e < f goto Ltrue
        goto Lfalse
    
    E.code: (black)
        if a < b goto Ltrue
        goto L1
    L1: if c < d goto L2
        goto Lfalse
    L2: if e < f goto Ltrue
        goto Lfalse

### 8.4.5 布尔表达式的一遍扫描翻译模式 ###

#### 1) 定义引入 ####

**「翻译过程以四元式为中间语言」**

*  四元式存入一个数组中，数组下标代表四元式的标号
 *  约定
    
     *  四元式 (jnz, a, -, p) 表示 if a goto p
     *  四元式 (jrop, x, y, p) 表示 if x rop y goto p
     *  四元式 (j, -, -, p) 表示 goto p
 *  过程 emit 将四元式代码送到输出数组中

**「E 综合属性 E.truelist 和 E.falselist」**

*  E.truelist 和 E.falselist 分别记录布尔表达式 E 所对应的四元式中需回填 “真”、“假” 出口的四元式的标号所构成的链表
 *  举例  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ogLZxO9B-1597798561061)(media/15895388795940.jpg)\]][img-ogLZxO9B-1597798561061_media_15895388795940.jpg]

**「语义变量和过程」**

*  变量nextquad
    
     *  指向下一条将要产生但尚未形成的四元式的地址（标号）
     *  `nextquad` 初值为 1，每当执行一次 emit 之后，`nextquad` 自动增一
 *  函数makelist(i)
    
     *  创建一个仅含 i 的新链表，其中 i 式四元式数组的一个下标（标号）
     *  函数返回指向这个链的指针
 *  函数merge(p\_1,p\_2)
    
     *  把以 p 1 p\_1 p1和 p 2 p\_2 p2为链首的两条链合并为一
     *  函数值返回合并后的链首
 *  过程 b a c k p a t c h ( p , t ) backpatch(p, t) backpatch(p,t)
    
     *  完成 “回填”
     *  把 p 所链接的每个四元式的第四区段都填为 t  
        ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cCurAXx2-1597798561062)(media/15895393549364.jpg)\]][img-cCurAXx2-1597798561062_media_15895393549364.jpg]

**「布尔表达式的文法」**

*   E → E 1   o r   M   E 2 E\\rightarrow E\_1\\ or \\ M\\ E\_2 E→E1 or M E2
 *   E → E 1   a n d   M   E 2 E\\rightarrow E\_1\\ and \\ M\\ E\_2 E→E1 and M E2
 *   E → n o t   E 1 E\\rightarrow not\\ E\_1 E→not E1
 *   E → ( E 1 ) E\\rightarrow (E\_1) E→(E1)
 *   E → i d 1   r e l o p   i d 2 E\\rightarrow id\_1\\ relop \\ id\_2 E→id1 relop id2
 *   E → i d E\\rightarrow id E→id
 *   M → ε M\\rightarrow \\varepsilon M→ε
    
     *   \{ M . q u a d   : =   n e x t q u a d \} \\\{M.quad \\ :=\\ nextquad\\\} \{ M.quad := nextquad\}

#### 2) 布尔表达式翻译模式 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-35JuHfwS-1597798561062)(media/15895414031191.jpg)\]][img-35JuHfwS-1597798561062_media_15895414031191.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oOK9xnYY-1597798561063)(media/15895414614340.jpg)\]][img-oOK9xnYY-1597798561063_media_15895414614340.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bA5TAtkj-1597798561064)(media/15895415100687.jpg)\]][img-bA5TAtkj-1597798561064_media_15895415100687.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LS2hH30m-1597798561065)(media/15895415280611.jpg)\]][img-LS2hH30m-1597798561065_media_15895415280611.jpg]

「举例：一遍扫描」  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SJUY39Q1-1621079129249)(https://gitee.com/fakerlove/picture\_1/raw/master/2020081909570077.png)\]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CDQJMlhn-1621079129251)(picture/20200819095711995.png)\]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Oubr9RJg-1621079129251)(https://gitee.com/fakerlove/picture\_1/raw/master/20200819095726580.png)\]

## 8.5 控制语句的翻译 ##

「常用的控制语句」

*  单分支： S → i f   E   t h e n   S 1 S\\rightarrow if \\ E \\ then \\ S\_1 S→if E then S1
 *  双分支： S → i f   E   t h e n   S 1   e l s e   S 2 S\\rightarrow if \\ E \\ then \\ S\_1 \\ else\\ S\_2 S→if E then S1 else S2
 *  循环:  S → w h i l e   E   d o   S 1 S\\to while\\ E\\ do\\ S\_1 S→while E do S1

### 8.5.1 控制语句的属性文法 ###

#### 1) 基础定义 ####

「属性定义」

*  E.true、E.false 表示 E 为真 / 假时的跳转语句标号
 *  S.begin、S.next 表示语句 S 开始执行、执行结束后的地址

「if-then 语句的属性文法」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dTht0Nic-1597798561067)(media/15895433822193.jpg)\]][img-dTht0Nic-1597798561067_media_15895433822193.jpg]

「if-then-else 语句的属性文法」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rI51Xk8p-1597798561067)(media/15895434092724.jpg)\]][img-rI51Xk8p-1597798561067_media_15895434092724.jpg]

「while-do 语句的属性文法」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-glSrLtJR-1597798561068)(media/15895437182547.jpg)\]][img-glSrLtJR-1597798561068_media_15895437182547.jpg]

#### 2) 三遍扫描示例 ####

「三遍扫描的属性计算示例」

while a<b do
        if c<d then x:=y+z
        else x:=y-z
    123

*  第一遍：构建语法树
 *  第二遍：自上而下计算继承属性  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dviyFC85-1597798561069)(media/15895467207133.jpg)\]][img-dviyFC85-1597798561069_media_15895467207133.jpg]
 *  第三遍：自下而上计算综合属性（code）  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L1v0afab-1597798561069)(media/15895468079525.jpg)\]][img-L1v0afab-1597798561069_media_15895468079525.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ohhk9Owy-1597798561070)(media/15895468302162.jpg)\]][img-ohhk9Owy-1597798561070_media_15895468302162.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HzJZawAk-1597798561070)(media/15895471619619.jpg)\]][img-HzJZawAk-1597798561070_media_15895471619619.jpg]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zlhhAGDE-1597798561071)(media/15895472088898.jpg)\]][img-zlhhAGDE-1597798561071_media_15895472088898.jpg]

即上述 while 控制语句最终得到如下所示的翻译结果：

L1: if a<b goto L2
        goto Lnext
    L2: if c<d goto L3
        goto L4
    L3: T1 := y+z
        x := T1
        goto L1
    L4: T2 := y-z
        x := T2
        goto L1
    12345678910

### 8.5.2 控制语句的属性文法 ###

「控制语句的文法」

*   S → i f   E   t h e n   S S\\rightarrow if \\ E \\ then \\ S S→if E then S
 *   S → i f   E   t h e n   S   e l s e   S S\\rightarrow if \\ E \\ then \\ S \\ else \\ S S→if E then S else S
 *   S → w h i l e   E   d o   S S\\rightarrow while \\ E \\ do \\ S S→while E do S
 *   S → b e g i n   L   e n d S\\rightarrow begin \\ L\\ end S→begin L end
 *   S → A S\\rightarrow A S→A
 *   L → L ; S L\\rightarrow L;S L→L;S
 *   L → S L\\rightarrow S L→S

其中 S 表示语句，L 表示语句表，A 表示赋值语句，E 表示布尔表达式。

#### 1) if 语句的翻译模式 ####

「改写后的产生式」

*   S → i f   E   t h e n   M   S 1 S\\rightarrow if\\ E\\ then \\ M\\ S\_1 S→if E then M S1
 *   S → i f   E   t h e n   M 1   S 1   N   e l s e   M 2   S 2 S\\rightarrow if \\ E\\ then\\ M\_1 \\ S\_1 \\ N \\ else \\ M\_2 \\ S\_2 S→if E then M1 S1 N else M2 S2
 *   M → ε M\\rightarrow \\varepsilon M→ε
 *   N → ε N\\rightarrow \\varepsilon N→ε

「翻译模式」

*  S.nextlist 属性：保存 S 翻译生成的代码中需要回填的，要跳转到 S 的后继语句的那些四元式。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SjRqT1VW-1597798561071)(media/15895486138059.jpg)\]][img-SjRqT1VW-1597798561071_media_15895486138059.jpg]

#### 2) while-do 语句的翻译模式 ####

「改写后的产生式」

*   S → w h i l e   M 1   E   d o   M 2   S 1 S\\rightarrow while \\ M\_1 \\ E \\ do \\ M\_2 \\ S\_1 S→while M1 E do M2 S1
 *   M → ε M\\rightarrow \\varepsilon M→ε

「翻译模式」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y50r0Lcs-1597798561072)(media/15895491815435.jpg)\]][img-y50r0Lcs-1597798561072_media_15895491815435.jpg]

#### 3) 复合语句的翻译模式 ####

「改写后的产生式」

*   S → b e g i n   L   e n d S\\rightarrow begin\\ L\\ end S→begin L end
 *   L → L 1 ;   M   S   ∣   S L\\rightarrow L\_1;\\ M\\ S\\ |\\ S L→L1; M S ∣ S
 *   M → ε M\\rightarrow \\varepsilon M→ε

「翻译模式」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tb0XcHrA-1597798561072)(media/15895500336148.jpg)\]][img-tb0XcHrA-1597798561072_media_15895500336148.jpg]

「其它语句的翻译」  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hipu8kPE-1597798561073)(media/15895500670602.jpg)\]][img-hipu8kPE-1597798561073_media_15895500670602.jpg]

#### 4) 一遍扫描示例 ####

「控制语句示例」

while a<b do
        if c<d then x:=y+z;

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dgHJcnh5-1621079129264)(picture/20200819100011982.png)\]

#### 5) for循环语句翻译 ####

现需要翻译语句：forI:=1step1untilYdoX:=X+1  
等价于C语言的：

for(I=1;I<=Y;++I) X=X+1;
    I:=1100
    goto 103
    I:=I+1
    if I<=Y goto 105
    goto 108
    T:=X+1
    X:=T
    goto 102

#### 6) 数组的翻译 ####

对于一个静态的n维数组，要访问其中一个元素，可以使用下标法：A\[i1,i2,…,in\]

由于内存是一维连续空间，对于行主数组，比如一个2×32×3的二维数组，在内存中的布局A\[1,1\]A\[1,2\]A\[1,3\]A\[2,1\]A\[2,2\]A\[2,3\]

现知道数组AA的地址为aa，那A\[i,j\]A\[i,j\]的地址为：

a+(i−1)×3+(j−1)

设BB为n维数组B\[l1:u1,l2:u2,…,ln:un\]

显然di=ui−li+1。令b是数组首元素地址，那么行主数组下B\[i1,i2,…,in\]的地址D为：

D=b+(i1−l1)d2d3…dn+(i2−l2)d3…dn+(in−1−ln−1)dn+(in−ln)

对式子展开可以提取出式子中的固定部分和变化部分：

D=constPart+varPart  
constPart=b−C  
C=l1d2d3…dn+l2d3…dn+…+ln−1dn−1+lndn  
varPart=i1d2d3…dn+i2d3…dn+…+in−1dn−1+indn

访问数组元素A\[i1,i2,…,in\]需要产生两组计算数组的四元式：

1.  一组计算varPart，存放结果到临时单元T中
2.  一组计算constPart，存放结果到另一个临时单元T1中

用T1\[T\]表示数组元素的地址

**变址取数的四元式**：(=\[\],T1\[T\],−,X),相当于X:=T1\[T\]  
**变址存数的四元式**：(\[\]=,X1,−,T1\[T\])相当于T1\[T\]:=X

现在有一个10\*20的数组A，即d1=10,d2=20。则X:=A\[I,J\]的四元式序列为：  
(∗,I,20,T1)  
(+,T1,J,T1)  
(−,A,21,T2)  
(=\[\],T2\[T1\],−,T3)  
(:=,T3,−,X)

对应：  
varPart=20∗I+J  
constPart=A−(1∗20+1)=A−21

[img-BSVEH68f-1597798561017_media_15892705115957.jpg]: /images/20221020/f12d0051ab90440c99911adc707d99b9.png
[2fdbe6824e05169adfd7c537e1a0190b.png]: /images/20221020/ce2923e3bf2f4517b41c95e9cb7698b1.png
[img-B9AvWI33-1597798561024_media_15892707198504.jpg]: /images/20221020/fd554d7b14a94954afbb1b742888e8eb.png
[img-BF2UFws7-1597798561026_media_15892707992936.jpg]: /images/20221020/91a32ab99889459ab38203007fd27e33.png
[img-clcholFF-1597798561030_media_15892708615183.jpg]: /images/20221020/1ac1de4eb7c0437286291c92097da0a7.png
[img]: /images/20221020/268ef0a4bdbc43198672dc0c3216564e.png
[img 1]: /images/20221020/4408327fbfe0472cb26d3baf98623f9f.png
[img-VWoROP0I-1597798561032_media_15892710452917.jpg]: /images/20221020/042dc9dbd6264cfcbbec47ede686b184.png
[img-UhTzo3xn-1597798561032_media_15892711766376.jpg]: /images/20221020/de951d11860c4809baa348ebdb7c90d8.png
[img-3CdouyC3-1597798561033_media_15892712462704.jpg]: /images/20221020/708c09a3c0ec4c2ebb9f64393cad6891.png
[img-0BOT8lpL-1597798561034_media_15892712864654.jpg]: /images/20221020/a075007c7654448283c805e39ac27bfc.png
[img-ZlY4IvLA-1597798561035_media_15892713218084.jpg]: /images/20221020/40f2d67601224809a05c0bc94f4127dc.png
[img-awrSinJF-1597798561036_media_15892713623197.jpg]: /images/20221020/370065c5596e470c9f267be2efa914cc.png
[img-kfBHhYsY-1597798561036_media_15892713765293.jpg]: /images/20221020/6f97351c0be141a6a9b0482fbc124738.png
[img-RCjxoYhl-1597798561037_media_15892715368455.jpg]: /images/20221020/ff04099318ad42ea92afcce645d35a47.png
[40a3719a9aa795c914adafb822c1c01b.png]: /images/20221020/0fc01792d1964da8b53341efd7721c42.png
[img-V4qonaeu-1597798561039_media_15892747439561.jpg]: /images/20221020/24120579280e422789bf3f14ff8dd4f1.png
[img-ZEQKeOlb-1597798561039_media_15892815565683.jpg]: /images/20221020/c4e1eaad98c94406a9cd00eaa5e32d41.png
[img-erKog688-1597798561041_media_15892816045157.jpg]: /images/20221020/76ac2b9a600c4a25a2f7e390b4ab0821.png
[img-NzEI982e-1597798561042_media_15892816187764.jpg]: /images/20221020/4334967b3e1d48378c7c1b0c42d011ca.png
[img-iDkBoLQw-1597798561043_media_15892831180039.jpg]: /images/20221020/fdecb6022fb84b0ebe13b21508aa5c8d.png
[img-2GclgfSI-1597798561043_media_15892831082623.jpg]: /images/20221020/4cf80afe68ac4841b35bc184aca87a11.png
[img-u5Sysj5x-1597798561044_media_15892831618853.jpg]: /images/20221020/5b64cb41a10441bead062ae76e526fea.png
[img-0v1nYIhS-1597798561045_media_15892831864980.jpg]: /images/20221020/4b55b4a3cf44464b93157b467e57276e.png
[img-VgvbmjZT-1597798561045_media_15892854553256.jpg]: /images/20221020/9d6562ab21a84a9a98090790f0b31a47.png
[img-IzMua23j-1597798561046_media_15892854993398.jpg]: /images/20221020/0c2eb1bec4424e779b85f440aefa682d.png
[2be39366a804a2af6dbee8737f644c75.png]: /images/20221020/e8847b3d418248d8a91d167af3c1e1c2.png
[img-G8uprSlz-1597798561047_media_15892855289679.jpg]: /images/20221020/035e8fa9a7614115a17c77d74975da80.png
[87275208adb092acd89e7f53b4f53a42.png]: /images/20221020/dad7d55f196c4178b7b9a3b40f71e40d.png
[img-V2Q1MN1p-1597798561049_media_15892855163621.jpg]: /images/20221020/a585c7881ec14781a3a76f7091928da4.png
[img-nbLipJeQ-1597798561049_media_15892860534181.jpg]: /images/20221020/f8253a27a7d0428b8435e5352467bbeb.png
[img-qlQOJvrW-1597798561050_media_15892860844077.jpg]: /images/20221020/6c010009b93343f2bf75ba810cfd60c9.png
[img-0YhwLse8-1597798561051_media_15892861297840.jpg]: /images/20221020/1e9120ac16814996b6658de24c2dc8a0.png
[img-oQInwVSG-1597798561051_media_15892861405335.jpg]: /images/20221020/57bf0f45fb3a4400b229a48419465091.png
[img-vYpZXmw3-1597798561052_media_15895214921645.jpg]: /images/20221020/735a495c5e9b403f90459df7b9e6d054.png
[img-6VJAXXOg-1597798561053_media_15895215805246.jpg]: /images/20221020/f2f8742511dd435e8351f2a00aca552a.png
[img-1GWbJBo2-1597798561053_media_15895245708896.jpg]: /images/20221020/516661dfffdb4bad8fd40625207335d5.png
[img-MQ4uCTKD-1597798561054_media_15895246972230.jpg]: /images/20221020/22bc49ee4f484911bdbde8c52e9f6322.png
[img-v4T6dVwG-1597798561054_media_15895247113214.jpg]: /images/20221020/8a92fce1bf5a4806801648ee3906ea19.png
[img-wScHMfBx-1597798561055_media_15895247751816.jpg]: /images/20221020/5c0b08069da1448ab000dddf92b0e819.png
[img-qDoM8d4i-1597798561056_media_15895272342148.jpg]: /images/20221020/d1bb3e7ed88246c79f49b46057023676.png
[img-MROs5sKt-1597798561057_media_15895272538033.jpg]: /images/20221020/beeb1ca765df44b08f32b7be35b41230.png
[img-wCHRazN1-1597798561058_media_15895283837288.jpg]: /images/20221020/640aa02b96fc431d82bfb26e2572534a.png
[img-ZpTB6Xz9-1597798561058_media_15895284369692.jpg]: /images/20221020/e1f76601980f4110a6d945adf1558979.png
[img-ovjLZPdS-1597798561059_media_15895284931410.jpg]: /images/20221020/5eecf06c014849aead4b7a52cae108ba.png
[img-Ps4cfmWY-1597798561059_media_15895285537911.jpg]: /images/20221020/dcf23747c9514706a2321f2e2d76eb57.png
[img-lnAaZtx1-1597798561060_media_15895307056494.jpg]: /images/20221020/7420618004964a8f8aeca6bb052861fe.png
[img-m4RxGJzb-1597798561060_media_15895307711290.jpg]: /images/20221020/dedf1b46e929492281062abbc379b919.png
[img-ogLZxO9B-1597798561061_media_15895388795940.jpg]: /images/20221020/64dfb978780b4640868516cd997f1936.png
[img-cCurAXx2-1597798561062_media_15895393549364.jpg]: /images/20221020/4676e90506c1403fac838d7e46b52bf6.png
[img-35JuHfwS-1597798561062_media_15895414031191.jpg]: /images/20221020/0ba05d7346c044ae91e6038df728040b.png
[img-oOK9xnYY-1597798561063_media_15895414614340.jpg]: /images/20221020/c6ba0f2197464e658341ac0dca45ebb7.png
[img-bA5TAtkj-1597798561064_media_15895415100687.jpg]: /images/20221020/92487f8e56ee44fea0cb2f94a3e5b5ae.png
[img-LS2hH30m-1597798561065_media_15895415280611.jpg]: /images/20221020/e5c0da341e904157867a243a9a53cfa2.png
[img-dTht0Nic-1597798561067_media_15895433822193.jpg]: /images/20221020/b2cdb93ddcb34787aa002ea2cf9a37dd.png
[img-rI51Xk8p-1597798561067_media_15895434092724.jpg]: /images/20221020/5bde8d397caa40d6a1eba52fde0fa15a.png
[img-glSrLtJR-1597798561068_media_15895437182547.jpg]: /images/20221020/7e1ab44341c64f73bd453a2715c3e600.png
[img-dviyFC85-1597798561069_media_15895467207133.jpg]: /images/20221020/62976beca2924ce3aa4d78edfd8353fe.png
[img-L1v0afab-1597798561069_media_15895468079525.jpg]: /images/20221020/932d3dcf874941a3bcdac334db4af2fb.png
[img-ohhk9Owy-1597798561070_media_15895468302162.jpg]: /images/20221020/200caf95147a4144affa33cd36f4af94.png
[img-HzJZawAk-1597798561070_media_15895471619619.jpg]: /images/20221020/eca7accae9424b65b07173abbc8b6a68.png
[img-zlhhAGDE-1597798561071_media_15895472088898.jpg]: /images/20221020/a91f773c73a443b6afe830b20e32aecd.png
[img-SjRqT1VW-1597798561071_media_15895486138059.jpg]: /images/20221020/b8919e5c1a9a4b4a80322890bf845569.png
[img-y50r0Lcs-1597798561072_media_15895491815435.jpg]: /images/20221020/74bb5fca939a43c18392ffcc79af7202.png
[img-tb0XcHrA-1597798561072_media_15895500336148.jpg]: /images/20221020/4b0278f67fb9476990a67e59dab532d4.png
[img-hipu8kPE-1597798561073_media_15895500670602.jpg]: /images/20221020/018bcde4312145ff90f67a223e1e326e.png