语法树上的SDD求值

在分析树上求值有助于属性计算的可视化，便于理解。所以就有注释语法分析树（annotated parse tree），包含了各个节点的各属性值的语法分析树。

步骤：

• 对于任意的输入串，首先构造出相应的分析树

• 给各个节点（根据其文法符号）加上相应的属性

• 按照语义规则计算这些属性的值

计算顺序：

$$定义：如果某个结点 N 的属性 a 为 f\left(N_{1} . b_{1}, N_{2} . b_{2}, \ldots, N_{k}. b_{k}\right) ，\\那么我们需要先算出 N_{1} . b_{1}, N_{2} . b_{2}, \ldots ， N_{k} . b_{k} 的值$$

如果可以给各个属性值排出一个计算顺序，那么这个注释分析树就可以计算得到。S属性的SDD一定可以按照自底向上的顺序求值。

$$A \rightarrow B \quad A \cdot s=B . i \quad B . i=A \cdot s+1$$

上面的SDD不能计算。

注释分析树的例子