208 编译原理及实践 China-pub.Co 下载 性。基本上，这等于将属性等式转化为计算规则。因此，属性等式 Xa=a,X。agXa,,Xa,，Xa,,Xa) 被看作把右边的函数表达式的值赋给属性X?。为达到这一点，在右边出现的所有属性值必须 已经存在。在属性文法的说明中，这个要求可能被忽略，可以将等式写成任意顺序而不会影响 正确性。实现对应于属性文法的算法规则的问题，主要在于为赋值和属性分配寻找 一个顺序 并确保当每次进行计算时使用的所有属性值都是有效的。属性等式本身指示了属性计算时的顺 序约束，首先是使用指示图表示这些约束来明确顺序的约束。这些指示图叫做相关图。 6.2.1相关图和赋值顺序 给定一个属性文法，每个文法规则选择有一个相关依赖图(associated dependency graph) 文法规则中的每个符号在这个图中都有用每个属性X标记的节点，对每个属性等式 Xa=f(.,X.a,…) 相关于文法规则从在右边的每个节点Xa,到节点Xa,有一条边（表示Xa对Xa,的依赖）。依据 上下文无关文法，在语言产生时给定一个合法的字符串，这个字符串的依赖图(dependency graph)就是字符串语法树中选择表示每个（非叶子）节点文法规则依赖图的联合。 在绘制每个文法规则或字符串的依赖图时，与每个符号X相关的节点均画在一组中，这样 依赖就可以看作是语法树的构造。 例6.6 考虑例6.1的文法，属性文法在表6-1中给出。这里只有一个属性vl,因此每个符号在 每个依赖图中只有一个节点对应于其al属性。选择umber,→number,.digit的文法规则有单个 的相关属性等式 number val number,.val *10+digit.val 这个文法规则选择的依赖图是 ber-val number.val (在以后的依赖图中，因为图形化表示可以清楚地区分不同节点的不同出现，所以对重复的符 号将省略下标)。 类似地，属性等式mber.ral=digit.val冲文法规则number一digi的相关图是 number.val digit.val 对于剩下的形如dig一D的文法规则，因为digit.val可以从规则的右边直接计算，其相关图是无 足轻重的（它们没有边）。 最后，对应于语法树（见图6-1），字符串345的相关图如下 digit.val di
性。基本上，这等于将属性等式转化为计算规则。因此，属性等式 Xi .aj = f i j (X0 .a1 , . . . , X0 .ak，X1 .a1 , . . . , X1 .ak，. . . ，Xn .a1 , . . . , Xn .ak ) 被看作把右边的函数表达式的值赋给属性 Xi . aj 。为达到这一点，在右边出现的所有属性值必须 已经存在。在属性文法的说明中，这个要求可能被忽略，可以将等式写成任意顺序而不会影响 正确性。实现对应于属性文法的算法规则的问题，主要在于为赋值和属性分配寻找一个顺序， 并确保当每次进行计算时使用的所有属性值都是有效的。属性等式本身指示了属性计算时的顺 序约束，首先是使用指示图表示这些约束来明确顺序的约束。这些指示图叫做相关图。 6.2.1 相关图和赋值顺序 给定一个属性文法，每个文法规则选择有一个相关依赖图 (associated dependency graph)。 文法规则中的每个符号在这个图中都有用每个属性 Xi . aj 标记的节点，对每个属性等式 Xi . aj = f i j ( . . . , Xm .ak , . . . ) 相关于文法规则从在右边的每个节点Xm .ak 到节点Xi . aj 有一条边(表示Xi . aj 对Xm .ak 的依赖)。依据 上下文无关文法，在语言产生时给定一个合法的字符串，这个字符串的依赖图 ( d e p e n d e n c y g r a p h )就是字符串语法树中选择表示每个(非叶子)节点文法规则依赖图的联合。 在绘制每个文法规则或字符串的依赖图时，与每个符号 X相关的节点均画在一组中，这样 依赖就可以看作是语法树的构造。 例6.6 考虑例6 . 1的文法，属性文法在表 6 - 1中给出。这里只有一个属性 v a l，因此每个符号在 每个依赖图中只有一个节点对应于其val 属性。选择n u m b e r1 → n u m b e r2 .digit 的文法规则有单个 的相关属性等式 n u m b e r1 .val = n u m b e r2 .val * 10 + d i g i t . v a l 这个文法规则选择的依赖图是 (在以后的依赖图中，因为图形化表示可以清楚地区分不同节点的不同出现，所以对重复的符 号将省略下标)。 类似地，属性等式n u m b e r. v a l = d i g i t . v a l中文法规则n u m b e r → d i g i t的相关图是 对于剩下的形如d i g i t→D的文法规则，因为digit.val 可以从规则的右边直接计算，其相关图是无 足轻重的(它们没有边)。 最后，对应于语法树(见图6 - 1 )，字符串3 4 5的相关图如下： 2 0 8 编译原理及实践 下载 n u m b e r. v a l ↑ d i g i t . v a l
China-pub.Com 下载 第6度语义分析209 例6.7考虑例6.3的文法，属性dpe的属性文法在表6-3中给出。在这个例子中，文法规则var lis,一id,rar-lis,有两个相关的属性等式 id dtype=var-list drype var-list,.dtype var-list,.dtype 依赖图是 varlistdrype var-list.dtype 类似地，文法规则var-ist一id的相关图是 var-list.dtype iddrype →int和ype 一f1oat两个规则的相关图无关紧要。 最后，与等式var-isl.dpe=pe.dpe相关的decl一ype var-lis规则的相关图是 ype.arype var-listdrype 在这种情况中，因为dcl不直接包含在相关图中，所以这个相关图相关的文法规则并不完全清 晰。正因为这一点（稍后将讨论其他一些原因），我们通常重叠在相应的文法规则的语法树片段 上绘制相关图。这样，上面的相关图就可以画作 decl -drype var-list 这就使和相关有关的文法规则更加清晰。还要注意，在画语法树节点时我们禁止使用属性的圆 点符号，而是通过写出与其相连的下一个节点来表示属性。这样，在这个例子中第一个相关图 也可以画作 drype var-list drype var-list 最后，字符串f1oatx,y的相关图是
例6.7 考虑例6 . 3的文法，属性d t y p e的属性文法在表6 - 3中给出。在这个例子中，文法规则v a rl i s t 1 →id , v a r- l i s t 2 有两个相关的属性等式 i d dtype = v a r- l i s t1 .d t y p e v a r- l i s t2 .dtype = v a r- l i s t1 .d t y p e 依赖图是 类似地，文法规则v a r- l i s t →i d 的相关图是 type →i n t 和type →f l o a t 两个规则的相关图无关紧要。 最后，与等式v a r- l i s t.dtype = t y p e.d t y p e相关的decl →type var-list 规则的相关图是 t y p e.dtype ——→ v a r- l i s t.d t y p e 在这种情况中，因为d e c l不直接包含在相关图中，所以这个相关图相关的文法规则并不完全清 晰。正因为这一点(稍后将讨论其他一些原因 )，我们通常重叠在相应的文法规则的语法树片段 上绘制相关图。这样，上面的相关图就可以画作 这就使和相关有关的文法规则更加清晰。还要注意，在画语法树节点时我们禁止使用属性的圆 点符号，而是通过写出与其相连的下一个节点来表示属性。这样，在这个例子中第一个相关图 也可以画作 最后，字符串float x,y的相关图是 第 6章 语 义 分 析 2 0 9 下载 v a r- l i s t.d t y p e i d. d t y p e
210 编译原理及实践 China-pub.Com 下载 例6.8 考虑例6.4基于数的文法，属性base和val的属性文法在表6-4中给出。画出下面4条文法 规则 based-num-num basecha num→num digi um一digit digit-9 和字符串3450的相关图，其语法树在图6-4中给出。 首先从文法规则based-um一num basechart的相关图开始： based-nm basechar bas 这个图表示了based-nm.val=num.ral和num.base=basechar..base两个相关的等式的相关。 接下来再画出与文法规则um一num digit相对应的相关图： 这个图表示3个属性等式的相关 num .val= if digit.val-error or numval-erron then error else num,.val num,base +digit.val num,base=mm,base digit.base=num base 文法规则m一dig的相关图也与此类似： base 最后，画出文法规则dgt→9的相关图： 这个图表示由等式ligit.val=if digi.base=8 then error else9创建的相关，也就是digit.val与于 digit base(这是if表达式测试的一部分)相关。现在剩下画出字符串345o的相关图，如图6-6所示
例6.8 考虑例6 . 4基于数的文法，属性b a s e和v a l的属性文法在表6 - 4中给出。画出下面4条文法 规则 b a s e d-n u m → n u m b a s e c h a r n u m → n u m d i g i t n u m → d i g i t d i g i t → 9 和字符串3 4 5 o的相关图，其语法树在图6 - 4中给出。 首先从文法规则b a s e d-n u m → n u m b a s e c h a r的相关图开始： 这个图表示了b a s e d-n u m.v a l = n u m.v a l和n u m.b a s e = b a s e c h a r.b a s e两个相关的等式的相关。 接下来再画出与文法规则n u m → n u m d i g i t相对应的相关图： 这个图表示3个属性等式的相关 n u m1 .v a l = i f d i g i t . v a l = e rro r o r n u m2 .v a l = e rro r then e rro r e l s e n u m2 .v a l * n u m1 .b a s e + d i g i t . v a l n u m2 .b a s e = n u m1 .b a s e d i g i t.b a s e = n u m1 .b a s e 文法规则n u m → d i g i t的相关图也与此类似： 最后，画出文法规则d i g i t → 9的相关图： 这个图表示由等式d i g i t . v a l = i f d i g i t.b a s e = 8 then e rro r else 9创建的相关，也就是digit.val 与于 d i g i t.b a s e(这是if 表达式测试的一部分)相关。现在剩下画出字符串3 4 5 o的相关图，如图6 - 6所示。 2 1 0 编译原理及实践 下载
China-pub.com 第6章语义分析211 下载 base 图6-6字符串345o的相关图（例6.8） 假设现在要确定一个算法，使用属性等式作为计算规则来计算一个属性文法的属性。给定 要转换的一个特定的记号字符串，字符串语法树的相关图根据计算字符串属性的算法给出了 系列顺序约束。实际上，任一个算法在试图计算任何后继节点的属性之前，必须计算相关图中 每个节点的属性。遵循这个限制的相关图遍历顺序称作拓扑排序((topological sort),而且众所周 知，存在拓扑排序的充分必要条件是相关图必须是非循环(acyclic)的。这样的图形称作确定非 循环图(directed acyclic graphs,DAGs). 例6.9图6-6的相关图是一个DAG。在图6-7中，给节点编上号（为便于观察别除了下面的语法 树)。根据节点的编号给出了一个拓扑排序的顺序。另一个拓扑排序的顺序是 1269121138457101314 ④al ②ba ①ba ③bae 回al ④bart⑦l⑧base ⑨vad 图6-7字符串345o的相关图（例6.9） 在图的根节点上如何找到属性值（图的根节点是没有前驱的节点）是在使用相关图的拓扑排 序计算属性值时产生的一个问题。在图6-7中，节点1、6、9、12都是图的根节点9。这些节点 的属性值不依赖于任何其他属性，因此必须使用直接可用的信息计算。这个信息通常在相应的 语法树节点的子孙记号表中。例如，在图6-7中，节点6的val依赖于记号3，它是对应于va的 dg节点的子节点（见图6-6）。因此，节点6的属性值是3。所有这些根节点的值都需要在计算其 他任何属性值之前计算。这些计算通常由扫描器或语法分析程序来完成。 ©相关图的根节点不要和语法树的根节点混淆
图6-6 字符串3 4 5 o 的相关图(例6 . 8 ) 假设现在要确定一个算法，使用属性等式作为计算规则来计算一个属性文法的属性。给定 要转换的一个特定的记号字符串，字符串语法树的相关图根据计算字符串属性的算法给出了一 系列顺序约束。实际上，任一个算法在试图计算任何后继节点的属性之前，必须计算相关图中 每个节点的属性。遵循这个限制的相关图遍历顺序称作拓扑排序 (topological sort)，而且众所周 知，存在拓扑排序的充分必要条件是相关图必须是非循环 ( a c y c l i c )的。这样的图形称作确定非 循环图(directed acyclic graphs，D A G s )。 例6.9 图6 - 6的相关图是一个D A G。在图6 - 7中，给节点编上号(为便于观察删除了下面的语法 树)。根据节点的编号给出了一个拓扑排序的顺序。另一个拓扑排序的顺序是 12 6 9 1 2 11 3 8 4 5 7 10 13 14 图6-7 字符串3 4 5 o 的相关图(例6 . 9 ) 在图的根节点上如何找到属性值 (图的根节点是没有前驱的节点 )是在使用相关图的拓扑排 序计算属性值时产生的一个问题。在图 6 - 7中，节点1、6、9、1 2都是图的根节点 。这些节点 的属性值不依赖于任何其他属性，因此必须使用直接可用的信息计算。这个信息通常在相应的 语法树节点的子孙记号表中。例如，在图 6 - 7中，节点6的v a l依赖于记号3，它是对应于v a l的 d i g i t节点的子节点(见图6 - 6 )。因此，节点6的属性值是3。所有这些根节点的值都需要在计算其 他任何属性值之前计算。这些计算通常由扫描器或语法分析程序来完成。 第 6章 语 义 分 析 2 1 1 下载 相关图的根节点不要和语法树的根节点混淆
212 编译原理及实践 China-pub.com 载 在编译以及随后的为了确定属性赋值的顺序而进行的相关图的拓扑排序过程中，基于一个 算法在相关图的构造上进行属性分析是可能的。因为在编译时相关图的构造是基于特定的语法 树的，这个方法有时称作分析树方法(parse tree method)。在任何非循环(noncircular)的属性文 法中能够对属性赋值，也就是说，对每一个可能的相关图属性文法是非循环的。 这种方法有几个问题。首先，在编译时构造相关图增加了额外的复杂性。其次，这种方法 在编译时确定相关图是否非循环时，它通常不恰当地等待发现一个环，直到到达编译时间，因 为在原始的属性文法中，环几乎都是表示错误。换句话说，属性文法必须预先进行无环测试。 有一个算法进行这个工作（参见“注意与参考”一节），但这是一个时间指数级增长的算法。当 然，这个算法只需要在编译器构造时运行一次，因此这不能成为反对这个算法的压倒性的证据 (至少对编译器的构造而言)。这种方法的复杂性就是更强的证据。 上述的属性赋值的另一种方法（几乎每一个编译器都采用）即编译器编写者在编译器构造时 分析属性文法，并固定一个属性赋值顺序。虽然这种方法仍然使用语法树作为属性赋值的指导， 但因为它依巅于对属性等式或语义规则的分析，所以它仍被称作基于规则的方法(rule-based mhod)。在编译器构造时固定属性赋值顺序的这一类属性文法没有所有的非循环属性文法通 用，但在实际中，所有合理的属性文法都有这个特性。它们有时称作强非循环(strongly noncircular)属性文法。在下面的例子后面，我们将对这类属性文法讨论基于规则的算法。 例6.10再次考虑例6.8的相关图和例6.9中讨论的相关图的拓扑排序（见图6-7）。虽然图6-7中的 节点6、9和12是DAG的根节点，并且因此都能够出现在拓扑排序的开始，但在基于规则的方 法中这是不可能的。其原因是如果相应的记号是8或9，任何l可能依赖于与它相关的dg1节 点的base。例如，对digit→9相关图是 9 因此，在图6-7中，节点6可能依赖于节点5，节点9可能依赖于节点8，而节点12可能依赖于节 点1。在基于规则的方法中，这些节点将在任何可能潜在依赖的节点之后被强制赋值。因此 一种赋值顺序，首先赋值节点12（见例6.9），这对图6-7中特定的树是正确的，但对基于规则的 算法这是错误的顺序，因为它将破坏其他语法树的顺序。 6.2.2合成和继承属性 基于规则的属性赋值依赖于分析树或语法树明确或不明确的遍历。不同种类的遍历处理的 属性相关，在项目和能力的种类上都不同。为了研究这些不同之处，首先必须根据它们具有的 相关的种类对属性分类。处理的最简单的依赖是综合属性，定义如下。 定义 一个属性是合成的(synthe zed) ,如果在语法树中它所有的相关都从子节点指 向父节点。等价地，一个属性a是合成的，如果给定一个文法规则A一X,X,X,左 边仅有一个a的相关属性等式有以下形式 A.a=f(X.a.,...,X.a. ...,Xa.,...,Xd.) 一个属性文法中所有的属性都是合成的，就称作S属性文法(S-attributed grammar)。 我们已经见过了一些合成属性和S属性文法的例子。在例6.I中数的l属性是合成的（参见
在编译以及随后的为了确定属性赋值的顺序而进行的相关图的拓扑排序过程中，基于一个 算法在相关图的构造上进行属性分析是可能的。因为在编译时相关图的构造是基于特定的语法 树的，这个方法有时称作分析树方法 (parse tree method)。在任何非循环( n o n c i r c u l a r )的属性文 法中能够对属性赋值，也就是说，对每一个可能的相关图属性文法是非循环的。 这种方法有几个问题。首先，在编译时构造相关图增加了额外的复杂性。其次，这种方法 在编译时确定相关图是否非循环时，它通常不恰当地等待发现一个环，直到到达编译时间，因 为在原始的属性文法中，环几乎都是表示错误。换句话说，属性文法必须预先进行无环测试。 有一个算法进行这个工作 (参见“注意与参考”一节 )，但这是一个时间指数级增长的算法。当 然，这个算法只需要在编译器构造时运行一次，因此这不能成为反对这个算法的压倒性的证据 (至少对编译器的构造而言)。这种方法的复杂性就是更强的证据。 上述的属性赋值的另一种方法 (几乎每一个编译器都采用 )即编译器编写者在编译器构造时 分析属性文法，并固定一个属性赋值顺序。虽然这种方法仍然使用语法树作为属性赋值的指导， 但因为它依赖于对属性等式或语义规则的分析，所以它仍被称作基于规则的方法 ( r u l e - b a s e d m e t h o d )。在编译器构造时固定属性赋值顺序的这一类属性文法没有所有的非循环属性文法通 用，但在实际中，所有合理的属性文法都有这个特性。它们有时称作强非循环 ( s t r o n g l y n o n c i r c u l a r )属性文法。在下面的例子后面，我们将对这类属性文法讨论基于规则的算法。 例6.10 再次考虑例6 . 8的相关图和例6 . 9中讨论的相关图的拓扑排序(见图6 - 7 )。虽然图6 - 7中的 节点6、9和1 2是D A G的根节点，并且因此都能够出现在拓扑排序的开始，但在基于规则的方 法中这是不可能的。其原因是如果相应的记号是 8或9，任何val 可能依赖于与它相关的digit 节 点的b a s e。例如，对d i g i t → 9相关图是 因此，在图6 - 7中，节点6可能依赖于节点5，节点9可能依赖于节点8，而节点1 2可能依赖于节 点11。在基于规则的方法中，这些节点将在任何可能潜在依赖的节点之后被强制赋值。因此， 一种赋值顺序，首先赋值节点 1 2 (见例6 . 9 )，这对图6 - 7中特定的树是正确的，但对基于规则的 算法这是错误的顺序，因为它将破坏其他语法树的顺序。 6.2.2 合成和继承属性 基于规则的属性赋值依赖于分析树或语法树明确或不明确的遍历。不同种类的遍历处理的 属性相关，在项目和能力的种类上都不同。为了研究这些不同之处，首先必须根据它们具有的 相关的种类对属性分类。处理的最简单的依赖是综合属性，定义如下。 定义 一个属性是合成的( s y n t h e s i z e d )，如果在语法树中它所有的相关都从子节点指 向父节点。等价地，一个属性a 是合成的，如果给定一个文法规则A →X1 X2 . . . Xn ，左 边仅有一个a 的相关属性等式有以下形式 A.a = f (X1 .a1，. . . ，X1 .ak，. . . ，Xn .a1，. . . ，Xn .ak ) 一个属性文法中所有的属性都是合成的，就称作S属性文法(S-attributed grammar)。 我们已经见过了一些合成属性和 S属性文法的例子。在例6 . 1中数的val 属性是合成的(参见 2 1 2 编译原理及实践 下载