【编译原理复习笔记】中间语言

（1）独立于机器 （2）复杂性介于源语言和目标语言之间 中间语言可以使编译程序的结构在逻辑上更为简单明确

后缀式 图表示：抽象语法树，有向无环图 三地址代码：三元式，四元式，间接三元式

（1）若 E 为单独的变量或常量，则其自身就为后缀式 （2）若 E 为 E1 op E2 的形式，则其后缀式为 E1’ E2’ op，其中前两项对应了各自的后缀式 （3）若 E 为（E1）形式，则 E 的后缀式为 E1 的后缀式 优点： 后缀式不用使用括号 自左向右扫描后缀式，每碰到运算量就推进栈，遇到 k 目运算符时就计算栈顶的 k 个项目

（1）抽象语法树 （2）有向无环图 DAG 对于表达式中的子表达式，DAG 中都有一个结点 一个内部结点表示一个操作符，其子节点代表操作数 在一个 DAG 中代表公共子表达式的节点有多个父节点

可以看作前两种方法的相线性表达方法 三地址：结果，第一操作数，第二操作数 而且三地址代码的复杂程度也与抽象语法树和有向无环图的复杂程度相关

赋值语句 操作语句（双操作数，单操作数） goto 语句 传参语句 返回语句 等等

将每个三元式都表示为带有四个域的记录结构，分别为 op，arg1，arg2，res

三元式不储存 res，用序号来表示 res

三元式表+间接码表 间接码表：一张指示器表，按运算的先后顺序列出有关三元式在三元式表中的位置，节省空间

在格外添加间接码表，此后再修改时只需要修改间接码表，这个三元式表就不用变动

赋值语句的形式： i d : = E id:=E id:=E 赋诗语句的 S 属性文法 非终结符 S 有综合属性 S.code，代表赋值语句的三地址代码 E 有两个属性 E.place 表示存放 E 的单元的地址 E.code 表示对 E 求值的三地址语句

设 A 为 n 维数组，按行存放，每个元素宽度为 w l o w i low_i lowi​为第 i 维 的下界 u p i up_i upi​为第 i 维的上界 n i n_i ni​为第 i 维的个数 b a s e base base为 A 的基准坐标（第一个元素地址）

红色为可变部分，蓝色为固定部分

十分复杂，建议直接观看视频： 哈工大编译原理 P6-4

（1）在运算符中带上类型信息 （2）新增加类型转换运算符 （3）用 E.type 表示非终结符 E 的类型，并增加类型检查

如果两者类型不同时对应的语义动作：

E → E o r E ∣ E a n d E ∣ n o t E ∣ ( E ) ∣ i r e l a t i o n o p i ∣ i E \to E\\ or \\ E|E\\ and\\ E|not\\ E|(E)|i \\ relationop \\ i|i E→EorE∣EandE∣notE∣(E)∣irelationopi∣i均为布尔表达式 计算布尔表达式的两种办法： （1）数值表示法 true 为 1，false 为 0 （2）带优化的翻译法、 可以节省计算过程 e.g. A a n d B = > i f A t h e n B e l s e F a l s e A and B => if A then B else False AandB=>ifAthenBelseFalse 如果采用数值表示法，那么 B 的真伪是必须要进行计算的，但是采用这种方法时，A 一旦为 false 就不用在计算 B

a or b and not c T1:=not c T2:=b and T1 T3:=a or T2 nextstate 用来记录下一条三地址语句的位置，方便 emit 来输出三元式

对于语义函数 newlabel，返回新的符号标号 对于一个布尔表达式，设置两个继承属性，E.true 是其为真时的控制流跳转符号 E.false 是其为假时控制流跳转符号 E.code 记录 E 生成三地址代码

以四元式为中间语言，使用 emit 将其送入输出数组 难点：产生四元式时转移地址无法立刻知道，只有知道了后续状态才能回填跳转状态 总的来说，一共有两种跳转可能，一种为“真”，一种为“假”，把这些未完成的四元式作为语义值保存，到合适的位置回填

引入语义变量： nextquad：指向下一条产生四元式的地址 makelist：创建一条长度为 1 的链，对应四元式的下标 merge：合并两条链，指向合并后的链首 backpatch：回填

if-then

双分支 if then else while