《编译原理课程教案》第5章：中间代码生成.ppt

语义分析和中间代码生成 第五章 本章要求 主要内容 语义分析和中间代码的功能 中间代码的形式 属性文法及语法制导的翻译程序 各种语句的语法制导的翻译过程重点掌握 属性文法 语义分析与处理的方法 中间代码的表示形式 各种语句的代码结构 各种语句的翻译方法 语义分析和中间代码生成所处的位置 5 1概述 语义分析和中间代码生成在编译器中的位置 静态语义检查 如 类型 运算 数组维数 越界等的检查语义处理 如 变量的存储分配 表达式的求值 语句的翻译 中间代码的生成 总目标 生成等价的中间代码 功能及任务 P166 输入 语法分析单位 输出 用中间代码形式表示的文本 出错处理 定位 继续编译 3 为什么要此阶段 逻辑结构清楚 利于不同目标机上实现同一种语言 利于进行与机器无关的优化 这些内部形式也能用于解释 4 什么是中间代码 Intermediatecode 源程序的一种内部表示 不依赖目标机的结构 易于机械生成目标代码的中间表示 5 中间代码的几种形式逆波兰 三元式 间接三元式 四元式 树 1 逆波兰式 运算对象写在前 运算符写在后 后缀表示形式 例 a b ab a b c ab c a b c abc a b c b d abc bd 5 2中间代码的几种形式 优点 易于计算机处理利用栈 将扫描到的运算对象入栈 碰到运算符 若是双目运算符 则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈 若是单目运算符 对栈顶元素 执行该运算 将运算结果代替该元素进栈 最后结果即栈顶元素 练习 写出下列算式的逆波兰表示a b c d e a b c b 34 notAornot CornotD abcde abc b34 AnotCDnotornotor 后缀式的推广 1 赋值语句A E 后缀式为 AE 2 转向语句GOTOL的后缀式为 L jmp 3 条件语句ifx ythenm xelsem y 2 三元式编号 运算符 第一运算数 第二运算数 如 a b c b d 1 b c 2 b d 3 1 2 4 3 a 对于单目运算符 只有一个运算对象 另一个为空注意 在三元式中的编号既代表了序号 又代表了结果的存放位置 3 四元式P172是目前最常用的中间代码形式 运算符 第一运算数 第二运算数 结果 例 a b c b d 1 b c t1 2 b d t2 3 t1 t2 t3 4 t3 a 也可以写成赋值语句形式 1 t1 b c 2 t2 b d 3 t3 t1 t2 4 a t3 练习 求 B C D的逆波兰表示形式 三元式和四元式 到目前为止 已知输入的语法单位 又知道要翻译的结果的形式 翻译的方法是什么 语义分析和翻译的方法 语义表示较流行的方法仍然是属性文法 翻译方法是语法制导的翻译 属性文法 属性文法 是在上下文无关文法的基础上 为每个文法符号 含终结符和非终结符 配备若干个属性值 对文法的每个产生式都配备了一组属性计算规则 称为语义规则 在语法分析过程中 完成语义规则所描述的动作 从而实现语义处理 属性 代表与文法符号相关的信息 如类型 值 代码序列 符号表的内容等 与变量一样 可以进行计算和传递 属性的加工过程就是语义的处理过程 属性分两类 综合属性 用于自下而上传递信息继承属性 用于自上而下传递信息注意 终结符只有综合属性 它由词法分析器提供 非终结符可有综合属性 也可有继承属性 它由词法分析器提供 文法的开始符号的所有继承属性作为属性计算前的初始值 产生式右边的文法符号的继承属性可以继承左边的文法符号的继承属性产生式左边的文法符号可以通过综合右边的文法符号的综合属性而得到但必须提供一个计算规则 计算规则中只能使用相应产生式中的文法符号的属性 实际应用中 一个结点的综合属性的值由其子结点的综合属性值决定 产生式右边 一个结点的继承属性由此结点的父结点和 或兄结点的某些属性决定 产生式左边 但产生式左边的继承属性和右边的综合属性不由所给的产生式的属性计算规则进行计算 它们由其它产生式的属性计算规则提供 digit lexval 3 F val 3 T val 3 F val 5 T val 15 E val 15 digit lexval 4 F val 4 T val 4 E val 19 L n digit lexval 5 若输入符号串为 3 5 4n 例 综合属性的计算 C语言中变量定义 intid1 id2 id3 综合属性的传递 继承属性的传递 例 继承属性的计算 语法制导的翻译方法 基于属性文法的处理过程通常是 对单词符号串进行语法分析 构造语法树 根据需要遍历语法树 在语法树的各结点处按语义规则进行计算 语义规则描述的工作 属性计算 静态语义检查 符号表的操作 代码生成等 通常写成过程和函数调用 称为语义子程序 语法制导翻译的基本思想 在语法分析过程中 根据语言的语义定义 随时翻译已识别的那部分语法成分的全部含义 语法制导的翻译方法 如果遍历语法树的操作和建立语法树的操作同时进行 称为语法制导的翻译方法 语法制导翻译的两种方法 1 在自下而上的语法分析中 使用和语法分析栈同步操作的语义栈进行语法制导翻译 2 在自上而下的语法分析中 如递归下降分析 利用隐含的堆栈存储各递归子程序中的局部变量所表示的语义信息 自下而上分析的语法制导翻译 语法分析是自下而上的情况时 语义计算的时机是 在用某一产生式进行规约的同时 执行相应的语义动作 在分析完一个句子时 这个句子的 值 也就同时产生了 例 属性文法如下 输入串为 3 5 4 其语法树如下图 E E1 T T T F F 3 5 F 4 在第一步规约时使用产生式6 执行的语义动作是将F val的值置为单词digit的值3 把语法树中每个结点得语义值写在结点后的括号中 则第一步完成规约后的情形如右图所示 E1 T T T F F 3 5 F 4 E 第一步规约 继续进行分析 逐步向上规约 得到下图所示的情形 最后用EE1 T规约到E时 它的值19就计算出来了 E1 15 T 4 E 在自下而上的LR语法分析过程中 首先把它的分析栈进行扩充 使得每个文法符号都带有语义值 修改后栈的结构如下图所示 同时把LR分析器的能力扩大 使它不仅执行语法分析任务 且能在用某个产生式进行规约的同时进行相应的语义处理 完成属性文法中定义的语义动作 每步工作后的语义值保存在扩充的语义栈中 例 在3 5 4的LR分析过程中增加了语义栈后的语法制导的实现过程 LR分析表 文法 启示 在刚才的翻译过程中有如下特点 句柄归约在先 语义动作在后 归约时 栈内句柄各符号的语义信息与该句柄同时出栈 整个句柄所表示的语义信息则赋给相应产生式左部非终结符的语义变量 并让该非终结符及其语义变量同时入栈 为了在某处调用语义动作 就必须先归约 因此 有时需要改写文法 常见语句的语法制导翻译 高级语言的两大类语句 说明语句 用于定义各种形式的有名实体及其属性 如常量 变量 数组 记录 结构 过程 子程序等 可执行语句 用于完成程序指定的功能 语义处理也按两大类处理 1 说明语句的处理 把说明语句中定义的名字和属性登记在符号表中 用以检查名字的引用和说明是否一致 以便在翻译可执行语句时使用 一般说明语句的语义处理不生成目标代码 过程说明和动态数组的说明有相应的代码 2 可执行语句 首先根据各源语句的语法结构和语义设计它的目标代码结构 找出源与目标的对应关系 然后根据语义规则进行翻译 生成四元式序列 语义翻译过程中涉及的数据结构 语义翻译过程中涉及的数据结构有符号表 四元式表和临时变量区 符号表 语义翻译过程中 在产生四元式时 通常不使用变量的名字 而是使用它们在符号表中的入口位置 一般用ENTRY i 表示变量i在符号表中的入口 因此语义子程序需要查阅符号表 而在翻译说明语句时需要填写符号表中的相关项 四元式表 四元式表是按翻译过程中四元式产生的顺序组成的 通常设置一个专门的过程GENCODE OP ARG1 ARG2 Ti 来产生一个四元式 将该四元式输出到四元式列表中 并使四元式的编号加1 临时变量区 用于存放翻译过程中建立的临时语义变量 假设过程newt用来生成临时变量 每调用一次 生成一个新的临时变量 第一次调用生成的是T1 第二次调用生成T2 说明语句的翻译 说明语句的作用 就是说明类型等属性信息 在翻译时主要是填符号表说明语句分多种 此处举例两种的翻译 变量说明语句的翻译常量说明语句的翻译 变量说明语句的翻译 变量说明语句的文法描述 变量说明语句的翻译 例如 vara b c integer 策略 先翻译第 产生式 再翻译 产生式 以便记录的类型 即在写程序时 读完一个说明语句 开始归约 再开始翻译 变量的类型朝前传递 翻译的语义动作 符号表 FILL entry i Type 表示将类型Type填入符号表中 entry i 表示变量名i在符号表中的入口 VARid1 id2 id3 integer 的归约过程 常量说明语句的翻译 常量说明语句的文法描述 常量说明语句的翻译 策略 和变量说明一样 先翻译后面的产生式 再翻译前面的产生式 以便在归约时 执行语义动作 将常量的值 类型 种属填入符号表 例 ConstantA 123 翻译的语义动作 将常量INT在符号表中的入口或值直接填入常量符号i所指符号表的VAL栏 将常数的类型填入符号表的Type栏 3 4产生式的翻译与5 6产生式的翻译相同1 2产生式没有语义动作 将常数的种属填入符号表的Kind栏 可执行语句的翻译 定义的一些语义变量和过程GENCODE OP ARG1 ARG2 RESULT 语义过程 产生一个四元式 并填入四元式表 编号自动增1 NEWT 函数 返回一个临时变量序号 在翻译可执行语句的过程中 可能需要使用临时变量 假定用NEWT过程来申请临时变量Ti 每申请一次 i增1 ENTRY i 函数 查找变量i的入口地址 检查id name是否在符号表中 如在则返回一指向该登陆项的指针 否则返回NULLE PLACE 与给终结符E相联系的语义变量 可能是某变量的入口地址 或者为临时变量序号 简单赋值语句的翻译 简单赋值语句的文法描述 2 简单赋值语句的代码结构 例如 x 2 3 2 3 简单赋值语句的翻译此处只假定是整数运算 例 赋值句A B C D 的自底向上分析 因此 四元式表中增加了4条四元式 简单算术表达式和赋值语句的翻译 1 S id E p lookup id name ifp nilthenemit p E place elseerror 2 E E1 E2 E place newtemp emit E place E1 place E2 place 3 E E1 E2 E place newtemp emit E place E1 place E2 place 4 E E1 E place newtemp emit E place uminus E1 place 5 E E1 E place E1 place 6 E id p lookup id name ifp nilthenE place pelseerror 张素琴编 编译原理 清华大学版 布尔表达式的翻译 1 布尔表达式的基本概念布尔表达式是将布尔运算符 and or not 作用到布尔变量或关系表达式上组成的表达式 关系表达式形如E1ropE2 其中E1和E2是算术表达式 rop表示关系运算符 或 Sample语言规定布尔运算符的优先级从高到低为not and or and和or都是左结合 2 布尔表达式的两个基本作用用作布尔赋值语句中的布尔运算 用作控制语句如if then if then else while do等之中的条件表达式 其作用是选择下一个执行点 3 布尔表达式的文法描述 例如 x notaand y z 是符合上述文法的布尔表达式 计算布尔表达式的值有两种方法 一种是像计算算术表达式那样 对布尔表达式中的每个因子都计算其布尔值 最后求得整个表达式的布尔值 另一种计算方法是根据布尔运算的特殊性采取某些优化措施 只计算部分表达式 例如要计算AorB 若计算出A的值为1 那么B的值就无需再计算了 因为不管B的值为何结果 AorB的值都为1 如同计算算术表达式一样 步步计算出各部分的真假值 最后计算出整个表达式的值 例如 用数值1表示true 用0表示false 那么布尔表达式1or not0and0 or0的计算过程是 1or not0and0 or0 1or 1and0 or0 1or0or0 1or0 1 4 用于布尔赋值语句中布尔表达式的翻译 使用这种翻译方法 可以参照算术表达式的赋值语句文法的语义动作 为布尔表达式文法配上合适的语义动作 张素琴编 编译原理 清华大学版 给出的方案如下 1 E E1orE2 E place newtemp emit E place E1 place or E2 place 2 E E1andE2 E place newtemp emit E place E1 place and E2 place 3 E notE1 E place newtemp emit E place not E1 place 4 E E1 E place E1 place 5 E id1ropid2 E place newtemp emit if id1 place rop id2 place goto nextstat 3 emit E place 0 emit goto nextstat 2 emit E place 1 6 E true E place newtemp emit E place 1 7 E false E place newtemp emit E place 0 布尔量的代码结构每个布尔量 布尔变量或关系表达式 的目标结构有两个出口 真出口指向布尔量为真时应跳转的位置 假出口指向布尔量为假时应跳转的位置 5 控制语句中布尔表达式的翻译 布尔量翻译为两条四元式 jnz A P 真出口 当A为真时跳转到四元式P j Q 假出口 无条件跳转到四元式Q 转移四元式的第4个分量表示转移去向 即P Q为某个四元式的编号 关系表达式也翻译为两条四元式 jrop i1 i2 P 真出口 当i1ropi2为真时转四元式P j Q 假出口 无条件跳转到四元式Q 问题 在翻译布尔表达式时 后面的语句未翻译 P Q如何知道 解决方法 回填技术在由多个因子组成的布尔表达式中 可能有多个因子的真出口或假出口的转移去向相同 但又不知道具体转向位置 在这种情况下 需要把这些转移方向相同的出口链在一起 形成真 假出口链 以便后续知道转移地址后再回填 对于给定的控制语句中的布尔表达式 翻译方法如下 若已知转移地址就直接填入 若不知道 时先填0 等知道后再返填 如果多个因子的转移去向相同 但又不知道具体位置 应该用链将这些未知且出口相同的四元式链在一起 例 写出布尔表达式 AandBandC D的四元式序列 当扫描到A后的and时 对A进行规约 产生两个四元式 1 和 2 四元式 1 的第4分量表示真出口 由于A为真时应计算B 因此A的真出口的值为3 即A为真时转向3 四元式 2 的第4个分量表示假出口 目前其值未知 先填入0 当扫描到B后的and时 对B进行规约 产生四元式 3 4 四元式 3 的第4分量表示真出口 由于B为真时应计算C D 因此B的真出口的值为5 即B为真时转向5 四元式 4 的第4个分量表示假出口 目前其值未知 但可以知道它与A的假出口相同 因此需将它与四元式 2 链接起来 即将 4 的第4个分量填入2 当扫描到最后 对关系表达式C D进行规约 产生两个四元式 5 6 此时 5 的第4个分量表示真出口 其值未知 即暂时不知道C D时转向哪里 填入0 6 的第4个分量表示假出口 其值未知 但它与A和B的假出口相同 因此需将它与四元式 4 链接起来 即将 6 的第4个分量填入4 假出口未知 填入0 当扫描到and时 对A进行归约 产生两个四元式1 2 其中真出口已知 为3 当扫描到B后的and时 对B进行归约 又产生两个四元式3 4 其中真出口已知 为5 假出口仍未知 但它与A的假出口相同 则链接起来 填2 当扫描到最后 对C D进行归约 又产生两个四元式5 6 此时真出口未知 填0 假出口仍未知 但它与上两个布尔量的假出口相同 则链接起来 填4 生成了真 假出口两个链 其中 1 3 5 形成一条真出口链 6 4 2 形成一条假出口链 每个链尾的四元式的第4个分量都为0 为结束标记 同时也是待填部分 等到以后翻译到后面再填入 一旦出现具体的转向目标 即把转向的目标四元式编号回填到链上对应四元式的第4个分量处 最后的四元式列表如下 控制语句中布尔表达式的语义处理 Sample语言中 在为布尔表达式设计语义动作时 提供了以下语义变量和语义过程 1 为每个非终结符X设置两个出口 真出口X TC和假出口X FC 它们同时分别表示真 假出口链的链首 例 对于E1orT的目标代码结构 只要E1为真 后面的表达式就不必计算 就知道E1orT为真 只有当E1为假 才读取T E1orT的值由T值决定 目标结构如下图 a 所示 对于E1andT的目标代码结构 只要E1为假 后面的表达式就不必计算 就知道E1andT为假 只有当E1为真 才读取T E1andT的值由T值决定 目标结构如下图 b 所示 2 变量NXQ 指代下一个即将形成的四元式编号 NXQ的初值为1 每执行一次GENCODE过程 产生一条新的四元式 NXQ就自动加1 3 函数MERG P1 P2 将P1 P2为链首两个真出口链或假出口链合并在一起 返回合并后的链首 MERG P1 P2 if P2 0 return P1 else P P2 while 四元式P的第4分量内容不为0 P 四元式P的第4分量内容 把P1填进四元式P的第4分量 return P2 4 函数BACKPATCH P t 把以P为链首的真出口链或假出口链中每个四元式的第4分量都改写为已知地址t 回填 BACKPATCH P t Q P while Q 0 do m 四元式Q的第4分量内容 把t填进四元式Q的第4分量 Q m 布尔表达式文法的改造 为语义翻译服务 分析E1orT和E1andT的目标代码结构 从上图 a 可以看出 E1的假出口应转向布尔表达式T的第一个四元式的位置 由于语法分析程序分析到运算符or时才能知道E1已分析完毕 开始生成T的四元式 这样 当分析程序扫描到or时 应执行一个语义动作 把下一个四元式的编号 即T的入口 回填给E1的假出口 为此 产生式 or应改造为 or or or这样 当用产生式or or进行规约时 就能立即执行回填动作 及时把的第一个四元式的编号回填给的假出口链 类似的产生式 and也应改造为下面两个产生式 and and and这样 当用产生式and and进行规约时 就能及时把的第一个四元式的编号回填给的真出口链 布尔表达式的文法改造方案 改造后的文法 改造前的文法 布尔表达式文法的语义翻译方案 NXQ表示当前产生的四元式的编号 单个的布尔量 关系运算 Not逻辑运算 带算术运算的关系运算 产生式6 3 的翻译与7相似 都是将右边的真假出口直接赋值到左边 5 4 构成and逻辑运算 2 1 构成or逻辑运算 控制语句的翻译 控制语句包括 if语句While语句Repeat语句For语句 IF语句的翻译 1 IF语句的文法 S是开始符号 产生式 1 4 生成无else的IF语句结构产生式 1 2 3 生成if then else的语句结构 1 S CS 1 2 C ifEthen 3 S TS 2 4 T CS 1 else 2 IF语句的目标结构及其翻译无else的结构 C Chain的作用 由于在用第一个产生式进行归约时 只生成了条件式E的代码 then时可以回填E TC E FC必须向后传递到下一各产生式中 ifa bthenx 3 2 IF语句的目标结构及其翻译有else的结构 ifa bthenx 3elsex 5 例 将下面的IF语句翻译为四元式序列 ifAandBand C D thenifA BthenF 1elseF 0elseG G 1 1 jnz A 3 A的四元式 2 j 13 3 jnz B 5 B的四元式 4 j 13 5 j C D 7 C D的四元式 6 j 13 7 j A B 9 A B的四元式 8 j 11 9 1 F F 1的四元式 10 j 15 11 0 F F 0的四元式 12 j 15 13 G 1 T G G 1的四元式 14 T G 15 练习 将下面的语句翻译为四元式序列 if A C and B D thenifA 1thenC C 1elseifA DthenA A 2 1 j A C 3 2 j 14 3 j B D 5 4 j 14 5 j A 1 7 6 j 10 7 C 1 T1 8 T C 9 j 14 10 j A D 12 11 j 14 12 A 2 T2 13 T2 A 14 REPEAT语句的翻译 1 文法描述 2 目标结构 例 repeatx x 1untilx 10 3 翻译 将下面的语句翻译为四元式序列 Ifw 1thena b c delserepeata a 1untila 0 1 j w 1 3 2 j 7 3 b c t1 4 t1 d t2 5 t2 a 6 j 11 7 a 1 t3 8 t3 a 9 j a 0 11 10 j 7 FOR语句的翻译 1 文法描述 2 目标结构 例 fori 1toa bdox x I FOR语句的翻译 fori 1toa bdox x I 将下面的语句翻译为四元式序列 fori a b 2toc d 10doifh gthenp p 1 自顶向下的语法制导翻译 优点 不需要改造文法在需要的任何位置调用语义动作自顶向下的语法分析有两种 递归下降分析LL 1 分析 递归下降的语法制导翻译 例 对如下文法进行递归下降的分析 并增加语义 只包含两个语句 赋值句和REPEAT语句 需要翻译布尔表达式 主程序 增加的语义部分 增加的语义部分 用C语言实现repeat int repeats repeat语句的语法制导的翻译过程 r head nxq 记录repeat语句开头的四元式编号 token getnexttoken 读取下一个token字 s1 chain st sort token 处理repeat后的语句 token getnexttoken if strcmp token 读到 token getnexttoken if strcmp token until error 缺少until 应为until backpatch 返回真出口 即repeat语句的下一个语句的四元式编号