编译原理(4)语义_3(控制语句的翻译)

1、第第 11 11 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：赵建邦主讲教师：赵建邦 第四章第四章 语义分析和中间代码生成语义分析和中间代码生成l4.1 4.1 语义分析概述语义分析概述l4.2 4.2 属性文法属性文法l4.3 4.3 几种常见的中间语言几种常见的中间语言l4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l4.5 4.5 控制语句的翻译控制语句的翻译l4.6 4.6 数组元素的翻译数组元素的翻译l4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l4.8 4.8 说明语句的翻译说明语句的翻译l4.9 4.9 递归下降语法制导翻译方

2、法简介递归下降语法制导翻译方法简介u第四章第四章语义分析和中间代码生成语义分析和中间代码生成l4.5 4.5 控制语句的翻译控制语句的翻译l条件语句条件语句ififl条件循环语句条件循环语句whilewhilel多分支控制语句多分支控制语句case(case(自学自学) )l转移语句转移语句gotogotou重点掌握重点掌握l通过代码结构图翻译通过代码结构图翻译ifif、whilewhile语句语句( (重点重点) )本讲目标本讲目标 4.5 4.5 控制语句的翻译控制语句的翻译u4.5 程序流程控制的三种基本结构程序流程控制的三种基本结构l顺序结构：一般用复合语句实现；顺序结构：一般用复合语

3、句实现；l选择结构：选择结构：if-else , switch-case;if-else , switch-case;l循环结构：循环结构：forfor，while, do-whilewhile, do-while4.5 4.5 控制语句的翻译控制语句的翻译图图4-11 if(E)S的代码结构的代码结构图图4-10 条件语句条件语句if(E)S1;else S2的的代码结构代码结构4.5 4.5 控制语句的翻译控制语句的翻译l为了在扫描条件语句过程中不失时机地处理和回填有关信息，为了在扫描条件语句过程中不失时机地处理和回填有关信息，可将可将GS改写为如下的改写为如下的GS ： GS: (1)

4、SCS(1) (2) Cif(E) (3) STPS(2) (4) TPCS(1);else4.5 4.5 控制语句的翻译控制语句的翻译(1)无论是哪种无论是哪种if语句，首先用产生式语句，首先用产生式(2) Cif(E)进行归约，这进行归约，这时时E的真出口即为的真出口即为S(1)的第一个四元式；的第一个四元式；E的假出口地址则作为的假出口地址则作为待填信息放在待填信息放在C的语义变量的语义变量C.chain中等待回填；中等待回填； 所以：所以：4.5 4.5 控制语句的翻译控制语句的翻译 Cif(E) Backpatch(E.tc, nxq); C.chain=E.fc; (1) SCS(

5、1) (2) Cif(E)扫描到扫描到“)”，立即回填，立即回填E的真出口的真出口C.chain中只保存中只保存E的待填假出口的待填假出口if ( E ) S(1) else S(2) TF(2)不含不含else时，用时，用(1) SCS(1)进行规约，进行规约，E的假出口是的假出口是S(1)的出的出口，将口，将C.chain和和S(1).chain一起作为一起作为S的待填信息链用函数的待填信息链用函数merge链在一起保留在链在一起保留在S的语义值的语义值S.chain中：中：4.5 4.5 控制语句的翻译控制语句的翻译 (1) SCS(1) (2) Cif(E)SCS(1) S.chain

6、 = merge(C.chain,S(1).chain)if ( E ) S(1)TFC S(1)S(1).chain=104C.chain=101S.chain=104规约后：S(1).chainC.chain练习：练习：if (a) if (b) c = 1;(3)用产生式用产生式(2) Cif(E)进行归约之后，如果：条件语句后有进行归约之后，如果：条件语句后有else，用，用(4)继续规约。继续规约。4.5 4.5 控制语句的翻译控制语句的翻译(2) Cif(E) (3) STPS(2) (4) TPCS(1);elseTP CS(1); else q=nxq; emit(j,_,_,

7、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.chain3：q就是就是S(1) .chainif ( E ) S(1) ;else S(2) TFq: (j,_,_,0)nxq:(4)最后用产生式最后用产生式(3) STPS(2)进行归约，进行归约， S(2)语句序列处理完语句序列处理

8、完后继续翻译后继续翻译if语句之后的后继语句。后继语句的四元式地址与语句之后的后继语句。后继语句的四元式地址与S(2)语句序列的出口一致，故将语句序列的出口一致，故将TP.chain与与S(2).chain链接后挂入链接后挂入链头为链头为S.chain的链中，即：的链中，即：4.5 4.5 控制语句的翻译控制语句的翻译(2) Cif(E) (3) STPS(2) (4) TPCS(1);elseSTPS(2) S.chain = merge(TP.chain, S(2).chain);练习：练习：if (a) b =1; else b = 2;课堂练习：将下列语句翻译成四元式课堂练习：将下列语

9、句翻译成四元式（重点）（重点）4.5 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对应对应 个无条件跳转四元式；个无条件跳转四元式； 注意真假出口的预留与回填。注意真

10、假出口的预留与回填。21TFTFTF4.5 4.5 控制语句的翻译控制语句的翻译u4.5.2 循环语句循环语句while的翻译的翻译l1.1.循环语句的代码结构图：循环语句的代码结构图：while (E) S(1) 图图4-12 4-12 条件循环语句条件循环语句whilewhile的代码结构的代码结构1：E的真出口是的真出口是S(1)2：E的假出口是循环的假出口是循环体外体外3：S(1)的后面无条件的后面无条件转移，重新判断转移，重新判断E4.5 4.5 控制语句的翻译控制语句的翻译l2.2.翻译思想：翻译思想：S while (E) S(1) (1)(1)翻译翻译E代码段，并留两个待填的代

11、码段，并留两个待填的E.tc和和E.fc; (2) 扫描过扫描过“)”之后，就可回填之后，就可回填E.tc; (3) 翻译翻译S(1) ，然后无条件转移到，然后无条件转移到E的第一条四元式；的第一条四元式； 因此：因此： 1. 为了保证为了保证(3)的无条件转移，必须保存的无条件转移，必须保存E的第一条四元式序的第一条四元式序号；号； 2. E为假时，需要回填，需要用为假时，需要回填，需要用S.chain保存保存E.fc;4.5 4.5 控制语句的翻译控制语句的翻译l3. 给出易于及时处理和回填的条件循环语句给出易于及时处理和回填的条件循环语句while的文法的文法GS如下：如下： GS: (

12、1) SWdS(1) (2) WdW(E) (3) Wwhilel语义子程序语义子程序 例：例：while(ab) S(1) (1) 使用使用(3) Wwhile进行规约。保存条件的开始位置，进行规约。保存条件的开始位置，也就是无条件语句转移的位置。也就是无条件语句转移的位置。 Wwhile W.quad=nxq; 4.5 4.5 控制语句的翻译控制语句的翻译l例：例：while(ab) S(1) (2)使用使用(2) WdW(E)进行规约。进行规约。 由于由于E的真出口已经确定为的真出口已经确定为nxq，回填，回填E.tc; E.fc无法确定，无法确定，Wd.chain用于保存待填信息，以备

13、回填；用于保存待填信息，以备回填； 的首入口的首入口(W.quad)用用Wd.quad保存，以备强制转移。保存，以备强制转移。 WdW(E) Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad= W.quad; 4.5 4.5 控制语句的翻译控制语句的翻译l例：例：while(ab) S(1) (3)使用使用(1) SWdS(1)进行规约。进行规约。 如果如果S(1)也是也是if-else语句，语句，S(1).chain表示表示S(1)后续的四元式序后续的四元式序列，但不是列，但不是while循环体外的四元式。这时的跳转一定是再回循环体外的四元式。这时的跳转

14、一定是再回到到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 4.5 控制语句的翻译控制语句的翻译（课本（课本 例例4.6）

15、while(AB) if (CD) X = Y+Z;解答解答：只需要画出：只需要画出代码结构图代码结构图，根据转换关系来翻译四元式：，根据转换关系来翻译四元式： 一个布尔分量对应一个布尔分量对应 个四元式；个四元式； else对应对应 个无条件跳转四元式；个无条件跳转四元式； while的循环体的循环体S最后必须有最后必须有 个强制跳转四元式。个强制跳转四元式。211 while(AB) if (CD) X = Y+Z; jump q:while后面的语句后面的语句TTFF课堂练习：将下列语句翻译成四元式课堂练习：将下列语句翻译成四元式（重点）（重点）（ 例例4.7 ）if (a b) whi

16、le (xn) x = x + y; /(+,x,y,x)qTFTFTFFTTF1. 将下面的语句翻译成四元式序列，规定四元式的标将下面的语句翻译成四元式序列，规定四元式的标号从号从100开始。开始。if(ab)while(AD) X = X-1； else X=X+1；else X=Y；void WhileStatement(): /while 语句语句 condition() StatementBlock() 程序程序 void main ( ) 语句块语句块* 语句块语句块 语句语句 | 语句块语句块* 语句语句 顺序语句顺序语句 | 条件语句条件语句 |循环语句循环语句实习内容：实习内

17、容：while语句的翻译语句的翻译cValue = qtTable.addQTInfo(new QTInfo(J, _, _, quad); / 回填回填cValue假链假链 quad = 条件语句四元式起始序号条件语句四元式起始序号; / 回填回填cValue真链真链 int quad; /记录条件语句四元式起始序号记录条件语句四元式起始序号ConditionValue cValue; / 条件表达式返回值：真、假链条件表达式返回值：真、假链 4.5 4.5 控制语句的翻译控制语句的翻译u4.5.3 for语句的翻译语句的翻译lforfor语句的代码结构图：语句的代码结构图：for ( E1

18、; E2; E3) S(1) 四元式的出现次序四元式的出现次序for语句代码结构语句代码结构4.5 4.5 控制语句的翻译控制语句的翻译u4.5.4 多分支控制语句多分支控制语句case的翻译的翻译(自学自学)u4.5.5 语句标号和转移语句的翻译语句标号和转移语句的翻译l程序语言中直接改变控制流程的语句是程序语言中直接改变控制流程的语句是goto Lgoto L语句，其中语句，其中L L是是源程序中的语句标号源程序中的语句标号。标号。标号L L在源程序中可以以两种方式出现在源程序中可以以两种方式出现(1) 定义性出现定义性出现。定义性出现的语句形式为。定义性出现的语句形式为L: S此时，带标

19、号的语句此时，带标号的语句S所生成的第一个四元式地址即为标号所生成的第一个四元式地址即为标号L的值。的值。(2) 引用性出现引用性出现。引用性出现的语句形式为。引用性出现的语句形式为 goto L它引用它引用L的值作为四元式的值作为四元式(j,_,_,L)中转向的目标地址。中转向的目标地址。4.5 4.5 控制语句的翻译控制语句的翻译l翻译翻译goto L 语句需要查询符号表，根据语句需要查询符号表，根据L是否已经定值，将该是否已经定值，将该语句的使用分为以下几种情况：语句的使用分为以下几种情况：l1. 先定义，后使用：先定义，后使用： (1)形式：形式： L:S GOTO L (2)文法：文

20、法： S goto L (使用标号使用标号) Label i: (定义标号定义标号)4.5 4.5 控制语句的翻译控制语句的翻译 (3) (3)翻译过程：遇到标号语句时，先将标号规约为翻译过程：遇到标号语句时，先将标号规约为Lable,Lable,再再将将L L填入符号表中：填入符号表中： 其中，其中，S.QUAD为为S对应的入口四元式序号；对应的入口四元式序号； 当后面的程序中遇到当后面的程序中遇到GOTO L时，便产生时，便产生(j,_,_,S.QUAD)。 4.5 4.5 控制语句的翻译控制语句的翻译l翻译翻译goto L 语句需要查询符号表，根据语句需要查询符号表，根据L是否已经定值，

21、将该是否已经定值，将该语句的使用分为以下几种情况：语句的使用分为以下几种情况：l2. 先使用，后定义：先使用，后定义： (1)形式：形式： GOTO L GOTO L L:S (2)翻译过程：当遇到符号翻译过程：当遇到符号L时，符号表中还未定义，填入符时，符号表中还未定义，填入符号表中的信息与之前有些不同，如下：号表中的信息与之前有些不同，如下：4.5 4.5 控制语句的翻译控制语句的翻译 第一次遇到第一次遇到L L的翻译过程：的翻译过程： (a)(a)填符号表，将填符号表，将“定义否定义否”一栏填写一栏填写“未未”，地址栏暂时，地址栏暂时填写即将生成的四元式序号，填写即将生成的四元式序号，CATCAT栏填写栏填写“标号标号”； (b)(b)生成四元式生成四元式(p)(j,_,_,0)(p)(j,_,_,0)等待回填；等待回填；4.5 4.5 控制语句的翻译控制语句的翻译 第二次遇到第二次遇到L L的翻译过程：的翻译过程： (c)(c)修改符号表，仅将地址栏内容修改为即将生成的四元式修改符号表，仅将地址栏内容修改为即将生成的四元式序号序号q q； (d)(d)生成四元式生成四元式(q)(j,_,_,p),(q)(j,_,_,p),其中第四字段的其中第四字段的p p取自取自L L的地的地址栏修改前的内容，即形