《中间代码生成》PPT课件.ppt

第七章 中间代码生成 序 7.1 中间语言 7.2 说明语句 7.3 赋值语句 7.4 布尔表达式 7.6 回填 7.7 过程语句 练习7.4 布尔表达式 布尔表达式:用布尔运算符号（and，or，not）作用到布尔变量或关系表达式上而组成 布尔表达式的作用：1.用作计算逻辑值2.用作控制流语句如if-then，if-then-else和 while-do等之中的条件表达式 本节考虑由如下文法生成的布尔表达式：EE or|E and E|not E|(E）|id relop id|true|false 7.4.1 翻译布尔表达式的方法 表示一个布尔表达式的值 方法一：用数值表示真和假，从而对布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算 方法二：通过程序的控制流，即用程序中控制转移到达的位置来表示布尔表达式的值方法二用于翻译控制流语句中的布尔表达式尤其方便。7.4.2 数值表示法 用1表示真，0表示假来实现布尔表达式的翻译布尔表达式：a or b and not c 翻译成三地址代码序列：100：t1:=not c 101：t2:=b and t1 102：t3:=a or t1 关系表达式：ab 等价于if ab then 1 else 0 翻译成三地址代码序列：100：if ab goto l03 101：t：=0 102：goto l04。103:t:=1 104：图7.11 关于布尔表达式的数值表示法的翻译模式 EE1 or E2 E.place:=newtemp;emit(E.place:=E1.placeor E2.place)EE1 and E2E.place:=newtemp;emit(E.place:=E1.placeand E2.place)（接上页）Enot E1 E.place:=newtemp;emit(E.place:=not E1.place)Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.placegoto nextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1)Eture E.place:=newtemp;emit(E.place:=1)Efalse E.place:=newtemp;emit(E.place:=0)7.4.3 控制流语句 文法：Sif E then S1|if E then S1 else S2|while E do S1 E.codeS1.codeE.true:.E.false:(a)if-thento E.trueto E.false代码结构：E.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.false(b)if-then-elseE.codeS1.codeE.true:E.false:goto S.begin.S.begin:to E.falseto E.true(c)while-do语法制导定义：产生式语义规则Sif E then S1E.true:=newlabel;E.false:=S.next;S1.next:=S.next S.code:=E.code|gen(E.true:)|S1.code产生式语义规则Sif E then S1else S2E.true:=newlabel;E.false:=newlabel;S1.next:=S.next;S2.next:=S.next;S.code:=E.code|gen(E.true:)|S1.code gen(gotoS.next)|gen(E.false:)|S2.code(接上页）产生式语义规则Swhile E do S1S.begin:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin:E.code gen(E.true:)S1.code gen(gotoS.begin)(接上页）7.4.4 控制流语句中的布尔表达式的翻译基本思想:假定E 形如ad,则将生成如下的 E的代码：if ab goto E.true 表7.5 语法制导定义 goto E.false 产生式语义规则EE1 or E2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false E.code:=E1.code|gen(E1.false:)|E2.code产生式语义规则EE1 and E2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code gen(E1.true:)E2.code（接上页）Enot E1 E1.true:=E.false;E1.false:=E.true;E.code:=E1.code 产生式语义规则Eid1 relop id2E.code:=gen(if id1.place relop.op id2.place goto E.true)|gen(goto E.false)Etrue E.code:=gen(goto E.true)Efalse E.code:=gen(goto E.false)E的true和false属性都是继承属性E(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code 例7.4 考虑如下语句：while ab do if cd then x：=yz else x：y-z 根据前面所述，生成代码如右：L1：if ab goto L2 goto Lnext L2：if cd goto L3 goto L4 L3：t1：=yz x：t1 goto L1 L4：t2:=yz x：t2 goto L1 Lnext：7.5 CASE语句 switch语句的语法：switch expression begin case valuE1：statement1 case valuE2：statement2 .case value n-1：statement n-1 defalt：statement n end switch语句翻译成的三地址代码控制流程：1对表达式求值；2在列出的valuE1，valuE2,，value n-1 这些值中寻找与表达式的值相等的值。如果没有这样的值存在，则让“缺席值”与表达式匹配；3执行在（2）中寻找到的值相联系的语 句（某个statement）。switch语句的目标代码结构：对expression求值并置于t的有关代码 goto test L1:有关statement1的代码 goto next L2：有关statement2的代码 goto next Ln-1：有关statement n-1的代码 goto next Ln:有关statementn的代码 goto next（接上页）test：if tvalue1 goto L1 if tvalue2 goto L2 .if tvaluen-1goto Ln-1 goto Ln next：expression:选择器，将被计算出一个值。valueE1,valueE2,，value n-1:表达式可能取的 值。default:“缺席值”。用来在expression的值不等 于任何value i时来匹配expression。7.6 回填 两遍扫描：从给定的输入构造出一棵语法树；对语法树按深度优先遍历，来进行定义中给出的翻译。一遍扫描：先产生暂时没有填写目标标号的转移指令。对于每一条这样的指令作适当的记录，一旦目标标号被确定下来，再将它“回填回填”到相应的指令中。7.6.1 使用回填翻译布尔表达式 布尔表达式文法：（1）EE1 or M E2 （2）|E1 and M E2 （3）|not E1 （4）|(E1)（5）|id1 relop id2 （6）|true （7）|false （8）M插入非终结符号M是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个四元式的索引，或说四元式的标号翻译模式用到如下三个函数：1makelist(i)：创建一个仅包含i的新表，i 是四元式数组的一个索引（下标），或说 i是四元式代码序列的一个标号。2merge(p1，p2)：连接由指针p1和p2指向 的两个表并且返回一个指向连接后的表的 指针。3backpatch（p，i）：把i作为目标标号回 填到p所指向的表中的每一个转移指令中 去。此处的“表”都是为“反填”所拉的链图7.14 使用一遍扫描的布尔表达式的翻译模式EE1 OR ME2 backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist EE1 AND ME2 backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist);Enot E1 E.truelist:=E1.falselist;E.falselist:=E1.truelist E(E)E.truelist:=E1.truelist;E.falselist:=E1.falselistE id1 relop id2 E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(ifid1.place relop.op id2.placegoto);emit(goto);E true E.truelist:=makelist(nextquad);emit(goto);E false E.falselist:=makelist(nextquad);emit(goto);M M.quad:=nextquad 例7.15 重新考虑表达式ab or cd and ef 一棵作了注释的分析树如下图所示E.t=100,104E.f=103,105E.t=100E.f=101E.t=104E.f=103,105OR M.q=102abE.t=102E.f=103E.t=104E.f=105andM.q=104cedf 依次分析，得到如下四元式：100：if ab goto-101：goto-102：if cd goto-103：goto-104：if ef goto-105：goto-经过回填得到：100：if ab goto L1 101：goto l02 102：if cd goio l04 103：goto L2 104：if ef goto L1 105：goto L2 当知道了条件为真时和条件为假时分别应做哪些事时就可以进行回填7.6.2 使用回填翻译控制流语句 文法：（1）Sif E then S （2）|if E then S else S （3）|while E do S （4）|begin L end （5）|A （6）LL；S （7）|S S表示语句L表示语句表A为赋值语句E为一个布尔表达式控制流语句的翻译模式：1.Sif E then M1 S1 N else M2 S2E.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.falseM1处反填E.truelistM2处反填E.falselistN出生成 goto S.next backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)N N.nextlist:=makelist(nextquad);emit(goto)Sif E then M S1 backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)Swhile M1 E do M2 S1 M1处生成标号S.begin，反填S1.nextlist。M2处反填E.truelist。S.nextlist:=E.falselist backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselist;emit(gotoM1.quad)S begin L end S.nextlist:=L.nextlistS A S.nextlist:=makelist()先记录要回填的转移指令地址，在适当的时候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序的控制流程。例7.6 使用自底向上的分析法生成四元式目标 代码，其中A1，A2和A3 均表示赋值语句。if ab or cd and ef then A1 else A2；while ab do A3 LL1;M S backpatch(L1.nextlist,M.quad);L.nextlist:=S.nextlist LS L.nextlist:=S.nextlist 全部四元式代码如下：100:if ab goto 106 101：goto l02 102：if cd goto l04 103：goto ll7 104：if ef goto l06 105：goto 117 106 此处反填E.truelist .(关于A1的四元式).116：goto 127 117:此处反填E.falselist (关于A2的四元式)127：if ab goto 129 此处反填S.nextlist 128:goto 140 129:此处反填E.truelist (关于A3的四元式)139:goto 127 140:此处反填E.falselist.7.4.3 标号和转 移语句 .goto L;.goto L;.goto L;.L:.goto nil.Lgoto .goto L:.拉链 反填7.7 过程调用 一个过程调用的翻译包括一个调用序列，即进入和离开每一个过程所采取的动作序列。考虑如下的一个简单的过程调用语句的文法：（1）Scall id（Elist）（2）ElistElist，E （3）Elist E怎样的语法制导定义可以实现该序列？发生一个过程调用时：为被调用过程分配它的活动记录的存储空间；把实在参数的信息传递到被调用过程的可取的指定位置；建立环境指针以便被调用过程能存取非局部过程的数据；保留调用过程的运行状态；返回地址应存入指定的单元中；应生成一条转移指令转移到被调用过程的代码的开始位置。从过程返回时：如果被调用过程是一个函数，则需将返回的结果值存放在一个指定的位置上；调用过程的活动记录需要恢复；应生成一条转移指令转移到调用过程的返回地址；例子：过程调用 “call i(a+b,c)”代码如下：计算ab置于单元t中 *t：=ab*param t *第一个实参地址*param c *第二个实参地址*call iPlace，2 *调用过程i*语法制导翻译：1.Scall id（Elist）for each item p on queue do emit（param p)；emit（call idplace）S的代码：首先是Elist的代码（即对各参数表达式求值），其次是顺序为每一个参数构造一条param语句，最后是一个call语句。2.ElistElist，E 将E.place加入到queue的队尾 3 ElistE 初始化queue仅包含E.place 作业：选作题7.9