ch08--中间代码生成.ppt

第8章中间代码生成 知识点 三地址代码语句的翻译布尔表达式的翻译回填技术 2 75 中间代码生成 中间代码生成程序的任务把经语法分析 语义分析后得到的源程序的中间表示翻译成中间代码表示采用中间代码作为过渡的优点便于编译程序的建立和移植便于进行与机器无关的代码优化工作缺点增加了I O操作 效率下降中间代码生成程序的位置 3 75 中间代码生成 8 1中间代码形式8 2赋值语句的翻译8 3布尔表达式的翻译8 4控制语句的翻译8 5标号和转移语句的翻译8 6CASE语句的翻译8 7过程调用语句的翻译小结 4 75 8 1中间代码形式 一 图形表示语法树dag图二 三地址代码三地址语句的形式三地址语句的种类三地址语句的实现 5 75 一 图形表示 语法树描绘了源程序的自然层次结构dag图以更紧凑的方式给出了同样的信息因为公共子表达式被标识出来了 6 75 为赋值语句产生语法树的语法制导定义 7 75 语法树表示 dag图形表示 赋值语句a b c b c的图表示法 8 75 二 三地址代码 三地址代码三地址语句组成的序列类似于汇编语言的代码语句可以有标号有控制流语句三地址语句的形式 x yopzx可以是名字 临时变量op代表运算符号 如定点 浮点 或逻辑算符等y z可以是名字 常数 或临时变量 9 75 三地址语句的种类 赋值语句x yopzx opyx y转移语句gotoLifxrelopygotoL过程调用语句paramxcallp n 数组赋值语句x y i x i y指针赋值语句x yx y x y 10 75 赋值语句a b c b c的三地址代码 对应语法树的代码t1 ct2 b t1t3 ct4 b t3t5 t2 t4a t5 对应dag的代码t1 ct2 b t1t5 t2 t2a t5 11 75 三地址语句的实现 四元式 四元式 op arg1 arg2 result op arg1 result param arg1 goto 语句标号 赋值语句a b c b c的四元式表示 12 75 三元式 op arg1 arg2 为避免把临时变量名也存入符号表 可不引入临时变量把由一个语句计算出来的中间结果直接提供给引用它的语句用计算中间结果的语句的指针代替存放中间结果的临时变量赋值语句a b c b c的三元式表示 三地址语句的实现 三元式 13 75 语句x i y和x y i 的三元式序列 语句x i y 语句x y i 14 75 间接三元式间接码表 为三元式序列建立的一个指针数组 其每个元素依次指向三元式序列中的一项赋值语句a b c b c的间接三元式表示间接码表三元式 三地址语句的实现 间接三元式 15 75 8 2赋值语句的翻译 假定赋值语句出现的环境可用下面的文法描述 P MD SM D D D D id T D procid ND SN T integer real array num ofT1 T1 recordDendS id EE E E E E E E id 16 75 一 仅涉及简单变量的赋值语句 文法S id EE E1 E2E E1 E2E E1E E1 E id 函数newtemp属性E place函数lookup e 17 75 翻译方案1 S id EE E1 E2E E1 E2E E1E E1 E id p lookup id name if p nil E place p elseerror E place E1 place E place newtemp emit E place uminus E1 place E place newtemp emit E place E1 place E2 place E place newtemp emit E place E1 place E2 place p lookup id name if p nil emit p E place elseerror 18 75 翻译方案2 考虑类型 S id E p lookup id name if p nil t gettype p if t E type emit p E place S type void elseif E type可转换为t u newtemp emit u 类型转换符E place emit p u S type void elseS type type error elseerror 19 75 E E1 E2 E place newtemp if E1 type integer 20 75 E E1 E place newtemp emit E place uminus E1 place E type E1 type E E1 E place E1 place E type E1 type E id p lookup id name if p nil E place p E type gettype p elseerror 21 75 翻译赋值语句x y i j 假定x和y的类型为real i和j的类型为integer 三地址代码 t1 newtemp t1 iint j t2 newtemp t3 newtemp t3 inttorealt1 t2 yreal t3 x t2 22 75 二 涉及数组元素的赋值语句 1 计算数组元素的地址数组元素存储在一个连续的存储块中 根据数组元素的下标可以快速地查找每个元素 一维数组A 基址 base域宽 w元素个数 high low 1 数组元素A i 的位置 base i low w i w base low w 23 75 二维数组A 存储方式 按行存放按列存放 每维的下界 low1 low2每维的上界 high1 high2每维的长度 n1 high1 low1 1n2 high2 low2 1域宽 w基址 base 数组元素A i j 的位置 base i low1 n2 j low2 w i n2 j w base low1 n2 low2 w 24 75 每维的下界 low1 low2 lowk每维的长度 n1 n2 nk存储方式 按行存放数组元素A i1 i2 ik 的位置 i1 n2 i2 n3 i3 nk ik w base low1 n2 low2 n3 low3 nk lowk w K维数组A 递归计算 e1 i1 e2 e1 n2 i2 e3 e2 n3 i3 ek ek 1 nk ik 25 75 2 涉及数组元素的赋值语句的翻译 L属性定义 语句X A i j 的分析树 赋值语句的文法 1 S L E 2 E E1 E2 3 E E1 4 E L 5 L id 6 L id Elist 7 Elist E 8 Elist Elist1 E 26 75 属性及函数设计 L综合属性L place和L offset简单变量 L offset nullL place 符号表入口指针数组元素 L offset 计算公式第一项L place 计算公式第二项E综合属性E place 保存E值的变量在符号表中的位置Elist继承属性array 综合属性ndim placeElist array 数组名在符号表中的位置Elist ndim 目前已经识别出的下标表达式的个数Elist place 保存递推公式中em值的临时变量在符号表中的位置函数limit array j 返回array指向的数组第j维的长度invariant array 返回array指向的数组的地址计算公式中的不变项 27 75 L属性定义翻译方案 S L E if L offset null L是简单变量 emit L place E place elseemit L place L offset E place E E1 E2 E place newtemp emit E place E1 place E2 place E E1 E place E1 place E L if L offset null L是简单变量 E place L place else E place newtemp emit E place L place L offset 28 75 L id L place id place L offset null L id Elist Elist Elist1 E Elist E Elist array id place t newtemp m Elist1 ndim 1 emit t Elist1 place limit Elist1 array m emit t t E place Elist place t Elist ndim m e2 e1 n2 i2e3 e2 n3 i3ek ek 1 nk ik L place newtemp emit L place Elist array invariant Elist array L offset newtemp emit L offset w Elist place Elist place E place Elist ndim 1 Elist1 array Elist array e1 i1 29 75 举例 已知 设A为一个10 20的数组 即n1 10 n2 20 并设域宽w 4 数组的第一个元素为A 1 1 则有low1 1 low2 1所以 low1 n2 low2 w 1 20 1 4 84问题 将赋值语句x A y z 翻译为三地址代码 30 75 产生三地址代码 t1 y 20t1 t1 zt2 A 84t3 4 t1t4 t2 t3 x t4 x A y z 31 75 3 涉及数组元素的赋值语句 S属性定义 S L EE E1 E2E E1 E LL id id Elist Elist Elist1 E E 语句X A i j 的分析树 改写文法 L id Elist Elist Elist1 E id E 32 75 属性及函数设计 L综合属性L place和L offset简单变量 L offset nullL place 符号表入口指针数组元素 L offset 计算公式第一项L place 计算公式第二项E综合属性E place 保存E值的变量在符号表中的位置Elist综合属性Elist array ndim placeElist array 数组名在符号表中的位置Elist ndim 目前已经识别出的下标表达式的个数Elist place 保存递推公式中em值的临时变量在符号表中的位置函数limit array j 返回array指向的数组第j维的长度invariant array 返回array指向的数组的地址计算公式中的不变项 33 75 S属性定义翻译方案 S L E if L offset null L是简单变量 emit L place E place elseemit L place L offset E place E E1 E2 E place newtemp emit E place E1 place E2 place E E1 E place E1 place E L if L offset null L是简单变量 E place L place else E place newtemp emit E place L place L offset 34 75 L id L place id place L offset null Elist id E Elist Elist1 E L Elist Elist place E place Elist ndim 1 Elist array id place t newtemp m Elist1 ndim 1 emit t Elist1 place limit Elist1 array m emit t t E place Elist array Elist1 array Elist place t Elist ndim m L place newtemp emit L place Elist array invariant Elist array L offset newtemp emit L offset w Elist place e2 e1 n2 i2e3 e2 n3 i3ek ek 1 nk ik e1 i1 35 75 赋值语句x A y z 的分析树 A x y z place x offset null place y offset null place y place y ndim 1 array A place z offset null place z place t1 ndim 2 array A place t2 offset t3 place t4 t4 t2 t3 t1 y 20t1 t1 z 36 75 三 记录中域的访问 声明 p recordinfo integer x realend 引用p info 1 编译器的动作lookup p Gettype根据t 找到记录的符号表根据info在表中找 37 75 8 3布尔表达式的翻译 布尔表达式的作用计算逻辑值用作控制语句中的条件表达式产生布尔表达式的文法 E EorEE EandEE notEE E E idrelopidE trueE false 38 75 一 翻译布尔表达式的方法 布尔表达式的值的表示方法数值表示法 1 true0 false非0 true0 false控制流表示法 利用控制流到达程序中的位置来表示true或false布尔表达式的翻译方法数值方法控制流方法 39 75 二 数值表示法 布尔表达式的求值类似于算术表达式的求值例如 三地址代码t1 notct2 bandt1t3 aort2 aorbandnotc 关系表达式a b等价于 ifa bthen1else0 a b的三地址代码 100 ifa bgoto103101 t 0102 goto104103 t 1104 40 75 翻译方案 属性 函数及变量说明属性E place 存放布尔表达式E的值的临时变量 临时变量在符号表中的入口位置 函数emit 产生并输出一条三地址语句变量nextstat 输出序列中下一条三地址语句的位置emit之后 nextstat自动加1 翻译方案 E E1orE2 E place newtemp emit E place E1 place or E2 place E E1andE2 E place newtemp emit E place E1 place and E2 place E notE1 E place newtemp emit E place not E1 place 41 75 E E1 E place E1 place E id1relopid2 E place newtemp emit if id1 placerelop opid2 place goto nextstat 3 emit E place 0 emit goto nextstat 2 emit E place 1 E true E false E place newtemp emit E place 1 E place newtemp emit E place 0 42 75 举例 a borc dande f 100 ifa bgoto103101 t1 0102 goto104103 t1 1 104 ifc dgoto107105 t2 0106 goto108107 t2 1 108 ife fgoto111109 t3 0110 goto112111 t3 1 112 t4 t2andt3 113 t5 t1ort4 43 75 三 控制流表示法 控制语句S ifEthenS1 ifEthenS1elseS2 whileEdoS1代码结构 E的代码 S1的代码 E true E falseS next E的代码 S1的代码 S2的代码 E true E false S next E的代码 S1的代码 E true S begin E falseS next 44 75 属性说明 继承属性 三地址语句标号E true E值为真时应执行的第一条语句的标号E false E值为假时应执行的第一条语句的标号S next 紧跟在语句S之后的三地址语句的标号S begin 语句S的第一条三地址语句的标号 45 75 布尔表达式的控制流翻译 布尔表达式被翻译为一系列条件转移和无条件转移三地址语句这些语句转移到的位置是E true E false之一例如a b翻译为 ifa bgotoE truegotoE false属性说明继承属性E true E为真时转移到的三地址语句的标号E false E为假时转移到的三地址语句的标号 46 75 布尔表达式的代码结构 E E1orE2 E E1andE2 E notE1 E id1relopid2 if id1 placerelop opid2 place goto E true goto E false 47 75 例 用控制流方法翻译布尔表达式a borc dande f a b的代码 c d的代码 e f的代码 LtrueLfalse L1 L2 ifa bgotoLtruegotoL1L1 ifc dgotoL2gotoLfalseL2 ife fgotoLtruegotoLfalse 48 75 布尔表达式的翻译 两遍扫描的翻译技术1 生成分析树2 为分析树加注释 翻译一遍扫描的分析和翻译技术问题 当生成某些转移指令时 目标地址可能还不知道解决办法先产生没有填写目标标号的转移指令 建立一个链表 把转向这个目标的所有转移指令的标号填入该链表 目标地址确定后 再把该地址填入该链表中记录的所有转移指令中 回填技术 backpatching 49 75 利用回填技术翻译布尔表达式 说明为明确起见 生成的中间代码用四元式表示四元式存放在数组中用数组下标表示三地址语句的标号综合属性E truelist 记录转移到E的真出口的指令链表的指针E falselist 记录转移到E的假出口的指令链表的指针M quad M所标识的三地址语句的地址变量nextquad 下一个可用的四元式地址 产生的下一条三地址语句在数组中的位置 50 75 函数说明 makelist i 建立新链表 其中只包括四元式指令在数组中的下标i 返回所建链表的指针 merge p1 p2 合并由指针p1和p2所指向的两个链表返回结果链表的指针 backpatch p i 用目标地址i回填p所指链表中记录的每一条转移指令 emit S 产生一条三地址语句S 并写入输出数组中该函数执行完后 变量nextquad加1 51 75 例 a borc dande f 100 ifa bgoto 101 goto 102 ifc dgoto 103 goto 104 ifc dgoto 105 goto t 100 f 101 102 t 102 f 103 104 t 104 f 105 104 truelist 104 falselist 103 105 102 truelist 100 104 falselist 103 105 52 75 翻译方案 布尔表达式的文法E E1orME2E E1andME2E notE1E E1 E id1relopid2E trueE falseM 标记非终结符号M标识布尔表达式E2的开始位置用属性M quad记录其所标识的布尔表达式的第一条三地址语句的地址相应于产生式M 的动作 M quad nextquad 53 75 E E1orME2 backpatch E1 falselist M quad E truelist merge E1 truelist E2 truelist E falselist E2 falselist E E1andME2 backpatch E1 truelist M quad E truelist E2 truelist E falselist merge E1 falselist E2 falselist E notE1 E truelist E1 falselist E falselist E1 truelist E E1 E truelist E1 truelist E falselist E1 falselist E id1relopid2 E truelist makelist nextquad E falselist makelist nextquad 1 emit if id1 placerelop opid2 place goto emit goto E true E truelist makelist nextquad emit goto E false E flaselist makelist nextquad emit goto M M quad nextquad 54 75 利用翻译方案翻译布尔表达式a borc dande f E E E a b c d e f or M E and M E t 100 f 101 100 ifa bgoto 101 goto q 102 t 102 f 103 102 ifc dgoto 103 goto q 104 t 104 f 105 104 ife fgoto 105 goto 104 t 104 f 103 105 102 t 100 104 f 103 105 假定变量nextquad的初值为100 55 75 8 4控制语句的翻译 文法S ifEthenS1S ifEthenS1elseS2S whileEdoS1S beginLendS AL L1 SL S M M1 M2 M2 M1 M N M N 属性 E truelistE falselistM quadN nextlistS nextlist变量 nextquad函数 makelistbackpatchmergeemit 转移到下一条语句的指令链表的指针 56 75 翻译方案 S ifEthenMS1 backpatch E truelist M quad S nextlist merge E falselist S1 nextlist S ifEthenM1S1NelseM2S2 backpatch E truelist M1 quad backpatch E falselist M2 quad S nextlist merge S1 nextlist N nextlist S2 nextlist S whileM1EdoM2S1 backpatch S1 nextlist M1 quad backpatch E truelist M2 quad S nextlist E falselist emit goto M1 quad M M quad nextquad N N nextlist makelist nextquad emit goto S beginLend S nextlist L nextlist S A S nextlist makelist L L1 MS backpatch L1 nextlist M quad L nextlist S nextlist L S L nextlist S nextlist 57 75 A1的代码 例 ifa borc dande fthenA1elseA2 whilea bdoA3 if语句的代码 while语句的代码 E的代码 A1的代码 A2的代码 E的代码 A3的代码 100 ifa bgoto 101 goto102102 ifc dgoto104103 goto 104 ife fgoto 105 goto 127 ifa bgoto 128 goto 106 115 116 goto 117 126 A2的代码 106 106 117 117 129 138 A3的代码 129 139 goto127 127 n 116 58 75 8 5标号和转移语句的翻译 标号的出现有两种形式L SgotoL 定义性出现 引用性出现 两种情况先定义 后引用 L S gotoL 先引用 后定义 gotoL L S 59 75 先定义后引用的情况 L S gotoL 1 查找当前符号表2 找到同名标识符 出错处理3 否则 将该标号L插入符号表 S的第一条三地址语句的位置 1 根据标号L查找当前符号表2 取出L所标识的三地址语句的位置A3 生成指令 goto A 60 75 先引用后定义的情况 gotoL gotoL L S p 1 根据标号L查找当前符号表2 若未找到 则 将标号L插入符号表生成目标地址未定义的goto语句将该语句的地址p填入L的表项中3 若找到 则 生成目标地址未定义的goto语句将该语句的地址q插在链首 p goto q goto p q 1 根据标号L查找当前符号表2 将 未定义 改为 已定义 3 用S的第一条三地址语句的地址A回填链表中的goto语句 t A A A 61 75 两种情况统一考虑 gotoL根据名字L查找符号表若未找到L 则将L插入符号表中 置类型为 label 置存在标志为 f 为该语句生成无目标地址的三地址语句 goto 将该三地址语句的地址q记入符号表中L的地址域中找到L 则如果L的类型不是label 则出错处理若L的类型为label且 已定义 则以L标识的三地址语句的地址A作为目标地址生成转移指令 goto A 若L的类型为label且 未定义 则说明前面已出现过 gotoL 为该语句生成无目标地址的三地址语句 goto 并将该三地址语句插入回填链的链首 62 75 根据名字L查找符号表找到L 则L的类型不是label 出错处理 L的类型为label且 已定义 出错处理 L的类型为label 但 未定义 则 置定义标志为 t 用变量nextquad的值回填 地址域 中记录的链表中的三地址语句未找到L 则将L插入符号表中 置类型为 label 置存在标志为 t 将S的三地址代码的始址 变量nextquad的值 填入 地址域 请思考 如何实现 goto语句只允许将控制从结构内转移出 而不允许转移入 L S 63 75 8 6CASE语句的翻译 CASE语句的语法结构switchEbegincaseV1 S1caseV2 S2 caseVn 1 Sn 1default Snend 生成的代码的功能1 对开关表达式求值 2 在V1 Vn中找与E值匹配的值 若找不到 则让 缺省值 与之匹配 3 执行与Vi相联系的语句Si 64 75 CASE语句的代码结构 对E求值的代码把求值结果置于t中的代码ift V1gotoL2S1的代码gotonextL2 ift V2gotoL3S2的代码gotonextL3 Ln 1 ift Vn 1gotoLnSn 1的代码gotonextLn Sn的代码next 对E求值的代码把求值结果置于t中的代码gototestL1 S1的代码gotonextL2 S2的代码gotonextL3 Ln 1 Sn 1的代码gotonextLn Sn的代码gotonexttest ift V1gotoL1ift V2gotoL2 ift Vn 1gotoLn 1gotoLnnext 控制结构复杂goto语句生成时不完整 65 75 CASE语句的翻译 switchEbegincaseV1 S1caseVi Si caseVn 1 Sn 1default Snend 1 生成test和next两个标号2 建立一个临时变量t 1 生成对E求值的代码2 结果值存入临时变量t中3 产生指令gototest 1 建立一个新的标号Li 并把它存入符号表 2 建立一个栈 令其为case栈 存放每个case对应的常量值及其标号在符号表的位置