文法符号及其语义属性教学幻灯片讲义.pptVIP

句子real id1，id2，id3的带注释的语法树的依赖图 id1 L , id2 L , id3 L real T D 4 type 5 in 6 - addtype(id.entry, L.in) 7 in 8 addtype 9 in 10 addtype 1 entry 2 entry 3 entry 产 生 式 语 义 规 则 D→TL L.in := T.type T→int T.type := integer T→real T.type := real L→L1, id L1.in :=L.in addtype(id.entry, L.in) L→id addtype(id.entry, L.in) 例6.7: 例6.4中语法分析树的依赖图 * ４. 属性的计算次序： 6.2 基于属性文法的处理方法 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。 注:在拓扑排序中,在一个结点上，语义规则 b:=f(c1,c2,…,ck)中的属性c1,c2,…,ck 在计算b以前是可用的。 良定义的：若一个属性文法不存在属性之间的循 环依赖关系，则称该文法为良定义的。 属性的计算次序 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 属性文法说明的翻译是很精确的 基础文法用于建立输入符号串的语法分析树 根据语义规则建立依赖图 从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序 输入串 语法树 依赖图 语义规则计算次序 句子real id1，id2，id3的带注释的语法树的依赖图 id1 L , id2 L , id3 L real T D 4 type 5 in 6 7 in 8 9 in 10 1 entry 2 entry 3 entry a4:=real; a5:=a4 addtype (id3.entry,a5); a7:=a5; addtype (id2.entry,a7); a9:=a7 addtype (id1.entry,a9); 6.2 基于属性文法的处理方法 依赖图 树遍历 一遍扫描 * 二、树遍历的属性计算方法 1.方法 A.前提：假设语法树已经建立起来了，且树中已 有如下信息：开始符号—继承属性 终结符——综合属性 B.遍历：以某种次序遍历语法树，直至计算出所 有属性. 遍历方法：深度优先，从左到右 6.2 基于属性文法的处理方法 * 2.算法 While 还有未被计算的属性 do VisitNode (S) /*S是开始符号*/ procedure VisitNode (N:Node); begin If N是一个非终结符 then /*假设它的产生式为N?X1…Xm*/ for i:=1 to m do if not Xi∈VT then /*即Xi是非终结符*/ begin 计算Xi的所有能够计算的继承属性; VisitNode (Xi) end; 计算N的所有能够计算的综合属性 end * 6.2 基于属性文法的处理方法 注：只要文法的属性是非循环定义的，则每次扫 描至少有一个属性值被计算出来。 * 其中，S有继承属性a，综合属性b；X有继承属性c，综合属性d；Y有继承属性e，综合属性f；Z有继承属性h，综合属性g。 3.举例 例6.9: 考虑下表所给的属性文法G。 产生式 语义规则 S?XYZ X?x Y?y Z?z Z.h:=S.a X.c:=Z.g S.b:=X.d-2 Y.e:=S.b X.d:=2*X.c Y.f:=Y.e*3 Z.g:=Z.h+1 6.2 基于属性文法的处理方法 * S:a=0 X Y Z x y (a) z 6.2 基于属性文法的处理方法 S:a=0 X Y Z：h=0 g=1 x y z (b) * 6.2 基于属性文法的处理方法 S:a=0,b=0 X:c=1 d=2 Y Z：h=0 g=1 x y z (c) S:a=0,b=0 X:c=1 d=2 Y:e=0 f=0 Z：h=0 g=1 x y z (d) 假设S.a的初始值为0，输入串为xyz S:a=0 X Y Z x y z Z:h=0 g=1 X:c=1 d=2 S:a=0, b=0 Y:e=0 f=0 产 生 式 语 义 规 则