编译原理课件chap6.ppt

《编译原理课件chap6.ppt》由会员分享，可在线阅读，更多相关《编译原理课件chap6.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第六第六章章 属性文法和语法制导属性文法和语法制导翻译翻译从本章开始，我们介绍有关语从本章开始，我们介绍有关语义分析及翻译的问题。其处理的方法义分析及翻译的问题。其处理的方法主要是属性文法和语法制导翻译方法。主要是属性文法和语法制导翻译方法。本章中，我们将首先介绍属性本章中，我们将首先介绍属性文法的基本概念，然后介绍基于属性文法的基本概念，然后介绍基于属性文法的处理方法，讨论如何自上而下文法的处理方法，讨论如何自上而下分析和自下而上分析中实现属性计算。分析和自下而上分析中实现属性计算。本章重点掌握前四节本章重点掌握前四节6.16.1属性文属性文法，法，6.26.2基于属性文法的处理方法，基于属

2、性文法的处理方法，6.3 6.3 SS属性文法的自下而上计算，属性文法的自下而上计算，6.4 6.4 LL属属性文法和自顶向下翻译。性文法和自顶向下翻译。第六章 属性文法和语法制导翻译6 6。1 1属性文法属性文法 属性文法是在上下文无关文法的基础上为每个文法符属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的号（终结符或非终结符）配备若干个相关的“值值”（称（称为为属性属性）。这些属性代表与文法符号相关的信息，例如）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列它的类型、值、代码序列、符号表内容等等。属性和变、符号表内容等等。属性和变量一样，

3、可以进行计算和传递。量一样，可以进行计算和传递。属性一般分为两类：属性一般分为两类：综合属性综合属性和和继承属性。继承属性。简单的简单的说，综合属性用于说，综合属性用于“自下而上自下而上”传递信息，而继承属性传递信息，而继承属性用于用于“自上而下自上而下”传递信息。传递信息。属性加工加工的过程即是语义处理的过程，对于文属性加工加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。为语义规则。在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A都有都有一套与之相关联的语义规则，每条语义

4、规则的形式为：一套与之相关联的语义规则，每条语义规则的形式为：第六章 属性文法和语法制导翻译 b:=f(c1,c2,ck)b:=f(c1,c2,ck)这里这里f f是一个函数，而且或者是一个函数，而且或者 （1 1）b b是是A A的一个综合属性并且的一个综合属性并且c1,c2,ckc1,c2,ck是产生式右边文是产生式右边文法符号的属性；或者法符号的属性；或者 （2 2）b b是产生式右边某个文法符号的一个继承属性并且是产生式右边某个文法符号的一个继承属性并且c1,c2,ckc1,c2,ck是是A A或产生式右边任何文法符号的属性或产生式右边任何文法符号的属性 在这两种情况下，我们都说属性在

5、这两种情况下，我们都说属性b b依赖于属性依赖于属性c1,c2,ck.c1,c2,ck.要特别强掉的是：要特别强掉的是：（1 1）终结符只有综合属性，它由词法分析器提供；）终结符只有综合属性，它由词法分析器提供；（2 2）非终结符既可以有综合属性也可以有继承属性，文法）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。开始符号的所有继承属性作为属性计算前的初始值。一般来讲，对出现在产生式右边的继承属性和出现在产生一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则式左边的综合属性都必须提供一个计算规则，

6、属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式中只能使用相应产生式的文法符号的属性，这有利于产生式范围内范围内“封装封装”属性的依赖性。然而，出现在产生式左边的属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计的属性计算规则进行计算，它们由其它产生式的属性规则计算算,由属性计算器的参数提供由属性计算器的参数提供第六章 属性文法和语法制导翻译 语义规则所描述的工作可以包括属性计算、静态语义规则所描述的工作可以包括属性计算、静态语义检查、

7、符号表操作、代码生成等。语义规则可能语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。这样的语义规则通常写成过程调用，或过程段。综合属性综合属性：在语法树中，一个结点的综合属性的值由其子在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅在每一个

8、结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法仅使用综合属性的属性文法称称SS属性文法。属性文法。继承属性继承属性：在语法树中，一个结点的继承属性由此结点的在语法树中，一个结点的继承属性由此结点的父结点和父结点和/或兄弟结点的某些属性确定。用继承属性来或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。表示程序语言结构中的上下文依赖关系很方便。第六章 属性文法和语法制导翻译6 6。2 2 基于属性文法的处理方法基于属性文法的处理方法 从概念上讲，基于属性文法的处理过程通常是这样的：对单词从概念上讲，基于属性文法的处理过程通常是这样的：对单词符号串进行

9、语法分析，构造语法分析树，然后根据需要遍历语法符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。树，并在语法树的各结点处按语义规则进行计算。输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序 这种由源程序的语法结构所驱动的处理办法就是这种由源程序的语法结构所驱动的处理办法就是语法制导翻译语法制导翻译法法。语义规则的计算可能产生代码、在符号表中存放信息、给出。语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行

10、计算得出结果。规则进行计算得出结果。6 6。2 2。1 1依赖图依赖图 如果在一棵语法树中一个结点的属性如果在一棵语法树中一个结点的属性b b依赖于属性依赖于属性c c，那么这那么这个结点处计算个结点处计算b b的属性规则必须在确定的属性规则必须在确定c c的语义规则之后使用。在的语义规则之后使用。在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。可以用称作依赖图的一个有向图来描述。在为一棵语法树构造依赖图以前，我们为每一个包含过程调在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规

11、则引入一个虚综合属性用的语义规则引入一个虚综合属性b b，这样把每一个语义规则都这样把每一个语义规则都写成写成 b:=f(cb:=f(c1 1,c,c2 2,c,ck k)的形式。依赖图中为每一个属性的形式。依赖图中为每一个属性设置一个结点，如果属性设置一个结点，如果属性b b依赖属性依赖属性c c，则从属性则从属性c c的结点有一条的结点有一条有向边连到属性有向边连到属性b b的结点。的结点。第六章 属性文法和语法制导翻译 这里要掌握这里要掌握依赖图依赖图的画法。的画法。例如，属性例如，属性 A.a:=f(X.x,Y.y)A.a:=f(X.x,Y.y)对应于产生式对应于产生式 A AXYXY

12、的语义规则的语义规则,这条语这条语义规则确定了依赖于属性义规则确定了依赖于属性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对应的语义规则还有：对应

13、的语义规则还有：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.第六章 属性文法和语法制导翻译例例6.3当下面的产生式应用于语法树时，我们就像图当下面的产生式应用于语法树时，我们就像图6.4所示的那样把有向边加到依赖图中。所示的那样把有向边加到依赖图中。产生式产生式 语义规则语义规则 EE1+E2 E.val:=E1.val+E2.val 例例例例6.46.46.46.

14、4下页的图是书中图下页的图是书中图下页的图是书中图下页的图是书中图6.2 6.2 6.2 6.2（P139P139P139P139）带注释语法树的带注释语法树的带注释语法树的带注释语法树的依赖图。依赖图中的结点由数字来标识，这些数字将依赖图。依赖图中的结点由数字来标识，这些数字将依赖图。依赖图中的结点由数字来标识，这些数字将依赖图。依赖图中的结点由数字来标识，这些数字将在讨论属性的计算次序时用到。从代表在讨论属性的计算次序时用到。从代表在讨论属性的计算次序时用到。从代表在讨论属性的计算次序时用到。从代表T.typeT.typeT.typeT.type的结点的结点的结点的结点4 4 4 4有一条

15、边连到代表有一条边连到代表有一条边连到代表有一条边连到代表L.inL.inL.inL.in的结点的结点的结点的结点5 5 5 5，因为根据产生式，因为根据产生式，因为根据产生式，因为根据产生式D D D DTLTLTLTL的语义规则的语义规则的语义规则的语义规则L1.in=L.in,L1.in=L.in,L1.in=L.in,L1.in=L.in,可知可知可知可知L1.inL1.inL1.inL1.in依赖于依赖于依赖于依赖于L.in,L.in,L.in,L.in,第六章 属性文法和语法制导翻译 所以有两条向下的边分别进入结点所以有两条向下的边分别进入结点7 和和9。每一个。每一个于于L产生式

16、有关的语义规则产生式有关的语义规则addtype(id.entry,L.in)都产都产生一个虚属性，结点生一个虚属性，结点6、8和和10都为这些虚属性构造的。都为这些虚属性构造的。如果一属性文法不存在属性之间的循环依赖关系，如果一属性文法不存在属性之间的循环依赖关系，那么该文法为那么该文法为良定义的。良定义的。为了设计编译程序，我们只为了设计编译程序，我们只处理良定义的属性文法。处理良定义的属性文法。第六章 属性文法和语法制导翻译 属性的计算次序属性的计算次序 一个有向非循环图的拓扑序是图中结点的任何顺序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,mk,使得边必须是从序列中前面的结

17、点指向使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果后面的结点。也就是说，如果mimj是是mi到到mj的一条的一条边，那么在序列边，那么在序列中中mi必须出现在必须出现在mj之前。之前。一个依赖图的任何拓扑排序都给出一个语法树中结一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语义规则中，在一个结点上，语义规则b:=f（c1,c2,ck)中的属中的属性性c1,c2ck在计算在计算b以前都是可用的。以前都是可用的。6。2。2树遍历的属性计算方法树遍历的属性计算方法 通过树遍

18、历计算属性值得方法很多种。这些方法都通过树遍历计算属性值得方法很多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有的属性。最常用的遍历方法是深法树，直至计算出所有的属性。最常用的遍历方法是深度优先，从左到右的遍历方法。度优先，从左到右的遍历方法。第六章 属性文法和语法制导翻译6 6。2 2。3 3一遍扫描的处理方法一遍扫描的处理方法 与树遍历的属性计算方法不同，一遍扫描的方法是在语与树遍历的属性计算方法不同，一遍扫描的

19、方法是在语法分析的同时计算属性值。法分析的同时计算属性值。如果按这种一遍扫描的编译程序模型来理解语法制导翻如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，所谓语法制导翻译法，直观上说是为文法中每译方法的话，所谓语法制导翻译法，直观上说是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则些语义规则.在自上而下的语义分析中在自上而下的语义分析中,若一个产生式匹配输若一个产生式匹配输入串成功入串成功,或者在自下而上分析中或者在自下而上分析中,当一个产生式被用于进行当一个产生式被用于进行归约时归约时,此产生式相应的语

20、义规则就被计算此产生式相应的语义规则就被计算,完成有关语义分完成有关语义分析和代码生成的工作析和代码生成的工作.6.2.4 6.2.4 抽象语法树抽象语法树 建立表达式的抽象语法树建立表达式的抽象语法树,我们通过为每个运算分量或我们通过为每个运算分量或运算符号都建立一个结点来为子表达式建立子树运算符号都建立一个结点来为子表达式建立子树.运算符号运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根表达式组成的子树的根.第六章 属性文法和语法制导翻译 抽象语法树中的每一个结点可以由包含抽象语法树中的每一个结点可以由包含

21、几个域的记录来实现的几个域的记录来实现的.在一个运算符号对在一个运算符号对应的结点中应的结点中,一个域标识运算符号，其它域包一个域标识运算符号，其它域包含指向运算分量的结点的指针。运算符号通含指向运算分量的结点的指针。运算符号通常叫做这个结点的标号。当我们进行翻译时，常叫做这个结点的标号。当我们进行翻译时，抽象语法树中的结点可能会用附加域来存放抽象语法树中的结点可能会用附加域来存放结点的属性值结点的属性值(或指向属性的指针）。或指向属性的指针）。6。3 S属属性文法的自下而上计算性文法的自下而上计算 这一节我们考虑这样一类属性文法：这一节我们考虑这样一类属性文法：S属性文法，它只含有综合属性。

22、属性文法，它只含有综合属性。下面我们讨论分析栈中的综合属性。下面我们讨论分析栈中的综合属性。在自底向上的分析法中。我们使用一个栈来在自底向上的分析法中。我们使用一个栈来存放已经分析过的子树的信息。现在我们可存放已经分析过的子树的信息。现在我们可以在分析栈中使用一个附域来存放综合属性以在分析栈中使用一个附域来存放综合属性值。图值。图6.9表示的是一个带有一个属性值空间表示的是一个带有一个属性值空间的分析栈的例子。的分析栈的例子。State State State State valvalvalval X X.xX X.xX X.xX X.xY Y.yY Y.yY Y.yY Y.yZ Z.zZ Z

23、.zZ Z.zZ Z.z 图图图图6.96.96.96.9toptoptoptop第六章 属性文法和语法制导翻译 我们假设图中的栈是由一对数组我们假设图中的栈是由一对数组state和和val来实现来实现的。每一个的。每一个state元素都是一个指向元素都是一个指向LR(1)分析表的指针分析表的指针（或索引）。（注意，文法符号隐含在（或索引）。（注意，文法符号隐含在state中而不需中而不需要存储在栈中）。然而，如果像第五章中的那样把文要存储在栈中）。然而，如果像第五章中的那样把文法符号存入栈中时，那么当第法符号存入栈中时，那么当第i个个state对应的符号为对应的符号为A时，时，vali中就存

24、放语法树中与结点中就存放语法树中与结点A对应的属性值对应的属性值。设当栈顶由指针设当栈顶由指针top指示。我们假设综合属性是刚指示。我们假设综合属性是刚好在每次归约前计算的。假设语义规则好在每次归约前计算的。假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生是对应于产生式式AXYZ的。在把的。在把XYZ归约成归约成A以前，属性以前，属性Z.z的值放在的值放在valtop中，中，Y.y的值放在的值放在valtop-1中，中，X.x的值放在的值放在valtop-2中。如中。如果一个符号没有综合属性，那么数组果一个符号没有综合属性，那么数组val中相应的元素中相应的元素就不定义。归约就不

25、定义。归约后，后，top值减值减2，A的状态存放在的状态存放在statetop中（也就是中（也就是X的位置）综合属性的位置）综合属性A.a的值存放的值存放在在valtop中。中。第六章 属性文法和语法制导翻译 6 6。4 4 LL属属性文法和自顶向下翻译性文法和自顶向下翻译 一个属性文法称为一个属性文法称为L属性文法属性文法：如果对于每个产生式：如果对于每个产生式AX1X2Xn其每个语义规则中的每个属性或者是综合属性，其每个语义规则中的每个属性或者是综合属性，或者是或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖于：的一个继承属性且这个继承属性仅依赖于：（1）产生式产生式Xj的左边符

26、号的左边符号X1,X2,Xj-1的属性的属性 （2）A的继承属性。的继承属性。6。4。1 翻译模式翻译模式 属性文法可以看成是关于语言翻译的高级规范说明，其属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，称为式，称为翻译模式翻译模式。翻译模式给出了使用语义规则进行计算。翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来。在翻译模式的次序，这样就可以把某些实现细节

27、表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号动作），用花括号 括起来，插入到产生式右部的合适位置括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。上。这样翻译模式给出了使用语义规则进行计算的顺序。第六章 属性文法和语法制导翻译 如果既有综合属性又有继承属性，在建立翻译模如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心：式时就必须特别小心：（1）产生式右边的符号的继承属性必须在这个符）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。号以前的动

28、作中计算出来。（2）一个动作不能引用这个动作右边符号的综合）一个动作不能引用这个动作右边符号的综合属性。属性。（3）产生式左边非终结符的综合属性只有在它所）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算。计算这种属引用的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。性的动作通常可放在产生式右端的末尾。6。4。2 自顶向下翻译自顶向下翻译 在第四章我们知道，为了构造不带回溯的自顶向下在第四章我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。现在我们把前语法分析，必须消除文法中的左递归。现在我们把前面消除左递归的方法加以扩

29、充面消除左递归的方法加以扩充,当消除一个翻译模式的当消除一个翻译模式的基本语法的左递归时同时考虑属性。这种方法适合带基本语法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样许多文法可以使用自顶向综合属性的翻译模式。这样许多文法可以使用自顶向下分析来实现。下分析来实现。第六章 属性文法和语法制导翻译 对于自顶向下的分析，我们假设动作是在处于相对于自顶向下的分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。一个符同位置上的符号被展开（匹配成功）时执行的。一个符号的继承属性必须由出现这个符号之前的动作来计算，号的继承属性必须由出现这个符号之前的动作来计算，产生式左边

30、非终结符的综合属性必须在它的所依赖的所产生式左边非终结符的综合属性必须在它的所依赖的所有属性都计算出来之后才能被计算。有属性都计算出来之后才能被计算。下面我们把转换左递规翻译模式的方法推广到一般，下面我们把转换左递规翻译模式的方法推广到一般，以便进行自顶向下分析：以便进行自顶向下分析：假设我们有下面的翻译模式：假设我们有下面的翻译模式：AA1Y A.a:=g(A1.a,Y.y)AX A.a:=f(X.x)其每个文法符号都有一个综合属性，用小写字母表示，其每个文法符号都有一个综合属性，用小写字母表示，g和和f是任意函数。是任意函数。利用第四章消除左递归的算法，可将其转换成下面利用第四章消除左递归

31、的算法，可将其转换成下面文法：文法：AXR R YR|第六章 属性文法和语法制导翻译再考虑语义动作，翻译模式变为：再考虑语义动作，翻译模式变为：AX R.i:=f(X.x)R A.a:=R.s RY R1.i:=g(R.i),Y.y)R1 R.s:=R1.s R R.s:=R.i 经过转换的翻译模式，使用了经过转换的翻译模式，使用了R的继承属性的继承属性i 和综和综合属性合属性s.6。4。3 递归下降翻译器的设计递归下降翻译器的设计 6。5 自下而上计算继承属性自下而上计算继承属性第六章 属性文法和语法制导翻译例题与习题解答例题与习题解答例例6。1 某程序设计语言说明部分的语法制导定义如下：某

32、程序设计语言说明部分的语法制导定义如下：DTLTint Treal LL1,id Lid 给出语法制导定义及自底向上的翻译模式，并给出语法制导定义及自底向上的翻译模式，并比较两者的不同。比较两者的不同。解：语法制导定义为：解：语法制导定义为：DTL L.in:=T.type Tint T.type:=integer Treal T.type:=real LL1,id L1.in:=L.in,addtype(id.entry,L.in )Lid addtype(id.entry,L.in)第六章 属性文法和语法制导翻译 自底向上分析的翻译模式为：自底向上分析的翻译模式为：DT L.in:=T.t

33、ype LTint T.type:=integer Treal T.type:=real L L1.in:=L.in L1,id addtype(id.entry,L.in )Lid addtype(id.entry,L.in)从上述定义看两者的区别仅在于在翻译模式中把语义动作插入在规则右部的任从上述定义看两者的区别仅在于在翻译模式中把语义动作插入在规则右部的任意位置。而语法制导中把语义动作都放在产生式的最后。意位置。而语法制导中把语义动作都放在产生式的最后。例例6。2 在一个移入在一个移入归约的分析中采用以下的语法制导的翻译模式，在某归约的分析中采用以下的语法制导的翻译模式，在某产生式归约时

34、，立即执行括号中的动作。产生式归约时，立即执行括号中的动作。AaB print “0”Ac print“1”BAb print “2”当分析器输入为当分析器输入为aacbb时，打印的字符串是什么时，打印的字符串是什么?第六章 属性文法和语法制导翻译解：解：分析器的分析过程如右图：分析器的分析过程如右图：由于分析器采用移入归约的方式进行分析，由于分析器采用移入归约的方式进行分析，符号串符号串aacbb的分析过程将按标号进行，的分析过程将按标号进行，而按一产生式归约时立即执行括号中的而按一产生式归约时立即执行括号中的动作所以分析器打印的字符为：动作所以分析器打印的字符为：12020例例6。3 已知

35、表达式抽象语法树的属性文已知表达式抽象语法树的属性文法的翻译模式为：法的翻译模式为：产生式产生式 EE1+T EE1*T ET T(E)Tnum语义动作语义动作语义动作语义动作E.E.E.E.nptrnptrnptrnptr:=:=:=:=mknodemknodemknodemknode(+,E1.(+,E1.(+,E1.(+,E1.nptrnptrnptrnptr,T.,T.,T.,T.nptrnptrnptrnptr)E.E.E.E.nptrnptrnptrnptr:=:=:=:=mknodemknodemknodemknode(*,E1.(*,E1.(*,E1.(*,E1.nptrnpt

36、rnptrnptr,T.,T.,T.,T.nptr nptr nptr nptr)E.E.E.E.nptrnptrnptrnptr:=T.:=T.:=T.:=T.nptrnptrnptrnptrT.T.T.T.nptrnptrnptrnptr:=E.:=E.:=E.:=E.nptrnptrnptrnptrT.T.T.T.npternpternpternpter:=:=:=:=mknodemknodemknodemknode(num,num.(num,num.(num,num.(num,num.val val val val)第六章 属性文法和语法制导翻译求其消除左递归后的翻译模式：求其消除左递

37、归后的翻译模式：解：解：E T R.i:=T.type R E.nptr:=R.s R+T R1.i :=mknode(+,R.i,T.nptr)R1 R.s :=R1.s R*T R1.i:=mknode(*,R.i,T.nptr)R1 R.s:=R1.s R R.s:=R.i T(E )T.nptr:=E.nptr Tnum T.nptr:=mknode(num,num.val)第六章 属性文法和语法制导翻译第七章第七章 语义分析和中间代码语义分析和中间代码的产生（的产生（1 1）本章首先要掌握几种中间语言的基本章首先要掌握几种中间语言的基本结构：逆波兰表示，图表示法（本结构：逆波兰表示，图表示法（DAG DAG 和和筹集语法树），三地址代码（四元式、三筹集语法树），三地址代码（四元式、三元式、间接三元式）元式、间接三元式）第六章 属性文法和语法制导翻译