new《编译原理》第五章.ppt

编译原理CompilerPrinciples 蒋凌云jianglingyun 南京邮电大学 计算机学院 第五章语法制导翻译及中间代码生成 教材 编译技术原理及其实现方法 王汝传编著 第五章语法制导翻译及中间代码生成 本章内容 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 5 2中间语言一 引言二 逆波兰表示三 三元式四 树形表示五 四元式 第五章语法制导翻译及中间代码生成 本章内容 5 3自底向上语法制导翻译一 简单算术表达式和赋值语句的翻译二 布尔表达式的翻译三 控制语句翻译 四 数组元素的翻译五 过程语句的翻译六 说明语句的翻译 5 4自顶向下语法制导翻译一 递归下降的语法制导翻译二 LL 1 语法制导翻译 5 5属性文法与属性翻译一 属性文法与L属性文法二 属性翻译 第五章语法制导翻译及中间代码生成 本节内容 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 5 2中间语言一 引言二 逆波兰表示三 三元式四 树形表示五 四元式 5 1语法制导翻译概述 本节内容 一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 第五章语法制导翻译及中间代码生成 5 1语法制导翻译概述在前面我们已经讨论了词法分析和语法分析 一个程序成功地通过词法分析和语法分析 只能说明它是一个合法程序 但是对程序内部的逻辑含义并未加以考虑 从整个编译程序来看 词法分析和语法分析仅仅是编译程序的一部分 编译程序最终的目的是将源程序翻译成可供计算机直接执行的目标程序 在某些编译程序中 是直接生成机器语言或汇编语言形式的目标代码 有些编译程序是把源程序翻译为某种形式中间语言代码 然后再把中间语言代码翻译为目标代码 下面就来介绍一种语法制导翻译方法 这种方法先将源程序单词序列翻译成中间语言 然后再将中间语言翻译成目标程序 那么 什么叫语法制导翻译呢 第五章语法制导翻译及中间代码 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 第五章语法制导翻译及中间代码 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 5 1语法制导翻译概述一 语法制导翻译定义语法制导翻译就是以语法分析为主导的语义处理 在自顶向下语法分析过程中嵌入语义动作 即调用对应的语义子程序 例如在前面语法分析时分析a b c表达式 其分析语法树如下 E E E E E a b c 语法分析是将a归约E 再将b归约E 将c归约为E 然后再将E E归约成E 再将E E归约成E 所以a b c是一个合法的句子 如果考虑语义 在归约过程中加上语义动作 先将a归约为E 将a值赋给E后 b归约成E 同时将b值赋给E 在将c值赋给E 然后再将b c E E 给E 最后再将左右两个E值相加就是最终结果 这就是语法制导翻译的基本思想 在语法分析同时进行语义分析 第五章语法制导翻译及中间代码 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 第五章语法制导翻译及中间代码 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 5 1语法制导翻译概述二 语法制导翻译原理语法制导翻译的原理就是先为每个文法规定相应的语义 即编写出相应语义处理子程序 整个分析是以语法分析为主导 在自顶向下语法分析时 若某一个规则右部与输入串相匹配时 或者 在自底向上语法分析时 当一个规则被用于归约时 此时该规则对应的语义子程序就进入工作 完成既定翻译任务 产生与语义相应的中间代码或目标代码 语义动作 给每个文法符号X赋以各种不同的语义值这里的语义值不一定指具体数值 可以是 类型 种属 地址 或 代码 等 我们用记号X TYPE X CAT或X VAL来表示这些值 如果某规则的右部有若干个同一符号出现 那么我们就用上角标来区别这些符号 例如 假定有如下规则和语义动作 例如 假定有如下规则和语义动作 E E 1 E 2 E VAL E 1 VAL E 2 VAL 语义动作写在规则之后的花括号里 这里语义动作是表明与规则左部文法符号E相关的语义值E VAL 它是通过把规则右部文法符号的语义值E 1 VAL和E 2 VAL加在一起来决定的 规则中终结符号 按语义规则被解释成通常 加 的意思 各规则的语义动作可以对表达式计算 也可以生成中间代码 甚至还可以来产生目标指令 例5 1设有文法 E E E E digit 这里digit代表0和9之间任一数字 如果我们的目的仅是为了求值 则语义动作如下 1 E E 1 E E VAL E 1 VAL E 2 VAL 2 E digit E VAL digit 假定语义动作中的 代表是整型加算术运算 规则 1 的语义动作为 E的语义值E VAL等于E 1 和E 2 的语义值E 1 VAL和E 2 VAL之和 规则 2 的语义动作为 E的语义值为0 9之间任一个数 这样 按照它们的语义动作 我们在分析每个句子的同时一步一步地算出每个句子的值 例如 假定有输入串1 2 3 我们通过语法树的分析来看如何进行语法制导翻译 来求出该句子最后值 输入串1 2 3的语法树如下图所示 下面我们采用自底向上归约过程 首先考虑底层最左E的结点 这个结点对应于规则E 1和语义动作E VAL 1 这样 底层最左的E的值1与语义值E VAL相关 类似地 值2与该结点的右兄弟的语义值E VAL相关 如下图所示 E E E E E 1 2 3 在图所示子树中 子树根处E VAL的语义值是3 这可用语义动作E VAL E 1 VAL E 2 VAL算出 使用这个语义动作时 以底部最左的E的E VAL的值来代替E 1 VAL 而以右边E的E VAL的值代替E 2 VAL 以这种方法继续下去 我们就推出如下图所示整个语法树每个结点的语义值 E E E VAL 1 E 1 2 E VAL 2 E E VAL 6 E E VAL 3 E E VAL 3 E E VAL 1 E E VAL 2 1 2 3 第五章语法制导翻译及中间代码 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 第五章语法制导翻译及中间代码 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 5 1语法制导翻译概述三 语法制导翻译实现上面我们从原则上讨论了语法制导翻译的原理 下面我们通过一个自底向上LR分析看如何实现语法制导翻译 例如 有规则 1 X 动作1 2 Y 动作2 3 A XY 动作3 当使用规则 1 2 归约时 动作1 和 动作2 工作结果的有关信息 作为X和Y的语义值 应暂时保存下来 以便以后用规则 3 在归约时 动作3 可引用这些值 现在对LR分析器的分析栈加以扩充 为了在语法分析过程中平行地进行语义处理 使得每个文法符号之后都跟着它的语义值 因此 设置一个语义信息栈 为了清晰起见 我们把这个分析栈每一项分三部分组成 状态STATE 文法符号SYM和语义值VAL 这样 分析栈如下图所示 TOP STATE VAL SYM TOP 100 归约前 TOP 99 归约后 Y VAL TOP 99 求值后 A VAL Y VAL和X VAL的处理结果 我们假定先归约后执行语义子程序 所以当X Y归约为A时 此时栈顶指针下退 例如 开始TOP指100VAL TOP Y VAL 100 VAL TOP 1 X VAL 99 若归约后 此时TOP指99 所以VAL TOP X VAL 99 VAL TOP 1 Y VAL 100 若求值后 此时TOP指99 所以VAL TOP A VAL 99 例5 2考虑下面文法及其语义描述 规则语义动作 0 S E printE VAL 1 E E 1 E 2 E VAL E 1 VAL E 2 VAL 2 E E 1 E 2 E VAL E 1 VAL E 2 VAL 3 E E 1 E VAL E 1 VAL 4 E i E VAL LEXVAL 其中 语义动作中的 代表整型加 乘算术运算 而且词法分析程序将送来每个i的整型内部值LEXVAL 假定语义动作是紧接在归约之后执行的 上面所列的语义动作就相当于下面所列的程序段 规则程序段 0 S E printVAL TOP 1 E E 1 E 2 VAL TOP VAL TOP VAL TOP 2 2 E E 1 E 2 VAL TOP VAL TOP VAL TOP 2 3 E E 1 VAL TOP VAL TOP 1 4 E i VAL TOP LEXVAL 由于有一个 号 所以为TOP 2 由于有一个 号 所以为TOP 1 由于有一个 号 所以为TOP 2 根据上述程序段 若输入2 3 2 就有如下图所示的语法制导翻译的分析树 S E E E E E 2 2 3 E VAL 8 E VAL 6 E VAL 2 E VAL 2 E VAL 3 LEXVAL 2 LEXVAL 3 LEXVAL 2 对2 3 2利用P136 表4 23进行分析和翻译 实为计算值 该输入串过程如下表所示 当状态1面临 时对应的分析动作为acc 接受 此时 相应的语义动作为printVAL TOP 即输出语义程序的计值结果 8 第五章语法制导翻译及中间代码生成 本节内容 5 1语法制导翻译概述一 语法制导翻译定义二 语法制导翻译原理三 语法制导翻译实现 5 2中间语言一 引言二 逆波兰表示三 三元式四 树形表示五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言一 引言1 什么是中间语言就是和源程序等价的一种编码形式 其复杂性介于源程序和机器语言中间 源程序 前端 中间代码 代码优化器 中间代码 代码生成器 目标程序 符号表 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言一 引言2 为什么要引入中间语言 1 为了使编译程序结构上逻辑简单明确 2 为了便于目标代码优化工作 3 便于目标代码生成 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言二 逆波兰表示1 表达式逆波兰表示 1 波兰表示的概念对于一个算术表达式A B或逻辑表达式A B 根据运算符和运算对象的位置关系 可分为三种等价表示形式 1 中缀表示法运算符在运算对象中间 如 A B A B a b c d e f 等 2 后缀表示法将运算符放在运算对象后面 通常将后缀表示称为逆波兰表示 如 A B表示为AB A B表示为AB a b c表示为abc 对于逆波兰表示非常适合机械处理 只要从左到右按运算顺序一个个计算下去3 前缀表示法即将运算符放在运算对象前面 如 AB AB 例如表达式中缀表示和后缀表示如下表所示 p155表5 2 说明 以后我们主要讨论逆波兰表示 即后缀表示 因前缀表示并不常用 所以有时也将后缀表示笼统地统称为波兰表示 从上表中可以看出 1 在中缀表示和后缀表示中 运算对象按相同次序出现 2 在后缀表示中 运算符是按实际计算顺序从左到右排列 且每一运算符总是跟在它的运算对象之后 2 逆波兰 后缀 表示的优点1 后缀表示是一种无括号表示法 不但简明 而且又确切规定了计算顺序 2 运算处理极其简单方便 只要从左到右扫描后缀表达式各个符号 就能进行对表达式的处理一般步骤是从左到右扫描后缀表达式各个符号 每碰到运算对象时就把它推进栈 每碰到一个K元运算符时 就取出栈顶的K个运算对象进行相应的运算 并且用运算结果去替换栈顶的K个运算对象 然后再继续扫描表达式中余留符号 如此等等 直到整个表达式计算完毕为止 当上述过程结束后 整个表达式之值将留于栈顶 3 便于生成目标指令 3 逆波兰 后缀 表示的形成为了说明逆波兰 后缀 表示的形成 荷兰学者W DEJKSTRA给出下面形象的解释 比栈顶高进栈 比栈顶低或相同的退栈 下面用图解形式来说明A B C形成的过程 A 运算对象A移进对象栈 B C 下面用图解形式来说明A B C形成的过程 A 向下进运算符栈 B C 下面用图解形式来说明A B C形成的过程 AB 运算对象B移进对象栈 C 下面用图解形式来说明A B C形成的过程 AB 向下进运算符栈 C 下面用图解形式来说明A B C形成的过程 ABC 运算对象C移进对象栈 下面用图解形式来说明A B C形成的过程 ABC 退栈往左 下面用图解形式来说明A B C形成的过程 ABC 退栈往左 最后生成A B C的后缀式ABC 4 用后缀表式对表达式处理的过程下面通过求后缀表达式ab c 的值 来说明用后缀表式对表达式处理的过程设a b和c分别为1 3和5 为了求13 5 的值 其计算过程如下 1 把1推进栈 2 把3推进栈 3 将栈顶两个元素1和3相加 使它们退出栈 然后把结果4存入栈 4 把5推进栈 5 将栈顶两个元素4和5相乘 使它们退出栈 然后将结果20存入栈 结束时栈顶的值 这里是20 是整个表达式值 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言二 逆波兰表示2 逆波兰表示的扩充只要遵守在运算对象后直接紧跟运算符这条规则 我们就可以简单地把这种后缀式扩充到比通常表达式更大范围 即扩充到程序语言的其它语法成分 1 赋值语句 左部 表达式 把赋值号 看成是一个赋值运算符 它的后缀式为 左部 表达式的后缀式 例如 x 5x a b c d的后缀式分别为x5 xab cd 赋值语句的后缀式的处理方法和后缀式表达式处理方法类似 所不同的是栈中保存的是左部变量的地址 而不是其值 在赋值运算处理结束后 不产生任何中间计算结果 因而也不存在保存中间计算结果的问题 而是把存放在运算栈中栈顶两项 左部 和 表达式 的值这两个量退掉 2 条件语句ifEthenS1elseS 对于用后缀式来表示条件语句 我们假定后缀式中各符号存放在一个一维数组POST 1 n 之中 每一个数组元素存放一个运算对象或运算符 同时我们约定如下几个符号 JUMP表示无条件转 JLT表示小于转 JEZ表示零转 后缀式PJUMP表示无条件转移到下标P所指那个元素POST p 即从该符号开始继续执行 后缀式ePJEZ表示当后缀表达式e的值为零时 则转移至POST P 后缀式e1e2PJLT表示当后缀表达式e1小于后缀表达式e2时 则转移至POST P 于是 对于形如 ifethenS1elseS2 的条件语句可按后缀式写成e p1JEZS1 p2JUMPS2 我们约定e 0时 该条件语句的值是S1 否则等于S2 对于后缀式条件语句中 e S1 和S2 分别是e S1和S2的后缀式 此外 p1表示S2 在数组POST的起始位置 p2表示S2 之后那个符号位置 上述后缀式条件语句的意思是 若e 0时 则转至POST p1 对S2 进行计算 否则计算S1 然后转到POST p2 的位置 e p1JEZS1 p2JUMPS2 p1和p2等处理S2后再反填 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言二 逆波兰表示3 语法制导翻译生成后缀式下面我们讨论语法制导翻译生成后缀式的过程 我们以例4 15文法G E 为例 说明如何按语法制导翻译方法把一个中缀形式的简单算术表达式翻译成为后缀式 后缀式的语义动作规则语义动作 1 E E 1 T E CODE E 1 CODE T CODE 2 E T E CODE T CODE 3 T T 1 F T CODE T 1 CODE F CODE 4 T F T CODE F CODE 5 F E F CODE E CODE 6 F i F CODE i 几点说明 E CODE T CODE F CODE表示构成后缀式的符号串符号 表示两个串的 捻接 运算 即并置运算 显然 E 1 CODE T CODE 是E CODE 因为符号在后 其它类似 下面将上述语义动作具体化成语义子程序 自底向上分析要归约时先调用相应子程序生成后缀式假定后缀式存放在数组POST中假设要归约的句柄为E 1 T 在语法分析栈中 则首先要求调用相应于E 1 T的语义子程序 此时E 1 和T已调用过相应的语义子程序 因此 它们的后缀式已被生成 对应于E 1 T的语义子程序所要完成的工作是把已生成的两后缀式捻接起来 然后再添上符号 如果我们设置一个数组存放后缀式 那么语义动作就可以不涉及捻接运算 令这个数组为POST p为下标 初值为1 如下图 POST P 对于上述文法G E 的语义动作 可以改写为如下相应的语义子程序 1 E E 1 T POST p p p 1 2 E T 3 T T 1 F POST p p p 1 4 T F 5 F E 6 F i POST p i p p 1 最后 我们以表达式a b c为例按照P118 表4 15文法G E LR分析表给出语法制导翻译产生后缀式过程 其中SUBK表示第K个规则相对应的语义子程序 分析过程如下表 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言三 三元式表示1 三元式 1 定义三元式的一般形式为 i OP ARG1 ARG2 其中 i 为三元式的编号 不同三元式不能有相同的编号OP是运算符部分ARG1和ARG2是运算对象部分 它们或者指向符号表登记项指示器 对于运算对象是常数或标识符的情况 或者是一个指向三元式序列 或三元式表 中某一个三元式位置的指示器 对于运算对象是中间结果的情况 如 A B C对应的三元式表示为 1 B C 2 A 1 注 运算符OP通常用一个整数码表示 它除了标识运算符的种属之外 还附带地表示其它一些语义特性 例如若OP表示一个加法运算符 则相应的整数码除了标识加法运算本身外 还兼有表示数据类型 如整型 实型等 运算方式 定点 浮点 和运算精度等信息 且不同语义属性使用不同的运算符代码 对于一目运算符OP ARG1和ARG2只需其一 我们可以随意规定选用一个 例如 规定用ARG1 至于多目运算符可以用若干个相继三元式表示 如 赋值语句x b c d 用三元式来表示 则可写成 1 b 2 c d 3 1 2 4 x 3 其中 三元式 3 就引用三元式 1 和 2 的结果作为它的两个运算对象 三元式出现先后顺序和表达式各部分计算顺序相一致 2 三元式的生成同样可以用语法制导翻译来产生三元式 下面给出文法G E 的语义动作来描述这种翻译的算法 1 E E 1 T E VAL TRIP E 1 VAL T VAL 2 E T E VAL T VAL 3 T T 1 F T VAL TRIP T 1 VAL F VAL 4 T F T VAL F VAL 5 F E F VAL E VAL 6 F i F VAL ENTRY i 其中语义值E VAL T VAL和F VAL 是一个指示器 或指向有关符号表某一项 或指向三元式表自身某一项 TRIP OP ARG1 ARG2 是一个语义子程序 回送新产生的三元式存放在三元式表位置 ENTRY i 是一个语义子程序 通过ENTRY查i在符号表中位置 即对应地址 若查不到 认为有错误 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言三 三元式表示2 间接三元式为了便于代码优化 常常采用间接三元式 这由两张表组成 1 三元式表 用来存放各三元式本身 2 执行表 间接码表 它按执行三元式顺序 依次列出相应各三元式在三元式表中位置 例如 对于如下赋值语句 x a b c a b 若按三元式表示 可写成 按间接三元式表示 则可写成 执行表三元式表 1 1 a b 2 2 1 c 1 3 2 1 3 4 x 3 4 1 a b 2 1 c 3 a b 4 2 3 5 x 4 其中 三元式 1 和 3 完全一样 但是不能将 3 省去 间接三元式的优点 1 便于代码优化在进行代码优化时 常常要从中间代码删去一些运算 或者把某些运算移到另外位置上 若采用一般三元式 则由于三元式之间引用太多 很难做到这一点 2 节省空间由于在间接三元式执行表中已经依次列出每次要执行的那个三元式 所以 若有若干个相同三元式 则仅须在三元式表中保存其中之一 如上面赋值语句右部表达式中有两个a b子表达式 而三元式表中只出现一次 a b 对于间接三元式表示 语义子程序应增添产生执行表的动作 在填写三元式表时 应首先看一下此三元式是否在其中 如已在其中 则无需填入 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言四 树形表示1 表示方法我们可以用树形数据结构来表示一个表达式或语句 在树表示中 叶子结点表示运算对象 即常量或变量 其它结点表示运算符 如表达式 a b a b a 的树表示分别定义为 a b a b a 双目运算对应二叉树 多目运算对应多叉树 单目运算对应单叉树 如表达式a b c d e f 的二叉树如下图 后序遍历上述二叉树便得到该表达式的逆波兰表示为ab cd ef a b c d e f 表达式的三元式可以看作是树的直接表示 图5 7所对应的三元式为 1 a b 2 c d 3 e f 4 2 3 5 1 4 显然 每一个三元式对应一棵子树 子树的根便是三元式的运算符 三元式的运算对象是子树两个分枝 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言四 树形表示2 树表示生成对文G E 翻译成树形表示语义动作描述如下 1 E E 1 T E VAL NODE E 1 VAL T VAL 2 E T E VAL T VAL 3 T T 1 F T VAL NODE T 1 VAL F VAL 4 T F T VAL F VAL 5 F E F VAL E VAL 6 F i F VAL LEAF i 其中 语义值E VAL T VAL和F VAL是一个指示器 指向树一个结点 NODE OP LEFT RIGHT 是一个函数子程序 OP是一个二元运算符 LEFT RIGHT为指示器 每调用此函数一次 就建立一个新结点 其标记为OP LEFT和RIGHT分别指向左右子树根结点指针 从NODE回送的值是一个指示器 指向这棵新树的根 LEAF i 是建立一个末端结点 叶结点 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 第五章语法制导翻译及中间代码生成 5 2中间语言一 引言1 什么是中间语言2 为什么要引入中间语言二 逆波兰表示1 表达式逆波兰表示2 逆波兰表示的扩充3 语法制导翻译生成后缀式三 三元式1 三元式2 间接三元式四 树形表示1 表示方法2 树表示生成五 四元式 5 2中间语言五 四元式表示 四元式是一种用得比较多的一种中间语言代码形式 四元式一般形式是 OP ARG1 ARG2 RESULT 其中 OP是运算符 其含义与三元式中OP类似 ARG1和ARG2是运算对象 RESULT是运算结果 例如 赋值语句a b c d 用四元式表示 则可写成 1 b T1 2 c d T2 3 T1 T2 T3 4 T3 a 四元式之间联系是通过临时变量实现的 调整四元式之间相对位置并不意味着一定要改变一系列指示器值 因此 对中间代码进行优化处理时 四元式比三元式方便得多 下面主要讨论如何用四元式表示各种语句 并产生四元式语义子程序 第五章语法制导翻译及中间代码生成 本节内容 5 3自底向上语法制导翻译一 简单算术表达式和赋值语句的翻译二 布尔表达式的翻译三 控制语句翻译四 数组元素的翻译五 过程语句的翻译六 说明语句的翻译 5 4自顶向下语法制导翻译一 递归下降的语法制导翻译二 LL 1 语法制导翻译 5 5属性文法与属性翻译一 属性文法与L属性文法二 属性翻译 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 5 3自底向上语法制导翻译一 简单算术表达式和赋值语句的翻译1 翻译成四元式我们首先讨论仅含有简单变量的表达式和赋值语句到四元式的翻译 对于复杂的表达式和赋值语句的翻译将在以后讨论 为简便起见 假定赋值语句中所含的全部变量是同一类型整型变量 此外在翻译过程中也不作语义检查 1 赋值语句的文法1 A V E5 T F2 E E 1 T6 F E 3 E T7 F i4 T T 1 F8 V i为了实现到四元式的翻译 需要引进一系列语义变量和语义子程序 2 语义变量和语义子程序 NEWTEMP是一个函数 每次调用时 都定义一个新临时变量 回送一个代表新临时变量名的整数码作为函数值 为直观起见 我们将NEWTEMP产生的临时变量依次记为T 等等 ENTRY i 是一个函数过程 查找符号名i在表中的入口地址 X PLACE是和非终结符X相联系的语义变量 表示存放X值的变量名在符号表的入口或整数码 若此变量是一个临时变量 如 F i F PLACE ENTRY i 表示存放F值变量名i在符号表中的入口地址 即从变量F PLACE值可知i在符号表中的位置 GEN OP ARG1 ARG2 RESULT 是一个语义过程 该过程把四元式 OP ARG1 ARG2 RESULT 填入四元式表中 因此 上面定义文法G A 语义子程序的描述如下 3 语义子程序的描述 1 A V E GEN E PLACE V PLACE 2 E E 1 T E PLACE NEWTEMP GEN E 1 PLACE T PLACE E PLACE 3 E T E PLACE T PLACE 4 T T 1 F T PLACE NEWTEMP GEN T 1 PLACE F PLACE T PLACE 5 T F T PLACE F PLACE 6 F E F PLACE E PLACE 7 F i F PLACE ENTRY i 8 V i V PLACE ENTRY i 在进行自底向上语法制导翻译时 还需一张LR分析表 上述文法G A 是一个SLR 1 文法 其分析表如下 4 文法G A SLR 1 分析表 5 对x a b c语法制导翻译产生四元式过程 以赋值语句x a b c为例 分析表几点说明 在分析表中Vx Ea Tb Fc之类记号 表示与非终结符V E T F相关联的V PLACE E PLACE T PLACE F PLACE中存放着ENTRY x ENTRY a ENTRY b ENTRY c 符号指针 指向符号表 在四元式中 如 b c T1 实际上是某种整数编码 反映运算符本身及其信息特征 如类型等 b c实际上也是指示器 指示符号表入口 T1是临时变量 实际上也是整数码 下面我们根据上面分析表叙述对x a b c语法制导翻译产生四元式过程 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 5 3自底向上语法制导翻译一 简单算术表达式和赋值语句的翻译2 类型检查与类型转换 1 目的1 类型检查是编译程序语义检查不可缺少的一部分 类型检查就是对访问数据的操作和被访问数据的类型进行检查检查操作的合法性和数据类型的相容性 例如 在PASCAL语言中 若算术运算符的操作数为布尔量 或者赋给实型变量值是个指针 则编译程序报告 类型不相容 的诊断信息 2 允许类型混合 但在处理时要统一 所以必须进行类型转换 例如 加法运算 允许运算对象是整型数或实型数 如果一个运算对象是实型 另一个运算对象是整型 其运算结果的类型是实型 由于实型数和整型数的内部表示不相同 因此为了使整型数能参加实型数运算 必须事先将整型数转换成实型数 2 类型检查类型检查可在生成中间代码时进行 也可在生成目标代码时进行 但最好是在生成中间代码时进行 因为语法和语义检查最好尽早进行 这样能尽早避免徒劳的工作 在上面对简单算术表达式和赋值语句翻译到四元式的讨论中 我们假定各个变量是同一类型整型变量 并且规定在四元式的op代码中 本身就会有类型信息 所以 在上例各语义子程序中 我们并未考虑有关类型方面语义处理 3 类型转换方法为了简单起见 我们仅考虑整型和实型的情况 这种混合运算中 给每个非终结符的语义值增添类型信息X MODEX MODE的值或为r 实型 或为int 整型 原来X的信息除X PLACE 还有X MODE 对表达式的每一规则的语义子程序进行修改 增加关于类型信息的语义规则 必要时应产生对运算量进行类型转换的四元式 itr A T 把整型变量A转换成实型变量 结果存在T中 此外 在书写语义子程序时 为阅读上的直观性 我们用 i i等表示整型运算符 用 r r等表示实型运算符 现以规则E E 1 OPE 2 为例 给出语义子程序的具体描述如下 现以规则E E 1 OPE 2 为例 给出语义子程序的具体描述如下 T NEWTEMP IFE 1 MODE intANDE 2 MODE intTHEN BEGINGEN opi E 1 PLACE E 2 PLACE T E MODE int END ELSEIFE 1 MODE rANDE 2 MODE rTHEN BEGINGEN opr E 1 PLACE E 2 PLACE T E MODE r END ELSEIFE 1 MODE int andE 2 MODE r THEN BEGINU NEWTEMP GEN itr E 1 PLACE U GEN opr U E 2 PLACE T E MODE r END ELSE E 1 MODE randE 2 MODE int BEGINU NEWTEMP GEN itr E 2 PLACE U GEN opr E 1 PLACE U T E MODE r END E PLACE T 这样 对于输入串为 X 2 A I 1 其中I为整型量 X A为实型量 则产生四元式序列为 itr 2 T1 r X T T i I 1 T3 itr T3 T r A T4 T5 r T2 T5 T6 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 5 3自底向上语法制导翻译二 布尔表达式的翻译1 概述布尔表达式由布尔运算符 与 或 和 非 等作用于布尔量或关系表达式构成 关系表达式的形式是E1ropE2 其中rop是关系运算符 如 及 而E1和E2是算术表达式 1 布尔表达式的用途在程序设计语言中 布尔表达式有两个基本用途 1 一个是求逻辑值 逻辑值的结果是真或假 2 另一个用得最多的是在控制语句中用作条件表达式 例如 在if then if then else和while do语句里表示控制条件 2 布尔表达式的文法布尔表达式文法G E 如下 E E E E E E E i iropi说明 1 布尔表达式的文法是一个二义文法例如 该文法的一个句子a b c有两棵不同的语法树与之对应 所以该文法是一个二义文法 E E E E E a b c E E E a E E b c 2 规定布尔运算符的优先顺序是 并假定 和 为左结合 所有关系运算符优先级相同 且高于任何布尔运算符 低于算术运算符 3 i可认为是布尔表达式也可视为数值 1为真true 0为假false 4 iropi中rop是关系运算符 i是布尔变量或算术值 3 布尔表达式求值方法1 把真和假数值化 使布尔表达式计算类似于算术表达式的计算 常用1表示真 0表示假 或者用非零整数表示真 如 1 0 0 0 1 1 0 0 1 0 0 12 采取某种优化措施 有时并不需要将一个布尔表达式从头算到尾 而只须计算它的一个子表达式 便能确定整个布尔表达式真和假 例如 对于A B 只要计算出A为真 则不管B值如何 A B之值一定为真 又如对A B 只要计算出A为假 则A B必然为假 等等 对于三种逻辑运算 可作如下等价的解释 A B ifAthentrueelseB A B ifAthenBelsefalse A ifAthenfalseelsetrue 用这种方式实现控制语句的布尔表达式尤其方便 对应上述两种计算方法 其布尔表达式有两种不同的翻译方法 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一 简单算术表达式和赋值语句的翻译1 翻译成四元式2 类型检查与类型转换二 布尔表达式的翻译1 概述2 布尔表达式的翻译方法3 翻译成四元式的实现三 控制语句翻译1 语句标号和goto语句的翻译2 条件语句的翻译3 布尔表达式的翻译方法4 while循环语句翻译5 for循环语句的翻译 四 数组元素的翻译1 下标变量地址的计算2 数组元素的翻译五 过程语句的翻译1 参数传递方式2 过程语句的翻译六 说明语句的翻译1 变量说明的翻译2 数组说明的翻译3 过程说明的翻译 5 3自底向上语法制导翻译二 布尔表达式的翻译2 布尔表达式的翻译方法 1 如同翻译算术表达式一样 用于求值例如 布尔表达式 a b c d 将被翻译成如下四元式 1 a T1 2 c d T2 3 b T2 T3 4 T1 T3 T4 仿照翻译算术表达式的方法 很容易写出布尔表达式文法G E 的每个规则用于求值的语义动作 1 E E 1 E 2 E PLACE NEWTEMP GEN E 1 PLACE E 2 PLACE E PLACE 2 E E 1 E 2 E PLACE NEWTEMP GEN E 1 PLACE E 2 PLACE E PLACE 3 E E 1 E PLACE NEWTEMP GEN E 1 PLACE E PLACE 4 E E 1 E PLACE E 1 PLACE 5 E i E PLACE ENTRY i 6 E iropi E PLACE NEWTEMP GEN rop ENTRY i 1 ENTRY i 2 E PLACE 2 作为条件控制的布尔表达式的翻译1 布尔表达式E作为条件控制的代码结构对于条件语句ifEthenS1elseS2中布尔表达式E 它的作用就是控制S1和S2的选择 我们赋于E代码两种出口 其一为 真出口 另一个是 假出口 它们分别指出当E值为true和false时 控制转向的目标 即某一四元式所在位置或序号 条件语句可翻译成如下图 E的代码 S1的代码 true false S2的代码 2 三种形式的四元式作为条件控制的布尔表达式E的翻译归纳起来只有三种形式的四元式 jnz a1 p 若a1为真时 则转向第p个四元式 jrop a1 a2 p 若关系a1ropa2成立时 转向第p个四元式 j p 无条件转向第p个四元式 除上述两种真转外 可用无条件表示假转 例如 对于条件语句 ifa b cthenS1elseS2经翻译后 可得如下四元式序列 1 jnz a 5 2 j 3 3 j b c 5 4 j p 1 5 关于S1的四元式序列 P j q p 1 关于S2的四元式序列 q 1 a为真 a b c就为真 转5执行 2 a为假 a b c的值取决于b c的值 所以转3执行 3 a为假 且b c 则a b c为真 转5执行 4 a为假 且b c也是假 则a b c为假 执行S2语句 即应转p 1执行 p 执行完S1 对应四元式为 5 则应转到条件语句的下一条语句执行 所以无条件跳转到 q 执行 四元式 1 4 中显然含有多余的四元式 如 2 显然是不需要 第五章语法制导翻译及中间代码生成 5 3自底向上语法制导翻译 一