说在前面

• 使用语言：javascript
• 语法分析：LL(1)
• 中间代码生成：三地址码 语法制导翻译
• 目标代码：mips代码
• 接上篇：【编译原理/类C编译器】(三)语法分析

运行界面

说明

语法制导翻译（在语法分析过程中，随着分析的步步进展，在使用某个产生式进行推导或归约时便执行相应的语义子程序，完成既定的翻译工作，生成中间代码）

写不动了，有时间再写，github在第一篇

在编译器的分析-综合模型中，前端对源程序进行分析并产生中间表示，后端在此基础上生成目标代码。理想情况下，和源语言相关的细节在前端分析中处理，而关于目标机器的细节则在后端处理。和中间代码相关的内容包括中间代码表示、静态类型检查和中间代码生成，本文将讨论关于中间代码表示的内容。

有向无环图

表达式的有向无环图（Directed Acyclic Graph，简称DAG）与语法分析树类似，一个DAG的叶子结点对应于原子运算分量，内部结点对应于运算符。与语法分析树不同的是，如果DAG中一个结点N表示一个公共子表达式，那么N可能有多个父结点。举个例子，表达式a+a*(b-c)+(b-c)*d的DAG如下：

DAG的每个结点通常作为一条记录被存放在数组中，一个记录包括的结点信息有：

• 结点标号：如果记录表示叶子结点，那么结点标号是该结点的文法符号；如果记录表示内部结点，那么结点标号是运算符；
• 词法值：如果记录表示叶子结点，那么记录还包括该结点的词法值，通常是一个指向符号表的指针或者一个常量；
• 左右子结点：如果记录表示内部结点，那么记录还包括该结点的左右子结点。

由于一个DAG的结点都会保存在一个记录数组中，因此我们可以通过数组下标引用某个记录从而获取结点信息，这个数组下标称为相应结点的值编码。

对图1的DAG，它的记录数组为：

其中，左边的下标是每个结点的值编码，并且在某些记录中可以包括值编码。例如：对于第5条记录，它表示内部结点”-“，该结点左边的子结点是叶子结点”b”，右边的子结点是叶子结点”c”，由于代表b和c的记录已经存在并且它们的值编码分别为2和3，因此内部结点”-“的记录为(-, 2, 3)。

三地址代码

三地址代码是形如x = y op z的指令集合，之所以名为“三地址代码”，是因为指令x = y op z具有三个地址：两个运算分量y和z，一个结果变量x。由于三地址代码会对多运算符算术表达式和控制流语句的嵌套结构进行拆分，因此适用于目标代码的生成和优化。

三地址代码基于两个基本的概念：地址和指令。简单地说，地址就是运算分量，指令就是运算符，一个地址的表现形式可以是变量名、常量或者编译器生成的临时变量。下面是几种常见的三地址指令形式：

除此之外，另一种方式是用记录表示三地址代码中的每条指令，四元式、三元式和间接三元式是三种用记录表示三地址代码的方式。

四元式

一个四元式是一条表示三地址指令的记录，它有4个字段：

• op：表示一个运算符；
• arg1：表示第一个运算分量；
• arg2：表示第二个运算分量；
• result：表示结果变量。

一个四元式中可能用到了所有4个字段，也可能只用到了其中几个字段，它的几个特例如下：

• 形如x = minus y的单目运算符指令不使用arg2字段，”minus”表示单目减运算符；
• 形如x = y的赋值指令不使用arg2字段，并且它的op字段是”=”；
• 形如param x的参数传递指令不使用arg2和result字段；
• 条件和非条件转移指令将目标标号放入result字段。

下图是一个例子，左边给出了三地址代码，右边是对应的四元式表示：

三元式

通过图2我们发现，一段三地址代码对应的四元式被存放在一个记录数组中，这一点和DAG结点的记录数组很像；另外，四元式中的result字段主要被用于保存临时变量名，这个临时变量是由编译器生成的。如果我们仿照DAG的记录数组用值编码表示临时变量的地址，那么就可以省略四元式中的result字段，三元式就是由此而来的。

一个三元式只有3个字段：op、arg1和arg2，它们的含义和在四元式中相同。为了取代四元式中的result字段，三元式用值编码表示结果变量的地址。图2中三地址代码的三元式表示如下：

在图3(b)中，表格左边的数字是值编码，它表示三元式的结果变量的地址，并且这些值编码可以在三元式中被使用（使用的时候用括号括起来）。另外，对形如x=y的赋值指令，和四元式不同的是，三元式的op字段是”=”，arg1字段是”x”，arg2字段是”y”。

间接三元式

三地址代码的三元式表示存在一个问题，如果记录数组中的某条记录R的位置发生改变，那么所有使用到记录R的值编码的记录都需要更新。举个例子，在图3(b)中，如果把第1和第2条记录的位置互换，那么第3和第4条记录的内容都会发生改变。为了解决这个问题，提出了用间接三元式来表示三地址代码。

一个间接三元式在三元式的基础上增加了一个列表，这个列表包含了指向三元式的指针。仍以例子说明，下图是图3中三元式的间接三元式：

图4(a)是图3(b)的间接三元式，它使用了一个instruction数组保存要执行的指令，每条指令是一个指向某个三元式的指针。这样的话，当我们改变指令顺序时，就不用再更新三元式了，如图4(b)所示。

静态单赋值形式

静态单赋值（Static Single Assignment，简称SSA）形式是另一种中间表示形式，它和三地址代码的主要区别在于：

第一，SSA中的所有赋值都是针对具有不同名字的变量的，这也是“静态单赋值”名字的由来。这一特性如下图中表示：

第二，由于同一个变量可能在两个不同的控制流路径中被定值，因此SSA使用一种被称为φ函数的表示规则将这个变量的两处定值合并起来。这一特性如下图所示：

欢迎关注微信公众号fightingZhヾ(◍°∇°◍)ﾉﾞ

基础

DAG

语法树是一种图形化的中间表示。但语法树中，公共子表达式每出现一次，就有一个对应的子树，产生了大量冗余，
因此定义了另一种中间表示：有向无环图(Directed Acyclic Graph, DAG)
有向无环图的构造与抽象语法树类似。

三地址代码

一般包括一个运算符和之多三个运算分量(地址)，所以叫做三地址代码。这里的地址包括：变量、常量、临时变量。

• 指令集合
  • 运算/赋值指令：x=y op z ，x = op y
  • 复制指令：x=y
  • 无条件转移指令：goto L
  • 条件转移指令：if x goto L ，ifFalse x goto L
  • 条件转移指令：if x relop y goto L
  • 过程调用/返回 p(x1, x2, …, xn)
    • param x1 //设置参数
    • param x2
    • …
    • param xn
    • call p, n //调用子过程p，n为参数个数
  • 带下标的复制指令：x=y[i] x[i]=y • 注意：i表示离开数组位置第i个字节，而不是数组的第i个元素
  • 地址/指针赋值指令： • x=&y x=*y *x=y

• 三地址代码的四元式表示
  格式（字段）： op arg1 arg2 result
  如：+ x y z
  对于有些指令，一些参数是空缺的，如
  param x1 null null
[if goto] x null L
  
• 三地址代码的三元式表示
  op arg1 arg2
  使用三元式的位置来引用三元式的运算结果
  
• 三地址代码的间接三元式表示
  包含了一个指向三元式的指针的列表  我们可以对这个列表进行操作，完成优化功能；操作时不 需要修改三元式中的参数
  
• 静态单赋值SAA
  

问题

声明语句的翻译

PPT 24-54

表达式和赋值语句的翻译

• 数组引用生成代码的翻译方案

非终结符号L的三个综合属性

1. L.addr指示一个临时变量，计算数组引用的偏移量 ij * wj
2. L.array是一个指向数组名字对应的符号表条目的指针， L.array.base为该数组的基地址
3. L.type是L生成的子数组的类型，对于任何数组类型t，其宽度由 t.width给出，t.elem给出其数组元素的类型
   

控制流翻译

• 文法：B表示布尔表达式，S代表语句 S → if (B) S1 ; S → if (B) S1 else S2 ;S → while (B) S1 . 代码的布局见下图
  
• 继承属性
  • B.true：B为真的跳转目标
  • B.false：B为假的跳转目标
  • S.next：S执行完毕时的跳转目标

例：$S⟶ifBthen{S}_1$

布尔表达式的翻译

• 当布尔表达式的计算用于跳转分治

布尔表达式翻译的主要语义动作是跳转，而跳转的标签主要根据短路规则来确定。

• 当布尔表达式的计算用于赋值
  采用临时变量的方法
  

switch 语句的翻译

过程调用的翻译

回填

布尔表达式用于语句的控制流时，它总是在取值true时和取值false 时分别跳转到某个位置

• 引入两个综合属性

  • truelist: 包含跳转指令（位置）的列表，这些指令在取值true时执行
  • falselist：包含跳转指令（位置）的列表，这些指令在取值false时执行

• 辅助函数

  • Makelist(i)：创建一个只包含i的列表
  • Merge(p1,p2)：将p1和p2指向的列表合并
  • Backpatch(p,i)：将i作为目标标号插入到p所指列表中的各指令中
    
    

• 控制转移语句的回填
  M的作用就是用M.instr记录下一个指令的位置 • N的作用是生成goto指令坯，N.nextlist只包含这个指令 的位置