语法制导定义(SDD)

语法制导定义(Syntax-Directed Defination, SDD)是一个上下文无关文法和属性及规则的结合。属性和文法符号关联，而规则和产生式关联。

属性(attribute)

如果X是一个符号而a是X的一个属性，那么可以用X.a表示a在某个标号为X的节点上的值。

属性可以有多种类型，比如数字、类型、表格引用、串。这些船甚至可能是很长的代码序列。

• 继承属性和综合属性

综合属性(synthesized attribute)：综合属性是由节点的子节点或者自身的属性值来定义的。
继承属性(inherited attribute)：继承属性是通过父节点、自身节点、和兄弟节点上的属性值来定义的。

终结符号可以有综合属性，但是不能有继承属性。
终结符号的属性值是由词法分析器提供的词法值，SDD中没有计算终结符号属性值的语义规则。

一个只包含综合属性的SDD称为S-属性的SDD。一个S属性的SDD可以和一个LR语法分析器一起自然地实现。

在语法分析树的节点上对SDD求值

一个显示了它的各个属性的语法分析树称为注释语法分析树(annotated syntax tree)。

对于综合属性，我们可以按照任何自底向上的顺序计算它们的值，比如对语法分析树进行后序遍历的顺序。

属性值之间可能存在循环依赖关系。

SDD的求值顺序

依赖图

依赖图(dependency graph)是一个有用的工具，它可以确定一棵给定的语法分析树中各个属性实例的求值顺序。

依赖图描述了某个语法分析树中的属性实例之间的信息流。

属性求值顺序

• 拓扑排序(topological sort)

GPT：拓扑排序是指把一个有向无环图的节点排成一个直线，让所有边都从左往右指，也就是确保所有箭头都指向同一边。拓扑排序的排列方式保证了图中每个节点都在它的依赖节点之后。

如果图中存在任意一个环，那么就不存在拓扑排序，也就是说无法在这棵树上对相应的SDD求值。

S属性的定义

如果一个SDD的每个属性都是综合属性，那它就是S属性的。（即S-SDD）

如果一个SDD是S属性的，我们可以按照语法分析树节点的任何自底向上顺序来计算各个属性值。对语法分析树进行后序遍历并对属性求值会非常简单。

L属性的定义

L属性定义(L-attributed definition)是另一种SDD。这类SDD的思想是在一个产生式体所关联的各个属性之间，依赖图的边总是从左到右，而不能从右到左。（因此称为L属性，意为Left）

更加准确的定义-每个属性必须是：
一、要么是一个综合属性。
二、 要么是一个继承属性，但是有限制，假如产生式$A->X_1X_2…X_n$，继承属性$Xi.a$只能使用：
1) 产生式头A关联的继承属性。
2) 位于Xi左边的文法符号实例$X_1X_2..X_{i-1}$相关的继承属性或者综合属性。
3) 和这个$X_i$的实例本身相关的继承属性或综合属性，但是在这个$X_i$的全部属性组成的依赖图中不包含环。

有副作用的语义规则

在实践中，翻译过程会出现一些副作用。比如一个计算器可能打印出一个结果，比如一个代码生成器可能吧一个标识符的类型加入到符号表中。

对于SDD，我们在属性文法和翻译方案直接按找到了一个平衡点。
属性文法没有副作用，并支持任何与依赖图一致的求值顺序。
翻译方案要求按从左到右顺序求值，并允许语义动作包含任何程序片段。

副作用必须是受控的。确保不会影响产生“正确的”翻译结果。

语法制导翻译的应用

语法翻译的技术可用于后面章节的类型检查和中间代码生成。

• 抽象语法树的构造

为简单表达式构造语法树：
|产生式|语义规则| |-|-| |$E -> E_1 + T$|E.node = new Node('+', E1.node, T.node)| |$E -> E_1 - T$|E.node = new Node('-', E1.node, T.node)| |$E -> T$|E.node = T.node| |$T -> ( E )$|T.node = E.node| |$T -> id$|T.node = new Leaf(id, id.entry)| |$T -> num$|T.node = new Leaf(num, num.val)|

（如果是非左递归的为自顶向下语法分析而设计的文法，那么得到的抽象语法树是一样的，详见《编译原理p205》）

• 其他

（比如处理一些类型的结构，详见编译原理p206）

（END）