中间语言

• 常用的中间语言：
  • 后缀式、逆波兰表示
  • 图表示：DAG、抽象语法树
  • 三地址代码：
    • 三元式
    • 四元式
    • 间接三元式

后缀式

• 又称为逆波兰表示法
• \(E_1\quad op\quad E_2\rightarrow E_1^\prime E_2^\prime op\)
  • 其中，\(E^\prime\)为\(E\)的后缀式
  • 如果\(E\)是\((E_1)\)形式的表达式，则\(E_1\)的后缀式就是\(E\)的后缀式
• 逆波兰表示法不用括号
  • 只需要知道每个算符的数目，对于后缀式，不论从那一段进行扫描，都能对其进行唯一分解
• 后缀式的计算
  • 使用一个栈来实现
  • 一般的计算过程：
    • 从左到右扫描后缀式
      • 每碰到运算量就将其入栈
      • 每碰到\(k\)目运算符，就将其作用域栈顶的\(k\)个运算量，并且使用运算结果替代这\(k\)个项
• 将表达式翻译为后缀式的语义规则描述：
  • E.code表示\(E\)的后缀形式
  • op表示任意二元操作符
  • ||表示后缀形式的连接

图表示法

1. DAG（无循环有向图Direct Acyclic Graph） - 对表达式中的每个子表达式，DAG中都有一个结点 - 一个内部结点代表一个操作符，其孩子代表一个操作数 - 在一个DAG中代表公共子表达式的结构具有多个父节点 2. 抽象语法树 - 产生赋值语句抽象语法树的属性文法：

三地址代码

• 三地址代码：x := y op z
• 三地址代码可以看成是抽象语法树或DAG的一种线性表示
• 在生成三地址代码时，临时变量的名字对应抽象语法树的内部结点
  • \(id:=E\)
    • 对表达式\(E\)求值并置于变量\(T\)中
    • id.place:=T

      [!note] 从赋值语句生成三地址代码的S-属性文法 - 非终结符号S有综合属性S.code，其代表赋值语句S的三地址代码 - 非终结符号\(E\)有如下两个属性： - E.place：存放E值的名字 - E.code：E求值的三地址语句序列 - 函数newtemp：返回一个不同临时变量名字，如\(T_1,T_2,\cdots\)

四元式

• 一个带有四个域的记录结构，这四个域分别为
  • op
  • arg1
  • arg2
  • result

三元式

• 通过计算临时变量值的语句位置来引用这个临时变量

间接三元式

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