南京大学：《编译原理》课程教学资源（PPT课件讲稿）第六章 中间代码生成

本章内容 ·中间代码表示 抽象语法树 一三地址代码:X=yopZ ·静态类型检查 类型检查( type checking) 语法分析之后的抽象语法( yntax检查,比如 break的位置 goto的 目标 中间代码生成

本章内容 • 中间代码表示 – 抽象语法树 – 三地址代码：x=y op z • 静态类型检查 – 类型检查（type checking） – 语法分析之后的抽象语法(syntax)检查，比如 break的位置，goto的目标…. • 中间代码生成

编译器前端的逻辑结构 语法 静态检 中间代码 中间 代码 分析器 查程序 生成器 代码 生成器 前端 —后端 图6-1一个编译器前端的逻辑结构

编译器前端的逻辑结构

三地址代码(1) ·每条指令右侧最多有一个远算符 般情况可以写成ⅹ=yopZ 允许的远算分量 名字:源程序中的名字作为三地址代码的地址 常量:源程序中出现或生成的常量 编译器生成的临时变量

三地址代码（1） • 每条指令右侧最多有一个运算符 – 一般情况可以写成x = y op z • 允许的运算分量： – 名字：源程序中的名字作为三地址代码的地址 – 常量：源程序中出现或生成的常量 – 编译器生成的临时变量

地址代码(2) 指令集合(1) 运算赋值指令:ⅹ=yopz X=op y 复制指令:Xy 无条件转移指令: goto L 条件转移指令: if x goto L if False x goto L 条件转移指令: if x relop y goto L

三地址代码（2） • 指令集合（1） – 运算/赋值指令：x=y op z x = op y – 复制指令：x=y – 无条件转移指令：goto L – 条件转移指令：if x goto L if False x goto L – 条件转移指令：if x relop y goto L

地址代码(3) 指令集合(2) 过程调用/返回: param xI ∥设置参数 param x2 param Xn call p,n ∥调用子过程p,n为参数个数 带下标的复制指令:X=y[ x[1= 注意:1表示离开数组位置第个字节,而不是数组的第 个元素 地址/指针赋值指令: Xay

三地址代码（3） • 指令集合（2） – 过程调用/返回： • 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

例子 语句 do i=i+ 1; while(a1<); L: t i+1 100:t1=i+1 1 101:i=t t2=1 102:t t3=a[t2] 103:t3=a[t2] if t3 v goto l 104: if t3 v goto 100 a)符号标号 b)位置号

例子 • 语句 – do i = i + 1; while (a[i]<v)；

地址指令的四元式表示方法 ·在实现时,可以使用四元式/三元式/间接三元式来 表示三地址指令 四元式:可以实现为纪录(或结构) 格式(字段) op an arg2 result op运算符的内部编码 argl,arg2, results是地址 Xy+z 单目运算符不使用arg2 param运算不使用ag2和 result 条件转移/非条件转移将目标标号放在 result字段

三地址指令的四元式表示方法 • 在实现时，可以使用四元式/三元式/间接三元式来 表示三地址指令 • 四元式：可以实现为纪录（或结构） – 格式（字段）： op arg1 arg2 result – op: 运算符的内部编码 – arg1,arg2,result是地址 – x=y+z + y z x • 单目运算符不使用arg2 • param运算不使用arg2和result • 条件转移/非条件转移将目标标号放在result字段

四元式的例子 p argarg 2 result minus c 0 minus i C I t1 2=b*t t1 2 t3 minus C 2minustc t 3 t4 b* t3 t3 t4 t5 ttt 4 t2t4t5 5 ts a a)三地址代码 b)四元式 图6-10三地址代码及其四元式表示 ·赋值语旬:a-b*-C+b*-c

四元式的例子 • 赋值语句：a=b* -c + b* -c

元式表示 元式( triple) op argl arg2 使用三元式的位置來引用三元式的运算结果 x[y需要拆分为两个三元式 求x[的地址,然后再赋值 Xy op Z需要拆分为(这里?是编号 ( op y 题:在优化时经常需要移动/删除/添加三元 式,导致三元式的移动

三元式表示 • 三元式（triple） op arg1 arg2 • 使用三元式的位置来引用三元式的运算结果 • x[i]=y需要拆分为两个三元式 – 求x[i]的地址，然后再赋值 • x=y op z需要拆分为（这里？是编号） – (?) op y z – = x ? • 问题：在优化时经常需要移动/删除/添加三元 式，导致三元式的移动

元式的例子 0pa91a792 minus b(0 2 c b minus b minus 345 +1(1)(3) (4) a)语法树 b)三元式 图6-11a=b*-c+b*-c的表示 ·a=b*C+b*-C

三元式的例子 • a=b*-c + b * -c