编译原理第7章(刘磊 机械工业出版社)

第 7 章 中间代码生成常用的中间代码结构 语法制导方法概论 类型检查和类型转换 中间代码生成中的几个问题

7.1 常用的中间代码结构后缀式----逆波兰式 后缀式----逆波兰式 ---抽象语法树和有向无环图——AGT和 DAG AGT和 抽象语法树和有向无环图 AGT 三地址中间代码(三元式、四元式) 三地址中间代码(三元式、四元式)

7.1.1 后缀式按操作符与其运算分量的位置，表达式可分为： 按操作符与其运算分量的位置，表达式可分为： 1. 前缀式：运算符在前，如+ AB 前缀式：运算符在前， 2. 中缀式 运算符在中间，如 A+ B 中缀式: 运算符在中间， 3. 后缀式 后缀式——逆波兰式 , 运算符在后，如 A B + 逆波兰式 运算符在后， 中缀式 a:=b*c+b/d 对应的后缀式 abc*bd/+:=

7.1.2 抽象语法树和有向无环图抽象语法树: 抽象语法树: Abstract Grammer 有向无环图: 有向无环图: Directed Acyclic 设有c:=a*b+a*b, c:=a*b+a*b,对应的 设有c:=a*b+a*b,对应的 AGT 和:= c * a b a + * b a DAG c

Tree ; AGT Graph ;DAG 如下。 DAG 如下。:= + * b

AGT

7.1.3 三地址中间代码三元式： OP,operand1,operand2) 三元式： (OP,operand1,operand2) 四元式： OP, 四元式：( OP, operand1, operand2 ,result)

b×c+b× 如：a:= b×c+b×d三元式 (×, b, c) × (×, b, d) × (+, (1), (2)) (:=, (3), a) 四元式 (×, b, c, t1) × (×, b, d, t2) × (+, t1, t2, t3) (:=, t3, a, -)

(1) (2) (3) (4)

(1) (2) (3) (4)

7.2 语法制导方法概论语法制导方法： 语法制导方法： (1)基于文法结构 (2)在每个产生式的右部增加语义动作 在分析语法的过程中，如遇到语义动作， (3)在分析语法的过程中，如遇到语义动作，就 完成相应的处理。 完成相应的处理。 语法制导方法的构成： 语法制导方法的构成： 抽象描述部分： 抽象描述部分：带有动作的文法描述 实现部分： 实现部分：语法分析的同时处理语义

语法制导方法的分类： 语法制导方法的分类： (1)自顶向下语法制导：以LL(1)分析为基础 )自顶向下语法制导： 分析为基础 (2)自底向上语法制导：以LR (1)分析为基础 )自底向上语法制导： 分析为基础

LL(1)文法： LL(1)文法： 文法 G: S → A B A → a A|b B → b B|c 的动作文法： G的动作文法： S → #Init# A B A → a A|b #Add # B → b #Add# B|c #Out_Val#

各动作符对应的语义子程序： 各动作符对应的语义子程序：

Init: m:=0 Add : m:=m+1 m≠ Out_Val: if m≠0 then begin print(m); m:=0; end

处理abbc的过程 的过程 处理 符号栈 S #Init# A B aAB AB b #Add #B #Add #B b #Add #B #Add #B B c #Out_Val# #Out_Val# 输入流 abbc# abbc# abbc# bbc# bbc# bc# bc# c# c# c# # # 语义动作 m:=0 匹配 匹配 m:=m+1 匹配 m:=m+1 匹配 print(m); m:=0; 成功结束

7.3 类型检查和

类型转换

把类型检查的工作放在中间代码生成时 进行。 进行。

类型检查类型和类型检查的语法单位类型相容性检查项目各种条件表达式的类型是否是布尔类型 运算符的运算分量是否相容 赋值语句的左、 赋值语句的左、右部类型是否相容 实参与形参的类型是否相容 下标表达式的类型是否为所允许的类型 函数说明中的函数类型与返回值的类型是 否一致

类型检查的语 法单位if语句、while语 if语句、while语 语句 repeat语句 句、repeat语句 表达式 赋值语句 过程调用语句、 过程调用语句、 函数调用语句 下标变量 赋值语句

7.4 中间代码生成中的几个问题语义信息的获取与保存 语义栈sem sem及其操作 语义栈sem及其操作 常用的语义子程序 1.申请临时单元 1.申请临时单元 2.存放中间代码的子程序 存放中间代码的子程序Generate 2.存放中间代码的子程序Generate 3.产生一条中间代码子程序GenCode。 产生一条中间代码子程序GenCode 3.产生一条中间代码子程序GenCode。