第六章中间代码江西师范大学ppt课件.ppt

第六章中间代码 中间代码的形式表达式的翻译简单赋值语句的翻译布尔表达式的翻译控制语句的翻译 何谓中间代码 源程序的一种内部表示 不依赖目标机的结构 易于机械生成目标代码的中间表示 为什么要此阶段 主要优点是可移植 与具体目标程序无关 且易于目标代码优化 中间代码的几种形式 逆波兰 N 元表示 四元式 三元式 树 方法 语法制导翻译 优点形式简单 语义明确 便于翻译独立于目标语言 要掌握几种常见的中间语言的基本结构 图表示法 抽象语法树逆波兰表示法 也称后缀式 三地址代码四元式三元式 间接三元式 几种常见的中间语言 4 图表示法 抽象语法树 语法制导翻译以语法树作基础 实际上 语法树可以作为一种合适的中间语言形式 现在对语法树进行改造 去掉那些对翻译不必要的信息 将语法树进行抽象 抽象语法树 在抽象语法树中 每个叶结点都表示诸如常量或变量这样的运算对象 而其它内部结点则表示运算符 语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行 采用的基本方法是一样的 5 为下面文法的句子x a 4 c建立抽象语法树 S V EV idE E E E E E E E id num为每个运算量或运算符号都建立一个结点 可以根据表达式的运算顺序自下而上的构造 手工构造 抽象语法树运算符作内部结点 语法树 比较 抽象语法树的特点是结构紧凑 容易构造 结点较少 6 构造赋值语句 x a b c d e f的抽象语法树 根据表达式的运算顺序自下而上的构造 可以设计属性文法构造抽象语法树 手工构造抽象语法树 逆波兰表示法 逆波兰表示法又称后缀式表示法 逆波兰表示法是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法 这种方法是 把运算量 操作数 写在运算符的前面 把运算符写在运算量的后面 后缀 例 a bab a b c abc a b c d ab cd 表达式的逆波兰表示 一个表达式的后缀式可以如下递归定义 1 如果E是一个变量或常量 则E的后缀式是E自身 2 如果E是E1opE2形式的表达式 这里op是任何二元操作符 则E的后缀式为E1 E2 op 这里E1 和E2 分别为E1和E2的后缀式 3 如果E是 E1 形式的表达式 则E1的后缀式就是E的后缀式 后缀式与抽象语法树的关系 后缀式是抽象语法树的线性表示形式 是树的后序遍历 左 右 根 的一个序列 例如 a b c b c的抽象语法树 后缀式 abc bc assign 无环有向图 DAG DAG指出了表达式中公共子表达式 结点N 一个公共子表达式 可能有多个父结点 a a b c b c d DAG的值编码方法 到i对应的条目 12345 给出a b c b c的DAG及其值编码 三地址代码 三地址代码是由下面一般形式的语句构成的序列 x yopz其中 x y z为名字 常数或编译时产生的临时变量 op代表运算符号 每个三地址语句的右边只能有一个运算符 例 表达式x y z翻译为三地址代码 t1 y zt2 x t1t1 t2是编译时产生的临时变量 三地址代码 说明 1 之所以称为三地址代码 是因为三地址代码语句类似与汇编指令 涉及三个地址x y和z 其中y z表示操作数 x存放结果 地址常用属性place addr 表示 名字 place 指向符号表名字入口的指针临时变量 place 临时变量值存放的单元地址常数 place 指向常数表中常数入口的指针2 在三地址代码中 一条指令的右侧最多有一个运算符 3 三地址代码是抽象语法树的线性化表示 树的每个内部结点对应一个三地址语句 按树自下而上的顺序写出每个内部结点对应的三地址代码 注 临时变量的名字对应抽象语法树的内部结点 算符结点 表达式中的每个运算都要引入一个新的临时变量存放计算结果 要多少引入多少 T1 b cT2 a T1T3 a T2T4 T1 dT5 T3 T4 画出赋值语句x a b c的抽象语法树 给出其三地址表示 T1 b cT2 a T1x T2 1 赋值语句x yopz op是二元算术或逻辑运算符 2 赋值语句x opy op是一元算符 如取负运算符minus 逻辑非运算符not 移位运算符及类型转换运算符 3 复制语句x y 4 无条件转移语句gotoL L是语句标号 5 条件转移语句ifxgotoL ifFalsexgotoL X为真或为假时转移到L 三地址语句的种类 6 条件转移语句ifxrelopygotoL 关系运算符号relop 等等 7 过程调用语句paramx1 xi是实参数paramx2 paramxn callp n p过程名 n实参个数y callp n p函数名返回语句returny y返回值 可有可无 三地址语句的种类 8 变址赋值语句x y i 变址取数x i y 变址存数 9 地址和指针赋值语句x y x y x y 四元式 op arg1 arg2 result 用了四个域三元式 op arg1 arg2 只用三个域间接三元式间接码表 三元式表 便于进行优化 三地址代码的具体实现 三地址代码的具体实现 用记录结构 含四个域 四元式需要较多的临时单元 四元式之间的联系通过临时变量实现 三元式之间的联系通过指针实现 中间代码优化处理时 四元式比三元式方便得多 间接三元式与四元式同样方便 四元式和三元式两种实现方式需要的存储空间大体相同 三地址语句四元式表示x yopz op y z x x y minus y x x y y x parx1 param x1 callP call P gotoL j L 无条件转移ifagotoL jnz a L 条件转移a是逻辑量 a非0 即a为真时转移ifxropygotoL jrop x y L 条件转移rop是关系运算符 x和y为算术量 xropy为真时转移 常用的三地址语句对应的四元式 例 赋值语句a b c b c的四元式 三地址代码实现 四元式表示 注 四元式出现的顺序与表达式计值的顺序一致 四元式之间的联系通过临时变量实现 例 赋值语句a b c b c的三元式 注 三元式中使用了指向三元式语句的指针 序号 序号也表示该三元式计算的结果值 三元式之间的联系通过指针实现 三地址代码实现 三元式表示 例 赋值语句a b c b c的间接三元式 间接码表按运算的次序列出三元式序号 三元式表只列出不同的三元式 三元式表中没有了重复的三元式 语句的移动仅改变左边的间接码表 三地址代码实现 间接三元式 写出赋值语句 A B C D E F G的逆波兰表示 三元式表示 四元式表示 解 四元式表示 C D T1 B T1 T2 F G T3 E T3 T4 T2 T4 T5 T5 A 解 三元式表示 C D B F G E A 解 逆波兰表示 ABCD EFG 给出a b c d c d的抽象语法树和DAG所对应的三地址代码 1 E addr表示存放E值的名字 语法制导翻译生成三地址代码 几个用到的量 2 newtemp是个函数 对它的调用将产生一个新的临时变量 S id EE E1 E2E E1E E1 E id gen id addr E addr 产生式 语义规则 E E1 E2 S id E E addr newtemp gen E addr E1 addr E2 addr E E1 E addr newtemp gen E addr minus E1 addr Entry id 产生式 语义规则 E addr E1 addr E E1 产生赋值语句三地址代码的语法制导定义 增加一条乘法的产生式及语义规则 E id E addr id addr E E1 E2 E addr newtemp gen E addr E1 addr E2 addr S code E code gen id addr E addr 产生式 语义规则 E E1 E2 S id E E addr newtemp E code E1 code E2 code gen E addr E1 addr E2 addr p lookup id name if p NULL error elsegen p E addr E E1 E2 E place newtemp E code E1 code E2 code gen E addr E1 addr E2 addr 语义规则 产生式 E E1 E addr newtemp E code E1 code gen E addr minus E1 addr 产生式 语义规则 E addr E1 addr E code E1 code E E1 E id E addr id addr E code p lookup id name if p NULL E addr p elseerror 三地址语句序列是语法树的线性表示 用临时变量代替语法树中的结点 实际实现中 三地址语句序列往往是被存放到一个输出文件中 而不是将三地址语句序列置入code属性之中 思考题 简单算术表达式和赋值语句到四元式的翻译 Gen OP ARG1 ARG2 Result 过程 产生四元式 1 S id E GEN E addr id addr Entry id 2 E E1 E2 E addr NewTemp Gen E1 addr E2 addr E addr 3 E E1 E2 E addr NewTemp Gen E1 addr E2 addr E addr 4 E E1 E addr NewTemp Gen minus E1 addr E addr 5 E E1 E addr E1 addr 6 E i E addr id addr 分析赋值语句 X B C D 的语法制导翻译过程 四元式序列 minus B T1 C D T2 T1 T2 T3 T3 X 考虑表达式的类型 在前面关于算术表达式和赋值语句的翻译中 我们假定所有的i都是同一类型的 实际上 在表达式中可能出现各种类型的变量或常量 编译程序必须做到 或者拒绝接受某种混合运算 或者产生有关类型转换的指令 这种表达式和赋值语句的语义规则简单说明如下 1 引入语义变量E type表示表达式E的类型 2 增加类型转换的三地址语句 x inttorealy 3 对E E 1 E 2 E 1 E 2 的语义动作进行修改 增加判断表达式类型并确定类型的操作 E E1 E2 E addr newtempifE1 type integerandE2 type integerthenbegingen E addr E1 addr int E2 addr E type integerendelseifE1 type integerandE2 type realthenbeginu newtemp gen u inttoreal E1 addr gen E addr u real E2 addr E type realelseif else 1 数组元素地址的计算公式 数组元素的三地址代码是什么 数组元素的寻址 每个数组元素的宽度 数组首地址 bace low w i w 如何生成数组元素的三地址代码 一维数组的数组元素计算公式 VARa ARRAY low high OFreal 求a i 的地址 base i low w 对于一个二维数组 可以按行或按列存放 若按行存放 则可用如下公式计算 数组地址计算 可在编译时计算出来 常量部分 变量部分 base low w i w base i1一low1 n2 i2一low2 w 令c low1 n2 low2 w则常量部分 a low1 low2 c A 1 1 A 1 2 A 1 3 A 2 1 A 2 2 A 2 3 A 2 3 按行存放 A i1 i2 的地址 A 1 2 base 1 3 1 1 3 2 base 1 base low1 n2 low2 w i1 n2 i2 w 整理后 常量部分 c low1 n2 low2 n3 low3 nk lowk w变量部分v i1 n2 i2 n3 i3 nk ik w 多维数组A i1 i2 ik 的地址的计算 i1 n2 i2 n3 i3 nk ik w base low1 n2 low2 n3 low3 nk lowk w a i1 i2 in 的地址 base c v x a i1 in 的三地址代码结构 t1 v t2 base c t3 t2 t1 x t3 令a表示2 3的整数数组 c i j都是整数 那么a的类型就是array 2 array 3 integer 假定整数的宽度为4 那么a类型的宽度就是24 a i 的类型是array 3 integer 宽度为12 要求给出c a i j 的三地址代码 t1 i 12t2 j 4t3 t1 t2t4 a t3 t5 c t4 数组引用的翻译 L id E L E 翻译a i1 j b i2 其中a表示2 3的整数数组 b为一维数组 整数的宽度为4 翻译x a i j b i 翻译x k a i j b i 增加产生式及语义规则 E E1 E2E L 试写出下列赋值语句的三地址中间代码 其中数组类型为整型 大小为1 数组的下界为1 上界为10 A A i i 1t1 i 1t2 t1 1t3 a t2 t4 t3 1t5 t4 1t6 i 1a t5 t6 布尔表达式的翻译 布尔表达式是用布尔运算符号not and or 作用到布尔变量或关系表达式上而组成的 关系表达式形式如E1relE2 其中E1和E2是算术表达式 rel代表6个关系运算符 程序设计语言中布尔表达式有两个基本作用 一个是用作计算逻辑值 真1 假0 另一个是用作控制流语句如if else和while等中的条件表达式 无论作用如何 都必须先计算布尔表达式的值 布尔表达式的文法 考虑由下列文法G B 产生的布尔表达式 B B B B B B ErelE true false 假定使用rel的属性rel op来确定rel所指的6种关系运算中的哪一个 假定按惯例确定算术运算符 关系运算符及布尔运算符 的优先级和结合性 布尔表达式的语义 布尔式的语义是指明计算一个逻辑值的规则 有两种计算规则 1 用数值 1 0 表示真和假 同计算算术表达式一样 一步不差地按顺序计算出整个布尔式的值 例如 计算1 0 0 0 12 优化 短路 方法 不一定一步不差的计算 可以由某个子布尔式的值确定整个布尔式的值 规则2用于翻译控制流语句中的布尔表达式尤其方便 对于像a b这样的关系表达式 可看成等价的条件语句ifa bthen1else0 它翻译成的三地址代码为 1 ifa bgoto 4 2 t 0 3 goto 5 4 t 1 5 其中用临时变量t存放布尔表达式a b的值 5 为后续的三地址序号 数值表示法 考虑由下列文法G B 产生的布尔表达式 B B B B B B ErelE true false的语法制导翻译 nextstat是一个计数器 指向下一个三地址语句在输出序列中的索引序号 也就是即将生成的三地址语句序号 地址常用属性place addr 表示 B B1 B2 B addr newtemp gen B addr B1 addr B2 addr B B1 B2 B addr newtemp gen B addr B1 addr B2 addr B B1 B addr newtemp gen B addr B1 addr B B1 B addr B1 addr B E1relE2 B addr newtemp gen if E1 addrrelE2 addr goto nextstat 3 gen B addr 0 gen goto nextstat 2 gen B addr 1 B true B addr newtemp gen B addr 1 B false B addr newtemp gen B addr 0 给出布尔表达式a b c d e f三地址代码 100 ifa bgoto103101 t1 0102 goto104103 t1 1104 ifc dgoto107105 t2 0106 goto108107 t2 1 108 t3 t1 t2109 ife fgoto112110 t4 0111 goto113112 t4 1113 t5 t3 t4 布尔式的优化计值规则 解释为 ifB1thentrueelseB2B1真则B真 不须计算B2 解释为 ifB1thenB2elsefalseB1假则B假 不须计算B2 a 计算 b 计算 理解布尔表达式的真 假出口 出现在条件语句 中的布尔表达式B 它的作用仅在于控制对S1和S2的选择 只要能完成这一使命 B的值就无需最终保留在某个临时单元中 因此 作为转移条件的布尔式B 可以赋予它两种 出口 一个是 真 出口 为真时出向S1 一个是 假 出口 为假时出向S2 ifBthenS1elseS2的代码结构 语义值B code表示布尔式B的中间代码语义值S code表示语句S的中间代码 语义值B true 真出口 B为 真 时控制流转向的标号语义值B false 假出口 B为 假 时控制流转向的标号语义值S next 一个标号 表示紧随S代码之后的地址 S ifBthenS1 ifBthenS1elseS2 whileBdoS1 S1 S2 控制流语句的翻译 S ifBthenS1 B true newlabel B false S next S1 next S next S code B code gen B true S1 code S ifBthenS1elseS2 B true newlabel B false newlabel S1 next S next S2 next S next S code B code gen B true S1 code gen goto S next gen B false S2 code S whileBdoS1 S begin newlabel B true newlabel B false S next S1 next S begin S code gen S begin B code gen B true S1 code gen goto S begin S S1 S2 S code S1 code gen S1 next S2 code 布尔表达式的翻译如果B是a b的形式 那么代码是 ifa bgotoB truegotoB false 表达式a b c d e f的代码是 ifa bgotoL1gotoLfalseL1 ifc dgotoL2gotoLfalseL2 ife fgotoLtruegotoLfalse B B1 B2 B1 true B true B1 false newlabel B2 true B true B2 false B false B code B1 code gen B1 false B2 code B B1 B1 true B false B1 false B true B code B1 code B B1B code B1 code B id1relopid2 B code gen if id1 addr relop op id2 addr goto B true gen goto B false B true B code gen goto B true B false B code gen goto B false 给出x200 x y的三地址翻译 Ifx200gotoL2gotoLfalseL2 ifx ygotoLtruegotoLfalseLtrue Lfalse 考虑如下语句 whilea bdoifc dthenx y zelsex y z根据前面所述 生成代码 L1 ifa bgotoL2gotoLnextL2 ifc dgotoL3gotoL4L3 t1 y zx t1gotoL1L4 t2 y zx t2gotoL1Lnext 回填 先产生暂时没有填写目标标号的转移指令 对于每一条这样的指令作适当的记录 一旦目标标号被确定下来 再将它 回填 到相应的指令中 使用回填翻译控制语句中的布尔表达式 1 B B1 B2 把文法翻译成什么形式 2 B1 B2 B1 code B2 code B1 false toB1 true toB1 false toB2 true toB2 false B1 code B2 code B1 true toB1 true toB1 false toB2 true toB2 false toB true toB false toB true toB false 使用回填翻译控制语句中的布尔表达式 3 B1 4 B1 使用回填翻译控制语句中的布尔表达式 5 id1relid2 6 true 7 false 使用回填翻译控制语句中的布尔表达式 1 B B1 MB2 2 B1 MB2 3 B1 4 B1 5 id1relid2 6 true 7 false 8 M 插入非终结符号M是为了引入一个语义动作 以便在适当的时候获得即将产生的下一个 三地址代码 四元式的索引 翻译模式用到如下三个函数 1 makelist i 创建一个仅包含i的新表 i是三地址代码数组的一个索引 下标 或说i是三地址代码序列的一个标号 2 merge p1 p2 连接由指针p1和p2指向的两个表并且返回一个指向连接后的表的指针 3 backpatch p i 把i作为目标标号回填到p所指向的表中的每一个转移指令中去 此处的 表 都是为 反填 所拉的链 B B1 MB2 backpatch B1 false M next B true merge B1 true B2 true B false B2 false B B1 B B1 B true B1 false B false B1 true B B1 B true B1 true B false B1 false B id1relid2 B true nextstat B false nextstat 1 gen if id1 addrrel opid2 addr goto gen goto B true B true nextstat gen goto B false B false nextstat gen goto M M next nextstat 例重新考虑表达式a b c d e f一棵作了注释的分析树如下图所示 B t 100 104 B f 103 105 B t 100 B f 101 B t 104 B f 103 105 or M q 102 a b B t 102 B f 103 B t 104 B f 105 and M q 104 c e f d 依次分析 得到如下三地址 100 ifa bgoto 101 goto 102 ifc dgoto 103 goto 104 ife fgoto 105 goto 经过回填得到 100 ifa bgotoL1101 gotol02102 ifc dgotol04103 goto 104 ife fgotoL1105 goto 当知道了条件为真时和条件为假时分别应做哪些事时就可以进行回填 控制流语句的翻译模式 1 S ifBthenM1S1 backpatch B true M next S next merge B false S1 next 控制流语句的翻译模式 2 S ifBthenM1S1NelseM2S2 B code S1 code B true S2 code B false gotoS next S next toB true toB false M1处反填B trueM2处反填B falseN出生成 gotoS next backpatch B true M1 next backpatch B false M2 next S next merge S1 next N next S2 next N N next nextstat emit goto 控制流语句的翻译模式 2 S whileM1BdoM2S1 B code S1 code B true B false gotoS begin S begin toB false toB true M1处反填S1 next生成标号S beginM2处反填B true backpatch B true M2 next backpatch S1 next M1 next S next B false emit goto M1 next S beginLend S next L next S A S next makelist L L1 MS backpatch L1 next M next L next S next L S L next S next 先记录要回填的转移指令地址 在适当的时候进行回填 以便赋值和布尔表达式的求值得到合适的连接 以完成程序的控制流程 例 翻译下列语句whileaydoz x 1 elsex y 100ifaygotoL5 105goto100 106x z 1 107goto104 108goto100 109x y 110goto100 B code B1 code S11 code S12 code S1 code switchEbegincaseV1 S1caseV2 S2 caseVn 1 Sn 1default Sne