编译原理6-5-自下而新上计算继承属性.pptVIP

第六章 属性文法和语法制导翻译;6.5 自下而上计算继承属性;从翻译模式中去掉嵌入在产生式中间的动作 ;例如，下面翻译模式 ;两个翻译模式中的文法接受相同的语言。通过画出带有表示动作的附加结点的分析树，可以看到动作的执行程序也是一样的。 在经过转换的翻译模式中，动作都在产生式右端的末尾，因此，可以在自下而上分析过程中产生式右部被归约时执行相应的动作。 ;分析栈中的继承属性 ;由于X.s的值在Y以下的子树中的任何归约之前已经放在栈中，这个值可以被Y继承。 也就是说，如果继承属性Y. i是由复写规则Y. i := X.s定义的，则可以在需要Y.i值的地方使用X.s的值。 我们将会看到，在自下而上分析中计算属性值时复写规则起非常重要的作用 ;下面例子说明复写规则的使用 ;按照这个翻译模式．标识符的类型可以通过继承属性的复写规则来传递。例如，对于输入串 int p, q, r 其属性的传递方向如图 ;输 入 串;从表6.9可以看出，当L的右部被归约时，T恰好在这个右部的下面。 假设分析栈是由一对数组state和val来实现的。 如果state[i]代表符号X，则val [i]存放X的综合属性X. s，则表6.9中给出了state数组的内容。 由于在表6.9中，每次L的右部被归约时，T恰好在这个右部的下面，因此这时可以方便地访问到T.type的值。 ;由于T. type在栈中相对于栈顶的位置是已知的，我们可以翻译模式中语义动作的实现如下表所示。;模拟继承属性的计算;为了解决这个问题，我们在上述翻译模式中的第二个产生式右部的C的前面插入一个新的标记非终结符M。;S;模拟不是复写规则的语义规则 继承属性是某个综合属性的一个函数 S ? aAC C.i := f (A.s) 增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行。 S ? aANC N.i := A.s; C.i := N.s N ? ? N.s := f (N.i) ;例6.13 数学排版语言EQN S ? {B.ps := 10 } B {S.ht := B.ht } ?B ? {B1.ps := B.ps } B1 {B2.ps := B.ps } B2 {B.ht := max(B1.ht, B2.ht ) } ?B ? { B1.ps :=B.ps } B1 sub { B2.ps := shrink(B.ps) } B2 {B.ht := disp (B1.ht, B2.ht ) } ?B ? text {B.ht := text.h ? B.ps };文字排版中引入标记符号;产 生 式 ;按照前面例子的做法，在必要的时候引进标记非终结符，可以实现在LR分析过程中对L-属性文法进行计算。 对于一个给定的LL(1)文法引入标记非终结符后，因为每个标记非终结符只有一个产生式，所以文法仍然保持是LL(1）文法。任何LL(1)文法也是LR（1)文法，因此，当标记非终结符加入到LL(1)文法时不会产生分析冲突。但对LR(1)文法引入标记非终结符之后，不能保证还是LR(1)的，因此可能引起分析冲突。;下面，我们给出一种带继承属性的自下而上的分析和翻译方法。对于一个基础文法是LL(1)文法的L-属性文法定义，通过下面方法可以得到一个计算分析栈中所有属性值的分析程序。 为了简单起见，假设 每一个非终结符A都有一个继承属性A.i 每个文法符号X都有一个综合属性X.s 如果X是一个终结符号，那么它的综合属性就是通过词法分析器返回的词法值，这个值将放在val栈中的适应位置。;对于每个产生式A→X1X2…Xn，引入n个新的标记非终结符M1，…Mn，用产生式A→M1X1…MnXn代替上面的产生式。 综合属性Xj.s将放在分析栈中与Xj相应的数组val的表项中。 如果有继承属性Xj.i,把它也放在数组val中，但放在与Mj相应的项中。 一个重要事实是，当我们进行分析时，如果继承属性A.i存在的话，它将在数组val中紧挨M1位置下面的位置中存放。 ;由于标记非终结符可能引起分析冲突，进行下面的简化是有益的。 (1) 如果Xj没有继承属性，则无需使用标记符Mj。当然，如果Mj被省略，栈中属性的位置会引起变化，但是这种变化可以通过对分析器稍加修改而适应。 (2) 如果X1.i存在，但是由复写规则X1.i:＝A.i计算，则可省略M1。因为我们知道A.i已经存放在栈中预定的位置，紧挨X1下面，因此这个值也可以作为X1.i使用。;用综合属性代替继承属性 ;因为标识符由L产生而类型不在L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。 事实上，如果非终结符L从第一个产生式中它的右