8-中间代码生成.ppt

《8-中间代码生成.ppt》由会员分享，可在线阅读，更多相关《8-中间代码生成.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成源程序源程序目标程序目标程序第第8 8章章 语法制导翻译和语法制导翻译和 中间代码生成中间代码生成1GE:EE+T|E-T|TTT*F|FF(E)|i例如，考虑：例如，考虑：EE+T符号意义？整个式子的意义？符号意义？整个式子的意义？2语义检查：语义检查：审查每个语法结构的审查每个语法结构的静态语义静态语义，即验证语法结构合，即验证语法结构合法的程序是否真正有意义。法的程序是否真正有意义。例：类型、运算、维数、越界例：类型、运算、维数、越界例：类型、运算、维数、越界例：类型、运算、维

2、数、越界语义分析的任务语义分析的任务语义处理：语义处理：执行真正的翻译，生成程序的中间代码目标代码。执行真正的翻译，生成程序的中间代码目标代码。例：变量的存储分配例：变量的存储分配例：变量的存储分配例：变量的存储分配例：表达式的求值例：表达式的求值例：表达式的求值例：表达式的求值例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）38.1 8.1 属性文法属性文法语义分析的描述语义分析的描述描述语法规则的同时，编写相应的语义描述语法规则的同时，编写相应的语义动作和计算顺序动作和计算顺序语义的形式化描述语义的形式化描述操

3、作语义学、公理语义学、指称语义学操作语义学、公理语义学、指称语义学属性文法属性文法接近形式化的语义描述方法接近形式化的语义描述方法4属性文法属性文法(attributegrammar)的定的定义义属性文法属性文法属性文法属性文法是一个三元组：是一个三元组：是一个三元组：是一个三元组：A A（GG，V V，F F），），），），其中其中其中其中 GG：是一个上下文无关文法。是一个上下文无关文法。是一个上下文无关文法。是一个上下文无关文法。V V：有有有有穷穷穷穷的的的的属属属属性性性性集集集集，每每每每个个个个属属属属性性性性与与与与文文文文法法法法的的的的一一一一个个个个终终终终结结结结符符符

4、符或或或或非非非非终终终终结结结结符符符符关关关关联联联联，这这这这些些些些属属属属性性性性代代代代表表表表与与与与文文文文法法法法符符符符号号号号相相相相关关关关信信信信息息息息，比比比比如如如如它它它它的的的的类类类类型型型型、值值值值、代代代代码码码码序序序序列列列列、符符符符号号号号表表表表内内内内容容容容等等等等等等等等。属属属属性性性性与与与与变变变变量量量量一一一一样样样样，可可可可以以以以进进进进行行行行计计计计算算算算和和和和传传传传递递递递。属属属属性性性性加加加加工工工工的的的的过过过过程程程程即即即即是是是是语语语语义义义义处处处处理理理理的的的的过过过过程。程。程。程

5、。F F：关关关关于于于于属属属属性性性性的的的的属属属属性性性性断断断断言言言言或或或或一一一一组组组组属属属属性性性性的的的的计计计计算算算算规规规规则则则则（称称称称为为为为语语语语义义义义规规规规则则则则）。断断断断言言言言或或或或语语语语义义义义规规规规则则则则与与与与一一一一个个个个产产产产生生生生式式式式关关关关联联联联，只只只只引引引引用用用用该该该该产产产产生生生生式式式式左左左左端端端端或或或或右右右右端的终结符或非终结符关联的属性。端的终结符或非终结符关联的属性。端的终结符或非终结符关联的属性。端的终结符或非终结符关联的属性。关系语义信息作为终结符和非终结符的属性关系语义

6、信息作为终结符和非终结符的属性关系语义信息作为终结符和非终结符的属性关系语义信息作为终结符和非终结符的属性 语义分析定义为语义分析定义为语义分析定义为语义分析定义为规则规则规则规则式的断言和谓词式的断言和谓词式的断言和谓词式的断言和谓词5用用 法法第一步：第一步：针对语义，为文法符号设置针对语义，为文法符号设置属性属性终结符使用单词的属性终结符使用单词的属性第二步：第二步：为为每个产生式每个产生式设置相应的语义规则设置相应的语义规则描述各属性的关系描述各属性的关系什么是什么是“语法制导翻译语法制导翻译”：语法制导：语法制导：语法制导：语法制导：语义的抽象说明；语义的抽象说明；语义的抽象说明；语

7、义的抽象说明；翻译：翻译：翻译：翻译：方案设计，规定实现方法（计算次序）方案设计，规定实现方法（计算次序）方案设计，规定实现方法（计算次序）方案设计，规定实现方法（计算次序）6属性文法的书写格式属性文法的书写格式语义规则语义规则相关的属性等式相关的属性等式.相关的属性等式相关的属性等式文法规则文法规则产生式产生式1.产生式产生式n7例：例：用属性文法表示简单的无符号整数文法：用属性文法表示简单的无符号整数文法：numbernumberdigit|digitdigit0|1|2|3|4|5|6|7|8|91 1、文法规则、文法规则、文法规则、文法规则digit0digit0，表明表明表明表明di

8、gitdigit的值为的值为的值为的值为0 0。可以用属性。可以用属性。可以用属性。可以用属性等式等式等式等式digit.digit.valval:=0:=0 表示，将它和规则表示，将它和规则表示，将它和规则表示，将它和规则digit0digit0 联系起来。联系起来。联系起来。联系起来。2 2、文法规则、文法规则、文法规则、文法规则numberdigitnumberdigit，表明这个数就只包含了一表明这个数就只包含了一表明这个数就只包含了一表明这个数就只包含了一个数字，其值就是这个数字的值。用属性等式表示为个数字，其值就是这个数字的值。用属性等式表示为个数字，其值就是这个数字的值。用属性等

9、式表示为个数字，其值就是这个数字的值。用属性等式表示为 number.number.valval:=digit.:=digit.valval。分析分析分析分析 一个数最重要的属性是它的值，命名为一个数最重要的属性是它的值，命名为一个数最重要的属性是它的值，命名为一个数最重要的属性是它的值，命名为valval。显然，每个显然，每个显然，每个显然，每个数字都有一个值。可以用它表示的实际数直接计算。数字都有一个值。可以用它表示的实际数直接计算。数字都有一个值。可以用它表示的实际数直接计算。数字都有一个值。可以用它表示的实际数直接计算。83 3、文法规则文法规则文法规则文法规则numbernumber

10、digitnumbernumberdigit，表明文法符号表明文法符号表明文法符号表明文法符号的数目不止一个。必须表示出这个文法产生式的数目不止一个。必须表示出这个文法产生式的数目不止一个。必须表示出这个文法产生式的数目不止一个。必须表示出这个文法产生式两边符两边符两边符两边符号的值号的值号的值号的值之间的关系。之间的关系。之间的关系。之间的关系。借用下标进行区分，将文法写成如下形式：借用下标进行区分，将文法写成如下形式：借用下标进行区分，将文法写成如下形式：借用下标进行区分，将文法写成如下形式：number1number2digitnumber1number2digit 注意：注意：注意：注

11、意：此写法并不是说左右的此写法并不是说左右的此写法并不是说左右的此写法并不是说左右的numbernumber不同，仅仅为不同，仅仅为不同，仅仅为不同，仅仅为了阅读的方便。了阅读的方便。了阅读的方便。了阅读的方便。语义规则可表示为：语义规则可表示为：语义规则可表示为：语义规则可表示为：number1.val:=number2.val*10+digit.val9完整的属性文法：完整的属性文法：完整的属性文法：完整的属性文法：左部左部右部右部number1number2digitnumber1number2digit，number1.number1.valval:=:=number2.number2

12、.valval*10+digit.*10+digit.valvalnumberdigitnumberdigit，number.number.valval:=digit.:=digit.valvaldigit0|1|2|3|4|5|6|7|8|9，digit.digit.valval:=0,1,2,3,4,5,6,7,8,9:=0,1,2,3,4,5,6,7,8,910分析分析首先将类型信息作为文法符号的属性，首先将类型信息作为文法符号的属性，记为记为type。1、文法规则文法规则Tint，所对应的属性等式是所对应的属性等式是T.type:=integer2、文法规则文法规则DTL，L.type

13、:=T.type例：例：用属性文法表示标识符的类型信息用属性文法表示标识符的类型信息DTLTint|realLL1,idLid113、文法规则文法规则Lid，addtype(id.entry,L.type)4、文法规则文法规则LL1,id，L1.type:=L.type;addtype(id.entry,L.type)12例例8-1 8-1 计算器的设计计算器的设计编制算术表达式的文法编制算术表达式的文法引入属性表示语义信息引入属性表示语义信息将值将值 valval 作为表达式作为表达式 E E、项项 T T 和因子和因子 F F 的属性的属性用用语义规则语义规则描述表达式的求值描述表达式的求

14、值13属性文法属性文法（语法制导定义）（语法制导定义）LEprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexvallexval是单词是单词digit的属性的属性例例例例8-38-314例例8-2 8-2 说明语句类型信息说明语句类型信息方法方法编写说明语句的文法编写说明语句的文法将将类型信息类型信息作为类型描述作为类型描述T的的属性属性type和变量表和变量表L的属性的属性in。目的目的分析说明

15、语句分析说明语句D，为变量指定类型为变量指定类型15语法制导定义语法制导定义DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,id L1.in:=L.inaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)entry单词单词id的属性的属性addtype在在符号表中为变量添加类型信息符号表中为变量添加类型信息16属性分类属性分类综合属性综合属性从其子结点的属性值计算出来的；从其子结点的属性值计算出来的；如：如：E.val、T.type继承属性继承属性从其兄弟结点和父结点的属性值计算出来的从其兄

16、弟结点和父结点的属性值计算出来的如：如：L.in固有属性（单词属性）固有属性（单词属性）17属性的计算属性的计算语法制导翻译：作语法分析，构造语法制导翻译：作语法分析，构造语法制导翻译：作语法分析，构造语法制导翻译：作语法分析，构造语法树语法树语法树语法树，然，然，然，然后在树的每个后在树的每个后在树的每个后在树的每个结点结点结点结点上添加相应的上添加相应的上添加相应的上添加相应的语义规则语义规则语义规则语义规则综合属性综合属性综合属性综合属性自底向上自底向上自底向上自底向上按照语义规则来计算各结点的综合按照语义规则来计算各结点的综合按照语义规则来计算各结点的综合按照语义规则来计算各结点的综合

17、属性值属性值属性值属性值继承属性继承属性继承属性继承属性需要探讨计算次序需要探讨计算次序需要探讨计算次序需要探讨计算次序18digit.lexval=3F.val=3T.val=3dgit.lexval=5F.val=5T.val=15E.val=15digit.lexval=4F.val=4T.val=4E.val=19Print(19)例例8-33*5+4的的语法树与属性计算语法树与属性计算文法文法文法文法19例例8-4realid1,id2,id3的分析树和属性计算的分析树和属性计算realT.type=realT.type=realid1L.in=real,id2L.in=real,i

18、d3L.in=realD Daddtypeaddtypeaddtype20仅包括综合属性仅包括综合属性对于所有对于所有12n，的属性计算仅用的属性计算仅用1n的属性的属性如：算术表达式求值的属性文法如：算术表达式求值的属性文法-属性定义属性定义 21-属性定义属性定义 其属性可用深度优先的顺序从左至右计算其属性可用深度优先的顺序从左至右计算对于所有对于所有 1 1 2 2 n ni i 属性计算仅使用属性计算仅使用 1 1 2 2 i-i-1 1 的属性的属性如：说明语句的属性文法如：说明语句的属性文法22identidentREADREADENDEND;语句语句语句语句表达式表达式表达式表达

19、式:=:=BEGINBEGIN语句语句语句语句语句语句语句语句)(identident,复习：语法描述图复习：语法描述图23项项表达式表达式+-项项+-项项 因子因子 因子因子 */语法图语法图24DTLLL1,id例例8-5建立说明语句的翻译方案建立说明语句的翻译方案25语法制导定义：语法制导定义：DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.inaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)entry单词单词id的属性，在符号表的位置的属性，在符号表的位置a

20、ddtype在符号表中为变量添加类型信息在符号表中为变量添加类型信息26翻译方案的设计翻译方案的设计将语义动作中的计算向前移，使继承属性的将语义动作中的计算向前移，使继承属性的计算出现在其文法符号之前计算出现在其文法符号之前DTL.in:=T.typeLTintT.type:=integerTrealT.type:=realLL1.in:=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)278.2 8.2 中间语言中间语言用于编译程序用于编译程序源程序经过语义分析被译成中间代码源程序经过语义分析被译成中间代码序列序列（中间语言的语

21、句）（中间语言的语句）用中间语言过渡的好处用中间语言过渡的好处：便于编译系统的实现、移植、代码优便于编译系统的实现、移植、代码优化化28编译中的语义分析编译中的语义分析描述方法描述方法利用属性文法描述如何将各种语句和表利用属性文法描述如何将各种语句和表达式翻译成中间代码达式翻译成中间代码工作方式工作方式分析与综合并行进行分析与综合并行进行每识别出一个语言结构时，每识别出一个语言结构时，完成相应的语义检查与中间代码生成完成相应的语义检查与中间代码生成29常用的中间语言常用的中间语言三地址代码（四元式）三地址代码（四元式）语法结构树（三元式）语法结构树（三元式）后缀式后缀式特点特点形式简单、语义明

22、确、便于翻译形式简单、语义明确、便于翻译独立于目标语言独立于目标语言30后缀式（逆波兰表示）后缀式（逆波兰表示）操作数操作数1，操作数，操作数2，运算符，运算符例例8-8a:=b*（-c）+b*（-34）的后缀的后缀式：式：abc-*b34-*+:=31三元式三元式操作符操作符op,运算对象运算对象1arg1,运算对象运算对象2arg2例例：赋值语句：赋值语句a:=b*（-c）+b*（-34）的三元式：的三元式：:=a+*b-c*b-3432例例 8-6 a:=b*(-c)+b*(-34)的语法结构树的语法结构树:=*-0+*-0id bnum34id bid cid aroot33语法结构树

23、的语法结构树的三元式表示三元式表示地址地址 算符算符 操作数操作数 操作数操作数 0 1 2 3 4 5 6 7 8 91034语法结构树语法结构树例例8-7表达式表达式(A-12)*B+6的语法结构树的语法结构树35将赋值语句变换为语法结构树将赋值语句变换为语法结构树设置属性：设置属性：E.p是语法结构树指针是语法结构树指针id.entry是名字的表项入口是名字的表项入口num.val是数值是数值树构造函数树构造函数mknode建中间结点建中间结点mkleaf建叶结点建叶结点36属性文法属性文法37生成后缀式的属性文法生成后缀式的属性文法38三地址代码三地址代码 一般形式一般形式 x :=y

24、 op z其中其中 x,y,z 为变量名、常数或编译产生为变量名、常数或编译产生的临时变量的临时变量四元式（四元式（op,x,y,z）种类：种类：x :=y op z 双目运算双目运算 x :=op y 单目运算单目运算 x :=y 赋值赋值 if x relop y goto L 条件转移条件转移39其他三地址代码其他三地址代码 gotogoto l l 无条件转移无条件转移 paramparam x x 实在参数实在参数 call p,n(ncall p,n(n是参数个数是参数个数)过程调用过程调用 return x return x 过程返回过程返回 x:=yix:=yi 数组运算数组运

25、算 xi:=yxi:=y x:=&y x:=&y 指针运算指针运算 x:=*yx:=*y *x:=y *x:=y 40例：赋值语句例：赋值语句a:=b*（-c）+b*（-34）的三地址代码的三地址代码(四元式四元式)：(1)t1:=-c;(2)t2:=b*t1;(3)t3:=-34;(4)t4:=b*t3;(5)t5:=t2+t4;(6)a:=t5;418.38.3 赋值语句的翻译赋值语句的翻译翻译的需求翻译的需求充分了解各种语言现象的语义充分了解各种语言现象的语义包括：控制结构、数据结构、单词包括：控制结构、数据结构、单词充分了解它们的实现方法充分了解它们的实现方法目标语言的语义目标语言的语

26、义了解中间代码的语义了解中间代码的语义了解运行环境了解运行环境428.3 8.3 实现赋值语句的语义翻译实现赋值语句的语义翻译语义过程语义过程产生中间代码产生中间代码emit产生新的临时变量产生新的临时变量newtemp在符号表中查找变量在符号表中查找变量lookup(id.name)属性设置属性设置存储位置存储位置place43赋值语句三地址代码的语义翻译赋值语句三地址代码的语义翻译Sid:=Ep:=lookup(id.name);ifpnilthenemit(p:=E.place)elseerrorEE1+E2E.place=newtemp;emit(E.place:=E1.place+E

27、2.place)EE1*E2E.place=newtemp;emit(E.place:=E1.place*E2.place)E-EE.place:=newtemp;emit(E.place:=-E.place44（接上页（接上页）E(E1)E.place:=E1.placeEidp:=lookup(id.name);ifpnilthenE.place:=pelseerrorEnumE.place:=num45例：翻译例：翻译a:=-c+b*3446a:=E.placea:=E.place:=E1.place+E2.placeE1.place:=-E11.place+E2.place:=E21.

28、place*E22.place*E22.place:=numE21.place:=id3b34-E11.place:=id2c47三地址代码的生成过程三地址代码的生成过程因为属性因为属性place是综合属性，所以用自底向是综合属性，所以用自底向上的分析方法来求每个非终结符的属性。最上的分析方法来求每个非终结符的属性。最终所得的代码序列如下：终所得的代码序列如下：1.E11.place:=c2.E1.place:=-E11.place3.E21.place:=b4.E22.place:=345.E2.place:=E21.place*E22.place6.E.place:=E1.place+E2

29、.place7.a:=E.place48翻译中的其他问题翻译中的其他问题运算合法性检查运算合法性检查利用符号表保存的名字类型利用符号表保存的名字类型利用符号表保存的名字类型利用符号表保存的名字类型类型自动转换类型自动转换填加专用指令填加专用指令填加专用指令填加专用指令临时变量空间的统计临时变量空间的统计了解需求、及时释放了解需求、及时释放了解需求、及时释放了解需求、及时释放498.4 布尔表达式的语义翻译布尔表达式的语义翻译布尔表达式布尔表达式：用布尔运算符作用到布尔变：用布尔运算符作用到布尔变量或关系表达式上而组成。量或关系表达式上而组成。布尔表达式的作用布尔表达式的作用用于计算逻辑值用于计

30、算逻辑值用于控制语句之中的条件表达式，用于控制语句之中的条件表达式，如如if-then，if-then-else和和while-do等之中等之中的条件表达式的条件表达式508.4.1 布尔表达式的翻译方法布尔表达式的翻译方法布尔表达式的表示布尔表达式的表示方法一：方法一：用数值表示真和假，从而对布尔表达用数值表示真和假，从而对布尔表达式的求值可以象对算术表达式的求值那样一步式的求值可以象对算术表达式的求值那样一步一步地来计算一步地来计算方法二：方法二：通过程序的控制流，即用程序中控制通过程序的控制流，即用程序中控制转移到达的位置来表示布尔表达式的值转移到达的位置来表示布尔表达式的值518.4.

31、2 数值表示法数值表示法布尔表达式：布尔表达式：aorbandnotc翻译成三地址代码序列：翻译成三地址代码序列：100：t1:=notc101：t2:=bandt1102：t3:=aort1关系表达式：关系表达式：ab等价等价于于ifabthen1else0翻译成三地址代码序列：翻译成三地址代码序列：100：ifabgotol03101：t：=0102：gotol04。103:t:=11表示真，表示真，0表示假表示假52关于布尔表达式的数值表示法的翻译关于布尔表达式的数值表示法的翻译语义过程语义过程产生中间代码产生中间代码 emitemit产生新的临时变量产生新的临时变量 newtempne

32、wtemp属性设置属性设置存储位置存储位置 placeplace53关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式 EE1EE1ororE2E2E.place:=E.place:=newtempnewtemp;emit(E.place:=E1.placeorE2.place)emit(E.place:=E1.placeorE2.place)EE1EE1andandE2E2E.place:=E.place:=newtempnewtemp;emit(E.place:=E1.placeandE2.pla

33、ce)emit(E.place:=E1.placeandE2.place)EEnotnotE1E1 E.place:=E.place:=newtempnewtemp;emit(E.place:=notE1.place)emit(E.place:=notE1.place)EEturetureE.place:=E.place:=newtempnewtemp;emit(E.place:=1)emit(E.place:=1)EfalseEfalseE.place:=E.place:=newtempnewtemp;emit(E.place:=0)emit(E.place:=0)54（接上页）接上页）Ei

34、d1relopid2E.place:=newtemp;emit(ifid1.placerelop.opd2.placegotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1)注：注：relop表示表示=、等等关系运算等等关系运算55控制语句中的布尔表达式翻译控制语句中的布尔表达式翻译例，例，C语言中的：语言中的：（1）ifa=a&ch=z)（3）for(i=0;i=20;i+).56控制语句中的布尔表达式控制语句中的布尔表达式（1）EE1orE2（把文法翻译成什么形式）把文法翻译成什么形式）把文法翻译成什么形式

35、）把文法翻译成什么形式）（2）EE1andE2 E1.code E1.code E2.code E2.codeE1.false:E1.false:to E1.trueto E1.trueto E1.falseto E1.falseto E2.trueto E2.trueto E2.falseto E2.false E1.code E1.code E2.code E2.codeE1.trueE1.true:to E1.trueto E1.trueto to E1.falseE1.falseto E2.trueto E2.trueto E2.falseto E2.falseto E.trueto

36、E.trueto E.falseto E.falseto E.trueto E.trueto E.falseto E.false57使用回填翻译控制语句中的布尔表达式使用回填翻译控制语句中的布尔表达式（3）EnotE1（4）E(E1)E1.codeE1.codeto to E1.trueE1.trueto E1.falseto E1.falseE.codeE.codeto E.falseto E.falseto E.trueto E.true E1.codeE1.codeto to E1.trueE1.trueto E1.falseto E1.falseE.codeE.codeto E.tru

37、eto E.trueto E.falseto E.false58使用回填翻译控制语句中的布尔表达式使用回填翻译控制语句中的布尔表达式（5）Eid1relopid2（6）Etrue（7）EfalseE.code if id1 E.code if id1 relop relop id2 then id2 then goto goto E.trueE.true goto goto E.false E.false to E.falseto E.falseto E.trueto E.trueE.code E.code goto goto E.true E.true to E.trueto E.trueE

38、.code E.code goto goto E.false E.false to E.falseto E.false59使用回填翻译控制语句中的布尔表达式使用回填翻译控制语句中的布尔表达式（1）EE1orME2（2）|E1andME2（3）|notE1（4）|(E1)（5）|id1relopid2（6）|true（7）|false（8）M插入非终结符号插入非终结符号M是为了引入一个语义动作，是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个四以便在适当的时候获得即将产生的下一个四元式的索引元式的索引60翻译模式用到如下三个函数：翻译模式用到如下三个函数：1makelist(i)：创

39、建一个仅包含创建一个仅包含i的新表，的新表，i是四元式数组的一个索引（下标），或是四元式数组的一个索引（下标），或说说i是四元式代码序列的一个标号。是四元式代码序列的一个标号。2merge(p1，p2)：连接由指针连接由指针p1和和p2指指向向的两个表并且返回一个指向连接后的表的两个表并且返回一个指向连接后的表的指针。的指针。3backpatch（p，i）：）：把把i作为目标标号作为目标标号回回填到填到p所指向的表中的每一个转移指令中所指向的表中的每一个转移指令中去。去。此处的此处的“表表”都是为都是为“回填回填”所拉的链所拉的链61EE1ORME2backpatch(E1.false,M.n

40、ext);E.true:=merge(E1.true,E2.true);E.false:=E2.falseEE1ANDME2backpatch(E1.true,M.next);E.true:=E2.true;E.false:=merge(E1.false,E2.false);62EnotE1E.true:=E1.false;E.false:=E1.trueE(E1)E.true:=E1.true;E.false:=E1.falseEid1relopid2E.true:=nextstat;E.false:=nextstat+1;emit(ifid1.placerelop.opid2.placeg

41、oto);emit(goto);63EtrueE.true:=nextstat;emit(goto);EfalseE.false:=nextstat;emit(goto);M M.next:=nextstat64例例 表达式表达式ab or cd and ef 一棵作了注释的分析树如下图所示一棵作了注释的分析树如下图所示E.t=100,104E.f=103,105E.t=100E.f=101E.t=104E.f=103,105or M.q=102a b E.t=102E.f=103E.t=104E.f=105andM.q=104cef d65依次分析，得到如依次分析，得到如下四元式：下四元式：

42、100：ifabgoto-101：goto-102：ifcdgoto-103：goto-104：ifefgoto-105：goto-经过回填得到：经过回填得到：100：ifabgotoL1101：gotol02102：ifcdgotol04103：goto-104：ifefgotoL1105：goto-当知道了条件为真时和条件为假时分别应做当知道了条件为真时和条件为假时分别应做哪些事时就可以进行回填哪些事时就可以进行回填668.5 控制语句的语义翻译控制语句的语义翻译这里只讨论下列文法所指定的控制流语句：这里只讨论下列文法所指定的控制流语句：（1）SifEthenS（2）|ifEthenSel

43、seS（3）|whileEdoS（4）|beginLend（5）|A（6）LL；S（7）|S67插入非终结符号插入非终结符号M和和N是为了引入一个语是为了引入一个语义动作，以便在适当的时候获得即将产生的义动作，以便在适当的时候获得即将产生的下一个四元式的索引。下一个四元式的索引。（1）SifEthenM1S1（2）|ifEthenM1S1N1elseM2S2（3）|whileM1EdoM1S1（4）|beginLend（5）|A（6）LL；S（7）|S（8）M（9）N68控制流语句的翻译模式控制流语句的翻译模式：1.Sif E then M1 S1E.codeS1.codeE.true:.E.

44、false:to E.trueto E.falseM1处处反填反填E.true backpatch(E.true,M.next);S.next:=merge(E.false,S1.next)69控制流语句的翻译模式控制流语句的翻译模式：2.Sif E then M1 S1 N else M2 S2 E.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.falseM1处反填处反填E.trueM2处反填处反填E.falseN出生成出生成 goto S.next70 backpatch(E.true,M1.next);

45、backpatch(E.false,M2.next);S.next:=merge(S1.next,N.next,S2.next)N N.next:=nextstat;emit(goto)71控制流语句的翻译模式控制流语句的翻译模式：2.Swhile M1 E do M2 S1E.codeS1.codeE.true:E.false:goto S.begin.S.begin:to E.falseto E.trueM1处反填处反填S1.next生成标号生成标号S.beginM2处反填处反填E.true72 backpatch(E.true,M2.next);backpatch(S1.next,M1.

46、next);S.next:=E.false;emit(gotoM1.next)S begin L end S.next:=L.next S A S.next:=makelist()LL1;M S backpatch(L1.next,M.next);L.next:=S.next LS L.next:=S.next 73 先记录要回填的转移指令地址，在适当的时先记录要回填的转移指令地址，在适当的时候进行回填，以便赋值和布尔表达式的求值候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序的控制流程。得到合适的连接，以完成程序的控制流程。例：翻译下列语句例：翻译下列语句whileabdoi

47、fcydoz:=x+1;elsex:=y74100 if a b goto 102；101 goto 111；102 if c y goto L5；105 goto 100；106 x:=z+1；107 goto 104；108 goto 100；109 x:=y；110 goto 100；E.codeE1.codeS11.codeS12.codeS1.code758.5 8.5 属性文法的实现属性文法的实现分析分析属性属于文法符号属性属于文法符号属性属于文法符号属性属于文法符号局限于产生式局限于产生式局限于产生式局限于产生式递归子程序的改进递归子程序的改进为每个文法符号设置结构或对象类为每个

48、文法符号设置结构或对象类为每个文法符号设置结构或对象类为每个文法符号设置结构或对象类以每个属性为分量以每个属性为分量以每个属性为分量以每个属性为分量每个函数设置一个结构（或对象类）指针每个函数设置一个结构（或对象类）指针每个函数设置一个结构（或对象类）指针每个函数设置一个结构（或对象类）指针76例例 8-11 条件语句的翻译实现条件语句的翻译实现S的结构的结构structS_AttrcharpCodeMAX;intiNext;E的结构的结构structE_AttrcharpCodeMAX;intiFalse;intiTrue;77语句语句 S 的递归函数的递归函数void S(void S(s

49、truct struct S_S_Attr Attr *pSpS)if(if(lookheadlookhead=IF)=IF)structstruct E_ E_Attr aEAttr aE;structstruct S_ S_Attr Attr aS1;aS1;/*/*if E then S1if E then S1*/*/match(IF);match(IF);E(&E(&aEaE););match(THEN);match(THEN);S(&aS1);S(&aS1);aEaE.iTrue iTrue =newLabelnewLabel();();aS1.iNext=aS1.iNext=aE

50、aE.iFalseiFalse=pSpS-iNextiNext;sprintfsprintf(pSpS-code,“%-code,“%sLsL%d:n%s”,%d:n%s”,aEaE.code,.code,aEaE.iTrueiTrue,aS1.code);,aS1.code);788.8.4 4 组合数据类型的翻译组合数据类型的翻译同质数据结构同质数据结构多维数组、枚举多维数组、枚举多维数组、枚举多维数组、枚举异质数据结构异质数据结构记录、结构、联合记录、结构、联合记录、结构、联合记录、结构、联合抽象数据类型抽象数据类型类、模块类、模块类、模块类、模块79功能与实现功能与实现操作操作元素的引