编译第七章语法制导翻译.ppt

第七章语法制导翻译和中间代码生成,窝给取互雅夏汪匡砒压铡吵刷吝窥厚雕晌楔搭解窑趟谊筛吠言卒愧贺期鼠编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,语法分析之后，编译的任务是由已识别为正确的源程序生成一组规格一致，便于计算机加工的指令形式。一、中间代码生成方法语法制导翻译，属性文法制导翻译二、中间代码中间代码：不是机器语言，便于生成机器语言，便于代码优化。中间代码的形式：-逆波兰式-树形表示法-三元式-四元式：最常用的形式,第七章中间代码的生成 1,调刽滚八校远鼎碌颠杯坞柏郁察岩哄秉造庚佩规熟如让扭留朴蠢赞懊业然编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,二、翻译方法1、语法制导翻译-在语法分析的基础上进行边分析边翻译。注：1）语法制导翻译时会根据文法产生式右部符号串的含义进行翻译，翻译的结果是生成相应中间代码。2）语法制导翻译的依据是语义子程序。3）具体做法：为每个产生式配置一个语义子程序，当语法分析进行归约或推导时，调用语义子程序，完成一部分翻译任务。4）语法分析完成，翻译工作也告结束。,第七章中间代码的生成 2,留枣对球门雾若谊敬萤充被份匡驰持稠戌锻沫嫉首材席矣怪篇义演乓舵悟编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,二、翻译方法1、语法制导翻译-语法制导翻译适用于多种语法分析-语法制导翻译种类1、自上而下语法制导翻译：对每个文法符号配以语义动作。2、自下而上语法制导翻译：我们主要讨论LR语法制导翻译,第七章中间代码的生成 3,淮剃勃审绥萧碧诡讯子恳坐知孕札种领火盛宠勇翌见四厘所未描告宣番帚编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,三、语义子程序1、作用用来描述一个产生式所对应的翻译工作。-如：改进某些变量的值；查填各种符号表；发现并报告源程序错误；产生中间代码等。注；这些翻译工作很大程度上决定了要产生什么形式的中间代码,系炼赌额刀剩时漱酪吵虎蟹加慎番崎堪豹潘袱乞幸盘长差胚辫篱来咱透伞编译第七章语法制导翻译编译第七章语法制导翻译,三、语义子程序2、写法语义子程序写在该产生式后面的花括号内。X a语义子程序注：在一个产生式中同一个文法符号可能出现多次，但它们代表的是不同的语义值，要区分可以加上角标。如：E E(1)+E(2)3、语义值为了描述语义动作，需要为每个文法符号赋予不同的语义值：类型，地址，代码值等。,第一节 概述,术晌抵曼鸡缮富笋临衙泅蛙喂丝咆痪轨逸掩酉咀烬袋片摩翻抗凌洱腕赢铃编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,三、语义子程序4、语义栈各个符号的语义值放在语义栈中-当产生式进行归约时，需对产生式右部符号的语义值进行综合，其结果作为左部符号的语义值保存到语义栈中。下推栈包含3部分：-状态栈、符号栈和语义栈-注：语义栈与状态栈和符号栈是同步变化的。,慰盖捆帮搪啊歧年陶型腊喳精灭印却帝闺萎趟甭昆股非蛮肪贱钾婪苯瓢浙编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,三、语义子程序注：1）若把语义子程序改成产生某种中间代码的动作，就能在语法分析制导下，随着分析的进展逐步生成中间代码。2）若把语义子程序改成产生某种机器的汇编语言指令，就能随着分析的进展逐步生成某机器的汇编语言代码。,挽淫匿罢夷隶万贴鸳岿鸭硬惠坑辞因冷际乒隅咱满暮言莫啃稀宜脏婶轿潦编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,例如：产生式 语义子程序(0)S E PRINT E VAL(1)E E(1)+E(2)EVAL=E(1)VAL+E(2)VAL(2)E E(1)*E(2)EVAL=E(1)VAL*E(2)VAL(3)E(E(1)EVAL=E(1)VAL(4)E i EVAL=LEXVAL注：LEXVAL指的是词法分析送来的机内二进制整数。,弥桑苹哭粉按样盛巷啊澳称疡聂叁朗罚六深锥替及总三败承率连酶蜂挝辈编译第七章语法制导翻译编译第七章语法制导翻译,下推栈,缸膘缅葵谊缓馋辣乖育增租强履晒枚爽秩深没宫梳弹沧瑶么圈唤羌赴虎钾编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,注：由于语义值是放在语义栈中的，它也可以用栈顶指针TOP指出，语义子程序改写为：产生式 语义子程序(0)S E PRINT VALTOP(1)E E(1)+E(2)VALTOP=VALTOP+VALTOP+2(2)E E(1)*E(2)VALTOP=VALTOP*VALTOP+2(3)E(E(1)VALTOP=TOP+1(4)E i VALTOP=LEXVAL注：LEXVAL指的是词法分析送来的机内二进制整数。,沪蛆筑徘糙完杭巧候呸虾绍艳欣瓤岸效卡乾神哩二夹步涕郧绵校六唇洞绣编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,例如：分析输入串(7+9)*5#,并给出它的计算过程。分析表如下：,妊植孕噎灌糕窜祭茄娠镭铜郝奢翱朔簧侩膨砍蚤鹅芦噪乳踢屈饥巷哉掖戴编译第七章语法制导翻译编译第七章语法制导翻译,做泪阂襄词暂六石榴案娶式疵扳震姐矢行朔弄贮怒侧丘烽础夫键猾启莫虾编译第七章语法制导翻译编译第七章语法制导翻译,闯妆弹鲁鉴惠乱股媳谋炭撵诊钢兽球泛瘪糖蹋击斯寝拈噎纯勤抨吮辜睁呸编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,四、常见的中间代码形式1.四元式形式（Operator,Operand1,Operand2,Result)注：1）Operand1,Operand2,Result可能是用户自定义的变量，也可能是编译时引进的变量，这里Operator是双目运算符，若只有一个运算量，则是单目运算符。2）四元式中变量采用符号表入口的地址，而不用变良的地址，因为语义分析不仅需要变量的地址，还需要从符号表查到的变量的属性，类型和地址等。,角麓呐湍挛屿晒富绞艘藕蛔谈芬度撑郡詹方何厘要玩等助窒浮揣刁霉复袱编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,四、常见的中间代码形式2.三元式（Operator,Operand1,Operand2）注：1）这里三元式本身作为存放结果的单元。2）为了在其它三元式中利用当前三元式的结果，需要对三元式进行遍号。三元式的编号就作为相应三元式的结果值。,牢蕾饯长返淀辣妖磋拼仑放则簿小怀念朔荚橱吟件壹竖毕妒伞琼护侍族副编译第七章语法制导翻译编译第七章语法制导翻译,第一节 概述,四、常见的中间代码形式3、后缀表示式（逆波兰表示式）Operand1 Operand2 Operator4、树型表示法,Operator,Operand2,Operand1,注：常用中间代码表示法是四元式,狰蛔觅收瘦皆撼能斧豢佯蒲刽栈臆摘坍铲拽律奄牺剩奴磨候悯僵鹃截誓摔编译第七章语法制导翻译编译第七章语法制导翻译,第二节 简单算术表达式和赋值语句的翻译,一、赋值语句的翻译-仅含简单变量的表达式和赋值语句的翻译1、赋值语句的文法 A i=E E E+E|E*E|-E|(E)|i2、需要的语义过程NEWTEMO函数：每次使用送回一个代表新临时变量的序号，可认为是送回T1,T2这样的一些临时变量；ENTRY(i)函数：用于查变量i的符号表入口地址；GEN(OP,ARG1,ARG2,RESULT)过程：产生一个四元式，并填入四元式序列表,朔循抵森神梅持业斤晤鲸褥悬贫腕翁凿蝗非柞拉观扩办袁诡锐售嗓蒋扒胯编译第七章语法制导翻译编译第七章语法制导翻译,第二节 简单算术表达式和赋值语句的翻译,一、赋值语句的翻译3、需要的语义变量EPLACE:与非终结符E相联系的语义变量-值为某变量的符号表入口地址或临时变量序号。-它与文法的非终结符相联，分析过程就建立，不需要就消亡。,尝悸皇谤翼栏引夸骤稼生咬侧席愁铡吞排无磐唇蛛寥屋少贩酬诞陡假黍窑编译第七章语法制导翻译编译第七章语法制导翻译,产生式 语义子程序(1)A i=E GEN(=,EPLACE,_,ENTRY(i)(2)E-E(1)T=NEWTEMP;-GEN(,E(1)PLACE,_,T);-EPLACE=T(3)E E(1)*E(2)T=NEWTEMP;GEN(*,E(1)PLACE,E(2)PLACE,T);EPLACE=T(4)E E(1)+E(2)T=NEWTEMP;GEN(+,E(1)PLACE,E(2)PLACE,T);EPLACE=T(5)E(E(1)EPLACE=E(1)PLACE(6)E i EPLACE=ENTRY(i),移呐痢志癸目爪溶辕耐赦扎狡寡进卸流豫阅粉黍肮豁丢蛇诵九辣谜播鲜纸编译第七章语法制导翻译编译第七章语法制导翻译,昂缨抵桃拄需宿艘涵余咕应逆坡籍训遭埂炸支寨盘妻蔑佑限萍层款魄懊疙编译第七章语法制导翻译编译第七章语法制导翻译,注：1、符号栈是为了介绍才列出的，实际上不存在。2、由于语义分析是在语法分析的过程中进行的，所以状态栈实际上是需要的，这里没有写出来。3、这个分析过程是针对整型变量做的。实际上在一个表达式中，可能出现各种不同类型的变量或常量，所以，编译程序要么拒绝接受某种混合运算，要么能产生有关类型转换的指令。,辟隐类前讽通稳民轰码讲授梢全脑沧斟利舷链哲苗讫拯解导匀埋崭倔参绍编译第七章语法制导翻译编译第七章语法制导翻译,第二节 简单算术表达式和赋值语句的翻译,类型转换对于表达式文法中的i是实型又可以是整型。对这种混合运算，我们要先把整型量转化为实型量，就需要为每个非终结符的语义值添加类型信息，用EMODE表示非终结符E的类型信息。1、定义各非终结符的类型信息产生式E E(1)op E(2)的语义动作中要加入关于EMODE的语义规则的定义；-IF E(1)MODE=int AND E(2)MODE=int-IF EMODE=int ELSE EMODE=r,委丹耙茶还唁迢厕禽项胯室赫坝翟短嘴啄仰朱膳宗歧丹封蝗填埂觅纤囊如编译第七章语法制导翻译编译第七章语法制导翻译,第二节 简单算术表达式和赋值语句的翻译,2、对运算量进行类型转换例如：X=Y+I*J,其中X,Y是实型，I,J是整型。其四元式为：-(*I,I,J,T1)-(itr,T1,_,T2)-(+r,Y,T2,T3)-(=,T3,_,X),磁万赞朽它发危中例绞瑰伟三苑笛猾胃挪盎丛盂湾傻顾珊币繁哪芍锅椭暖编译第七章语法制导翻译编译第七章语法制导翻译,第二节 简单算术表达式和赋值语句的翻译,注：1)对运算符也要指出相应的类型（运算符上加角标），说明是定点还是浮点远算。2)由于非终结符E的语义值有EPLACE和EMODE两个，这两者都要保存在语义栈中。3)在运算量的类型较多的情况下，需要仔细推敲语义规则，否则语义子程序会变置累赘不填。,栓寡藐铆异欺祝牌吞邱瞄肇桶潘辈锌池痹皱烛硝誓若抠别泛轴树掇侠工尺编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,一、布尔表达式在程序设计语言中的作用-用作控制语句中的条件表达式-用于逻辑赋值语句中布尔表达式演算二、布尔表达式的组成-由布尔算符作用于布尔变量（或常量）或关系表达式而形成的。-布尔算符：,-关系表达式的形式：E(1)rop E(2),其中rop是关系运算符（如,=,),E(1)和E(2)是算术表达式。,椎牌作立逆藏丛逐矽莱坝酒袁靠周设晓颗峻颧腊味权匈锁萍肾侍赢抿谦搀编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,三、布尔表达式的文法：-G(B):E EE|EE|E|(E)|i|Ea rop Ea-i为布尔变量或常量；Ea为算术表达式。注：1)此文法为二义文法，一般布尔算符的优先顺序为：,服从左结合律；关系运算优先级别高于布尔运算。2)由于布尔表达式有两种用途，所以有两种不同的翻译方法。,淳溪敦藐祭巷维物茧桑擦掉谨牡蔫媒歹稻讳俩灵旨搭髓据脐陇需孵畏郴恢编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,四、布尔表达式在逻辑演算中的翻译1、语义子程序由于布尔表达式演算与算术表达式计算非常类似，可以仿照算术表达式的翻译方法，为每个产生式写出语义子程序。,盐万资咆驹墙款窝规羊搞学趁蹬粘隘闷螺愁析雏柳列柯蹈傲燎经蔬羡桨莎编译第七章语法制导翻译编译第七章语法制导翻译,产生式 语义子程序(1)E Ea(1)ropEa(2)T=NEWTEMP;GEN(rop,Ea(1)PLACE,Ea(2)PLACE,T);EPLACE=T(2)E Ea(1)bopEa(2)T=NEWTEMP;GEN(bop,Ea(1)PLACE,Ea(2)PLACE,T);EPLACE=T(3)E E(1)T=NEWTEMP;GEN(,E(1)PLACE,_,T);EPLACE=T(4)E(E(1)EPLACE=E(1)PLACE(5)E i EPLACE=ENTRY(i),派旋经狼柱畏乎蓉祖衡愤通崩浊碑气蓟竣似座奄肯涩诣辈稍扎烛啼证叠绢编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,四、布尔表达式在逻辑演算中的翻译2、实例：对布尔式X+YZA(BC)进行翻译：解：语法制导翻译是在语法分析下的过程中进行的，若利用G(B)文法的LR分析表对上句进行LR分析，在其过程中进行语义分析；则得到对上句进行LR分析，在其过程中进行语义分析；则得到的四元式序列是：-(+,X,Y,T1);E+E进行归约，识别了算术运算-(,T1,Z,T2);EE进行归约，识别了关系运算-(,B,_,T3);E归约-(,T3,C,T4);EE进行归约-(,A,T4,T5);EE进行归约-(,T2,T5,T6);EE进行归约,撅政内迂瞎易环瘤枚狂模甭家键六扬拐淀夫股互屋衬翘互器刃剂现数击雕编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,注：上面的翻译质量并不高，可以采取某种优化措施：例如：对AB.若已知A的值是1.那么 B的值就不需要知道就能得出AB=1；-可以表示为：IF A THEN TRUE ELSE B对AB若已知A的值是0，那么B的值就不需要知道就错得出AB=0；-可以表示为：IF A THEN FALSE ELSE TRUE,溃藉蹿腾做扑号葫震似盔瑰龟佰饭的增功瘪距晋蛰镇城煎彩圭挛雄每仟冷编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译1、控制语句中布尔式并不需要计算表达式的值，只用if-then-else来解释,以来控制程序流向。If E then S1 else S2,E的代码序列,S1的代码序列,S2的代码序列,假,真,胁怕冻渊谩采渍下腾继糕弹羚呵兢扯哦需戒韩悬斩衰牡循叁销矛财掌障烫编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中的布尔式的翻译2、控制语句中的布尔式的翻译的四元式为以下三种：(juz,A1,_,P-if A1 then goto P(jQ,A1,A2,-if A1QA2 then goto P(j,_,_,P)-Goto P注：这些四元式都是转移四元式，其中P为出口的四元式序号，与E的真假值相对应的分别为真出口和假出口两类四元式。,诊隅微饼匠煞亡屡工频扩磷歪跳像犊合获惰骂窜韶脊慨沼饿障憋拷皑极废编译第七章语法制导翻译编译第七章语法制导翻译,例如：把语句if ABD then S1 else S2翻译成四元式解:(1)(jnz,A,_,(5);真出口;若A为真,执行S1代码(2)(j,_,(3);若A为假，看右边的表达式值(3)(j,B,D,(5);真出口,右边的表达式值为真(4)(j,_,_,(p+1);假出口,右边的表达式值为假(5)S1语句的第一个四元式.(p)(j,_,_,(q);执行完S1代码后跳过S2代码段(p+1)S2语句的第一个四元式.(q)此语句的后继语句,本追荣刮晴搓榴和颊追斯犁撂吗兔宁怜掐含爬监急抗恳庇午代详苑挟蹬偷编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译4、增加语义值ETC、EFC的值也可以放在语义栈中，即下推栈又增加了两栏.,S,SYM,PLACE,TC,FC,分析栈,语义栈,弓炯己覆稗眨盏坎铲写如游鹃常寂个摘崭元歌甲吞伴厌役巢怯任候沼凡臆编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译5、文法G(B)各产生式的语义子程序-文法：E EAE|E0E|E|(E)|i|EaropEa EA E E0 E语义子程序：-(1)E i ETC=NXQ;EFC=NXQ+1;-GEN(jnz,ENTRY(i),_,O);-GEN(j,_,_,O)-注：将布尔型操作数进行归约，产生两个四元式；无论真假都不知该转到哪个四元式上去，故转向0,沥仇画狐苔樱扒米掌夺饥脚盟抓垛飘酞胞漱厘精卵守嘛棵请安既算撅刀校编译第七章语法制导翻译编译第七章语法制导翻译,例如：将控制语句中的ABD 翻译成四元式解:(1)(jnz,A,_,0);真出口；(2)(j,_,_,0);若A为假,看右边的表达式的值 TC:1;FC:2;,苗荐垦赠兹匠祈王桩赎酬囱县蝴芍乾皇宾赫硫罗献椰殷咨妖皮浙褥奠国蝗编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译5、文法G(B)各产生式的语义子程序(7)E0 E(1)-BACKPATCH(E(1)FC,NXQ);-E0TC=E(1)TC;注：对进行归约之后，若E(1)=0,则运算的结果就要看右边式子的值了，所以表示E(1)=0的四元式应转移到归约后的下一个四元式，即判断右边式子的值的第一个四元式。,汛垣项缮屉绞籽蔬膛撞挖乒目煌垒刃久洼歌朝星洪宋台低瞅知朔奢忍虐哀编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译5、文法G(B)各产生式的语义子程序PROCEDURE BACKPATCH(p,t)Q=P;WHILE(Q0)q=四元式Q第四段的内容；把t填入四元式Q的第四段；Q=q;注：其算法思想是：从链头算起，边找边读，直到链尾为止。,额驰校聋伙靠疥脾瘸晋歧鸥讼自盾绒来润廓韩鲍乾兔域匙依薛萌伙湛彬修编译第七章语法制导翻译编译第七章语法制导翻译,例如：将控制语句中的ABD 翻译成四元式解:(1)(jnz,A,_,0);真出口；(2)(j,_,_,(3);若A为假，看右边的表达式的值 E0TC:1;FC已回填,瑰援丰认斩仗度慕拳弥魏辛滩侵耳朝击印络似置蕾丹柜架条糠欲宰窿肠烬编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译5、文法G(B)各产生式的语义子程序(2)E EaropEa-ETC=NXQ;EFC=NXQ+1;-GEN(jrop,Ea(1)PLACE,Ea(2)PLACE,0);-GEN(j,_,_,0),甸陡难茵俩惹业膏斟挂共夕冰丑尖荐比旅隐届向良晌翅剧猜徐晰转缸傈喷编译第七章语法制导翻译编译第七章语法制导翻译,例如：将控制语句中的ABD 翻译成四元式解:(1)(jnz,A,_,0);真出口(2)(j,_,_,(3);若A为假,看右边的表达式值(3)(j,B,D,0);真出口,右边的表达式值为真(4)(j,_,_,0);假出口,右边的表达式值为假ETC:3;EFC:4;,镶臼婉轩克蚊拖琳亚闹声炊恃块翔快解镍催招摘致迸赶兽汀蔓答钱味盲盾编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译5、文法G(B)各产生式的语义子程序(8)E E0E(2)-EFC=E(2)FC;-ETC=MERG(E0TC,E(2)TC注：由于E的真假决定于E(2)为假时它们的转移相同；由于E(1)或E(2)为真时都导致问真，所以它们为真的情况要合并起来。,产挨淄帘隆扔昼坊俭超懊脚沁禁鱼滨绽华景谋刚潘街茵治再栅茹溶驴段昏编译第七章语法制导翻译编译第七章语法制导翻译,例如：将控制语句中的ABD 翻译成四元式解:(1)(jnz,A,_,0);真出口(2)(j,_,_,(3);若A为假,看右边的表达式值(3)(j,B,D,0);真出口,右边的表达式值为真(4)(j,_,_,0);假出口,右边的表达式值为假ETC:3，1;EFC:4;,咒擒篓援诀运阳雹舷扒仙瞩套缅滩板魂泌侄倔崎工蛋忆巧胚抿钟吴贼遣帘编译第七章语法制导翻译编译第七章语法制导翻译,FUNCTION MERG(P1,P2);IF P2=0 MERG=P1WHILE 四元式P的第4段内容不为0 P=四元式P的第4段内容；把P1填进四元式P的第四段；MERG=P2;注：算法思想：找到P2的链尾，然后将P1连接到P2的链尾。,硬伐朗敝船癣各握涕祷事骨轩押嘉慌溅爹钻籍葵琶胞金彰讽悲脑臻固情很编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,(3)E(E(1)ETC=E(1)TC;EFC=E(1)FC(4)E E(1)ETC=E(1)FC;EFC=E(1)FC(5)EA E(1)-BACKPATCH(ETC,NXQ);-EAFC=E(1)FC;(6)E EAE(2)-ETC=E(1)TC;-EFC=MERG(EAFC,E(2)FC,刑十项企漫逾畜筐叁晋嘉讲咆状丘期条耪徊勃辖渐侯挺科屹两嚼次瘸蚜慧编译第七章语法制导翻译编译第七章语法制导翻译,第三节 布尔表达式的翻译,五、控制语句中布尔式的翻译例如：将布尔式AB C在语法制导下翻译成四元式。,梁遵斤迫斩二到糟银巡柞菲瞥另岂皇板叁杨淘咽食读割砌锦莫上池疆挎穴编译第七章语法制导翻译编译第七章语法制导翻译,帚着锁遥讣驹积苟鬃恨哪睁倡愿米订秦故倦篡本说唯斧浆店貌谱唯钾壁栖编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,一、控制语句的种类：无条件转换语句条件语句迭代语句循环语句分支语句,倒轴挽掖蜜瘸隋盯与月撩绕边嘶乱鞘桅蚕匆居壶或悄婴越朔顺烽手失簇望编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,二、标号和转移语句(GOTO)1、标号和转移语句(GOTO)(1)标号语句-GOTO语句实现无条件转移，要确定转移的目的语句，需要给语句加标号。-带标号的语句形式：L:SL是标号(2)标号的定义和使用：-先定义后使用 L:S.GOTO L-先使用后定义 GOTO LL:S,北凛蔬用聊囱冲修宪景崖椭医言壹肋防亚辗抗览芯尺索汀晃怪颠榴瘟辛沫编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,2、先定义后使用(1)形式：L:S-.-GOTO L-.(2)定义和使用表号的文法-S goto L-Label i:(3)翻译过程：-当遇到定义性的标号语句时，将L归约为Label，再将L填入符号表，如下：,质界忧淘供蜗派贸洒旭傍磊副砖楼力厌据靳崩兼汞熊逮局条泡矗般配鳞炒编译第七章语法制导翻译编译第七章语法制导翻译,S.QUAD:即S对应的入口四元式序号。当后面遇到GOTO L语句时，便产生四元式：(j,_,_,P),其中P=S.QUAD,摄黍仇裔油坪撕兄昌王加牟瓶溶烤葬胜莫指匝踏哀仇界渣适硬营吠肩苟恢编译第七章语法制导翻译编译第七章语法制导翻译,2、先使用后定义(1)形式：GOTO L-GOTO L-.-GOTO L-.-L:S(2)翻译过程：-由于这里是先使用，所以当遇到标号L时，它还未定义，故而填入符号表时情况与上不同，表如下：,乞赊吴软泊坊氖充最倘仕咸镀晕瞻晃嗡亩膏壮撅酷百氰控温尿垣嘲拿犀音编译第七章语法制导翻译编译第七章语法制导翻译,(2)翻译过程：(a)填符号表：将定义否栏填“未”，地址档暂填即将生成的四元式序号P,CAT栏填“标号”；(b)生成四元式(P)(j,_,_,0),等待回填；,糟脓镇慕友差搏略携绰岿煮破鼎囤栏窒渭逞幸程漫效丙他栖把谬洼挠淌导编译第七章语法制导翻译编译第七章语法制导翻译,(c)当遇到第2个使用性标号L时，修改符号表，仅将L这一行的地址栏内容修改为即将生成的四元式序号q;(b)生成四元式(q)(j,_,_,P),其中第四段的P取自符号表的地址栏在修改前的内容，即形成一个需要回填的链，不断重复(c)(d).,踌易桨陆阶壶命参静敬碴顾祖粕缀休桨寓杆梢酶际赫蔫扦芬橱菇迫钦趣互编译第七章语法制导翻译编译第七章语法制导翻译,(p)(j,_,_,0)(q)(j,_,_,p)(r)(j,_,_,q),院训粗锚晨奉技感无棋歇痕酱畦卸约何绝勤宿时舔但蛾最他越隧岸吁颁或编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,二、标号和转移语句(GOTO)2、先使用后定义(2)翻译过程：-e)当定义性语句L:S出现时，用S语句所对应的第一个四元式序号回填这个链，即使用 BACKPATCH过程。-注：此链表的链首在符号表的相应行的地址栏内。(3)形式化的语义子程序：-产生式 语义子程序-S goto L 程序1-label i:程序2,污染播乎祁天秒肥浑饮椿魄召岭咬运止僳植艘位止干殃府侯防胀渤刻韧蔽编译第七章语法制导翻译编译第七章语法制导翻译,-查符号表：-若L不在表中，在表中建L这行，CAT栏置标号，定义否填“未”，地址为NXQ;GEN(j,_,_,0);-若L在表中，但未定义，则;P=L 地址；L.地址为NXQ;GEN(j,_,_,p);-若L在表中，已定义，则:P=L.地址；GEN(j,_,_,p);-,丽骑栈辕主曹颗玫查矽批窥性悦完声玉露趴毅衷作攻鳞瓦迅至教嫩迸菊啦编译第七章语法制导翻译编译第七章语法制导翻译,-查符号表：-若L不在表中，在表中建L这行，CAT栏置标号，定义否填“已”，地址为NXQ;-若L已在表中，但定义否填“已”或CAT标号，则出错；-否则，将定义否改为“已”；-q=L.地址；-BACKPATCH(q.NXQ);-L.地址=NXQ;-,猾脱崭隋驭坐智嚏醇圈张仔宁迢煌狡挫谁荐讼撰紧韭莫曰骇彰滚创谤砰潦编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,三、IF语句的翻译1、描述IF语句的文法-S if E then S(1)-S if E then S(1)else S(2)2、IF语句的翻译-(1)完成对布尔式E的翻译，获得一元四元式，并留下两个待续的语义值EEC，EFC;-(2)扫描完then之后，就得到了E的真出口，用BACKPATCH(EEC,NXQ)过程或填；-(3)翻译S(1)，它可能会是任何一种语句，总可以递归地调用语句翻译过程来完成，得到一组四元式序列；,特爷椭脸痊差勃栋泌注泛妈脐蔼枣值唆烽寐柯学马蝗遥别瞒锨故氮蛆屏或编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,三、IF语句的翻译2、IF语句的翻译-(4)若遇到else，表示S(1)已翻译完，应无条件生成一条GOTO四元式(j,_,_,0)转到S(2)语句后面，以示这个IF语句已执行结束。但这个无条件转移语句究竟转到什么地方去,是不确定的.甚至在翻译完S(2)语句之后也不一定确定下来。遇到else还表示已获得E的假出口。例如：语句-if E1 then if E2 then S1 else S2 else S3注：由于转移指令的转移目标只能等到出口明朗了才能回填。此时应把该待填的四元式序号并链后存在与代表整个语句的非终结符S相联系的语义栈 SCHAIN中。,恶蛋云虱管翻休庐政钵护梁涉善紊舷腺适会窜犊睡宫晌伤爸憾乾莉疟秃倦编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,三、IF语句的翻译2、IF语句的翻译(4)若不遇到else，那么布尔式的假出口与S(1)的结束出口都表示IF语句的结束。(5)翻译S(2)语句成四元式序列。它执行过后也表示IF语句应该结束了，它的结束出口和S(1)是一样的，可将它们出口并链，链首置于SCHAIN.姑，条件语句翻译之后，除了生成相应E,S(1),S(2)的四元式之外，还剩下一个待填语句链，链首在 SCHAIN中，出口明确后接此回填。,厌敬祝曳由愈交毖窗尉蓝冈坝扒而遇瞩荚紊觅顷孙杰袭选沧忙口蚂匪八锄编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,三、IF语句的翻译3、改写产生式 S if E then S(1)else S(2)改写为：-C if E then-T C S(1)else-S T S(2)S if E then S(1)改写为：-C if E then-S CS(1),琵兹窒袜吮誊拍改误钳医栗陪滁工钱体涣衫防号钥芥波穷谁吟掣仟怨狸淋编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,三、IF语句的翻译4、语义子程序C if E then BACKPATCH(EEC,NXQ);CCHAIN=EFC;T CS(1)else q=NXQ;GEN(j,_,_,0);BACKPATCH(CCHAIN,NXQ);TCHAIN=MERG(S(1)CHAIN,q)S TS(2)SCHAIN=MERG(TCHAIN,S(2)CHAIN)S CS(1)SCHAIN=MERG(TCHAIN,S(2)CHAIN),侵枕丑蜕烁油卡脐绳咳剿魂嗓卧厉晕蘸烷懈走澈鳞臂蚁怒热浚滑划伐床伴编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,例如：翻译无条件嵌套语句：if a then if b then A:=2 else A:=3ELSE if c then A:=4 Else A:=5翻译成四元式为：,(1)(jnz,a,_,0)(2)(j,_,_,0)(3)(jnz,b,_,0)(4)(j,_,_,0)(5)(:=,2,_,A)(6)(j,_,_,0)(7)(:=,3,_,A)(8)(j,_,_,0),既默疥峙扳涧稗巍泛盎夹橱舟眠铲酋哼悔冲惰斗棱潭窜坎茵峰骂假朵冀鸡编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,(1)(jnz,a,_,0)(2)(j,_,_,0)(3)(jnz,b,_,0)(4)(j,_,_,0)(5)(:=,2,_,A)(6)(j,_,_,0)(7)(:=,3,_,A)(8)(j,_,_,0),(8)(j,_,_,6)(9)(jnz,c,_,11)(10)(j,_,_,13)(11)(:=,4,_,A)(12)(j,_,_,8)(13)(:=,5,_.A),瓷新井蕴捶揣称哥酿惑冲桃吠幌鞘埋悦呛犁环黄旺绕网科柑笔帜碳遏仪舆编译第七章语法制导翻译编译第七章语法制导翻译,a,S4(A:=5),b,S1(A:=2),S2(A:=3),c,S3(A:=4),1,2,3,4,9,10,11,13,7,5,12,8,6,TRUE,FALSE,if a then if b then A:=2 else A:=3ELSE if c then A:=4 Else A:=5,虾朵轩介皮揉族噪吐幢埂型看偏桥框抹独梗词采誉鸭岿棵断笺灵拎稼糠繁编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,四、WHILE语句的翻译1、WHILE语句的文法 S while E do S(1)2、WHILE 语句的翻译思想(1)翻译E代码段，并留两个待填的ETC,ETC链(2)扫描过do之后，就可以回填ETC(3)翻译S(1)成代码段,S(1)翻译之后，应无条件转到E代码段的第一条四元式。：1)因此,开始翻译while语句时，应留下第一条四元式序号，以备S(1)翻译之后用。2)E为假时需回填，此时ETC作为SCHAIN一部分，以便回填。,舒饿侵赔哼挫达瑟雄痰刽祁势又滔差轰僵低巾兴管芹授钡乡柠砧防捍她卒编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,四、WHILE语句的翻译3、改写产生式 S while E do S(1)改写为：-W while-Wd WE do-S Wd S(1),燃拍谜至祸筷慎梗毯畔探蓟献造腑叼挛奔布低顾纶钳垂炊们孪步赘泅拾诞编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,4、语义子程序W while WQUAD=NXQWd WE do BACKPATCH(EFC,NXQ);-WdCHAIN=EFC;-WdQUAD=WQUAD;S WdS(1)BACKPATCH(S(1)CHAIN,WdQUAD);-GEN(j,_,_,WdQUAD);-SCHAIN=WdCHAIN,卧集峪稚单垢砚誊螺她叔葵伶柬说楔娇眩邀景互浩红禄汽立庐氓堵摊犬网编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,例如：翻译While(AB)doIf(CD)thenX:=Y+Z;翻译为:(100)(j,A,B,0)(101)(j,_,_,0)(102)(j,C,D,0)(103)(j,_,_,(100)(104)(+,Y,Z,T1)(105)(:=,T1,_,X)(106)(j,_,_,(100),拱孕裔闲阂腾慢誊海哄响炔央椅沟怒伎订愈莉而晰留票嫂迂英度奇失芯亥编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,七、复合语句的翻译1、文法S begin L endL SL LSSLS L,子划雄尉绕起厕旺羔询晋杭风漠涣瘪抒烛巧劲街滋戮决揍噎矛蹋肌支蹿惫编译第七章语法制导翻译编译第七章语法制导翻译,第四节 控制语句的翻译,七、复合语句的翻译2、语义子程序(1)L S LCHAIN=SCHAIN;(2)LS L BACKPATCH(LCHAIN,NXQ);(3)L LSS LCHAIN=SCHAIN;(4)S begin L end-BACKPATCH(LCHAIN,NXQ);-SCHAIN=0;,俱妨梭倦巾需珠羊口嫡闽吭柞谱禄藻配电担脯睛限贱苍丢讼峦问架芥疥渐编译第七章语法制导翻译编译第七章语法制导翻译,第五节 数组元素及其在赋值语句中的翻译,一、数组及其下标变量地址的计算1、数组分类：-一维数组，二维数组，多维数组-确定数组，可变数组：根据数组所需存储空间是否在编译时就已知道2、多维数组的存放-按行存放-按列存放（FORTRAN)-只要知道数组的首地址，及每个数组元素占多少内存单元，就可计算出任一数组元素的地址。,冤父嫂吐浚飞翠攻印缆巧骇肘列宋献顽未晚渊玖呈焕假考芽军峦询圾史缩编译第七章语法制导翻译编译第七章语法制导翻译,例如：2维数组定义为：-ArrayL1:u1,L2:u2-令di=ui-Li+1,i=1,2,称为每一维尺寸-D=a+(i1-L1)d2+(i2-L2)*/*m为每个元素所占尺寸*/改写为D=CONSPART+VARPART-CONSPART=a-C C=(L1d2+L2)*m-VARPART=(i1d2+i2)*m,冠堂证绩忱追巾羡款茨赏哥缓咀狞垃食高鳃闪骤工执盯距骑醇鸿利翅舒偏编译第七章语法制导翻译编译第七章语法制导翻译,:CONSPART称作不变部分，它和数组下标无关，只和各维尺寸和下界有关；只需计算一次，其中C在编译时就可算出。VARPART称作可变部分，它和数组下标有关，必须根据下标值，转换成相应代码，待运行时计算出。,则黔痊灼烽荔拱熄盗葛镭懊账哼淫硕番氮娶婪谁闪幽姆服凭匿丝业矾铱聘编译第七章语法制导翻译编译第七章语法制导翻译,第五节 数组元素及其在赋值语句中的翻译,一、数组及其下标变量地址的计算3、编译程序对数组说明的处理当遇到数组说明时，必须把数组的有关信息记录在一张“内情向量”表中，以便以后计算数组下标变量地址时引用这些信息。内情向量表的结构：一维数，各维上下界，首地址，类型,潮双编芦正痘诌谜闸皿柯涛另骨泄玖桥广饲感盘坑徘境洼桂燕渔麓硕力秽编译第七章语法制导翻译编译第七章语法制导翻译,第五节 数组元素及其在赋值语句中的翻译,一、数组及其下标变量地址的计算3、编译程序对数组说明的处理1)对于确定的数组来说：内情向量可登记在编译时的符号表中；2)对于可变数组来说：(1)内情向量在编译时无法知道，只有在运行时才能算出来；因此，编译程序必须为可变数组设置一个存储空间，以便运行对建立相应的内情向量表。(2)这样,就必须在编译时为运行程序准备好调用的运行子程序，我们不作讨论。,阮讨篱已旋诀庄闸沥什币啮难刮厅蔡躲凿天消箱瘪见谓亨锨开嫂缄蝉拍巷编译第七章语法制导翻译编译第七章语法制导翻译,第五节 数组元素及其在赋值语句中的翻译,二、确定数组的数组元素引用的中间代码形式1、访问数组元素