第5章 语法制导的翻译
语法制导定义
语法制导定义 SDD 是一个上下文无关文法和属性及规则的结合。属性与文法相关联，而规则和产生式相关联。
这里定义非终结符号的两种属性：
综合属性：与自身节点上的产生式所关联的语义规则来定义。节点 N 上的综合属性只能通过 N 的子节点或 N 本身的属性值来定义。
继承属性：与父节点上产生式所关联的语义规则来定义。节点 N 上的综合属性只能通过 N 的父节点、N 本身和 N 的兄弟节点上的属性来定义。
终结符号可以具有综合属性，但不能有继承属性。终结符号的属性值是由词法分析器提供的词法值。
一个只包含综合属性的 SDD 被称为 S 属性的 SDD。它可以和一个 LR 语法分析器一起自然地实现。
SDD 的求值顺序
使用依赖图来确定给定的语法分析树中各个属性实例的求值顺序。
具体而言，从一个属性实例到另一个属性实例的边表示计算后一个时需要使用到前一个的值；这些边也即代表着语义规则蕴含的约束。
对依赖图求其拓扑排序，即可得到计算节点属性的顺序。如果依赖图中存在环，那么就没有办法在这棵语法分析树上进行 SDD 求值。
对于给定的一个 SDD，想要判断是否存在某棵语法分析树使得其依赖图是存在环的是困难的。在实践上，下面介绍的两种特定类型的 SDD 满足一定不会产生带有环的依赖图。且这两类 SDD 还可以与自顶向下和自底向上的语法分析过程一起高效地实现。
第一类是：如果一个 SDD 的每个属性都是综合属性，它就是 S 属性的。此时对语法分析树进行后序遍历即可得到其属性求值顺序。
这一过程可以方便地在自底向上语法分析的过程中实现，因为一个自底向上的语法分析过程对应于一次后序遍历。
第二类是：L 属性定义。在一个产生式体所关联的各个属性之间，依赖图总是从左到右（而不能从右到左）。
这一类适合自顶向下分析。
实践过程中的翻译动作可能会带有一定的副作用。对于 SDD，我们在属性文法与翻译方案之间找到了一个平衡点。属性文法没有副作用，并支持任何与依赖图一致的求值顺序。翻译方案要求按从左到右的顺序求值，并允许语义动作包含任何程序片段。
语法制导的翻译方案
我们主要关注如何使用语法制导的翻译方案 SDT 来实现两类 SDD：
一类是基本文法可以用 LR 技术分析，且 SDD 是 S 属性的；
一类是基本文法可以用 LL 技术分析，且 SDD 是 L 属性的。
通用 SDT 的实现方法：
- 忽略语义动作，对输入进行语法分析，并产生一棵语法分析树
- 检查每个内部节点 N ，假设它的产生式是 ，将 a 中的各个动作当作 N 的附加子节点加入，使得 N 的子节点从左到右和 a 中的符号和动作完全一致。
- 对这棵语法分析树进行前序遍历。对于访问到的动作节点立即执行这个动作。
对于上述的第一类 SDT，实现上是比较简单的，因为我们总可以构造出使得每个动作都放在产生式的最后，并且都在将产生式体归约为产生式头的时候执行这个动作。
第二类 SDT 的转换规则如下：
- 把计算某个非终结符号 A 的继承属性的动作插入到产生式体中，紧靠在 A 的本次出现之前的位置。如果 A 的多个继承属性以无环的方式相互依赖，那么还需要考虑内部顺序（若有环则无解）。
- 将计算一个产生式头的综合属性的动作放在这个产生式体的最右端。
实现 L 属性的 SDD
上文已经讨论过构造语法分析树、插入动作、然后按照前序执行的翻译方法，下面记录几种其他的方法。
使用一个递归下降的语法分析器，为每一个非终结符号都建立一个函数。对于非终结符号 A 的函数，以参数的方式接受 A 的继承属性，并返回 A 的综合属性。
使用一个递归下降的语法分析器，以边扫描边生成的方式生成代码。
与 LL 语法分析器结合，实现一个 SDT。属性的值存放在语法分析栈中，而各个规则则从栈中已知位置获取需要的属性值。
与 LR 语法分析器结合，实现一个 SDT。如果基础语法是 LL 的，我们总可以按照自底向上的方式来处理语法分析和翻译过程。