编译原理课件chap6

《编译原理课件chap6》由会员分享，可在线阅读，更多相关《编译原理课件chap6（21页珍藏版）》请在金锄头文库上搜索。

1、第六第六章章 属性文法和语法制导属性文法和语法制导 翻译翻译从本章开始，我们介绍有关语 义分析及翻译的问题。其处理的方法 主要是属性文法和语法制导翻译方法 。 本章中，我们将首先介绍属性 文法的基本概念，然后介绍基于属性 文法的处理方法，讨论如何自上而下 分析和自下而上分析中实现属性计算 。 本章重点掌握前四节6.1属性文 法，6.2基于属性文法的处理方法， 6.3 S属性文法的自下而上计算， 6.4 L属性文法和自顶向下翻译。第六章 属性文法和语法制导翻译6。1属性文法属性文法是在上下文无关文法的基础上为每个文 法符号（终结符或非终结符）配备若干个相关的“值”（ 称为属性）。这些属性代表与文

2、法符号相关的信息，例如 它的类型、值、代码序列、符号表内容等等。属性和变量 一样，可以进行计算和传递。属性一般分为两类：综合属性和继承属性。简 单的说，综合属性用于“自下而上”传递信息，而继承属 性用于“自上而下”传递信息。属性加工加工的过程即是语义处理的过程，对 于文法的每一个产生式都配备了一组属性的计算规则，则 称为语义规则。在一个属性文法中，对应于每个产生式A 都有一套与之相关联的语义规则，每条语义规则的形式为 ：第六章 属性文法和语法制导翻译b:=f(c1,c2,ck) 这里f是一个函数，而且或者（1）b是A的一个综合属性并且c1,c2,ck是产生式右边文法 符号的属性；或者（2）b是

3、产生式右边某个文法符号的一个继承属性并且 c1,c2,ck是A或产生式右边任何文法符号的属性在这两种情况下，我们都说属性b依赖于属性 c1,c2,ck.要特别强掉的是：（1）终结符只有综合属性，它由词法分析器提供；（2）非终结符既可以有综合属性也可以有继承属性，文法开 始符号的所有继承属性作为属性计算前的初始值。一般来讲，对出现在产生式右边的继承属性和出现在产生式 左边的综合属性都必须提供一个计算规则，属性计算规则中只 能使用相应产生式的文法符号的属性，这有利于产生式范围内 “封装”属性的依赖性。然而，出现在产生式左边的继承属性 和出现在产生式右边的综合属性不由所给的产生式的属性计算 规则进行

4、计算，它们由其它产生式的属性规则计算,由属性计算 器的参数提供第六章 属性文法和语法制导翻译语义规则所描述的工作可以包括属性计算 、静态语义检查、符号表操作、代码生成等。语义规则 可能产生副作用（如产生代码），也可能不是变元的严 格函数（如某个规则给出可用的下一个数据单元的地址 ）。这样的语义规则通常写成过程调用，或过程段。综合属性：在语法树中，一个结点的综合属性的值 由其子结点的属性值确定。因此，通常使用自底向上的 方法在每一个结点处使用语义规则计算综合属性的值。 仅仅使用综合属性的属性文法称S属性文法。继承属性：在语法树中，一个结点的继承属性由此 结点的父结点和/或兄弟结点的某些属性确定。

5、用继承属 性来表示程序语言结构中的上下文依赖关系很方便。第六章 属性文法和语法制导翻译6。2 基于属性文法的处理方法 从概念上讲，基于属性文法的处理过程通常是这样的： 对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历 语法树，并在语法树的各结点处按语义规则进行计算。输入串语法树依赖图语义规则计算次序这种由源程序的语法结构所驱动的处理办法就是语法制 导翻译法。语义规则的计算可能产生代码、在符号表中存放信息、 给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语 义规则进行计算得出结果。 6。2。1依赖图如果在一棵语法树中一个结点的属性b依赖于属性c， 那么这个结点处计算b的属性规

6、则必须在确定c的语义规则之后使用 。在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关 系可以用称作依赖图的一个有向图来描述。 在为一棵语法树构造依赖图以前，我们为每一个包含 过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则 都写成 b:= f(c1,c2, ck) 的形式。依赖图中为每一 个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一 条有向边连到属性b的结点。第六章 属性文法和语法制导翻译这里要掌握依赖图的画法。例如，属性A.a:=f( X.x, Y.y )对应于产生式 AXY的语义规则, 这条语义规则确定了依赖于属性X.x和Y.y的综合 属性A.a。 如

7、果在语法树中应用这个产生式，那 么在依赖图中会有三个结点A.a,X.x,和Y.y。由 于A.a依赖X.x，所以有一条有向边从X.x到A.a. 由于A.a也依赖于Y.y，所以还有一条有向边从 Y.y连到A.a.如果与产生式AXY对应的语义规则 还有：X.i:=g(A.a,Y.y)那么，图中还应有两条有向边，一条从 A.a连到X.i，另一条从Y.y连到X.i ,因为X.i依赖于A.a和Y.y.第六章 属性文法和语法制导翻译例6.3当下面的产生式应用于语法树时，我们就像 图6.4所示的那样把有向边加到依赖图中。产生式 语义规则EE1+E2 E.val:=E1.val+E2.val 例例6.46.4下

8、页的图是书中图下页的图是书中图6.2 6.2 （P139P139）带注释语法带注释语法 树的依赖图。依赖图中的结点由数字来标识，这些数字树的依赖图。依赖图中的结点由数字来标识，这些数字 将在讨论属性的计算次序时用到。从代表将在讨论属性的计算次序时用到。从代表T.typeT.type的结点的结点4 4 有一条边连到代表有一条边连到代表L.inL.in的结点的结点5 5，因为根据产生式，因为根据产生式D DTLTL 的语义规则的语义规则L1.in=L.in,L1.in=L.in,可知可知L1.inL1.in依赖于依赖于L.in,L.in,第六章 属性文法和语法制导翻译所以有两条向下的边分别进入结点

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

10、，在一个结点上，语义规则b:=f（c1,c2,ck)中的属 性c1,c2ck在计算b以前都是可用的。 6。2。2树遍历的属性计算方法通过树遍历计算属性值得方法很多种。这些 方法都假设语法树已经建立起了，并且树中已带有开始符 号的继承属性和终结符的综合属性。然后以某种次序遍历 语法树，直至计算出所有的属性。最常用的遍历方法是深 度优先，从左到右的遍历方法。第六章 属性文法和语法制导翻译6。2。3一遍扫描的处理方法与树遍历的属性计算方法不同，一遍扫描的方法是 在语法分析的同时计算属性值。如果按这种一遍扫描的编译程序模型来理解语法制 导翻译方法的话，所谓语法制导翻译法，直观上说是为文法中 每个产生式

11、配上一组语义规则，并且在语法分析的同时执行这 些语义规则.在自上而下的语义分析中,若一个产生式匹配输入 串成功,或者在自下而上分析中,当一个产生式被用于进行归约 时,此产生式相应的语义规则就被计算,完成有关语义分析和代 码生成的工作. 6.2.4 抽象语法树建立表达式的抽象语法树,我们通过为每个运算分 量或运算符号都建立一个结点来为子表达式建立子树. 运算符 号结点的各子结点分别是表示该运算符号的各个运算分量的子 表达式组成的子树的根.第六章 属性文法和语法制导翻译抽象语法树中的每一个结点可以由 包含几个域的记录来实现的. 在一个运算符号 对应的结点中,一个域标识运算符号，其它域包 含指向运算

12、分量的结点的指针。运算符号通常 叫做这个结点的标号。当我们进行翻译时，抽 象语法树中的结点可能会用附加域来存放结点 的属性值(或指向属性的指针）。 6。3 S属性文法的自下而上计算这一节我们考虑这样一类属性文法 ：S属性文法，它只含有综合属性。下面我们讨论分析栈中的综合属性。在自底向上的分析法中。我们使用一个 栈来存放已经分析过的子树的信息。现在我们 可以在分析栈中使用一个附域来存放综合属性 值。图6.9表示的是一个带有一个属性值空间的 分析栈的例子。State State valval X X.xX X.x Y Y.yY Y.y Z Z.zZ Z.z 图图6.96.9toptop第六章 属性

13、文法和语法制导翻译我们假设图中的栈是由一对数组state和val 来实现的。每一个state元素都是一个指向LR(1)分析表的 指针（或索引）。（注意，文法符号隐含在state中而不 需要存储在栈中）。然而，如果像第五章中的那样把文 法符号存入栈中时，那么当第i个state对应的符号为A时 ，vali中就存放语法树中与结点A对应的属性值。设当栈顶由指针top指示。我们假设综合属性 是刚好在每次归约前计算的。假设语义规则 A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的。在把 XYZ归约成A以前，属性Z.z的值放在valtop中，Y.y的 值放在valtop-1中，X.x的值放在v

14、altop-2中。如果一个 符号没有综合属性，那么数组val中相应的元素就不定义 。归约后，top值减2，A的状态存放在statetop中（也就 是X的位置）综合属性A.a的值存放在valtop中。第六章 属性文法和语法制导翻译6。4 L属性文法和自顶向下翻译一个属性文法称为L属性文法：如果对于每个产 生式AX1X2Xn其每个语义规则中的每个属性或者是综合属 性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖 于：（1）产生式Xj的左边符号X1,X2,Xj-1的属性（2）A的继承属性。 6。4。1 翻译模式属性文法可以看成是关于语言翻译的高级规范说明 ，其中隐去实现细节，使用户从明

15、确说明翻译顺序的工作中解 脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形 式，称为翻译模式。翻译模式给出了使用语义规则进行计算的 次序，这样就可以把某些实现细节表示出来。在翻译模式中， 和文法符号相关的属性和语义规则（这里我们也称语义动作） ，用花括号 括起来，插入到产生式右部的合适位置上。这样 翻译模式给出了使用语义规则进行计算的顺序。第六章 属性文法和语法制导翻译如果既有综合属性又有继承属性，在建立翻 译模式时就必须特别小心：（1）产生式右边的符号的继承属性必须在这 个符号以前的动作中计算出来。（2）一个动作不能引用这个动作右边符号的 综合属性。（3）产生式左边非终结符的综合属性只

16、有在 它所引用的所有属性都计算出来后才能计算。计算这种 属性的动作通常可放在产生式右端的末尾。 6。4。2 自顶向下翻译在第四章我们知道，为了构造不带回溯的自顶 向下语法分析，必须消除文法中的左递归。现在我们把 前面消除左递归的方法加以扩充,当消除一个翻译模式的 基本语法的左递归时同时考虑属性。这种方法适合带综 合属性的翻译模式。这样许多文法可以使用自顶向下分 析来实现。第六章 属性文法和语法制导翻译对于自顶向下的分析，我们假设动作是在处 于相同位置上的符号被展开（匹配成功）时执行的。一个 符号的继承属性必须由出现这个符号之前的动作来计算， 产生式左边非终结符的综合属性必须在它的所依赖的所有 属性都计算出来之后才能被计算。下面我们把转换左递规翻译模式的