语法制导翻译技术幻灯片.ppt

《语法制导翻译技术幻灯片.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译技术幻灯片.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语法制导翻译技术第1页，共65页，编辑于2022年，星期二例如:表达式A+B*C对运算对象进行类型检查,对变量进行先定义后使用检查如果静态语义正确,语义处理则要执行真正的翻译,即生成程序的某种中间代码的形式或直接生成目标代码。执行真正的翻译执行真正的翻译第5章 语法制导翻译技术和中间代码生成第2页，共65页，编辑于2022年，星期二目前多数编译程序进行语义分析的方法是采用语法制导翻译法采用语法制导翻译法。它不是一种形式系统,但它比较接近形式化。语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。第5章 语法制导翻译技术和中间代码生成第3页，共65页，编辑于2022年，星期二(1)属性对文

2、法的每一个符号,引进一些属性,这些属性代表与文法符号相关的信息,如类型、值、存储位置等。与属性相关的信息,即属性值,可以在语法分析过程中计算和传递。5.2属性文法第5章 语法制导翻译技术和中间代码生成第4页，共65页，编辑于2022年，星期二属性分为两类:综合属性其计算规则按“自下而上”方式进行,即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。属性加工的过程即是语义的处理过程。属性加工的过程即是语义的处理过程。综合属性和继承属性。第5章 语法制导翻译技术和中间代码生成第5页，共65页，编辑于2022年，星期二继承属性其计算规则按“自上而下”方式进行,即规则右部符号的

3、某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算而得。第5章 语法制导翻译技术和中间代码生成第6页，共65页，编辑于2022年，星期二(2)属性文法为文法的每一个规则配备的计算属性的计算规则,称为语义规则(描述语义处理的加工动作)。属性文法包含一个上下文无关文法和一系列语义规则。语义规则:第5章 语法制导翻译技术和中间代码生成第7页，共65页，编辑于2022年，星期二这些语义规则附在文法的每个产生式上,在语法分析过程中,执行语义规则描述的动作,从而实现语义处理。也就是说,附在文法的每个产生式上语义规则描述了语义处理的加工动作。目前流行的语义描述和语义处理的方法主要是属性文法和语法

4、制导翻译方法。第5章 语法制导翻译技术和中间代码生成第8页，共65页，编辑于2022年，星期二G：EE+T|TTT*F|FF(E)|iG：DTLTinteger|realLL,id|id第9页，共65页，编辑于2022年，星期二5.3 语法制导翻译概述语法制导翻译概述为文法的每个产生式都配备一个语义动作或语义子程序。在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作,从而实现语义处理。第5章 语法制导翻译技术和中间代码生成(1)语法制导翻译法的基本思想第10页，共65页，编辑于2022年，星期二SAxya1a2a3aiai+1an语义处理的加工动作语法制导翻译法

5、使用属性文法为工具来说明程序设计语言的语义。第5章 语法制导翻译技术和中间代码生成第11页，共65页，编辑于2022年，星期二(2)语法制导翻译法语法制导翻译法 在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译的方法。第5章 语法制导翻译技术和中间代码生成第12页，共65页，编辑于2022年，星期二为文法每一产生式设计相应的求值的语义描述(语义动作)：例如，设有简单算术表达式的文法：EEE|E*E|(E)|digit1.EE(1)E(2)E.valE(1).valE(2).val2.EE(1)*E(2)E.valE(1).val*

6、E(2).val3.E(E(1)E.valE(1).val4.EdigitE.valLex.digit7+8*5,3+8,6*5,第5章 语法制导翻译技术和中间代码生成第13页，共65页，编辑于2022年，星期二1.EE(1)E(2)E.valE(1).valE(2).val2.EE(1)*E(2)E.valE(1).val*E(2).val3.E(E(1)E.valE(1).val4.EdigitE.valLex.digit句子7+8*5E.val=47E.val=8E.val=40E.val=7E.val=5+5*87EEEEE第14页，共65页，编辑于2022年，星期二5.4编译中常用的

7、中间代码:逆波兰式四元式三元式树形表示第5章 语法制导翻译技术和中间代码生成第15页，共65页，编辑于2022年，星期二逆波兰式逆波兰式 逆波兰式除去了原表达式中的括号，并将运算对象写在前面，运算符写在后面，因而又称为后缀式后缀式。例如：逆波兰式a*bab*(a+b)*(c+d)ab+cd+*中缀表达式第5章 语法制导翻译技术和中间代码生成第16页，共65页，编辑于2022年，星期二逆波兰式表示法同中缀表示法相比其优点是:1.不再有括号,且运算符出现的顺序体现了中缀表达式的运算顺序2.易于计算机处理第5章 语法制导翻译技术和中间代码生成第17页，共65页，编辑于2022年，星期二一般表达式计值

8、时，要处理两类符号，一类是运算对象，另一类是运算符，通常用两个工作栈分别处理。但处理用逆波兰式表示的表达式却只用一个工作栈。第5章 语法制导翻译技术和中间代码生成第18页，共65页，编辑于2022年，星期二当计算机自左到右顺序扫描逆兰波式时，若当前符号是运算对象则进栈，若当前符号是运算符，设为K元运算符，则将栈顶的K个元素依次取出，同时进行K元运算，并将运算结果置于栈顶，表达式处理完毕时，其计算结果自然呈现在栈顶。第5章 语法制导翻译技术和中间代码生成第19页，共65页，编辑于2022年，星期二逆波兰式ab+c*的处理过程如下图：baT1cT1T2第5章 语法制导翻译技术和中间代码生成第20页

9、，共65页，编辑于2022年，星期二逆波兰形式可以推广到其他语法结构：赋值语句V=E逆波兰式VE=条件语句逆波兰式ifES1;elseS2ES1S2￥第5章 语法制导翻译技术和中间代码生成第21页，共65页，编辑于2022年，星期二三元式和树形表示三元式三元式主要由三部分组成：（OP，arg1,arg2）其中OP是运算符，arg1,arg2分别是第一和第二两个运算对象。当OP是一目运算时，常常将运算对象定义为arg1。第5章 语法制导翻译技术和中间代码生成第22页，共65页，编辑于2022年，星期二例如a+b*c的三元式序列：(1)(*,b,c)(2)(+,a,(1)运算对象是指向符号表的某一

10、项或指向三元式表的某一项。第5章 语法制导翻译技术和中间代码生成第23页，共65页，编辑于2022年，星期二1.三元式出现的顺序和语法成份的计值顺序相一致。三元式的特点：2.三元式之间的联系是通过指示器实现的。第5章 语法制导翻译技术和中间代码生成第24页，共65页，编辑于2022年，星期二间接三元式(1)间接三元式表:用来存放各三元式本身。(2)间接码表:按执行各三元式的顺序,依次列出各三元式在三元式表中的位置。注意注意:间接三元式表中不存放重复的间接三元式表中不存放重复的 三元式。三元式。第5章 语法制导翻译技术和中间代码生成第25页，共65页，编辑于2022年，星期二例如语句X=(A+B

11、)*CY=D(A+B)三元式序列(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2)(5)(,D,(4)(4)(+,A,B)(6)(=,Y,(5)间接三元式间接码表三元式表(1)(2)(3)(1)(4)(5)(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2)(4)(,D,(1)(5)(=,Y,(4)第5章 语法制导翻译技术和中间代码生成第26页，共65页，编辑于2022年，星期二树形表示A*B+C*D+C*A*BD末端结点表示一个运算对象,每一个内结点表示一个一元或二元运算符。树形表示是三元式的翻版(3)+(1)*(2)*CABD第5章 语法制导翻译技术和中间代码

12、生成第27页，共65页，编辑于2022年，星期二四元式四元式主要由四部分组成：（OP，arg1,arg2,result）其中OP是运算符，arg1,arg2分别是第一和第二两个运算对象。当OP是一目运算时，常常将运算对象定义为arg1。第5章 语法制导翻译技术和中间代码生成第28页，共65页，编辑于2022年，星期二四元式的第四个分量result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。例如Xa*bc/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X)第5章 语法

13、制导翻译技术和中间代码生成第29页，共65页，编辑于2022年，星期二2.四元式之间的联系是通过临时变量实现的，这样易于调整和变动四元式。1.四元式出现的顺序和语法成份的计值顺序相一致。四元式的特点：3.便于优化处理。第5章 语法制导翻译技术和中间代码生成四元式还可以表示条件的转移(ifabgoto0)(goto0)第30页，共65页，编辑于2022年，星期二编译系统中，有时将四元式表示成另一种更直观，更易理解的形式三地址代码或三地址语句。result:arg1OParg2三地址语句三地址语句:语句中是三个量的赋值语句,每个量占一个地址。三地址代码形式定义为：第5章 语法制导翻译技术和中间代码

14、生成第31页，共65页，编辑于2022年，星期二例如Xa*bc/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X)相应的三地址语句序列为：（1）T1a*b（2）T2c/d（3）T3T1T2（4）XT3第5章 语法制导翻译技术和中间代码生成第32页，共65页，编辑于2022年，星期二例1.a+b*(c+d)的逆波兰式abcd+*+第5章 语法制导翻译技术和中间代码生成第33页，共65页，编辑于2022年，星期二t1=at2=ct3=t2+dt5=t1+t4a+b*(c+d)的四元式表示t4=b*t3第5章 语法制导翻译技术

15、和中间代码生成第34页，共65页，编辑于2022年，星期二i(i/(ii)的逆波兰式i(i/(ii)的四元式t1=iit2=i/t1t3=it2iiii/例2.第5章 语法制导翻译技术和中间代码生成第35页，共65页，编辑于2022年，星期二语义函数emit（Targ1 OP arg2）功能是生成一个三地址语句，并送到输出文件中。语义函数newtemp()功能是产生一个新的临时变量名字，并回送新的临时变量名的整数码。如T1，T2等。5.5.1简单算术表达式和赋值语句的翻译第36页，共65页，编辑于2022年，星期二(2)不进符号表，临时变量单词值部分用整数码表示。(1)送到符号表。对临时变量有

16、两种不同的处理方法:第5章 语法制导翻译技术和中间代码生成第37页，共65页，编辑于2022年，星期二语义过程Lookup（i.name）功能是审查i.name是否出现在符号表中，在则返回其指针，否则返回NULL。语义变量E.place表示存放非终结符E值的变量名在符号表中的入口地址或临时变量名的整数码。第5章 语法制导翻译技术和中间代码生成第38页，共65页，编辑于2022年，星期二 1.E E(1)E(2)2.E E(1)*E(2)E.placenewtemp();emit(E.placeE(1).placeE(2).place)E.placenewtemp();emit(E.placeE

17、(1).place*E(2).place)第5章 语法制导翻译技术和中间代码生成3.E（E(1)）E.placeE(1).place；第39页，共65页，编辑于2022年，星期二4.E i pLookup(i.name);if(p!=NULL)E.placep;elseerror();第5章 语法制导翻译技术和中间代码生成5.Ai=EpLookup(i.name);if(p!=NULL)emit(pE.place;)elseerror();第40页，共65页，编辑于2022年，星期二5.5.2布尔表达式到四元式的翻译一.布尔表达式的文法计算逻辑值程序设计语言中布尔表达式有两个作用:用作控制语句

18、中的条件式布尔表达式是由布尔算符(、和)施于布尔变量或关系表达式而成。第41页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译EE(1)E(2)EE(1)E(2)EE(1)E(E(1)Ei(1)ropi(2)Ei第42页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译二.布尔表达式的计值方法1.如同计算算术表达式一样,步步计算出各部分真、假值,最后计算出整个表达式的值。2.根据布尔运算的特殊性,采取某种优化措施,可避免计算整个表达式的值。第43页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译AB解释成AB解释成A解释成ifAthentrueelseBifA

19、thenBelsefalseifAthenfalseelsetrue三.布尔表达式的翻译方法1.同翻译算术表达式一样,翻译布尔表达式。第44页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译1.EE(1)E(2)E.placenewtemp()；emit(E.placeE(1).placeE(2).place)2.EE(1)E(2)E.placenewtemp()；emit(E.placeE(1).placeE(2).place)第45页，共65页，编辑于2022年，星期二3.E(E(1)E.placeE(1).place；4.Ei(1)ropi(2)E.placenewtemp(

20、)；emit(ifi(1).placerop.opi(2).placegotonextq+3);emit(E.place0);emit(gotonextq+2);emit(E.place1);E.placei.place；5.Ei第46页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译例如布尔表达式a=bcd对应如下四元式序列:101ifa=bgoto104102t1=0103goto105104t1=1105t2=cd106t3=t1t2第47页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译2.控制语句中布尔表达式的翻译条件语句的语法为:根据条件语句的语义,条件语句

21、的代码结构为:ifEthenS(1)elseS(2)E的代码S(1)的代码S(2)的代码Jumpoutout:真假第48页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译E是布尔表达式,根据布尔运算的特殊性,布尔表达式的目标结构为:假E(1)的代码E(2)的代码真S(1)S(2)真假真E(1)的代码E(2)的代码假S(2)S(1)假真第49页，共65页，编辑于2022年，星期二(1)真出口和假出口:真出口表示布尔表达式E为真时控制流向的转移目标假出口表示布尔表达式E为假时控制流向的转移目标布尔表达式到四元式的翻译第50页，共65页，编辑于2022年，星期二(2)作为条件转移的E,把

22、E翻译成的代码是一串条件转或无条件转的四元式对于E为aropb的形式生成代码为:ifaropbgoto真出口goto假出口布尔表达式到四元式的翻译第51页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译布尔表达式的真、假出口不能在产生其四元式的同时得知E.true:记录表达式E所对应的四元式需回填真出口的四元式的地址所构成的链E.false:记录表达式E所对应的四元式需回填假出口的四元式的地址所构成的链(3)设置两个语义变量:第52页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译把以p1,p2为链首的两条链合并为一,返回合并后的链首(4)链结函数和回填函数:merge

23、(p1,p2):backpatch(intp,intt):将p所链结的每个四元式的第四区分量都回填t;第53页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译(5)为及时回填转移地址,使用语义变量E.bcode记录表达式E的第一个四元式语句序号。(6)定义语义变量nextq为四元式表指针。第54页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译布尔表达式语义动作的设计1.EE(1)E(2)backpatch(E(1).false,E(2).bcode)；E.bcode=E(1).bcode;E.true=merge(E(1).true,E(2).true);E.fals

24、e=E(2).false;第55页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译布尔表达式语义动作的设计2.EE(1)E(2)backpatch(E(1).true,E(2).bcode)；E.bcode=E(1).bcode;E.true=E(2).true;E.false=merge(E(1).false,E(2).false);第56页，共65页，编辑于2022年，星期二布尔表达式语义动作的设计3.EE(1)E.bcode=E(1).bcode;E.true=E(1).false;E.false=E(1).true;布尔表达式到四元式的翻译4.E(E(1)E.bcode=E

25、(1).bcode;E.true=E(1).true;E.false=E(1).false;第57页，共65页，编辑于2022年，星期二布尔表达式语义动作的设计5.Ei(1)ropi(2)E.true=nextq;E.bcode=nextq;E.false=nextq+1;emit(ifi(1).placerop.opi(2).placegoto0);emit(goto0);布尔表达式到四元式的翻译第58页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译布尔表达式语义动作的设计6.EiE.true=nextq;E.false=nextq+1;E.bcode=nextq;emit(i

26、fi.placegoto0);emit(goto0);第59页，共65页，编辑于2022年，星期二布尔表达式到四元式的翻译例如布尔表达式abcd的翻译过程第60页，共65页，编辑于2022年，星期二5.5.3 控制语句的翻译1.SifEthenS(1)2.|ifEthenS(1)elseS(2)3.|whileEdoS(1)4.LL；S5.|S第61页，共65页，编辑于2022年，星期二CifEthenSCS(1)CifEthenbackpatch(E.true,nextq);C.chain=E.false1、单分支条件句：SCS(1)S.chain=merge(C.chain,S(1).chain)例：ifay then x=x+1 else y=y+1 if A v B3doa=a+3*bwhile A B6)thenx=x-1elsey=x+1第64页，共65页，编辑于2022年，星期二4、语句组：LLsSLsL;LSLSL.chain=S.chainLsL;backpatch(L.chain,nextq)LLsSL.chain=S.chain第65页，共65页，编辑于2022年，星期二