3*5的注释分析树 请观察inh属性是如何传递的。 T.val= 15 T.h=3 F.a=3 T syn= 15 T1.ih=15 digit leval=3 F.a=5 T1.yn= 15 digit leval= 5
3*5的注释分析树 • 请观察inh属性是如何传递的
消直接左递归肘语义规则的处理 ·假设 A→A1YAa=g(A1a,Y!a) A→X Aa=f(X.x) ·那么 A→XR R 1=f(X.x); A.a=Rs R>YRI Ri=g(Rl,Yy) ;R.SRS R→ RS=R. 新文法中R对应的部分和原文法中A对应的部分互补; 对于A→XY1Y2…Yn;如果R对应于YY1…Yn;互补的 A对应于AY1……Y R1等于互补的A的AS
消直接左递归时语义规则的处理 • 假设： – A→A1Y A.a = g(A1 .a, Y.a) – A→X A.a = f(X.x) • 那么 – A → XR R.i = f(X.x); A.a = R.s – R → YR1 R1 .i = g(R.i, Y.y); R.s=R1 .s – R → ε R.s = R.i • 新文法中R对应的部分和原文法中A对应的部分互补； – 对于A→XY1Y2……Yn；如果R对应于YYi……Yn；互补的 A对应于AY1……Yi-1 – R.i等于互补的A的A.s
SDD的求值顺序 在对SDD的求值过程中,如果结点N的属性 a依赖于结点M1的属性a1,M2的属性a2, 那么我们必须先计算出M的属性,才能计 算N的属性a。 使用依赖图来表示计算顺序。 显然,这些值的计算顺序应该形成一个偏 序关系。如果依赖图中出现了环,表示属 性值无法计算
SDD的求值顺序 • 在对SDD的求值过程中，如果结点N的属性 a依赖于结点M1的属性a1，M2的属性a2，…。 那么我们必须先计算出Mi的属性，才能计 算N的属性a。 • 使用依赖图来表示计算顺序。 • 显然，这些值的计算顺序应该形成一个偏 序关系。如果依赖图中出现了环，表示属 性值无法计算
依赖图 ·描述了某棵特定的分析树上各个属性实例之间 的信息流(计箅顺序 从实例a1-到实例a的有向边表示计算a时需要a1的值。 (必须先计算a2,再计算a1) ·对于标号为Ⅹ的分析树结点N,和Ⅹ关联的每个 属性a都对应依赖图的一个结点Na。 ·结点N对应的产生式的语义规则通过Ⅹc计算了 A.b的值,且在分析树中Ⅹ和A分别对应于N和 N,那么从N1C到Nb有一条边。 N1和N可以等于/不等于N
依赖图 • 描述了某棵特定的分析树上各个属性实例之间 的信息流（计算顺序） – 从实例a1到实例a2的有向边表示计算a2时需要a1的值。 （必须先计算a2，再计算a1） • 对于标号为X的分析树结点N，和X关联的每个 属性a都对应依赖图的一个结点N.a。 • 结点N对应的产生式的语义规则通过X.c计算了 A.b的值，且在分析树中X和A分别对应于N1和 N2，那么从N1 .c到N2 .b有一条边。 – N1和N2可以等于/不等于N
依赖图的例子 ·3*2的注释分析树 产生式 语义规则 TFTT. val=T,syn; T, inh=F 1)T→FT T. inh= F.val 边el、e2。 Tval=T syn ·可能的计算顺序: 2)T→*FT1r1mi=rwmh×Funl T syn=Ti.sym 2,3,4,5,6,7,8.9 Tsyn=T inh -1.35,24.6,7.8,9 4)F, digit F.val=digit leval T9 val e2 el F3"0b inh 5 T"8 syn digit 1 larval F 4 val inh 6 T 7 syn digit 2 leval
依赖图的例子 • 3*2的注释分析树； • T→FT’ {T.val = T’.syn; T’.inh = F.val;} – 边e1、e2。 • 可能的计算顺序： – 1,2,3,4,5,6,7,8.9 – 1,3,5,2,4,6,7,8,9