编译原理与技术讲义

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理与技术讲义,*,编译原理与技术,中间代码生成,11/9/2024,1,编译原理与技术讲义,中间代码生成,布尔表达式翻译,控制流语句翻译,11/9/2024,2,编译原理与技术讲义,布尔表达式的翻译,布尔表达式文法,G,4,E,E,1,or,E,2,|E,1,and,E,2,|,not,E,1,|(E,1,),|id,1,relop,id,2,|true|false|id,3,布尔运算符,or,、,and,和,not,（优先级、结合性）,关系运算符,relop,：、,、,、,和,布尔常量：,true,和,false,布尔变量：,id,3,11/9/2024,3,编译原理与技术讲义,布尔表达式的翻译,两种翻译方法,数值表示法（完全计算）,类似算术表达式的翻译，如布尔表达式,true,and,false,or,(2 1),的计算为,false,or,(21)false,or,truetrue,短路计算法（不完全计算或解释法）,A or B,if A then true else B,A and B,if A then B else false,not A,if A then false else true,借助控制流语句的思路，部分（不完全地用转移语句）“计算”布尔表达式的值以确定整个表达式的真、假。,11/9/2024,4,编译原理与技术讲义,布尔表达式的翻译,数值表示法,用,1,表示,true,，,0,代表,false,。,（,1,）,E,E,1,or,E,2,t:=,newtemp,;,emit(t“:=”E,1,.place“or”E,2,.place);,E.place,:=t,（,2,）,EE,1,and,E,2,（,3,）,E,not,E,1,（,4,）,E(E,1,),11/9/2024,5,编译原理与技术讲义,布尔表达式的翻译,数值表示法,（,5,）,E,id,1,relop,id,2,t:=,newtemp,;,emit(“if”id,1,.place,relop.op,id,2,.place,goto,nextcode+3);,emit(t“:=”0);,emit(“,goto,”,nextcode,2);,emit(t“:=”1);,E.place,:=t;,nextcode,:emit,产生三地址语句的编号,;,产生后，,nextcode,+,11/9/2024,6,编译原理与技术讲义,id,1,relop,id,2,（关系表达式）,if id,1,relop,id,2,goto,i+3,i:,t:=0,i+1:,goto,i+4,i+2:,t:=1,i+3:,i+4:,true,false,11/9/2024,7,编译原理与技术讲义,布尔表达式的翻译,数值表示法,（,6,）,E,true t:=,newtemp,;,emit(t“:=”1);,E.place,:=t,（,7,）,E,false t:=,newtemp,;,emit(t“:=”0);,E.place,:=t,（,8,）,E,id,3,t:=,newtemp,;,emit(if,id.place,“,goto,”nexcode+3);,emit(t“:=”0);,emit(“,goto,”nextcode+2);,emit(t“:=”1);,E.place,:=t,11/9/2024,8,编译原理与技术讲义,id,（布尔变量）,if id,goto,i+3,i:,t:=0,i+1:,goto,i+4,i+2:,t:=1,i+3:,i+4:,true,false,11/9/2024,9,编译原理与技术讲义,e.g.16 af,的三地址码：,(100)if ab,goto,103,(101)t,1,:=0,(102),goto,104,(103)t,1,:=1,/,以上为,af,goto,111,(109)t,3,:=0,(110),goto,112,(111)t,3,:=1,/,以上为,ef,的翻译,(112)t,4,:=not t,3,/,以上为,not ef,的翻译,(113)t,5,:=t,2,and t,4,/,以上为,c=d and not ef,的翻译,(115)t,6,:=t,1,or t,5,/,以上为,af,的翻译,11/9/2024,11,编译原理与技术讲义,af,布尔表达式的翻译短路计算,true,L_true,false,true,false,L_false,false,true,L_true,-,真出口：整个布尔表达式为,真,时，控制流应转移到的目标语句（代码）；反之为,假,时则转到,L_false,-,假出口。,表示转移到的目标语句在有关布尔表达式翻译时尚未确定。,11/9/2024,12,编译原理与技术讲义,布尔表达式的翻译,短路计算,e.g.17 af,的短路计算三地址码：,if af,goto,L_false,goto,L_true,11/9/2024,13,编译原理与技术讲义,短路计算,E,1,or,M,E,2,true,false,真出口,假出口,E,1,and,M,E,2,false,true,假出口,真出口,false,true,not E,1,false,真出口,假出口,true,(E,1,),假出口,false,真出口,true,11/9/2024,14,编译原理与技术讲义,短路计算,id,1,relop,id,2,if id,1,relop,id,2,goto,goto,true,真出口,假出口,false,true,true,真出口,false,false,假出口,goto,goto,11/9/2024,15,编译原理与技术讲义,短路计算,回填技术,布尔表达式短路计算翻译中，产生了转移目标不明确的条件或无条件代码；,当有关目标地址确定后，可将这些目标地址填回到有关代码中。,将有相同转移目标的转移代码的,编号串起来形成链；,可以方便回填目标地址。,11/9/2024,16,编译原理与技术讲义,回填技术,相关符号属性及语义函数：,E.truelist,：布尔表达式代码中所有转向真出口的代码语句链；,E.falselist,：所有转向假出口的代码语句链；,backpatch,(code-list,target-code),/,将目标地址,target-code,填回,code-list,中每条语句,merge(code-list,1,code-list,2,),/,合并链,code-list,1,和,code-list,2,（它们包含的语句转移目标相同）,makelist,(code-No),makelist,(),建立含语句编号为,code-No,的链或空链,M,M.code,:=,nextcode,/,获取下一三地址代码（语句）的编号（作为转移目标来回填）,11/9/2024,17,编译原理与技术讲义,短路计算及回填的翻译方案,(1)E,E,1,or,M E,2,backpatch,(E,1,.falselist,M.code,);,E.truelist,:=merge(E,1,.truelist,E,2,.truelist);,E.falselist,:=E,2,.falselist;,(2),E,E,1,and,M E,2,backpatch,(E,1,.truelist,M.code,);,E.falselist,:=merge(E,1,.falselist,E,2,.falselist);,E.truelist,:=E,2,.truelist;,11/9/2024,18,编译原理与技术讲义,(3),E,not,E,1,E.truelist,:=E,1,.falselist;,E.falselist,:=E,1,.truelist;,(4),E,(E,1,),E.truelist,:=E,1,.truelist;,E.falselist,:=E,1,.falselist;,(5),E,id,1,relop,id,2,E.truelist,:=,makelist(nextcode,);,emit(“if”id,1,.place,relop.op,id,2,.place“,goto,”,）,;,E.falselist,:=,makelist,(,nextcode,);,emit(“,goto,”,);,11/9/2024,19,编译原理与技术讲义,(6),E,true,E.truelist,:=,makelist,(,nextcode,);,emit(“,goto,”,);,E.falselist,:=,makelist,();,(7),E,false,E.falselist,:=,makelist,(,nextcode,);,emit(“,goto,”,);,E.truelist,:=,makelist,();,11/9/2024,20,编译原理与技术讲义,控制流语句的翻译,描述控制流语句的文法,G,5,：,(1)S,if E then S,1,(2)S if E then S,1,else S,2,(3)S while E do S,1,(4)S for id:=E,1,to E,2,do S,1,(5)S begin L end /compound statement,(6)S A/,赋值语句,(7)L L,1,;S /Statements List,(8)L S,11/9/2024,21,编译原理与技术讲义,条件语句的翻译（,1,）,E.code,S,1,.code,if E then S,1,的代码结构,E.truelist,E.falselist,S,1,.nextlist,?,M,箭头线表示控制流方向；,E.truelist,和,E.falselist,意义同前；,S.nextlist,语句,S,的代码中所有跳转到未知目标地址的转移代码（,如果有的话,）的编号链。,该未知目标地址是指,语义上,语句,S,执行结束后应执行的下一代码的位置。,未知目标地址,11/9/2024,22,编译原理与技术讲义,条件语句的翻译（,1,）,(1)S,if E then,M,S,1,backpatch,(,E.truelist,M.code,);,S.nextlist,:=merge(,E.falselist,S,1,.nextlist),11/9/2024,23,编译原理与技术讲义,条件语句的翻译（,2,）,E.code,S,1,.code,t,:,goto,if E then S,1,else S,2,的代码结构,E.truelist,E.falselist,S,2,.nextlist,S,2,.code,S,1,.nextlist,?,未知目标地址,在代码标号,t,处强制产生无条件转移代码，转移目标待回填。,M,1,M,2,11/9/2024,24,编译原理与技术讲义,条件语句的翻译（,2,）,(2)S if E then,M,1,S,1,N,else,M,2,S,2,backpatch,(,E.truelist,M,1,.code);,backpatch,(,E.falselist,M,2,.code);,S.nextlist,:=merge(S,1,.nextlist,S,2,.nextlist,N.code,);,N,N.code,:=,makelist(nextcode,);/,标号,t,emit(“,goto,”,）,;,11/9/2024,25,编译原理与技术讲义,循环语句的翻译（,1,）,M,1,:,E.code,S,1,.code,goto,M,1,while E do S,1,的代码结构,E.truelist,E.falselist,S,1,.nextlist,?,M,2,产生无条件转移语句,goto,M,1,（跳转至循环条件测试代码开始处）,未知目标地址,M,1,