语法制导翻译技术市公开课金奖市赛课一等奖课件

语义分析任务：静态语义审查审查每个语法结构静态语义,即验证语法结构合法程序,是否真正故意义。第5章语法制导翻译技术和中间代码生成5.1概述第1页第1页比如:表示式A+B*C对运算对象进行类型检查,对变量进行先定义后使用检查假如静态语义正确,语义处理则要执行真正翻译,即生成程序某种中间代码形式或直接生成目的代码。执行真正翻译第5章语法制导翻译技术和中间代码生成第2页第2页当前多数编译程序进行语义分析办法是采用语法制导翻译法

。它不是一个形式系统,但它比较靠近形式化。

语法制导翻译法使用属性文法为工具来描述程序设计语言语义。第5章语法制导翻译技术和中间代码生成第3页第3页(1)属性对文法每一个符号,引进一些属性,这些属性代表与文法符号相关信息,如类型、值、存储位置等。与属性相关信息,即属性值,能够在语法分析过程中计算和传递。5.2属性文法第5章语法制导翻译技术和中间代码生成第4页第4页属性分为两类:综合属性其计算规则按“自下而上”方式进行,即规则左部符号一些属性依据其右部符号属性和(或)自己其它属性计算而得。属性加工过程即是语义处理过程。综合属性和继承属性。第5章语法制导翻译技术和中间代码生成第5页第5页继承属性其计算规则按“自上而下”方式进行,即规则右部符号一些属性依据其左部符号属性和(或)右部其它符号一些属性计算而得。第5章语法制导翻译技术和中间代码生成第6页第6页(2)属性文法为文法每一个规则配备计算属性计算规则,称为语义规则(描述语义处理加工动作)。属性文法包括一个上下文无关文法和一系列语义规则。语义规则:第5章语法制导翻译技术和中间代码生成第7页第7页这些语义规则附在文法每个产生式上,在语法分析过程中,执行语义规则描述动作,从而实现语义处理。也就是说,附在文法每个产生式上语义规则描述了语义处理加工动作。当前流行语义描述和语义处理办法主要是属性文法和语法制导翻译办法。第5章语法制导翻译技术和中间代码生成第8页第8页G：E→E+T|TT→T*F|FF→(E)|iG：D→TLT→integer|realL→L,id|id

第9页第9页5.3语法制导翻译概述

为文法每个产生式都配备一个语义动作或语义子程序。在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式语义动作,从而实现语义处理。第5章语法制导翻译技术和中间代码生成(1)语法制导翻译法基本思想第10页第10页S→……{……}………A→xy{……}………

a1a2a3…aiai+1…an语义处理加工动作语法制导翻译法使用属性文法为工具来阐明程序设计语言语义。第5章语法制导翻译技术和中间代码生成第11页第11页(2)语法制导翻译法在语法分析过程中，依随分析过程，依据每个产生式所相应语义子程序(或语义规则描述语义处理加工动作)进行翻译办法。第5章语法制导翻译技术和中间代码生成第12页第12页为文法每一产生式设计相应求值语义描述(语义动作)：比如，设有简朴算术表示式文法：

E→E＋E|E*E|(E)|digit1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}{7+8*5,3+8,6*5,…}第5章语法制导翻译技术和中间代码生成第13页第13页1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}句子7+8*5E.val=47E.val=8E.val=40E.val=7E.val=5+5*87EEEEE第14页第14页 5.4

编译中惯用中间代码:逆波兰式四元式三元式树形表示第5章语法制导翻译技术和中间代码生成第15页第15页逆波兰式

逆波兰式除去了原表示式中括号，并将运算对象写在前面，运算符写在后面，因而又称为后缀式。比如：逆波兰式a*bab*(a+b)*(c+d)ab+cd+*中缀表示式第5章语法制导翻译技术和中间代码生成第16页第16页逆波兰式表示法同中缀表示法相比其长处是:不再有括号,且运算符出现顺序体现了中缀表示式运算顺序2.易于计算机处理第5章语法制导翻译技术和中间代码生成第17页第17页普通表示式计值时，要处理两类符号，一类是运算对象，另一类是运算符，通惯用两个工作栈分别处理。但处理用逆波兰式表示表示式却只用一个工作栈。第5章语法制导翻译技术和中间代码生成第18页第18页当计算机自左到右顺序扫描逆兰波式时，若当前符号是运算对象则进栈，若当前符号是运算符，设为K元运算符，则将栈顶K个元素依次取出，同时进行K元运算，并将运算结果置于栈顶，表示式处理完毕时，其计算结果自然呈现在栈顶。第5章语法制导翻译技术和中间代码生成第19页第19页逆波兰式ab+c*处理过程以下图：baT1cT1T2第5章语法制导翻译技术和中间代码生成第20页第20页逆波兰形式能够推广到其它语法结构：赋值语句V=E逆波兰式VE=条件语句逆波兰式ifES1;elseS2ES1S2￥第5章语法制导翻译技术和中间代码生成第21页第21页三元式和树形表示三元式主要由三部分构成：（OP，arg1,arg2）其中OP是运算符，arg1,arg2分别是第一和第二两个运算对象。当OP是一目运算时，经常将运算对象定义为arg1。第5章语法制导翻译技术和中间代码生成第22页第22页比如a+b*c三元式序列：(1)(*,b,c)(2)(+,a,(1))运算对象是指向符号表某一项或指向三元式表某一项。第5章语法制导翻译技术和中间代码生成第23页第23页1.三元式出现顺序和语法成份计值顺序相一致。三元式特点：2.三元式之间联系是通过批示器实现。第5章语法制导翻译技术和中间代码生成第24页第24页间接三元式(1)间接三元式表:用来存储各三元式本身。(2)间接码表:按执行各三元式顺序,依次列出各三元式在三元式表中位置。注意:间接三元式表中不存储重复三元式。第5章语法制导翻译技术和中间代码生成第25页第25页比如

语句X=(A+B)*C

Y=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页第26页树形表示

A*B+C*D+C*A*BD末端结点表示一个运算对象,每一个内结点表示一个一元或二元运算符。树形表示是三元式翻版(3)+(1)*(2)*CABD第5章语法制导翻译技术和中间代码生成第27页第27页四元式主要由四部分构成：（OP，arg1,arg2,result）其中OP是运算符，arg1,arg2分别是第一和第二两个运算对象。当OP是一目运算时，经常将运算对象定义为arg1。第5章语法制导翻译技术和中间代码生成第28页第28页四元式第四个分量result是编译程序为存储中间运算结果而暂时引进变量，常称为暂时变量，如Ti，也能够是用户自定义变量，如X。比如X＝a*b＋c/d四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)第5章语法制导翻译技术和中间代码生成第29页第29页2.四元式之间联系是通过暂时变量实现，这样易于调整和变动四元式。1.四元式出现顺序和语法成份计值顺序相一致。四元式特点：3.便于优化处理。第5章语法制导翻译技术和中间代码生成四元式还能够表示条件转移(ifa>bgoto0)(goto0)第30页第30页编译系统中，有时将四元式表示成另一个更直观，更易理解形式——三地址代码或三地址语句。result:＝arg1OParg2

三地址语句:语句中是三个量赋值语句,每个量占一个地址。三地址代码形式定义为：第5章语法制导翻译技术和中间代码生成第31页第31页比如X＝a*b＋c/d四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)相应三地址语句序列为：（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

第5章语法制导翻译技术和中间代码生成第32页第32页例1.–a+b*(–c+d)逆波兰式a@bc@d+*+第5章语法制导翻译技术和中间代码生成第33页第33页t1=@a

t2=@c

t3=t2+dt5=t1+t4

–a+b*(–c+d)四元式表示

t4=b*t3第5章语法制导翻译技术和中间代码生成第34页第34页i↑(i/(i–i))逆波兰式

i↑(i/(i–i))四元式

t1=i–i

t2=i/t1t3=i↑t2iiii–/↑例2.第5章语法制导翻译技术和中间代码生成第35页第35页语义函数emit（T＝arg1OParg2）

功效是生成一个三地址语句，并送到输出文献中。语义函数newtemp()

功效是产生一个新暂时变量名字，并回送新暂时变量名整数码。如T1，T2等。5.5.1简朴算术表示式和赋值语句翻译第36页第36页(2)不进符号表，暂时变量单词值部分用整数码表示。(1)送到符号表。对暂时变量有两种不同处理方法:第5章语法制导翻译技术和中间代码生成第37页第37页语义过程Lookup（）

功效是审查是否出现在符号表中，在则返回其指针，不然返回NULL。语义变量E.place

表示存储非终止符E值变量名在符号表中入口地址或暂时变量名整数码。第5章语法制导翻译技术和中间代码生成第38页第38页1.E→E(1)＋E(2)2.E→E(1)*E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}{E.place＝newtemp();emit(E.place’＝’E(1).place’*’E(2).place)}第5章语法制导翻译技术和中间代码生成3.E→（E(1)）{E.place＝E(1).place；}第39页第39页4.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}第5章语法制导翻译技术和中间代码生成5.A→i=E

{p＝Lookup();if(p!=NULL)emit(p’＝’E.place;)elseerror();}第40页第40页5.5.2布尔表示式到四元式翻译一.布尔表示式文法

●计算逻辑值程序设计语言中布尔表示式有两个作用:

●用作控制语句中条件式布尔表示式是由布尔算符(∧、∨和)施于布尔变量或关系表示式而成。

第41页第41页布尔表示式到四元式翻译

E→E(1)∨E(2)

E→E(1)∧E(2)

E→

E(1)

E→(E(1))

E→i(1)ropi(2)

E→i第42页第42页布尔表示式到四元式翻译二.布尔表示式计值办法1.如同计算算术表示式同样,步步计算出各部分真、假值,最后计算出整个表示式值。2.依据布尔运算特殊性,采用某种优化办法,可避免计算整个表示式值。第43页第43页布尔表示式到四元式翻译

A∨B解释成

A∧B解释成

A解释成ifAthentrueelseBifAthenBelsefalseifAthenfalseelsetrue三.布尔表示式翻译办法1.同翻译算术表示式同样,翻译布尔表示式。第44页第44页布尔表示式到四元式翻译1.E→E(1)∨E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∨’E(2).place)}2.E→E(1)∧E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∧’E(2).place)}第45页第45页3.E→(E(1)){E.place＝E(1).place；}4.E→i(1)ropi(2){E.place＝newtemp()；emit(‘if’i(1).placerop.opi(2).place‘goto’nextq+3);emit(E.place’＝’‘0’);emit(gotonextq+2);emit(E.place’＝’‘1’);}{E.place＝i.place；}5.E→i

第46页第46页布尔表示式到四元式翻译比如布尔表示式a=b∨c∧d相应下列四元式序列:101ifa=bgoto104102t1=0103goto105104t1=1105t2=c∧d106t3=t1∨

t2

第47页第47页布尔表示式到四元式翻译2.控制语句中布尔表示式翻译条件语句语法为:依据条件语句语义,条件语句代码结构为:ifEthenS(1)elseS(2)E代码S(1)代码S(2)代码Jumpout

out:

真

假第48页第48页布尔表示式到四元式翻译

E是布尔表示式,依据布尔运算特殊性,布尔表示式目的结构为:假E(1)代码∨E(2)代码真S(1)S(2)真假真E(1)代码∧E(2)代码假S(2)S(1)假真第49页第49页(1)真出口和假出口:真出口表示布尔表示式E为真时控制流向转移目的假出口表示布尔表示式E为假时控制流向转移目的布尔表示式到四元式翻译第50页第50页(2)作为条件转移E,把E翻译成代码是一串条件转或无条件转四元式对于E为aropb形式生成代码为:ifaropbgoto真出口goto假出口布尔表示式到四元式翻译第51页第51页布尔表示式到四元式翻译布尔表示式真、假出口不能在产生其四元式同时得知E.true:统计表示式E所相应四元式需回填真出口四元式地址所构成链E.false:统计表示式E所相应四元式需回填假出口四元式地址所构成链(3)设置两个语义变量:第52页第52页布尔表示式到四元式翻译把以p1,p2为链首两条链合并为一,返回合并后链首(4)链结函数和回填函数:●merge(p1,p2):●backpatch(intp,intt):

将p所链结每个四元式第四区别量都回填t;第53页第53页布尔表示式到四元式翻译为及时回填转移地址,使用语义变量

E.bcode统计表示式E第一个四元式语句序号。(6)定义语义变量nextq为四元式表指针。第54页第54页布尔表示式到四元式翻译布尔表示式语义动作设计1.E→E(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.false=E(2).false;}第55页第55页布尔表示式到四元式翻译布尔表示式语义动作设计2.E→E(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页第56页布尔表示式语义动作设计3.E→

E(1){E.bcode=E(1).bcode;E.true=E(1).false

;E.false=E(1).true;}布尔表示式到四元式翻译

4.E→(E(1)){E.bcode=E(1).bcode;E.true=E(1).true;E.false=E(1).false;}第57页第57页布尔表示式语义动作设计

5.E→i(1)ropi(2){E.true=nextq;E.bcode=nextq;E.false=nextq+1;emit(ifi(1).placerop.opi(2).placegoto0);emit(goto0);}布尔表示式到四元式翻译第58页第58页布尔表示式到四元式翻译布尔表示式语义动作设计

6.E→i{E.true=nextq;E.false=nextq+1;E.bcode=nextq;emit(ifi.placegoto0);emit(goto0);}第59页第59页布尔表示式到四元式翻译比如布尔表示式a<b∨c<d翻译过程第60页第60页5.5.3控制语句翻译1.S→ifEthenS(1)2.

|ifEthenS(1)

elseS(2)3.

|whileEdoS(1)

4.

L→L；S5.

|S第61页第61页C→ifEthenS→CS(1)C→ifEthen{backpatch(E.true,nextq);C.chain=E.false}1、单分支条件句：S→CS(1){S.chain=merge(C.chain,S(1).chain)}例：ifa<bthena=b第62页第62页2、双分支if语句：C→ifE