编译器笔记21-语法制导翻译-SDD的求值顺序

SDD的求值顺序

SDD 为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值。

问: 按照什么顺序计算属性值？
答: 语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值。

依赖图 (Dependency Graph)

• 依赖图是一个描述了分析树中结点属性间依赖关系的有向图
• 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
• 如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边。

依赖图.png

第四条产生式的第二条语义规则是产生一个副作用，也就是说在符号表中将id.lexeme所代表的标识符的类型设置为L.in所代表的类型。我们可以把它看成是产生式左部的L的一个虚综合属性规则。因此我们在依赖图中为L设置一个虚节点。L的虚综合属性它用到了其子节点的lexeme属性和其自身的in属性。因此在依赖图中分别从L的in属性节点和id的lexeme属性节点引出指向L虚属性节点的有向边。

属性值的计算顺序

可行的求值顺序是满足下列条件的结点序列N1, N2, … ,Nk：如果依赖图中有一条从结点Ni到Nj的边(Ni →Nj), 那么i < j（即：在节点序列中，Ni排在Nj前面）。这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序 (topological sort)。

顺序.png

说明：对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值。对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值。

循环依赖.png

从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系。

幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图。

不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现。

• S- 属性定义 (S-Attributed Definitions, S-SDD)
• L- 属性定义 (L-Attributed Definitions, L-SDD)