语义分析和中间代码生成

一、中间语言

1.1 概述

「特点」

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

「优点」

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

「常用的中间语言」

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

1.2 后缀式

1.2.1 定义

1.2.2 计算方式

1.2.3 表达式 => 后缀式

• 表达式 => 后缀式的属性文法

• 中缀表达式 => 后缀式

1.3 图表示法

1.3.1 有向无环图

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

1.3.2 举例

1.4 三地址代码

1.4.1 概述

• 「形式」x:=y op z
• 「理解」三地址代码可以看成是抽象语法树或有向无环图的一种线性表示
• 「抽象语法树 vs. 三地址代码」

• 「有向无环图 vs. 三地址代码」

• 「三地址语句的种类」

1.4.2 四元式

1.4.3 三元式

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

1.4.4 间接三元式

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

• 「定义」间接三元式 = 三元式表 + 间接码表
• 间接码表：一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置

• 「优点」方便优化，节省空间

二、赋值语句的翻译

2.1 赋值语句的属性文法

2.1.1 概述

• 「赋值语句形式」id:=E
• 「赋值语句意义」
• 对表达式 E 求值并置于变量 T 中
• id.place:=T

• 「赋值语句 => 三地址代码的 S-属性文法」

2.1.2 语义规则

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

2.2 赋值语句的翻译模式

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

三、数组元素引用的翻译

3.1 数组元素地址计算

3.1.1 计算公式

• 设 A 为 n 维数组，按行存放，每个元素宽度为 w
• low_i 为第 i 维的下界
• up_i 为第 i 维的上界
• n_i 为第 i 维可取值的个数 (n_i=up_i-low_i+1)
• base 为 A 的第一个元素相对地址

• 元素 A[i_1,i_2,…,i_k] 相对地址公式
• 可变部分 V=((…((i_1n_2+i_2)n_3+i_3)…)n_k+i_k)*w
• 不变部分 C=base-((…((low_1n_2+low_2)n_3+low_3)…)n_k+low_k)*w
• 相对地址 = V+C

3.1.2 产生式 / 属性定义

• 产生式

• 属性定义

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

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

3.2.1 赋值语句类别

3.2.2 赋值语句翻译

3.3 类型转换

「类型转换的三个功能」

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

「类型转换的三地址代码举例」

「类型转换属性文法」

「类型转换的语义动作举例」

四、布尔表达式的翻译

4.1 布尔表达式概述

4.1.1 文法 & 用途

「文法」

Erightarrow E or E | E and E | not E | (E) | i rop i | i

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

「用途」

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

4.1.2 布尔表达式两种计算方法

「数值表示法」

• 如同计算算术表达式一样，一步步算
• 举例

「带优化的翻译法」

• 相比数值表示法，可以减少很多冗余计算，效率更高
• 适合于作为条件表达式的布尔表达式使用
• 举例

4.2 按数值表示法翻译

4.2.1 数值表示法

「a or b and not c」

• T_1:=not c
• T_2:=b and T_1
• T_3:=a or T_2

「a < b」

• 等价于「if a < b then 1 else 0」，进行如下翻译
• 100:if a<b goto 103
• 101:T := 0
• 102:goto 104
• 103:T := 1
• 104:

4.2.2 翻译模式

「基础说明」

• 过程 emit 将三地址代码送到输出文件中
• nextstat: 输出序列中下一条三地址语句的地址索引
• 过程 emit 每产生一条指令，nextstat 加 1
• 举例

「布尔表达式翻译模式」

「布尔表达式 a<b or c<d and e<f 翻译举例」

4.3 带优化的翻译

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

「举例」

4.4 布尔表达式的属性文法

4.4.1 属性

• 语义函数 newlabel，返回一个新的符号标号
• 对于一个布尔表达式 E，设置两个继承属性
• E.true 是 E 为 ‘真’ 时控制流转向的标号
• E.false 是 E 为 ‘假’ 时控制流转向的标号

• E.code 记录 E 生成的三地址代码序列

4.4.2 文法

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

「Erightarrow E_1 or E_2」

「Erightarrow E_1 and E_2」

「Erightarrow not E_1, Erightarrow (E_1)」

「Erightarrow id_1 relop id_2」

• 举例

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

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

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

「翻译流程：第二遍扫描 — 自上而下求出继承属性」

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