编译原理4语义3控制语句的翻译.ppt
第 11 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第四章 语义分析和中间代码生成,4.1 语义分析概述 4.2 属性文法 4.3 几种常见的中间语言 4.4 表达式及赋值语句的翻译 4.5 控制语句的翻译 4.6 数组元素的翻译 4.7 过程或函数调用语句的翻译 4.8 说明语句的翻译 4.9 递归下降语法制导翻译方法简介,第四章语义分析和中间代码生成 4.5 控制语句的翻译 条件语句if 条件循环语句while 多分支控制语句case(自学) 转移语句goto 重点掌握 通过代码结构图翻译if、while语句(重点),本讲目标,4.5 控制语句的翻译,4.5 程序流程控制的三种基本结构 顺序结构：一般用复合语句实现； 选择结构：if-else if-else, switch-case; 循环结构：for，while, do-while,4.5 控制语句的翻译,图4-11 if(E)S的代码结构,图4-10 条件语句if(E)S1;else S2的代码结构,4.5 控制语句的翻译,为了在扫描条件语句过程中不失时机地处理和回填有关信息，可将GS改写为如下的G'S ： G'S: (1) SCS(1) (2) Cif(E) (3) STPS(2) (4) TPCS(1);else,4.5 控制语句的翻译,(1)无论是哪种if语句，首先用产生式(2) Cif(E)进行归约，这时E的真出口即为S(1)的第一个四元式；E的假出口地址则作为待填信息放在C的语义变量C.chain中等待回填； 所以：,4.5 控制语句的翻译,Cif(E) Backpatch(E.tc, nxq); C.chain = E.fc; ,(1) SCS(1) (2) Cif(E),扫描到“)”，立即回填E的真出口,C.chain中只保存E的待填假出口,(2)不含else时，用(1) SCS(1)进行规约，E的假出口是S(1)的出口，将C.chain和S(1).chain一起作为S的待填信息链用函数merge链在一起保留在S的语义值S.chain中：,4.5 控制语句的翻译,(1) SCS(1) (2) Cif(E),SCS(1) S.chain = merge(C.chain,S(1).chain),C S(1),规约后：,S(1).chain,(3)用产生式(2) Cif(E)进行归约之后，如果：条件语句后有else，用(4)继续规约。,4.5 控制语句的翻译,(2) Cif(E) (3) STPS(2) (4) TPCS(1);else,TP CS(1); else q=nxq; emit(j,_,_,0); Backpatch(C.chain,nxq); TP.chain = merge(S(1) .chain, q); ,注意1：只要遇到有else的规约，必须先产生一条无条件转移。,if ( E ) S(1) ;else S(2),C S(1) ;else S(2),TP S(2),2： S(2) 就是C.chain,3：q就是S(1) .chain,(4)最后用产生式(3) STPS(2)进行归约， S(2)语句序列处理完后继续翻译if语句之后的后继语句。后继语句的四元式地址与S(2)语句序列的出口一致，故将TP.chain与S(2).chain链接后挂入链头为S.chain的链中，即：,4.5 控制语句的翻译,(2) Cif(E) (3) STPS(2) (4) TPCS(1);else,STPS(2) S.chain = merge(TP.chain, S(2).chain);,课堂练习：将下列语句翻译成四元式（重点）,4.5 控制语句的翻译,（课本P120 例4.5）,if (xy) if(a b) m=m+1;else m=m-1;else x=y;,解答：解题技巧：不需要根据语义子程序，只需要画出 代码结构图，根据转换关系来翻译四元式：,if (xy) if(a b) m=m+1;else m=m-1;else x=y;,一个布尔分量对应 个四元式； else对应 个无条件跳转四元式； 注意真假出口的预留与回填。,2,1,4.5 控制语句的翻译,4.5.2 条件循环语句while的翻译 1.循环语句的代码结构图：while (E) S(1),图4-12 条件循环语句while的代码结构,1：E的真出口是S(1),2：E的假出口是循环体外,3：S(1)的后面无条件转移，重新判断E,4.5 控制语句的翻译,2.翻译思想：S while (E) S(1) (1)翻译E代码段，并留两个待填的E.tc和E.fc; (2) 扫描过“)”之后，就可回填E.tc; (3) 翻译S(1) ，然后无条件转移到E的第一条四元式； 因此： 1. 为了保证(3)的无条件转移，必须保存E的第一条四元式序号； 2. E为假时，需要回填，需要用S.chain保存E.fc;,4.5 控制语句的翻译,3. 给出易于及时处理和回填的条件循环语句while的文法GS如下： GS: (1) SWdS(1) (2) WdW(E) (3) Wwhile 语义子程序 例：while(ab) S(1) (1) 使用(3) Wwhile进行规约。保存条件的开始位置，也就是无条件语句转移的位置。,Wwhile W.quad=nxq; ,4.5 控制语句的翻译,例：while(ab) S(1) (2)使用(2) WdW(E)进行规约。 由于E的真出口已经确定为nxq，回填E.tc; E.fc无法确定，Wd.chain用于保存待填信息，以备回填； 的首入口(W.quad)用Wd.quad保存，以备强制转移。,WdW(E) Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad= W.quad; ,4.5 控制语句的翻译,例：while(ab) S(1) (3)使用(1) SWdS(1)进行规约。 如果S(1)也是if-else语句，S(1).chain表示S(1)后续的四元式序列，但不是while循环体外的四元式。这时的跳转一定是再回到E条件，因此需要回填S(1).chain对应的四元式串； 产生无条件跳转四元式，回到E条件，进行循环； 整个while语句的出口，是Wd 的出口，也就是E.fc。,SWd S(1) Backpatch (S(1).chain,Wd.quad); emit(j,_,_,Wd.quad); S.chain= Wd .chain; ,课堂练习：将下列语句翻译成四元式（重点）,4.5 控制语句的翻译,（课本P121 例4.6）,while(AB) if (CD) X = Y+Z;,解答：只需要画出代码结构图，根据转换关系来翻译四元式：,一个布尔分量对应 个四元式； else对应 个无条件跳转四元式； while的循环体S最后必须有 个强制跳转四元式。,2,1,1,课堂练习：将下列语句翻译成四元式（重点）,4.5 控制语句的翻译,（课本P121 例4.7）,if (a b) while (xn) x = x + y; /(+,x,y,x),T,T,T,T,jump,F,F,F,F,q,T,F,4.5 控制语句的翻译,4.5.4 多分支控制语句case的翻译(自学) 4.5.5 语句标号和转移语句的翻译 程序语言中直接改变控制流程的语句是goto L语句，其中L是源程序中的语句标号。标号L在源程序中可以以两种方式出现,(1) 定义性出现。定义性出现的语句形式为 L: S 此时，带标号的语句S所生成的第一个四元式地址即为标号L的值。,(2) 引用性出现。引用性出现的语句形式为 goto L 它引用L的值作为四元式(j,_,_,L)中转向的目标地址。,4.5 控制语句的翻译,翻译goto L 语句需要查询符号表，根据L是否已经定值，将该语句的使用分为以下几种情况： 1. 先定义，后使用： (1)形式： L:S GOTO L (2)文法： S goto L (使用标号) Label i: (定义标号),4.5 控制语句的翻译,(3)翻译过程：遇到标号语句时，先将标号规约为Lable,再将L填入符号表中： 其中，S.QUAD为S对应的入口四元式序号； 当后面的程序中遇到GOTO L时，便产生(j,_,_,S.QUAD)。,4.5 控制语句的翻译,翻译goto L 语句需要查询符号表，根据L是否已经定值，将该语句的使用分为以下几种情况： 2. 先使用，后定义： (1)形式： GOTO L GOTO L L:S (2)翻译过程：当遇到符号L时，符号表中还未定义，填入符号表中的信息与之前有些不同，如下：,4.5 控制语句的翻译,第一次遇到L的翻译过程： (a)填符号表，将“定义否”一栏填写“未”，地址栏暂时填写即将生成的四元式序号，CAT栏填写“标号”； (b)生成四元式(p)(j,_,_,0)等待回填；,4.5 控制语句的翻译,第二次遇到L的翻译过程： (c)修改符号表，仅将地址栏内容修改为即将生成的四元式序号q； (d)生成四元式(q)(j,_,_,p),其中第四字段的p取自L的地址栏修改前的内容，即形成一个需要回填的链，重复(c)(d)；,4.5 控制语句的翻译,(e)遇到定义性语句L:S出现时，用S语句第一个四元式序号r回填L所对应的链。修改“定义否”为“是”，修改地址栏为r.,课后习题： 4.8 4.9,4.5 控制语句的翻译,
