研究生院第五章_1_.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * S属性定义的自下而上翻译（12） S属性的自下而上计算 综合属性可以通过自下而上的分析器在分析时完成计算 Yacc是常用的自下而上的分析器的生成器，因此可以利用Yacc实现综合属性的自下而上的计算 修改分析栈：将文法符号的综合属性值放在它的栈里 归约时，根据栈中的产生式右部文法符号的属性值计算新的文法符号的综合属性值 这种实现也支持一些继承属性的计算 实现的例子： 分析栈中用文法符号代替状态和文法符号对（state），增加一个内容，记录文法符号对应的属性值（val），这两部分内容都可以用数组来表示，注意：state[ I ]和val[ I ]存在对应关系 如果文法符号没有属性，则val数组对应的条目没有意义 栈顶用指针top指示 S属性定义的自下而上翻译（13） 如果综合属性刚好在归约前计算，对于产生式A→XYZ的语义规则是A.a := f( X.x , Y.y , Z.z )，栈中形式如下 在进行归约前，属性Z.z的值在val[top]中，属性Y.y的值在val[top-1]中，属性X.x的值在val[top-2]中 归约后，top减2，覆盖A的状态放在state[top]中，综合属性的值A.a放进val[top]中 S属性定义的自下而上翻译（14） 例：再次考虑计算器的语法制导定义： 属性digit.lexval的值由词法分析器提供 产生式 代码段 L→E n print(val[top – 1]) E→E1+T val[ntop] := val[top-2] + val[top] E→T T→T1*F val[ntop] := val[top-2] * val[top] T→F F→(E) val[ntop] := val[top-1] F→digit S属性定义的自下而上翻译（15） 上表中的代码段用属性在val数组中的位置代替原来的语义规则 每次归约一定是选择唯一的产生式吗？ 考虑LR分析的定义，这个结论是明显的，因此可以把属性计算和归约联系起来 每次归约后，val栈顶存放的是归约所用产生式的左边符号的属性值 如果用于归约的产生式的右部有r个文法符号，则ntop的值置为top – r + 1，代码段执行后，top置为ntop 代码段与归约挂钩，用户可以根据需要决定与产生式对应的动作 S属性定义的自下而上翻译（16） 输 入 state val 所用产生式 3*5+4 n - - *5+4 n 3 3 *5+4 n F 3 F→digit *5+4 n T 3 T→F 5+4 n T* 3 - +4 n T*5 3 - 5 +4 n T*F 3 – 5 F→digit +4 n T 15 T→T*F +4 n E 15 E→T 4 n E+ 15 - n E+4 15 - 4 n E+F 15 – 4 F→digit n E+T 15 – 4 T→F n E 19 E→E+T E n 19 – L 19 L→E n L属性定义（1） 分析树结点的建立次序 vs. 属性的计算次序 翻译方法的自然次序一般依照深度优先的次序 procedure dfvisit( n : node ) begin for n 的每个子结点m，从左到右 do begin 计算m的继承属性 dfvisit( m ) end 计算n的综合属性 end 什么是L属性定义？ 它的属性总可以按深度优先次序计算，其中L代表左（Left），表示属性信息是从左到右流 L属性定义（2） L属性定义的形式定义 语法制导定义是L属性的，如果每个产生式A→X1X2…Xn的每条语义规则计算的属性都是综合属性或是Xj的继承属性，1≤j≤n，它仅依赖于以下两点： 该产生式中Xj左边的符号X1 ， X2 ， …Xj-1的属性； A的继承属性 L属性定义包含了所有基于LL（1）文法的语法制导定义 S属性定义是L属性定义的子集：因为限制1和2仅对继承属性作限制 L属性定义（3） 例：非L属性的语法制导定义 产生式 语义规则 A→LM L.i := l( A.i ) M.i := m( L.s ) A.s := f( M.s )