China-pub.com 下载 第6京语义分析203 表6-2例6.2的属性文法 文法规则 语义规则 exp,→ep:+ierm ep一exp-lerm ep→lerm exp.val-term.val term,→ierl,*factor term,val -term,val factor.val term→factor term.val -factor.val factor→(exp) factoryal exp val factor→number factor.val =number.val 这些等式表示了表达式的语法和它所进行的算术运算的语义之间的关系。注意，在文法 规则 xp,一ep,+term 中语义符号+（记号）和等式 exp,val exp,val term.val 中执行的算术加运算符+的不同。还要注意aumber.val不会在等式的左边。就像在下一节将看 到的，这意味着必须在任意一个使用这个属性文法（例如扫描器）的语义分析之前计算 number.val。换句话说，如果想在属性文法中明确这个值，就必须在属性文法中加进文法规 则和属性等式（例如，例6.1中的等式）。 如例6.1一样，也可以通过在语法树的节点上附加等式来表示属性文法包含的计算。例如， 给定表达式(34-3)*42，可以用在其语法树上值的语义来表达，如图6-2所示。 0al3302 0al=3到2=130z 3) () facte 31) a5 (d 331) () 234 036 图6-2(34-3)*42的语法树，显示例6,2中属性文法的val属性计算
表6-2 例6 . 2的属性文法 文 法 规 则 语 义 规 则 e x p1 → e x p2 + t e r m e x p1 .val = e x p2 .val + t e r m.v a l e x p1 → e x p2 - t e r m e x p1 .val = e x p2 .v a l - t e r m.v a l exp → t e r m e x p.v a l = t e r m.v a l t e r m1 → t e r m2 * f a c t o r t e r m1 .val = t e r m2 .val * f a c t o r.v a l t e r m → f a c t o r term.val = f a c t o r.v a l f a c t o r → (e x p) f a c t o r.val = exp.val f a c t o r → n u m b e r f a c t o r.val = n u m b e r.val 这些等式表示了表达式的语法和它所进行的算术运算的语义之间的关系。注意，在文法 规则 e x p1→ e x p2 + t e r m 中语义符号 +(记号)和等式 e x p1 .val = e x p2 .val + t e r m.v a l 中执行的算术加运算符 + 的不同。还要注意n u m b e r. v a l不会在等式的左边。就像在下一节将看 到的，这意味着必须在任意一个使用这个属性文法 (例如扫描器 )的语义分析之前计算 n u m b e r. v a l。换句话说，如果想在属性文法中明确这个值，就必须在属性文法中加进文法规 则和属性等式(例如，例6 . 1中的等式)。 如例6 . 1一样，也可以通过在语法树的节点上附加等式来表示属性文法包含的计算。例如， 给定表达式( 3 4 - 3 ) * 4 2，可以用在其语法树上值的语义来表达，如图 6 - 2所示。 图6-2 ( 3 4 - 3 ) * 4 2 的语法树，显示例6 . 2中属性文法的v a l属性计算 第 6章 语 义 分 析 2 0 3 下载
204编形服理及实我 China-pub.c 下载 例6.3考虑下列类似C语法中变量声明的简单文法 decl type var-list pe→int|float var-list -id var-list id 我们要为在声明中标识符给出的变量定义一个数据类型属性，并写出一个等式来表示数据 类型属性是如何与声明的类型相关的。通过构造dp属性的一个属性文法可以实现这一点（使 用名字dpe和非终结符p的属性进行区分)。dpe的属性文法在表6-3中给出。在图中关于属 性等式我们做了以下标记。 首先，从{integer,real集合中得出dpe的值，相应的记号为int和E1oat。非终结符pe 有一个它表示的记号给定的dpe。通过decl文法规则的等式，这个dpe对应于全体var-lis的 dpe。通过var-list的等式，表中的每个id都有相同的dpe。注意，没有等式包含非终结符 dcl的dpe。实际上decl并不需要dpe,一个属性的值没有必要为所有的文法符号指定。 同前面一样，可以在一个语法树上显示属性等式。图6-3给出了一个例子。 表6-3例6.3的属性文法 文法规则 语义规则 var-lisopeype.dype type.drype intege 0pe→f1oat pe.drype real ran-lil.→主d,ar-isl id dnype var-list drype var-list drype=var-list,drype var-list-id id -var-list.drype 图6-3字符串foat x.y的语法树，显示表6-3冲属性文法指定的dypc属性 到目前为止，所有的例子都只有一个属性，但属性文法可能会包含几个独立的属性。下一 个例子是一个有几个相互联系属性的简单情形。 例6.4考虑对例6.1中数文法进行修改，数可以是八进制或十进制的。假设这通过一个字符的 后缀o(八进制)或（什进制）来表示。这样就有下面的文法 based-num-num basechar basechar→old mum→num digit digit digt→0111213141516171819
例6.3 考虑下列类似C语法中变量声明的简单文法： decl → type var-l i s t type → i n t | f l o a t v a r-list → i d, v a r-list | i d 我们要为在声明中标识符给出的变量定义一个数据类型属性，并写出一个等式来表示数据 类型属性是如何与声明的类型相关的。通过构造 d t y p e属性的一个属性文法可以实现这一点 (使 用名字d t y p e和非终结符t y p e的属性进行区分)。d t y p e的属性文法在表6 - 3中给出。在图中关于属 性等式我们做了以下标记。 首先，从{integer , re a l}集合中得出d t y p e的值，相应的记号为i n t和f l o a t。非终结符t y p e 有一个它表示的记号给定的 d t y p e。通过d e c l文法规则的等式，这个 d t y p e对应于全体v a r- l i s t的 d t y p e。通过v a r- l i s t的等式，表中的每个 i d都有相同的d t y p e。注意，没有等式包含非终结符 decl 的d t y p e。实际上d e c l并不需要d t y p e，一个属性的值没有必要为所有的文法符号指定。 同前面一样，可以在一个语法树上显示属性等式。图 6 - 3给出了一个例子。 表6-3 例6 . 3的属性文法 文 法 规 则 语 义 规 则 decl → type var- l i s t v a r-list.dtype = t y p e . d t y p e type → i n t type.dtype = i n t e g e r type → f l o a t type.dtype = re a l v a r- l i s t 1 → i d ,v a r- l i s t 2 i d.dtype = v a r- l i s t 1 . d t y p e v a r- l i s t 2 .dtype = v a r- l i s t 1 .d t y p e v a r-list → i d i d.dtype = v a r- l i s t . d t y p e 图6-3 字符串float x,y的语法树，显示表6 - 3中属性文法指定的d t y p e属性 到目前为止，所有的例子都只有一个属性，但属性文法可能会包含几个独立的属性。下一 个例子是一个有几个相互联系属性的简单情形。 例6.4 考虑对例6 . 1中数文法进行修改，数可以是八进制或十进制的。假设这通过一个字符的 后缀o (八进制)或d (十进制)来表示。这样就有下面的文法： based-num → num basechar basechar → o | d num → num digit | d i g i t digit → 0|1|2|3|4|5|6|7|8|9 2 0 4 编译原理及实践 下载
China-pub.com 第6章语义分析 205 下载 在这种情况中，nm和digit均需要一个新的属性base用来计算属性val。base和val的属性文法在 表6-4中给出。 表6-4例6.4的属性文法 文法规则 语义规则 based-num Based-num.val =num.val num basechar num.base basechar base basechar-o basechar base =8 basechar-d basechar.base =10 um,一um,dign ifdigit.valerrormal-ero then erro else num,valmum,base+digit.val nunt,.base num,base digit base =num.base num一dign nunyal digitval digit.base num.base digit.val-0 dig7 digit.val=7 dign→g digit.val= if digit.base=8 then error else8 dign→9 digit.val= if digit.base-8 then error else 9 在这个属性文法中必须注意两个新的特性。首先，这个BNF文法在后缀为。时自己不能排 除错误的（非八进制）数字8和9的组合。例如，按照上面的BNF文法，字符串1890在语法上是 (val29 a=288+5=29 (s) (base 8) (val 图64例6.4中属性计算的语法树
在这种情况中，n u m和d i g i t均需要一个新的属性b a s e用来计算属性v a l。b a s e和v a l的属性文法在 表6 - 4中给出。 表6-4 例6 . 4的属性文法 文 法 规 则 语 义 规 则 based-num → Based-num.val = n u m . v a l num basechar n u m.b a s e = b a s e c h a r.b a s e b a s e c h a r → o b a s e c h a r.b a s e = 8 b a s e c h a r → d b a s e c h a r.b a s e = 10 n u m1 →n u m2 d i g i t 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 t h e n 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 n u m . v a l = d i g i t.v a l d i g i t.b a s e = n u m.b a s e d i g i t →0 d i g i t.v a l = 0 d i g i t →1 d i g i t.v a l = 1 . . . . . . d i g i t →7 d i g i t.v a l = 7 d i g i t →8 d i g i t.v a l = i f d i g i t.b a s e = 8 t h e n e rro r e l s e 8 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 t h e n e rro r e l s e 9 在这个属性文法中必须注意两个新的特性。首先，这个 B N F文法在后缀为o时自己不能排 除错误的(非八进制)数字8和9的组合。例如，按照上面的 B N F文法，字符串1 8 9 o在语法上是 第 6章 语 义 分 析 2 0 5 下载 图6-4 例6 . 4中属性计算的语法树
206 编译原理及实践 China-pub.Co 下载 正确的，但不能赋予任何值。因此，对于这些情况需要一个新的r值。另外，这个属性文法 必须能表示这样的事实，一个带有后缀o的数中包括数字8或9时将导致值为ror。最简单的方 法是在合适的属性等式函数中使用if.then-else表达式。例如，等式 num .val if digit.val=error or num,val=error then error else num,val*num,base +digit.val 对应于文法规则nm,一nm,digit,表示如果um,.val或digit.val为eor,那么num,-ral也必须为 error,除此之外只有一种情况：m,ra的值由公式um,ral*um,base+digit.val给出。 总结这个例子，再在一个语法树上表示属性计算。图6-4给出了数3450的语法树，同时根 据表64的属性文法计算出属性值。 6.1.2属性文法的简化和扩充 if-then-else表达式的使用扩充了表达式的种类，它们可以通过有用的途径出现在属性等式 中，在属性等式中，允许出现的表达式的集合称作属性文法的元语言(metalanguage)。通常我 们希塑元语言的内酒尽可能清晰，不致于引起其自身语义的混淆。我们还希望元语言接近于 种实际使用的编程语言，因为就像我们即将看到的一样，在语义分析程序中需要把属性等式转 换成执行代码。在本书中，我们使用的元语言局限于算术式、逻辑式以及一些其他种类的表达 式，再加上if-then-else表达式，偶尔还有case或switch表达式。 定义属性等式的另一个有用的特征是在元语言中加入了函数的使用，函数的定义可以在别 处给出。例如，在数的文法中，我们对g的每个选择都写出了属性等式。可以采用一个更简 洁的惯例来代替，为dig1写一个文法规则digi→D(这里D是数字中的一个)，相应的属性等式是 digit.al=nval(D） 这里umyal是函数，必须在别处说明其作为属性文法的补充的定义。例如，我们可以用C代码 给出nmva的定义： int numval char D) return (int)D-(int)'0':】 在说明属性文法时更简化的有用方法是使用原始文法二义性的但简单的形式。事实上，因 为假定已经构造了分析程序，所有二义性在那个阶段都己经处理过了，属性文法可以自由地基 于二义性概念，而无须在结果属性中说明任何二义性，例如，例62的算术表达式文法有以下 简单的但二义性的形式： exp-exp+expl exp-exp l exp exp exp number 使用这个文法，属性a可以通过表6-5中的表定义（与表6-2相比较）。 表6-5使用二义性文法定义表达式的va属性 文法规则 语义规则 p,→p,+p exp val exp,val exp.val cxp,→ep-ep, exp,val-exp,val-exp,vat ep,一ep*cp, expval -exp,val*exp val exp.(ep) exp,val=exp,val cp number exp.val-number.val
正确的，但不能赋予任何值。因此，对于这些情况需要一个新的 e rro r值。另外，这个属性文法 必须能表示这样的事实，一个带有后缀 o的数中包括数字8或9时将导致值为e rro r。最简单的方 法是在合适的属性等式函数中使用i f - t h e n - e l s e表达式。例如，等式 n u m1 .val = 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 m1 →n u m2 d i g i t，表示如果n u m2 .v a l或d i g i t . v a l为e rro r，那么n u m1 .v a l也必须为 e rro r，除此之外只有一种情况：n u m1 .v a l的值由公式n u m2 .val * n u m1 .base + d i g i t . v a l给出。 总结这个例子，再在一个语法树上表示属性计算。图 6 - 4给出了数3 4 5 o的语法树，同时根 据表6 - 4的属性文法计算出属性值。 6.1.2 属性文法的简化和扩充 i f - t h e n - e l s e表达式的使用扩充了表达式的种类，它们可以通过有用的途径出现在属性等式 中，在属性等式中，允许出现的表达式的集合称作属性文法的元语言 ( m e t a l a n g u a g e )。通常我 们希望元语言的内涵尽可能清晰，不致于引起其自身语义的混淆。我们还希望元语言接近于一 种实际使用的编程语言，因为就像我们即将看到的一样，在语义分析程序中需要把属性等式转 换成执行代码。在本书中，我们使用的元语言局限于算术式、逻辑式以及一些其他种类的表达 式，再加上i f - t h e n - e l s e表达式，偶尔还有c a s e或s w i t c h表达式。 定义属性等式的另一个有用的特征是在元语言中加入了函数的使用，函数的定义可以在别 处给出。例如，在数的文法中，我们对digit 的每个选择都写出了属性等式。可以采用一个更简 洁的惯例来代替，为digit 写一个文法规则d i g i t →D (这里D是数字中的一个)，相应的属性等式是 d i g i t . v a l = numval (D) 这里n u m v a l是函数，必须在别处说明其作为属性文法的补充的定义。例如，我们可以用 C代码 给出n u m v a l的定义： int numval ( char D) { return (int)D-(int)'0';} 在说明属性文法时更简化的有用方法是使用原始文法二义性的但简单的形式。事实上，因 为假定已经构造了分析程序，所有二义性在那个阶段都已经处理过了，属性文法可以自由地基 于二义性概念，而无须在结果属性中说明任何二义性，例如，例 6 . 2的算术表达式文法有以下 简单的但二义性的形式： exp → exp + exp | exp - exp | exp * exp | ( exp ) | n u m b e r 使用这个文法，属性v a l可以通过表6 - 5中的表定义(与表6 - 2相比较)。 表6-5 使用二义性文法定义表达式的 v a l属性 文 法 规 则 语 义 规 则 e x p1 → e x p2 + e x p3 e x p1 .v a l = e x p2 .v a l + e x p3 .v a l e x p1 → e x p2 - e x p3 e x p1 .v a l = e x p2 .v a l - e x p3 .v a l e x p1 → e x p2 * e x p3 e x p1 .v a l = e x p2 .v a l * e x p3 .v a l e x p1 → ( e x p2 ) e x p1 .v a l = e x p2 .v a l exp → n u m b e r e x p.v a l = n u m b e r.val 2 0 6 编译原理及实践 下载
China-pub.com 第6章语义分析 207 下载 在显示属性值时，也可以通过使用抽象语法树代替分析树进行简化。抽象语法树通常必须 用足够的结构来表达属性文法定义的语义。例如表达式(34-3)*42，其分析树和属性在图 6-2中已给出，通过图6-5的抽象语法树也能完全表达它的语义。 如下一个例子所示，语法树自身也可以用属性文法指定，这并不奇怪。 (6al=31*42=1302 (al=343=3) 0a兰3yoa3 图6-534-3)*42的抽象语法树，显示表6-2或表6-5中属性文法的val属性计算 例6.5给定例6.2的简单整数表达式文法，通过表6-6给出的属性文法可以定义表达式的抽象语 法树。在这个属性文法中，我们使用了两个辅助函数mkOpNode和mkNumNode。mkOpNode函 数有3个参数（一个操作符记号和两个语法树）并构成一个新的树节点，其操作符记号是第1个参 数，子节点是第2个和第3个参数。mkNumNode函数有一个参数（数字值）并构成一个叶子节点， 它表示具有这个值的一个数。在表6-6中我们把数字值写作number.lexval,表示它是由扫描器 构成的。事实上，根据不同的实现，这可以是实际的数字值，或用它的字符串表示（比较表66 中的等式和附录B中TINY语法树递归下降构造)。 表66简单整型算术表达式的抽象语法树的属性文法 文法规则 语义规则 ep,一ep,+tem exp,tree- mkOpNode (+exptree,term.tree) ep,一ep,-term exp tree mkOpNode (-exp,tree,term.tree) exp→erm exp.tree term.tree 1erm→erm,*factor mkOpNode (term,treefactor ee erm一factor factor.tree exp.tree jactor.tree= mkNumNode (number.lexval) 如何确保一个特定的属性文法是一致的和完整的，是使用属性文法的属性说明的一个主要 问题，也就是说，它能唯一定义给定的属性。简单的答案是到目前为止还不能做到。这个问题 与确定一个文法是否是二义的类似。实际上，这是用来确定一个文法充分性的分析算法，类似 的情形发生在属性文法的情况中。因此，下一节将研究属性计算的算法规则方法，确定一个属 性文法是否足够能定义属性值。 6.2属性计算算法 这一节将以属性文法为基础，研究编译程序中如何计算和使用由属性文法的等式定义的属
在显示属性值时，也可以通过使用抽象语法树代替分析树进行简化。抽象语法树通常必须 用足够的结构来表达属性文法定义的语义。例如表达式 ( 3 4 - 3 ) * 4 2，其分析树和v a l属性在图 6 - 2中已给出，通过图6 - 5的抽象语法树也能完全表达它的语义。 如下一个例子所示，语法树自身也可以用属性文法指定，这并不奇怪。 图6-5 ( 3 4 - 3 ) * 4 2 的抽象语法树，显示表6 - 2或表6 - 5中属性文法的v a l属性计算 例6.5 给定例6 . 2的简单整数表达式文法，通过表6 - 6给出的属性文法可以定义表达式的抽象语 法树。在这个属性文法中，我们使用了两个辅助函数 m k O p N o d e和m k N u m N o d e。m k O p N o d e函 数有3个参数(一个操作符记号和两个语法树 )并构成一个新的树节点，其操作符记号是第 1个参 数，子节点是第2个和第3个参数。m k N u m N o d e函数有一个参数(数字值)并构成一个叶子节点， 它表示具有这个值的一个数。在表 6 - 6中我们把数字值写作n u m b e r.l e x v a l，表示它是由扫描器 构成的。事实上，根据不同的实现，这可以是实际的数字值，或用它的字符串表示 (比较表6 - 6 中的等式和附录B中T I N Y语法树递归下降构造)。 表6-6 简单整型算术表达式的抽象语法树的属性文法 文 法 规 则 语 义 规 则 e x p1 → e x p2 + t e r m e x p1 .t re e = m k O p N o d e (+, e x p2 .t re e, t e r m. t re e) e x p1 → e x p2 - t e r m e x p1 .t re e = m k O p N o d e (-, e x p2 .t re e,t e r m. t re e) exp → t e r m e x p.t ree = t e r m.t re e t e r m1 → t e r m2 * f a c t o r t e r m1 .t ree = m k O p N o d e (*, t e r m2 .t re e,f a c t o r .t re e) t e r m → f a c t o r t e r m.t ree = f a c t o r. t re e f a c t o r → ( exp ) f a c t o r.t re e = e x P. t re e f a c t o r → n u m b e r f a c t o r.t ree = m k N u m N o d e (n u m b e r.l e x v a l) 如何确保一个特定的属性文法是一致的和完整的，是使用属性文法的属性说明的一个主要 问题，也就是说，它能唯一定义给定的属性。简单的答案是到目前为止还不能做到。这个问题 与确定一个文法是否是二义的类似。实际上，这是用来确定一个文法充分性的分析算法，类似 的情形发生在属性文法的情况中。因此，下一节将研究属性计算的算法规则方法，确定一个属 性文法是否足够能定义属性值。 6.2 属性计算算法 这一节将以属性文法为基础，研究编译程序中如何计算和使用由属性文法的等式定义的属 第 6章 语 义 分 析 2 0 7 下载