编译-第07章-生成中间代码

•
Compiler

中间代码有多种形式：波兰表示，N-元表示，抽象代码，LLVM IR

7.1 （逆）波兰表示

算术表达式（中缀表达式）：F*3.1416*R*(H+R)

波兰表示（后缀表达式）：F 3.1416* R* H R+*

转换算法

  • 采用操作符栈实现中缀表达式到波兰表示的转换
  • 算法步骤：
    1. 读到操作数时立即输出
    2. 遇到操作符时与栈顶操作符比较优先级
    3. 栈顶操作符优先级高则输出栈顶操作符
    4. 栈外操作符优先级高则入栈

优点

  1. 无二义性表达算术表达式
  2. 易于转换为汇编语言或机器语言
  3. 操作符顺序即为计算顺序
  4. 适用于多种语言结构

条件语句的波兰表示

if语句：if <expr> then <stmt1> else <stmt2>

波兰表示：<expr> <label1> BZ <stmt1> <label2> BR <stmt2>

  • BZ操作符：二目操作符，当<expr>结果为0(false)时转移到<label1>（<stmt2>的头符号）
  • BR操作符：一目操作符，无条件转移到<label2>（if语句后的第一个语句）

image

7.2 N-元表示

每条指令由n个域组成，通常第一个域表示操作符，其余为操作数

条件语句示例

1
if x>y then z:=x else z:=y+1;

三元式表示：

1
2
3
4
5
6
7
(1) >, x, y
(2) BMZ, (1), (5)    # 若(1)≤0则转移到(5)
(3) :=, z, x
(4) BR, , (7)        # 无条件转移到(7)
(5) +, y, 1
(6) :=, z, (5)
(7) ...

间接三元式

  • 为解决优化时三元式位置变更问题而设计
  • 使用单独的执行顺序表记录三元式的执行次序
  • 优化时只需调整顺序表，三元式本身保持不变

四元式表示

格式：操作符、操作数1、操作数2、结果

示例：(A+B)*(C+D)-E

1
2
3
4
+, A, B, T1
+, C, D, T2
*, T1, T2, T3
-, T3, E, T4

优点：便于优化处理

7.3 抽象机代码

P-code概述

  • 基于虚拟的”堆栈计算机”模型
  • 操作主要在运行栈的栈顶进行
  • 便于程序移植和解释执行

寄存器组成

  1. PC：程序计数器
  2. NP：New指针，指向堆的顶部
  3. SP：运行栈指针，指向可直接寻址的数据
  4. BP：基地址指针，指向当前活动记录起始位置
  5. MP：栈标志指针
  6. EP：极限栈指针

7.4 其他形式的中间代码

抽象语法树(AST)

  • 树型图表示中间代码
  • 叶节点为操作数，中间节点为操作符
  • 直观展示表达式结构层次

有向无环图(DAG)

  • 语法树的归约表达方式
  • 叶节点标记为变量名或常量
  • 中间节点标记为操作符
  • 支持公共子表达式消除等优化

示例：a:=b*(-c)+b*(-c)的DAG表示

image

静态单一赋值形式(SSA)

  • 每个变量只赋值一次的特殊四元式
  • 优点：简化优化过程，获得更好优化结果
  • 通过插入Φ函数实现从普通四元式转换

image