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

第六章 属性文法和语法制导翻译,6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S-属性文法的自下而上计算 6.4 L-树性文法和自顶向下翻译 6.5 自下而上计算继承属性,6.5 自下而上计算继承属性,讨论在自下而上的分析过程中实现L-属性文法的方法。 这种方法可以实现任何基于LL(1)文法的L-属性文法，它还可以实现许多（不是所有）基于LR(1)文法的L-属性文法。,从翻译模式中去掉嵌入在产生式中间的动作,介绍一种转换方法，它可以使所有嵌入的动作都出现在产生式的末尾，这样就可以自下而上处理继承属性。 转换方法是，在基础文法中加入新的产生式，这种产生式的形式为M,其中M为新引入的一个标记非终结符。我们把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾。,例如，下面翻译模式,ET R R+T print（）R | -Tprint（） R | T numprint（num.val）,ETR R+ TMR | TNR | T num print（num.val） M print （） N print（）,使用标记非终结符号M和N转换为,两个翻译模式中的文法接受相同的语言。通过画出带有表示动作的附加结点的分析树，可以看到动作的执行程序也是一样的。 在经过转换的翻译模式中，动作都在产生式右端的末尾，因此，可以在自下而上分析过程中产生式右部被归约时执行相应的动作。,分析栈中的继承属性,自下而上分析器对产生式AXY的右部是通过把X和Y从分析栈中移出并用A代替它们。 假设X有一个综合属性X.s，按照6.3节所介绍的方法我们把它与X一起放在分析栈中。,由于X.s的值在Y以下的子树中的任何归约之前已经放在栈中，这个值可以被Y继承。 也就是说，如果继承属性Y. i是由复写规则Y. i := X.s定义的，则可以在需要Y.i值的地方使用X.s的值。 我们将会看到，在自下而上分析中计算属性值时复写规则起非常重要的作用,下面例子说明复写规则的使用,假设某翻译模式为,D T L.in := T.type L T int T. type := integer T real T. type := real L L1.in := L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),按照这个翻译模式标识符的类型可以通过继承属性的复写规则来传递。例如，对于输入串 int p, q, r 其属性的传递方向如图,图6.21 在每个L结点L.in =T.type,表6.9 int p, q, r的分析过程,从表6.9可以看出，当L的右部被归约时，T恰好在这个右部的下面。 假设分析栈是由一对数组state和val来实现的。 如果statei代表符号X，则val i存放X的综合属性X. s，则表6.9中给出了state数组的内容。 由于在表6.9中，每次L的右部被归约时，T恰好在这个右部的下面，因此这时可以方便地访问到T.type的值。,由于T. type在栈中相对于栈顶的位置是已知的，我们可以翻译模式中语义动作的实现如下表所示。,表6.10 语义动作的实现,模拟继承属性的计算,属性的位置不能预测 产生式 语义规则 S aAC C.i := A.s S bABC C.i := A.s C c C.s := g(C.i),属性C.i通过复写规则继承综合属性A.s的值。注意在栈中A和C之间可能有B也可能没有B，当通过Cc进行归约时，C.i的值可能在valtop-1处也可能在valtop-2处，但我们不能确定究竟在哪个位置。,为了解决这个问题，我们在上述翻译模式中的第二个产生式右部的C的前面插入一个新的标记非终结符M。,产生式 语义规则 S aAC C.i := A.s S bABMC M.i := A.s; C.i := M.s C c C.s := g(C.i) M M.s := M.i,图6.22 通过标记M传递属性值,（a）修改前,（b）修改后,模拟不是复写规则的语义规则 继承属性是某个综合属性的一个函数 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.4),例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 ,文字排版中引入标记符号,为了自底向上计算： B text B.ht := text.h B.ps 必须确定继承属性B.ps的（“属性栈”）位置。为此引 入标记非终结符L、M和N及其属性，包括相应的空产 生式和有关属性规则。这样B.ps即可在紧靠“句柄”text 下方的位置上找到。(L的综合属性置为B.ps的初值) SL B BB1M B2 BB1 sub N B2,表6.11 所有继承属性都由复写规则赋值,L 用于初始化，M的用法同图6.22，N的用法同式(6.4),按照前面例子的做法，在必要的时候引进标记非终结符，可以实现在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栈中的适应位置。,对于每个产生式AX1X2Xn，引入n个新的标记非终结符M1，Mn，用产生式AM1X1MnXn代替上面的产生式。 综合属性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使用。,用综合属性代替继承属性,有时，改变基础文法可能避免继承属性。 例如，一个Pascal的说明由一标识符序列后跟类型组成，如 m, n: integer 相应文法 D L: T T integer | char L L，id | id,因为标识符由L产生而类型不在L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。 事实上，如果非终结符L从第一个产生式中它的右边T中继承了类型，则我们得到的属性文法就不是L-属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。,一个解决的方法是重新构造文法，使类型作为标识符表的最后一个元素。这样，类型可以通过综合属性L.type进行传递，当通过L产生每个标识符时，它的类型就可以填入到符号表中。,相应文法 D id L L ，id L | : T T integer | char,例 题 4,给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。 例如，因为和是左结合，(a (b + c ) (d )可以重写成a (b + c ) d。 先把表达式的括号都去掉，然后在必要的地方再加括号。 去掉表达式中的冗余括号，保留必要的括号。,例 题 4,第一种方法 S E print ( E. code ) E E1 + T if T. op = plus then E.code:=E1.code|“+”|“(”|T.code|“)” else E. code := E1. code | “+” | T. code; E. op := plus E T E. code := T. code; E. op := T. op,例 题 4,T T1 F if (F. op = plus) or (F. op = times) then if T1. op := plus then T. code := “(” | T1. code | “)” | “” | “(” | F. code | “)” else T. code := T1. code | “” | “(” | F. code | “)” else if T1. op := plus then T. code := “(” | T1. code | “)” | “” | F. code else T. code := T1. code | “” | F. code; T. op := times,例 题 4,T F T. code := F. code; T. op := F. op F id F. code := id. lexeme; F. op := id F ( E ) F. code := E. code; F. op := E. op,例 题 4,第二种方法 给E，T和F两个继承属性left_op和right_op 分别表示左右两侧算符的优先级 给它们一个综合属性self_op表示自身主算符的优先级 再给一个综合属性code表示没有冗余括号的代码。 分别用1和2表示加和乘的优先级，用3表示id和(E)的优先级，用0表示左侧或右侧没有运算对象的情况。,例 题 4,S E E. left_op := 0; E. right_op := 0; print ( E. code ) E E1 + T E1. left_op := E. left_op; E1. right_op := 1; T. left_op := 1; T. right_op := E. right_op; E.code:=E1.code| “+” | T. code ; E. self_op := 1; E T T. left_op := E. left_op; T. right_op := E. right_op; E. code := T. code; E. self_op := T. self_op,例 题 4,T T1 F T1. left_op := T. left_op; T1. right_op := 2; F. left_op := 2; F. right_op := T. right_op; T.code:=T1.code| “*” | F. code ; T. self_op := 2; T F F. left_op := T. left_op; F. right_op := T. right_op; T. code := F. code; T. self