《语法制导翻译和中间代码课件.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码课件.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、语法制导翻译和中间代码第1页，此课件共72页哦本章内容本章内容8.1 8.1 属性文法属性文法8.2 8.2 语法制导翻译概论语法制导翻译概论8.3 8.3 中间代码的形式中间代码的形式8.4 8.4 简单赋值语句的翻译简单赋值语句的翻译8.5 8.5 布尔表达式的翻译布尔表达式的翻译8.6 8.6 控制结构的翻译控制结构的翻译8.7 8.7 说明语句的翻译说明语句的翻译8.8 8.8 数组和结构的翻译符号表数组和结构的翻译符号表第2页，此课件共72页哦 编译程序的任务编译程序的任务是将汇编语言或高级语言书写成是将汇编语言或高级语言书写成的源程序转换成等价的目标代码程序。其中要求目的源程序转换
2、成等价的目标代码程序。其中要求目标代码程序和源程序的语义标代码程序和源程序的语义(Semantics(Semantics）必须相同。）必须相同。什么是语义？什么是语义？程序的语义就是它的程序的语义就是它的“意思意思”。语义分析的任务包括两方面语义分析的任务包括两方面:一个是静态语义检查一个是静态语义检查;一个是动态语义的解释执行（通俗地说就是计算并生成一个是动态语义的解释执行（通俗地说就是计算并生成中间代码。中间代码。8.1 8.1 属性文法属性文法第3页，此课件共72页哦一、静态语义分析或静态语义审查一、静态语义分析或静态语义审查语义分析的工作语义分析的工作:包括：包括：（1）类型检查。根据
3、类型相容性要求，验证程序中）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。必须报告不符合类型系统的信息。（2）控制流检查。控制流语句必须使控制转移到合法的地方。）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在例如，在C语言中语言中break语句使控制跳离包括该语句的最小语句使控制跳离包括该语句的最小while、for或或switch语句。如果不存在包括它的这样的语句，语句。如果不存在包括它的这样的语句，则报错。则报错。（3）一致性检查。）一致性检查。（4）
4、上下文相关性检查。比如，变量名字必须先声明后引用；）上下文相关性检查。比如，变量名字必须先声明后引用；(5)名字的作用域分析名字的作用域分析例例例例第4页，此课件共72页哦二、动态语义处理二、动态语义处理 如果静态语义正确，语义处理则执行真正的如果静态语义正确，语义处理则执行真正的翻译（动态语义）翻译（动态语义）即：生成程序的一种即：生成程序的一种中间表中间表示形式或生成实际的目标代码。示形式或生成实际的目标代码。中间代码中间代码(中间语言中间语言)是介于源语言和机器语言的一种表示是介于源语言和机器语言的一种表示形式。形式。通常语义分析生成中间代码的原因：通常语义分析生成中间代码的原因：便于移
5、植：中间代码相对独立于目标机，在编译程序移便于移植：中间代码相对独立于目标机，在编译程序移植时编译前端保持不变。植时编译前端保持不变。利于优化：将优化分为与目标机无关的中间代码优化，利于优化：将优化分为与目标机无关的中间代码优化，以及与目标机相关的目标代码的优化，使优化更加细以及与目标机相关的目标代码的优化，使优化更加细致有效。致有效。第7页，此课件共72页哦 语义分析的整个过程和词法及语法分析相类似。语义分析的整个过程和词法及语法分析相类似。例如例如,在语法分析中，使用在语法分析中，使用BackusNausBackusNaus范式范式(BNF)(BNF)中的上中的上下文无关文法描述语法结构，
6、并用各种自顶向下和下文无关文法描述语法结构，并用各种自顶向下和自底向上的分析算法实现语法结构。由于没有标准自底向上的分析算法实现语法结构。由于没有标准的方法的方法(如如BNF)BNF)来说明语言的静态语义，因此语义分析就来说明语言的静态语义，因此语义分析就没有这么简单。常采用没有这么简单。常采用属性文法属性文法(attribute grammar)(attribute grammar)来来描述语义描述语义。语义的形式化描述语义的形式化描述第8页，此课件共72页哦8.18.1属性文法属性文法一、属性（一、属性（Attribute Attribute ）属性翻译文法属性翻译文法是在上下文无关文法的
7、基础上，为是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相每个文法符号（终结符或非终结符）配备若干相关的关的“值值”（称为（称为属性属性）。）。属性属性代表与文法符号相关信息，例如它的类型、值、代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程。对于文法的。对于文法的每个产生式都配备了一组属性的计算规则，每个产生式都配备了一组属性的计算规则，称为称为语义规则。语义规则。第9页，此课件共72页哦
8、二、属性文法二、属性文法（AttributeGrammar）的定义的定义 一个属性文法是一个一个属性文法是一个三元组三元组A A(G,V,F)(G,V,F)，其，其中：中：uG G为一为一上下文无关文法上下文无关文法 。uV V为为属性的有穷集属性的有穷集。uF F是关于属性的断言或一组属性的计算规则是关于属性的断言或一组属性的计算规则(称为称为语义规则语义规则)。第10页，此课件共72页哦属性文法的表示分两部分属性文法的表示分两部分：首先首先在上下文无关文法中，在上下文无关文法中，对于每个文法符号引对于每个文法符号引进相关的属性符号；进相关的属性符号；其次对于每个产生式写出计算属性值的计算规
9、则其次对于每个产生式写出计算属性值的计算规则（即（即语义规则）语义规则）,来描述各属性间的关系。来描述各属性间的关系。形式为：形式为：文法规则文法规则 语义规则语义规则规则规则1 1 相关的属性等式相关的属性等式 .规则规则n n 相关的属性等式相关的属性等式第11页，此课件共72页哦【例例】用属性文法表示简单的无符号整数文法：用属性文法表示简单的无符号整数文法：number number digit|digitnumber number digit|digitdigit 0|1|2|3|4|5|6|7|8|9digit 0|1|2|3|4|5|6|7|8|9【分析分析】一个数最重要的属性是它
10、的值，将其命名为一个数最重要的属性是它的值，将其命名为valval。每个数字。每个数字都有一个值，可以用它表示的实际数直接计算。都有一个值，可以用它表示的实际数直接计算。1 1、文法规则：、文法规则：digit0digit0 语义规则：语义规则：digit.val=0digit.val=0 2 2、文法规则：、文法规则：number digitnumber digit 语义规则：语义规则：number.val=digit.valnumber.val=digit.val。3 3、文法规则、文法规则number number digitnumber number digit,必须表示出这个文法规则
11、必须表示出这个文法规则左边符号的值和右边符号的值之间的关系。通过使用下标进左边符号的值和右边符号的值之间的关系。通过使用下标进行区分，将文法写成如下形式：行区分，将文法写成如下形式：number1 number2 digitnumber1 number2 digit语义规则：语义规则：number1.val:=number2.val*10+digit.valnumber1.val:=number2.val*10+digit.val第12页，此课件共72页哦三、属性的分类三、属性的分类（1）综合属性综合属性：用于：用于“自下而上自下而上”传递信息传递信息 分析树中，如果一个结点的属性值是通过子结
12、分析树中，如果一个结点的属性值是通过子结点的属性值计算得到则称综合属性。点的属性值计算得到则称综合属性。（2）继承属性继承属性：用于：用于“自上而下自上而下”传递信息传递信息 分析树中，如果一个结点的属性值由该结点的父分析树中，如果一个结点的属性值由该结点的父结点和结点和/或兄弟结点定义的则称继承属性。或兄弟结点定义的则称继承属性。第13页，此课件共72页哦四、语义规则四、语义规则 在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都有一都有一套与之相关联的语义规则，每条规则的形式为：套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,ck)这里，这里，f是一
13、个函数，而且或者是一个函数，而且或者1）b是是A的的一一个个综综合合属属性性并并且且c1,c2,ck是是产产生生式式右右边边文法符号的属性，或者文法符号的属性，或者2）b是是产产生生式式右右边边某某个个文文法法符符号号的的一一个个继继承承属属性性并并且且c1,c2,ck 是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。属性属性b依赖于属性依赖于属性c1,c2,ck。第14页，此课件共72页哦说明：说明：n终结符只有综合属性，由词法分析器提供终结符只有综合属性，由词法分析器提供n非非终终结结符符既既可可有有综综合合属属性性也也可可有有继继承承属属性性，文文法法开开始符号的所
14、有继承属性作为属性计算前的初始值始符号的所有继承属性作为属性计算前的初始值n对对出出现现在在产产生生式式右右边边的的继继承承属属性性和和出出现现在在产产生生式式左左边边的的综综合合属属性性都都必必须须提提供供一一个个计计算算规规则则。属属性性计计算算规规则中只能使用相应产生式中的文法符号的属性则中只能使用相应产生式中的文法符号的属性n出出现现在在产产生生式式左左边边的的继继承承属属性性和和出出现现在在产产生生式式右右边边的的综综合合属属性性不不由由所所给给的的产产生生式式的的属属性性计计算算规规则则进进行行计计算算，它它们们由由其其它它产产生生式式的的属属性性规规则则计计算算或或者者由由属属性
15、性计计算算器器的的参参数数提提供供第15页，此课件共72页哦【例例8.1】算术表达式求值的语义描述算术表达式求值的语义描述:产产生式生式语义规则语义规则LEprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.valF.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val=digit.lexval语义过程语义过程L的属性为空的属性为空E、T、F的的val为综合属性为综合属性digit仅有综合属性仅有综合属性由词法分析程序提供由词法分析程序提供第16页，此课件共72页哦【例例8.2】带
16、有继承属性带有继承属性L.inL.in的语义规则的语义规则 产生式产生式语义规则语义规则DTLL in:=T typeTintT type:=intTrealT type:=realLL1,idL1 in:=L inaddtype(id entry,L in)Lidaddtype(id entry,L in)第17页，此课件共72页哦8.2 8.2 语法制导翻译概论语法制导翻译概论u语法制导翻译法语法制导翻译法 在语法分析的基础上进行边分析边翻译。在语法分析的基础上进行边分析边翻译。注：注：1 1）语法制导翻译时会根据文法产生式右部符号串）语法制导翻译时会根据文法产生式右部符号串的含义，进行翻
17、译，翻译的结果是生成相应中间代的含义，进行翻译，翻译的结果是生成相应中间代码。码。2 2）语法制导翻译的依据是语义子程序。）语法制导翻译的依据是语义子程序。3 3）具体做法：为每个产生式配置一个语义子程序，）具体做法：为每个产生式配置一个语义子程序，当语法分析进行归约或推导时，调用语义子程序，当语法分析进行归约或推导时，调用语义子程序，完成一部分翻译任务。完成一部分翻译任务。4 4）语法分析完成，翻译工作也结束。）语法分析完成，翻译工作也结束。第18页，此课件共72页哦语法制导翻译过程通常是这样的：语法制导翻译过程通常是这样的：1)1)对单词符号串进行语法分析，构造语法分析树对单词符号串进行语
18、法分析，构造语法分析树;2)2)从语法分析树得到描述节点属性间依赖关从语法分析树得到描述节点属性间依赖关系的依赖图系的依赖图;3)3)由此依赖图得到语义规则的计算次序由此依赖图得到语义规则的计算次序;进行语进行语义规则计算，得到翻译结果义规则计算，得到翻译结果可表示为：可表示为：输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序 第19页，此课件共72页哦u 在一棵语法树中结点的继承属性和综合属性之间的相互在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖关系可以用称作依赖图依赖图的一个有向图来描述。的一个有向图来描述。u在为一棵语法树构造依赖图以前，为每
19、一个包含过在为一棵语法树构造依赖图以前，为每一个包含过程调用的语义规则引入一个虚综合属性程调用的语义规则引入一个虚综合属性b b，这样把每，这样把每一个语义规则都写成如下形式：一个语义规则都写成如下形式：b:=f(cb:=f(c1 1,c,c2 2,c ck k)u依赖图中为每一个属性设置一个结点，如果属性依赖图中为每一个属性设置一个结点，如果属性b b依赖属依赖属性性c c，则从属性，则从属性c c的结点有一条有向边连到属性的结点有一条有向边连到属性b b的结点。的结点。依赖图依赖图第20页，此课件共72页哦 for分析树中每一个结点分析树中每一个结点n do for 结点的文法符号的每一个
20、属性结点的文法符号的每一个属性a do 为为a在依赖图中建立一个结点；在依赖图中建立一个结点；for 分析树中每一个结点分析树中每一个结点n do for结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b:=f(c1,c2,ck)do for i:=1 to k do 从从ci结点到结点到b结点构造一条有向边结点构造一条有向边 对于给定的一棵语法分析树、依赖图是按下面步骤对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：构造出来的：第21页，此课件共72页哦【例如例如】属性属性 A.a:=f(X.x,Y.y)A.a:=f(X.x,Y.y)对应于产生式对应于产生式
21、A AXYXY的语义规则的语义规则,这条语义这条语义规则确定了依赖于属性规则确定了依赖于属性X.xX.x和和Y.yY.y的综合属的综合属性性A.aA.a。如果在语法树中应用这个产生式，如果在语法树中应用这个产生式，那么在依赖图中会有三个结点那么在依赖图中会有三个结点A.a,X.x,A.a,X.x,和和Y.yY.y。由于。由于A.aA.a依赖依赖X.xX.x，所以有一条有向边从，所以有一条有向边从X.xX.x到到A.a.A.a.由于由于A.aA.a也依赖于也依赖于Y.yY.y，所以还有一，所以还有一条有向边从条有向边从Y.yY.y连到连到A.a.A.a.如果与产生式如果与产生式A AXYXY对应
22、的语义规则还有：对应的语义规则还有：X.i:=g(A.a,Y.y)X.i:=g(A.a,Y.y)那么，图中还应有两条有向边，一条从那么，图中还应有两条有向边，一条从A.aA.a连到连到X.iX.i，另一条从，另一条从Y.yY.y连到连到X.iX.i,因为因为X.iX.i依赖于依赖于A.aA.a和和Y.y.Y.y.A.aA.aX.xX.xY.yY.yX.iX.i第22页，此课件共72页哦 如果一属性文法不存在属性之间的循环依如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。译程序，我们只处理良定
23、义的属性文法。第23页，此课件共72页哦8.2.2 S-8.2.2 S-属性文法的自下而上计算属性文法的自下而上计算1、S-属性文法属性文法n仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性文法属性文法n综合属性可以在分析输入符号串的同时由自下而上的综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。分析器来计算。n分析器可以保存与栈中文法符号有关的综合属性值，每分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。边符号的属性值来计算。第24页，此课件共7
24、2页哦2、S-属性文法的翻译器属性文法的翻译器n S-属性文法的翻译器通常可借助属性文法的翻译器通常可借助LR分析器来实现分析器来实现n 在分析栈中使用一个附加的域来存放综合属性值在分析栈中使用一个附加的域来存放综合属性值 n假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式是对应于产生式AXYZ的的 第25页，此课件共72页哦产生式产生式 代代 码码 段段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtop ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigi
25、t 产产 生生 式式 语语 义义 规规 则则 LEn print(E.val)EE1+T E.val:=E1.val+T.val ET E.val:=T.val TT1*F T.val:=T1.val*F.val TF T.val:=F.val F(E)F.val:=E.val Fdigit F.val:=digit.lexval第26页，此课件共72页哦 输入输入 statesym val 用到的产生式用到的产生式 3*5+4n 0#-*5+4n 05#3 -3 *5+4n 03#F -3 Fdigit *5+4n 02#T -3 TF 5+4n 027#T*-3-+4n 0275#T*5
26、-3-5产生式产生式 代代 码码 段段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtop ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigit 第27页，此课件共72页哦 输入输入 statesym val 用到的产生式用到的产生式 +4n 0275#T*5 -3-5 +4n 02710#T*F -3-5 Fdigit +4n 02#T -15 TT*F +4n 01#E -15 ET 4n 016#E+-15-n 0165#E+4 -15-4产生式产生式 代代 码码 段段 LEnp
27、rint(valtop)EE1+Tvalntop:=valtop-2+valtop ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigit 第28页，此课件共72页哦 输入输入 statesym val 用到的产生式用到的产生式 n 0165#E+4 -15-4 n 0163#E+F -15-4Fdigit n 0169#E+T -15-4TF n 01#E -19EE+T#En -19-#L -19 LEn产生式产生式 代代 码码 段段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valto
28、p ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigit 第29页，此课件共72页哦8.2.3 L-8.2.3 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 通过深度优先的方法对语法树进行遍历，计通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值算属性文法的所有属性值LL(1)：自上而下分析方法，深度优先建立：自上而下分析方法，深度优先建立语法树语法树第30页，此课件共72页哦一个属性文法称为一个属性文法称为L-属性文法属性文法，如果对于每，如果对于每个产生式个产生式AX1X2Xn，其每个语义规则中，其每个语义
29、规则中的每个属性或者是综合属性，或者是的每个属性或者是综合属性，或者是Xj(1 j n)的一个继承属性且这个继承属性的一个继承属性且这个继承属性仅依赖于：仅依赖于：(1)产生式产生式Xj的左边符号的左边符号X1，X2，Xj-1的属性；的属性；(2)A的继承属性。的继承属性。S-属性文法一定是属性文法一定是L-属性文法属性文法第31页，此课件共72页哦【思考思考】非非L-L-属性的语法制导定义属性的语法制导定义【分析分析】该语法制导定义不是该语法制导定义不是L-L-属性定义，属性定义，文法符号文法符号Q Q的继承属性依赖于它右边文法符的继承属性依赖于它右边文法符号号R R的属性。的属性。产生式语
30、义规则ALMA QRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)第32页，此课件共72页哦8.3 8.3 中间代码的形式中间代码的形式n中间代码中间代码是源程序的一种内部表示是源程序的一种内部表示复杂性介于源语言和目标机语言之间复杂性介于源语言和目标机语言之间n中间代码的作用中间代码的作用使编译程序的逻辑结构更加简单明确使编译程序的逻辑结构更加简单明确利于进行与目标机无关的优化利于进行与目标机无关的优化利于在不同目标机上实现同一种语言利于在不同目标机上实现同一种语言n中间代码的形式中间代码的形式 逆波兰式、
31、四元式、三元式、树逆波兰式、四元式、三元式、树第33页，此课件共72页哦1、后缀表示式后缀表示式Lukasiewicz发发明明的的一一种种表表示示表表达达式式的的方方法法，又又称称逆逆波兰波兰表示法。表示法。n一个表达式一个表达式E的后缀形式可以如下定义：的后缀形式可以如下定义：1）如果如果E是一个变量或常量，则是一个变量或常量，则E的后缀式是的后缀式是E自身。自身。2）如果如果E是是E1 op E2形式的表达式，其中形式的表达式，其中op是是任何二元运算符，则任何二元运算符，则E的后缀式为的后缀式为E1 E2 op，其中其中E1 和和E2 分别为分别为E1 和和E2的后缀式。的后缀式。3）如
32、果如果E是是(E1)形式的表达式，则形式的表达式，则E1 的后缀式的后缀式就是就是E的后缀式。的后缀式。第34页，此课件共72页哦1、后缀表示式后缀表示式逆逆波波兰兰表表示示法法不不用用括括号号。只只要要知知道道每每个个算算符符的的目目数数，对对于于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。例如：（例如：（a+b）*c 表示成表示成ab+c*n后缀式的计算后缀式的计算用一个栈实现。用一个栈实现。一一般般的的计计算算过过程程是是：自自左左至至右右扫扫描描后后缀缀式式，每每碰碰到到运运算算量量就就把把它它推推进进栈栈。每每碰碰到到k目目
33、运运算算符符就就把把它它作作用用于于栈栈顶顶的的k个个项项，并并用用运运算算结结果果代代替这替这k个项。个项。第35页，此课件共72页哦1、后缀表示式后缀表示式把表达式翻译成后缀式的语义规则描述把表达式翻译成后缀式的语义规则描述产生式产生式EE(1)opE(2)E(E(1)Eid语义动作语义动作E.code:=E(1).code|E(2).code|opE.code:=E(1).codeE.code:=idE.code表示表示E后缀形式后缀形式op表示任意二元运算符表示任意二元运算符“|”表示后缀形式的连接表示后缀形式的连接。第36页，此课件共72页哦数组数组POST存放后缀式：存放后缀式：k
34、为下标，初值为为下标，初值为1上述语义动作可实现为：上述语义动作可实现为：产生式产生式程序段程序段EE(1)op E(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1例：输入串例：输入串a+b+c的分析和翻译的分析和翻译POST：1 2 3 4 5EE(1)opE(2)E.code:=E(1).code|E(2).code|opE(E(1)E.code:=E(1).codeEidE.code:=idab+c+第37页，此课件共72页哦2、图表示法、图表示法nDAG（无循环有向图）（无循环有向图）n抽象语法树抽象语法树（1）无循环有向图）无循环有向图(Direc
35、ted Acyclic Graph，简称简称DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个中都有一个结点结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表，它的孩子代表操作数操作数在一个在一个DAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点第38页，此课件共72页哦 a:=b*(-c)+b*(-c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc 后缀式是抽象语法树的线性表示形式：后缀式是抽象语法树的线性表示形式：abc-*b
36、c-*+:=第39页，此课件共72页哦抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象语法树抽象语法树*buminusc第40页，此课件共72页哦DAG对应的代码：对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5第41页，此课件共72页哦三地址代码三地址代码 三地址代码三地址代
37、码x:=y op z 三地址代码可以看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的一种线性表示的一种线性表示 第42页，此课件共72页哦三地址语句的种类三地址语句的种类 x:=y op z x:=op y x:=y goto L if x relop y goto L或或if a goto Lparam x和和call p,n，以及返回语句，以及返回语句return yx:=yi及及xi:=y的索引赋值的索引赋值x:=&y,x:=*y和和*x:=y的地址和指针赋值的地址和指针赋值第43页，此课件共72页哦3、四元式形式：、四元式形式：一个带有四个域的记录结构：一个带有四个域的记录结
38、构：（Op，ARG1，ARG2，Result）注：注：1）ARG1，ARG2，Result可能是用户自己定义的可能是用户自己定义的变量，也可能是编译时引进的变量。这里变量，也可能是编译时引进的变量。这里Op是双目是双目运算符，若只有一个运算量，则是单目运算符。运算符，若只有一个运算量，则是单目运算符。2）四元式中变量采用符号表的入口地址，而不用）四元式中变量采用符号表的入口地址，而不用变量的地址，因为语义分析不仅需要变量的地址，还变量的地址，因为语义分析不仅需要变量的地址，还需要从符号表查到变量的属性、类型和地址等。需要从符号表查到变量的属性、类型和地址等。第44页，此课件共72页哦3、四元式
39、形式：、四元式形式：例如：例如：a：=b*c+b*d的四元式表示如下：的四元式表示如下：（1）（）（*，b，c，t1）（2）（）（*，b，d，t2）（3）（）（+，t1，t2，t3）（4）（）（:=，t3，-，a）第45页，此课件共72页哦4、三元式形式、三元式形式（Op，ARG1，ARG2）注：注：1）这里三元式本身作为存放结果的单元。）这里三元式本身作为存放结果的单元。2）为了在其它三元式中利用当前三元式的结果，）为了在其它三元式中利用当前三元式的结果，需要对三元式进行编号。三元式的编号就作为相应三需要对三元式进行编号。三元式的编号就作为相应三元式的结果值。元式的结果值。例如：例如：a：=
40、b*c+b*d的四元式表示如下：的四元式表示如下：（1）（）（*，b，c）（2）（）（*，b，d）（3）（）（+，（，（1），（），（2）（4）（）（:=，（，（3），），a ）第46页，此课件共72页哦8.5 布尔表达式的翻译布尔表达式的翻译n布尔表达式的两个基本作用布尔表达式的两个基本作用:用于逻辑演算用于逻辑演算,计算逻辑值计算逻辑值;用于控制语句的条件式。用于控制语句的条件式。n产生布尔表达式的文法产生布尔表达式的文法:EE or E|E andE|not E|(E)|i rop i|i第47页，此课件共72页哦n计算布尔表达式通常采用两种方法计算布尔表达式通常采用两种方法:1.如同计
41、算算术表达式一样如同计算算术表达式一样,一步步算一步步算 1 or(not 0 and 0)or 0 =1 or(1 and 0)or 0 =1 or 0 or 0 =1 or 0 =12.采用某种优化措施采用某种优化措施 把把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第48页，此课件共72页哦n两种不同的翻译方法两种不同的翻译方法:第一种翻译法：第一种翻译法：A or B and C=D翻译成翻译成(1)(=,
42、C,D,T1)(2)(and,B,T1,T2)(3)(or,A,T2,T3)第第二二种种翻翻译译法法适适合合于于作作为为条条件件表表达达式式的的布尔表达式使用。布尔表达式使用。第49页，此课件共72页哦8.5.1 数值表示法数值表示法 a or b and not c 翻译成翻译成T1:=not cT2:=b and T1T3:=a or T1ab的关系表达式可等价地写成的关系表达式可等价地写成if ab then 1 else 0，翻译成，翻译成 100:if ab goto 103101:T:=0102:goto 104103:T:=1104:第50页，此课件共72页哦 关于布尔表达式的数
43、值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式 过程过程emit将三地址代码送到输出文件中将三地址代码送到输出文件中nextstat给出输出序列中下一条三地址语句的地址给出输出序列中下一条三地址语句的地址索引索引每产生一条三地址语句后，过程每产生一条三地址语句后，过程emit便把便把nextstat加加1 第51页，此课件共72页哦 关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式 EE1 or E2 E.place:=newtemp;emit(E.place:=E 1.place or E2.place)EE1 and E2 E.place:=newtemp;
44、emit(E.place:=E 1.place and E2.place)Enot E1 E.place:=newtemp;emit(E.place:=not E 1.place)E(E1)E.place:=E1.place第52页，此课件共72页哦关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place goto nextstat+3);emit(E.place:=0);emit(goto nextstat+2);emit(E.place:=
45、1)Eid E.place:=id.place ab 翻译成翻译成100:if ab goto 103101:T:=0102:goto 104103:T:=1104:第53页，此课件共72页哦布尔表达式布尔表达式ab or cd and ef的翻译结果的翻译结果 100:if ab goto 103101:T1:=0102:goto 104103:T1:=1104:if cd goto 107105:T2:=0106:goto 108107:T2:=1108:if ec or b c goto L2 “真真”出口出口 goto L1L1:if bd goto L2 “真真”出口出口 goto
46、L3 “假假”出口出口 L2:(关于关于S1的三地址代码序列的三地址代码序列)goto LnextL3:(关于关于S2的三地址代码序列的三地址代码序列)Lnext:第56页，此课件共72页哦产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则每次调用函数每次调用函数newlabel后都返回一个新的后都返回一个新的符号标号符号标号对于一个布尔表达式对于一个布尔表达式E，引用两个标号，引用两个标号E.true是是E为为真真时控制流转向的标号时控制流转向的标号E.false是是E为为假假时控制流转向的标号时控制流转向的标号 第57页，此课件共72页哦产生布尔表达式三地址代码的语义规则
47、产生布尔表达式三地址代码的语义规则 产生式产生式语义规则语义规则 EE1 or E2 E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.code E1.codeToE.trueToE1.falseE2.codeToE.trueToE.false第58页，此课件共72页哦产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则 产生式产生式语义规则语义规则EE1 and E2 E1.true:=newlabel;E1.false:
48、=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code|gen(E1.true:)|E2.codeE1.codeToE.falseToE1.trueE2.codeToE.trueToE.false第59页，此课件共72页哦产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则 产生式产生式语义规则语义规则Enot E1 E1.true:=E.false;E1.false:=E.true;E.code:=E1.code E(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.c
49、ode第60页，此课件共72页哦产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则 产生式产生式语义规则语义规则 Eid1 relop id2 E.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)第61页，此课件共72页哦考虑如下表达式：考虑如下表达式：ab or cd and ef假定整个表达式的真假出口已分别置为假定整个表达式的真假出口已分别置为Ltrue
50、和和Lfalse，则按定义将生成如下的代码：，则按定义将生成如下的代码：if ab goto Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto Lfalse第62页，此课件共72页哦布尔表达式的翻译布尔表达式的翻译两遍扫描两遍扫描为给定的输入串构造一棵语法树；为给定的输入串构造一棵语法树；对语法树进行深度优先遍历，进行语义规则中对语法树进行深度优先遍历，进行语义规则中规定的翻译。规定的翻译。一遍扫描一遍扫描第63页，此课件共72页哦一遍扫描实现布尔表达式的翻译一遍扫描实现布尔表达式的翻译采用四元式形式采用四元式形式把四