语法制导翻译
最通用的语法制导翻译的方法是先通过构造一棵语法分析树，然后通过访问这棵树的各个结点来计算结点的属性值。在很多情况下，翻译可以在语法扫描分析期间完成，不需要构造出明确的语法分析树。语法制导翻译主要有两类：
- L 属性翻译 (从左到右)，可以在语法分析过程中完成的翻译方案
- S 属性翻译 (综合)，可以很容易与自底向上语法分析过程联系起来
语法制导定义
语法制导定义 (Syntax-Directed Definition, SDD) 是一个上下文无关文法
(Context-Free Grammar, CFG) 和属性及规则的结合，属性和文法符号相关联，而规则和产生式相关联。如果 X 是一个符号而 a 是 X 的一个属性，那么我们用 X.a 表示 a 在某个标号为 X 的分析树结点上的值。
继承属性与综合属性
处理非终结符的两种属性：
- 综合属性 (synthesized attribute)
- 在分析树结点 N 上的非终结符 A 的综合属性是由 N 上的产生式所关联的语义规则来定义的。这个产生式的头部一定是 A，结点 N 上的综合属性只能通过 N 的子结点或 N 本身的属性值来定义。
- 继承属性 (inherited attribute)
- 在分析树结点 N 上的非终结符 B 的继承属性是由 N 的父结点上的产生式所关联的语义规则来定义的。这个产生式的体中必然包含符号 B，结点 N 上的继承属性只能通过 N 的父结点、N 本身和 N 的兄弟结点上的属性来定义。
虽然不允许结点 N 的继承属性通过子结点上的属性来定义，但可以通过结点本身的继承属性定义综合属性。另外，终结符可以由综合属性，但不能有继承属性，它的属性值是由词法分析器提供的词法值，SDD 中没有计算终结符的属性值的语义规则。
比如有一个简单的加乘计算器。
| 编号 | 产生式 | 语义规则 |
|---|---|---|
| 1 | \(L\rightarrow{}E\textbf{n}\) | \(L.val = E.val\) |
| 2 | \(E\rightarrow{}E_{1}+T\) | \(E.val = E_{1}.val + T.val\) |
| 3 | \(E\rightarrow{}T\) | \(E.val = T.val\) |
| 4 | \(T\rightarrow{}T_{1}*F\) | \(T.val = T_{1}.val \times F.val\) |
| 5 | \(T\rightarrow{}F\) | \(T.val = F.val\) |
| 6 | \(F\rightarrow(E)\) | \(F.val = E.val\) |
| 7 | \(F\rightarrow{}\textbf{digit}\) | \(F.val = \textbf{digit}.lexval\) |
产生式 1 设置了整个表达式的值，而产生式 2 的值由它的两个子结点的值求和得来，类似的产生式 4 的值由它的两个子结点的值求积得来。而产生式 7 的值由词法单元返回的数值得来。这个只包含综合属性的 SDD 被称作 S 属性 (S-attribute) SDD，它的头部的非终结符的值都由产生式的体的属性值计算得来。
一个没有副作用的 SDD 也被称为属性文法 (attribute grammar)，一个属性文法的规则仅仅通过其他属性值和常量值来定义一个属性值。
在语法分析树的结点上对 SDD 求值
在语法分析器上进行求值有助于将 SDD 翻译方案可视化，虽然实际上不需要构建语法分析树。在应用一个 SDD 规则之前首先构造出一棵语法分析树，并用这些规则对树上的各个结点上的所有属性进行求值。一个显示了各个属性值的语法分析树称作注释语法分析树 (annotated parse tree)。
根据上节的产生式和规则，可以构造出一棵语法分析树，对应的非终结符的每个结点都按照自底向上的顺序计算。
在对某个结点的属性进行求值之前，需要先求出这个属性所依赖的所有属性值。比如上一节提到的计算器示例 S-attribute SSD，在求值结点的 val 属性之前就必须求值那个结点的所有子结点的属性值。对于综合属性，可以按照任何自底向上的书序计算属性值 (如 postorder)。对于由综合属性和继承属性的 SDD，不能保证有一个顺序来对各个结点上的属性进行求值。比如产生式 \(A\rightarrow{}B\)，语义规则为 \(A.s = B.i;\ {}B.i=A.s+1;\)，这个规则是循环的，不可能先求出结点的 A.s 或子结点的 B.i 中的一个值。
从计算的角度上看，给定一个 SDD，很难确定是否存在属性值上的循环依赖关系，但存在 SDD 的一个有用子类，它能保证对每棵语法分析树都存在一个求值顺序。
当一棵语法分析树的结构和源代码的抽象语法不匹配时，继承属性是很有用的。因为文法不是为了翻译而定义的，是为了语法分析而进行定义的，因此可能产生不匹配的情况。
现在再实现一个无左递归的 SDD 文法，用于计算 3*5 这样的项。
| 编号 | 产生式 | 语义规则 |
|---|---|---|
| 1 | \(T\rightarrow{}FT^{’}\) | \(T^{’}.inh = F.val; T.val = T^{’}.syn\) |
| 2 | \(T^{’}\rightarrow{}*FT^{’}_1\) | \(T^{’}_{1}.inh = T^{’}.inh \times{} F.val; T^{’}.syn = T^{’}_{1}.syn\) |
| 3 | \(T^{’}\rightarrow{}\varepsilon\) | \(T^{’}.syn=T^{’}.inh\) |
| 4 | \(F\rightarrow{}\textbf{digit}\) | \(F.val = \textbf{digit}.lexval\) |
自顶向下的过程中，第一个输入 3 将与 \(\times\) 不在同一棵子树下，我们需要使用继承属性将运算分量传递给运算符 *。非终结符 T 和 F 各自有一个综合属性 val，终结符
digit 有一个综合属性 lexval，非终结符 \(T^{’}\) 有一个继承属性 inh 和一个综合属性 syn。
这些语义规则基于如下思想：运算符 * 的做运算分量是通过继承得到的。也就是说，
\(T^{’}\rightarrow{}*FT^{’}\) 的头部继承了产生体中的 * 左运算分量。当递归地处理完毕后，这个结果就通过综合属性传递到树的根部。
SDD 求值顺序
依赖图 (dependency graph) 是一个有用的工具，它可以确定一棵给定的语法分析树中各个属性实例的求值顺序。注释语法分析树显示了各个属性的值，依赖图可以帮我们确定如何计算这些值。
依赖图
依赖图描述了某个语法分析树中的属性实例之间的信息流。从一个属性实例到另一个属性实例的边表示计算第二个属性实例时需要第一个属性实例的值。图中的边表示语义规则所蕴含的约束。详细说明：
- 对于语法分析树的结点，比如一个标号为文法符号 X 的结点，和 X 关联的每个属性都在依赖图中有一个结点。
- 假设和产生式 p 关联的语义规则通过 X.c 的值定义了综合属性 A.b 的值 (还可能用到其他属性值)。那么相应依赖图中有一条从 X.c 到 A.b 的边。
- 假设和产生式 p 关联的一个语义规则通过 X.a 的值定义了继承属性 B.c 的值。那么在相应依赖图中有一条从 X.a 到 B.c 的边。
属性求值顺序
依赖图刻画了对一棵语法分析树中不同结点上的属性求值时可能采取的顺序。如果依赖图中有一条从结点 M 到结点 N 的边，那么先对 M 对应的属性求值，再对 N 对应的属性求值。因此，所有的棵性求值顺序就是满足下列条件的结点顺序 \(N_{1}, N_{2}, \cdots, N_{k}\)；如果有一条从结点 \(N_{i}\) 到 \(N_{j}\) 的依赖图的边，那么 \(i < j\)。这样的排序将一个有向图变成了线性排序，即图的拓扑排序 (topological sort)。
如果依赖图中存在任意的环，将不存在拓扑排序，即没办法对相应的 SDD 求值；如果图中没有没有环，那么总能找到至少一个拓扑排序。
S 属性的定义
有些特定类型的 SDD 不允许产生带环的依赖图，且有两类还可以和自顶向下以及自底向上语法分析过程一起高效实现的 SSD，即之前提到的 S-attribute 和 L-attribute。
如果一个 SDD 的每个属性都是综合属性，那么这个 SDD 就是 S-attribute Definition。 S-attribute SDD 可以按照分析树的结点，以任何自底向上的顺序计算各个属性值。最简单的方式即后序遍历语法分析树。因此 S-attribute SDD 可以在自底向上语法分析的过程中实现。
L 属性的定义
L-attribute SSD 的思想是在一个产生式体所关联的各个属性之间，依赖图的边总是从左到右。也就是说每个属性必须：
- 要么是一个综合属性；
- 要么是一个继承属性。但这个继承属性有如下规则限制。假设存在一个产生式
\(A\rightarrow{}X_{1}X_{2}\cdots{}X_{n}\)，且有一个通过这个产生式关联的规则计算得到的继承属性 \(X_{i}.a\)，那么这个规则只能使用
- 和产生式的头部 A 关联的继承属性
- 位于 \(X_{i}\) 左边的文法符号实例 \(X_{1}, X_{2}, \cdots, X_{i-1}\) 相关的继承属性或综合属性
- 和这个 \(X_{i}\) 实例本身相关的继承属性或综合属性，但是在由这个 \(X_{i}\) 的全部属性组成的依赖图中不存在环
因此可以确定，之前乘法文法的规则，是一个 L-attribute Definition SSD。
具有受控副作用的语义规则
有时一个语义规则可能出现副作用，比如打印一个结果，或将一个标识符类型加入到符号表中。
对于 SDD，需要在属性文法与翻译方案之间找到一个平衡点。属性文法没有副作用，并支持任何与依赖图一致的求值顺序。翻译方案要求从左向右顺序求值，并允许语义行为包含任何代码片段。那么我们可以用以下方法之一控制 SDD 中的副作用：
- 支持那些不会对属性求值产生约束的附带副作用。即如果按照依赖图的任何拓扑排序进行属性求值，最终都可以产生正确的翻译结果，那么就允许副作用存在。
- 对允许的求值顺序添加约束，使得以任何允许的顺序求值都会产生相同的翻译结果。这个约束可以看作隐含加入到依赖图的边。
简单实现一个声明 D，可以声明基本类型 T (int 或 float)，后跟一个标识符列表。假设每个标识符录入符号表条目中。假设一个标识符的类型不会影响其他标识符对应的符号表条目，条目可以按照任意顺序进行更新。另外，SDD 也不检查标识符是否被声明了多次。
| 编号 | 产生式 | 语义规则 |
|---|---|---|
| 1 | \(D\rightarrow{}TL\) | \(L.inh=T.type\) |
| 2 | \(T\rightarrow{}\textbf{int}\) | \(T.type=integer\) |
| 3 | \(T\rightarrow{}\textbf{float}\) | \(T.type=float\) |
| 4 | \(L\rightarrow{}L_{1}\,\textit{,}\,\textbf{id}\) | \(L_{1}.inh=L.inh; addType(\textbf{id}.entry, L.inh)\) |
| 5 | \(L\rightarrow{}\textbf{id}\) | \(addType(\textbf{id}.entry, L.inh)\) |
需要注意的是 addType 的参数
- id.entry: 在词法分析中得到的一个指向某个符号表对象的值
- L.inh: 标识符的类型值
因此 addType 可以正确的将 id 所代表的标识符类型设置为 L.inh。也可以认为调用
addType 是设置该结点的哑属性。比如输入串 float f1, f2, f3，我们依据此输入构建依赖图。
语法制导翻译的应用
语法制导的翻译技术通常用于类型检查与中间代码生成。本节主要应用与抽象语法树的构造。为了完成到中间代码的翻译，编译器接下来可能使用一组规则来编译这棵语法树 (实际建立在 SSD 上)。
抽象语法树的构建
一棵语法树中的每个结点代表一个程序构造，这个结点的子结点代表这个构造有意义的组成部分。比如表达式 \(E_{1}+E_{2}\) 的语法树结点的标号为 \(+\)，两个子结点分别代表子表达式 \(E_{1}\) 和 \(E_{2}\)。
我们将使用具有适当数量的字段的对象来实现一棵语法分析树的各个结点。每个对象将有一个 op 字段，即这个结点的标号。这些对象将具有如下所述的其他字段：
- 如果结点是叶结点，那么对象将有一个附加字段来存放这些叶节点的词法值。构造函数
Leaf(op, val)创建一个叶对象。也可以把结点看作记录，那么 Leaf 可以返回指向叶结点对应的新记录的指针。 - 如果结点是内部结点，那么它的附加字段的个数与该结点在语法分析树中的子结点个数相同。构造函数 Node 带有两个或多个参数
Node(op, c1, c2, ..., ck)。
以下示例为 S 属性定义为一个简单的表达式文法构造出语法树，这个文法只有二元运算符 \(+\) 和 \(-\)，通常这两个运算符具有相同优先级且都是左结合。所有非终结符都有一个综合属性 node，表示相应抽象语法树结点
| 编号 | 产生式 | 语义规则 |
|---|---|---|
| 1 | \(E\rightarrow{}E_{1}+T\) | \(E.node=\textbf{new}\ Node(’+’, E_{1}.node, T.node)\) |
| 2 | \(E\rightarrow{}E_{1}-T\) | \(E.node=\textbf{new}\ Node(’-’, E_{1}.node,T.node)\) |
| 3 | \(E\rightarrow{}T\) | \(E.node=T.node\) |
| 4 | \(T\rightarrow(E)\) | \(T.node=E.node\) |
| 5 | \(T\rightarrow{}\textbf{id}\) | \(T.node=\textbf{new}\ Leaf(\textbf{id}, \textbf{id}.entry)\) |
| 6 | \(T\rightarrow{}\textbf{num}\) | \(T.node=\textbf{new}\ Leaf(\textbf{num}, \textbf{num}.val)\) |
比如说输入 \(a-4+c\) 构造一棵抽象语法树，这棵抽象语法树的结点被显示为记录，这些记录的第一个字段是 op。现在抽象语法树的边用实线表示，基础的语法分析树的边用点状虚线表示 (并没有真的生成它)，最后一种线状虚线表示 \(E.node\) 和 \(T.node\) 的值，每条线都指向适当的抽象语法树的结点。
在自底向上分析过程中，我们可以得到如下的抽象语法树构造步骤。 \[\begin{aligned} p_{1}&={}\textbf{new}\ Leaf(\textbf{id}, entry-a);\\ p_{2}&={}\textbf{new}\ Leaf(\textbf{num}, 4);\\ p_{3}&={}\textbf{new}\ Node(’-’, p_{1}, p_{2});\\ p_{4}&={}\textbf{new}\ Leaf(\textbf{id}, entry-c);\\ p_{5}&={}\textbf{new}\ Node(’+’, p_{3}, p_{4}); \end{aligned}\]
如果改用自顶向下语法分析，得到的抽象语法树是相同的，其构造步骤也相同，但语法分析树的构造与抽象语法树的构造有极大不同。
| 编号 | 产生式 | 语义规则 |
|---|---|---|
| 1 | \(E\rightarrow{}TE^{’}\) | \(E.node=E^{’}.syn;\ E^{’}.inh=T.node\) |
| 2 | \(E^{’}\rightarrow{}+TE^{’}_{1}\) | \(E^{’}_{1}.inh={}\textbf{new}\ Node(’+’,E^{’}.inh,T.node); E^{’}.syn=E^{’}_{1}.syn\) |
| 3 | \(E^{’}\rightarrow{}-TE^{’}_{1}\) | \(E^{’}_{1}.inh={}\textbf{new}\ Node(’-’,E^{’}.inh,T.node); E^{’}.syn=E^{’}_{1}.syn\) |
| 4 | \(E^{’}\rightarrow{}\varepsilon\) | \(E^{’}.syn={}E^{’}.inh\) |
| 5 | \(T\rightarrow{}(E)\) | \(T.node=E.node\) |
| 6 | \(T\rightarrow{}\textbf{id}\) | \(T.node={}\textbf{new}\ Leaf(\textbf{id},\textbf{id}.entry)\) |
| 7 | \(T\rightarrow{}\textbf{num}\) | \(T.node={}\textbf{new}\ Leaf(\textbf{num},\textbf{num}.val)\) |
这个在语法分析树的结点上对 SDD 求值提到的简易乘加计算器类似，通过继承属性将左边的计算结果进行传递。对于同样的表达式 a-4+c 将有不一样的依赖图。
类型的结构
当语法分析树的结构与输入的抽象语法树结构不同时，继承属性是很有用的。这种情况下，继承属性可以用来将信息从语法分析树的一部分传递到另一部分。
比如 C 语言中的 int[2][3]，相应的表达式可以是 array(2, array(3, integer))。因此我们可以尝试用以下的 SDD 来构造语法分析树。
| 产生式 | 语义规则 |
|---|---|
| \(T\rightarrow{}BC\) | \(T.t=C.t;\ C.b=B.t\) |
| \(B\rightarrow{}\textbf{int}\) | \(B.t=integer\) |
| \(B\rightarrow{}\textbf{float}\) | \(B.t=float\) |
| \(C\rightarrow{}[\textbf{num}]C_{1}\) | \(C.t=array(\textbf{num}.val, C_{1}.t);\ C_{1}.b=C.b\) |
| \(C\rightarrow{}\varepsilon\) | \(C.t=C.b\) |
非终结符 B 和 T 有一个表示类型的综合属性 t，非终结符 C 有两个属性：继承属性 b 和综合属性 t。继承属性 b 将一个基本类型沿树向下传播，而综合属性 t 则收集最终得到的结果。
语法制导的翻译方案
语法制导的翻译方案 (Syntax-Directed Translation Scheme, SDT) 是语法制导定义的一种补充，是在其产生式体中嵌入了程序片段的一个上下文无关文法，这些片段称为语义动作，它们可以出现在产生式体的任何地方。任何 SDT 都可以通过下面的方式实现：首先构造一棵语法分析树，然后按照从左到右的深度优先顺序来执行这些动作，也就是说在一个前序遍历过程中执行。
通常 SDT 在语法分析的过程中实现，不会真的构造一棵语法分析树。但着重点我们放在两类 SDD 上：
- 基本文法可以用 LR 技术分析，且是 S-attribute SDD
- 基本文法可以用 LL 技术分析，且是 L-attribute SDD
在语法分析过程中实现的 SDT 可以按照如下的方式识别：将每个内嵌的语义动作替换为一个独有的非终结符 (marker nonterminal)。每个标记非终结符 M 只有一个产生式 \(M\rightarrow{}\varepsilon\)。如果带有标记非终结符的文法可以使用某个方法进行语法分析，那么这个 SDT 就可以在语法分析过程中实现。
后缀翻译方案
最简单的实现 SDD 的情况是第一种文法，即可以用 LR 技术分析，且是 S-attribute SDD。这种情况下我们可以构造出一个 SDT，其中的每个动作都放在产生式的最后，并在归约为头部的时候执行这个动作。所有动作都在产生式最右端的 SDT 称为后缀翻译方案。
后缀 SDT 当归约发生时执行相应的语义动作。各个文法符号的属性值可以放到栈中的某个位置，使得执行归约的时候可以找到它们，最好的方法就是将属性和文法符号一起放入栈的记录里。
如果所有属性都是综合属性，且所有动作都位于产生式某位，那么我们可以在把产生式体归约成产生式头的时候计算各个属性的值。
产生式内部带有语义动作的 SDT
动作可以放在产生式体中的任何位置上。当一个动作左边的所有符号都被处理后，该动作立即执行。因此，如果有一个产生式 \(B\rightarrow{}X\{a\}Y\)，那么我们识别的 X 或者所有从 X 推导出的终结符之后，动作 a 就会执行。即：
- 如果语法分析过程是自底向上的，那么我们在 X 的此次出现位于语法分析栈的栈顶时，立即执行动作 a
- 如果语法分析过程是自顶向下的，那么在试图展开 Y 的本次出现或输入中检测 Y 之前执行动作语义 a
可以在语法分析过程中实现的 SDT 包括后缀 SDT 和 实现 L 属性的 SDD 介绍的 L-attribute 定义 SDT。但不是所有的 SDT 都可以在语法分析过程中实现。
作为 SDT 的极端例子，不能在自顶向下或自底向上的语法分析过程中实现这个 SDT。因此语法分析程序必须在它还不知道出现在输入中的运算符是 \(*\) 还是 \(+\) 的时候，就执行打印这些操作。
| 编号 | 产生式 |
|---|---|
| 1 | \(L\rightarrow{}E\textbf{n}\) |
| 2 | \(E\rightarrow{}\texttt{\{\,print(’+’);\,\}}\ E_{1}+T\) |
| 3 | \(E\rightarrow{}T\) |
| 4 | \(T\rightarrow{}\texttt{\{\,print(’-’);\,\}}\ T_{1}*F\) |
| 5 | \(T\rightarrow{}F\) |
| 6 | \(F\rightarrow{}(E)\) |
| 7 | \(F\rightarrow{}\textbf{digit}\ \texttt{\{\,print(}\textbf{digit}\texttt{.lexval);\,\}}\) |
任何 SDT 都可以按照下列方法实现：
- 忽略语义动作，对输入进行语法分析，并产生一棵语法分析树
- 检查每个内部结点 N，假设它的产生式为 \(A\rightarrow{}\alpha\)，将 \(\alpha\) 中的各个动作当作 N 的附加结点加入，使得 N 的子结点从左到右和 \(\alpha\) 中的符号及动作完全一致
- 对这棵语法分析树进行前序遍历，且当访问到一个以某个动作为标号的结点时立刻执行这个动作
现在构造表达式 \(3*5+4\) 的语法分析树，可以按照构造的语法分析树得到这个前缀形式 \(+\,*\,3\,5\,4\)
从 SDT 中消除左递归
由于左递归文法不能在自顶向下的语法分析中进行，因此有了消除左递归的算法。当文法是 SDT 的一部分时，还需要考虑如何处理其中的动作。
最简单的情况下，只关心一个 SDT 的动作的执行顺序的情况。如果每个动作只打印一个字符串，那就关心的是打印字符串的顺序。
当转换文法的时候，将动作当成终结符好处理。基于这个思路，文法转换保存了由文法生成的符号串中终结符的顺序，因此动作在任何从左到右分析过程中都按照相同的顺序执行 (无论是 LR 还是 LL)。
消除左递归在 LL 文法中讲过。比如将 \(A\rightarrow{}A\alpha\,|\,\beta\) 转换为 \[\begin{aligned} A &\rightarrow{} \beta{}R\\ R &\rightarrow{} \alpha{}R\,|\,\varepsilon \end{aligned}\]
如过将其应用到一个带有动作的产生式 \(E \rightarrow{} E_{1} + T\ \{\,\texttt{print}(’+’);\,\} \ |\ T\)，消除左递归后得到 \[\begin{aligned} E &\rightarrow{} TR\\ R &\rightarrow{} + T\ \{\,\texttt{print}(’+’);\,\}\ R\\ R &\rightarrow{} \varepsilon \end{aligned}\]
但是这种方式在计算 S-attribute SDD 时没有什么问题，但计算 L-attribute SDD 时需要非常小心。好消息是，可以实现一个通用的，解决单个递归产生式、单个非递归产生式并该左递归非终结符只有单个属性的方案。可以将此方案推广到多个递归 / 非递归产生式，但实现起来非常麻烦。
假设 \[\begin{aligned} A &\rightarrow{} A_{1}Y\ \{\,A.a\,=\,g(A_{1}.a,Y.y)\,\}\\ A &\rightarrow{} X\ \{\,A.a\,=\,f(X.x)\,\} \end{aligned}\]
基础文法可以消除左递归改为 \[\begin{aligned} A &\rightarrow{} XR\\ R &\rightarrow{} YR\,|\,\varepsilon \end{aligned}\]
可以看出无论是在原文法上应用后缀 SDT 还是消除左递归后应用 SDT，其结果都是相同的。只不过消除左递归后，还需要一个综合属性 R.s 沿树向上拷贝。
最终可以得到 SDT \[\begin{aligned} A &\rightarrow{} X\ \{\,R.i\,=\,f(X.x);\,\}\ R\ \{\,A.a\,=\,R.s;\,\}\\ R &\rightarrow{} Y\ \{\,R_{1}.i\,=\,g(R.i,Y.y);\,\}\ R_{1}\ \{\,R.s\,=\,R_{1}.s;\,\}\\ R &\rightarrow{} \varepsilon\ \{\,R.s\,=\,R.i;\,\} \end{aligned}\]
L 属性定义的 SDT
只要文法是 LR 的，就能保证 S-attribute SDD 转换成后缀 SDT，后缀 SDT 可以正确的按照自底向上的方式进行语法分析和翻译。
现在我们考虑更加一般化的情况，L-attribute SDD。基础文法假设采用自顶向下的方式进行语法分析，只需要将动作附加到一棵语法分析树中，并对其进行前序遍历时完成动作。因此我们可以用以下规则将 L-attribute SDD 转换到 SDT：
- 把计算某个非终结符 A 的继承属性的动作插入到产生式体中紧靠在 A 的本次出现之前的位置上。
- 将计算一个产生式头的综合属性动作放在最右端。
比如 C 语言的 while 语句 \(S \rightarrow{} \textbf{while}\, ( C)\, S_{1}\)，
- 继承属性 \(S.next\) 是必须在 S 执行结束之后执行的代码的开始处标号
- 综合属性 \(S.code\) 是中间代码序列，实现了语句 S 并在最后转跳到 \(S.next\)
- 继承属性 \(C.true\) 是必须在 C 为真时执行的代码的开始处标号
- 继承属性 \(C.false\) 是必须在 C 为假时执行的代码的开始处标号
- 综合属性 \(C.code\) 是一个中间代码序列，实现了表达式 C，并根据 C 的值转跳到 \(C.true\) 或 \(C.false\)
实现的 SDD 类似 \[\begin{aligned} S\rightarrow{} \textbf{while}\,( C)\,S_{1} &\qquad L_{1} = new();\\ &\qquad L_{2} = new();\\ &\qquad S_{1}.next = L_{1};\\ &\qquad C.false = S.next;\\ &\qquad C.true = L_{2};\\ &\qquad S.code = \textbf{label}\ ||\ L_{1} \ ||\ C.code\ ||\ \textbf{label} \ ||\ L_{2}\ ||\ S_{1}.code \end{aligned}\]
当然最后的 \(||\) 表示连接各代码片段的符号。这个 SDD 是 L 属性的，因此转换为 SDT 时还需要考虑变量 \(L_{1}\) 和 \(L_{2}\)。如果将语义动作当作哑非终结符来处理，那么变量可以当作其综合属性处理。由于不依赖于其他属性，因此可以分配到表达式的第一个语义动作中。 \[\begin{aligned} S\rightarrow{} &\textbf{while}\,( & \{\,L_{1}=new();\ L_{2}=new();\ C.false=S.next;\ C.true=L_{2};\,\}\\ & C\,) & \{\,S_{1}.next=L_{1};\,\}\\ & S_{1} & \{\,S.code=\textbf{label}\ ||\ L_{1} \ ||\ C.code\ ||\ \textbf{label} \ ||\ L_{2}\ ||\ S_{1}.code\,\} \end{aligned}\]
实现 L 属性的 SDD
在递归下降语法分析中进行翻译
可以按照如下方法将一个语法分析器扩展成一个翻译器
- 函数 A 的参数是非终结符 A 的继承属性
- 函数 A 的返回值是非终结符 A 的综合属性集合。在函数内要进行语法分析并处理属性
- 决定用哪个产生式展开 A
- 需要读入终结符时，在输入中检查这些符号是否出现
- 在局部变量中保存所有必要的属性值
- 调用对应于被选定非终结符的函数，并提供正确的参数
类似的，可以写出关于上一个示例 while 的伪代码
string S(label next):
string Scode, Ccode;
label L1, L2;
if curr_input is while:
read curr_input;
check next punctuation is ‘(’, and read it;
L1 = new();
L2 = new();
Ccode = C(next, L2);
check next punctuation is ‘)’, and read it;
Scode = S(L1);
return “label” || L1 || Ccode || “label” || L2 || Scode;
else:
pass
边扫描边生成代码
使用属性来构造代码并构造出很长的串，代价是很大的。通常在代码生成的时，执行一个 SDT 语义动作，逐步将各个代码片段加入到缓冲区或文件中。为了实现这个功能，下列要素必不可少：
- 存在一个 (一个或多个非终结符的) 主属性
- 主属性是综合属性
- 对主属性求值规则保证： a. 主属性是将相关产生式体中的非终结符的主属性值连接起来得到的 b. 各个非终结符的主属性值在连接运算中出现的顺序，和这些非终结符在产生式体中出现的顺序相同
现在用 print 将各个元素打印出来，修改为边扫描边生成的函数
现在我们可以实现相应的 SDT \[\begin{aligned} S\rightarrow{} &\textbf{while}\,( & \{\,L_{1}=new();\ L_{2}=new();\ C.false=S.next;\ C.true=L_{2};\ print(“label”, L_{1});\,\}\\ & C\,) & \{\,S_{1}.next=L_{1};\ print(“label”, L_{2});\,\}\\ & S_{1} & \end{aligned}\]
L 属性的 SDD 和 LL 语法分析
假设一个 L 属性的 SDD 的基础文法是 LL 文法，且按照 L 属性定义的 SDT 一节将其转换为一个 SDT，其语义动作被嵌入到各个产生式中。可以 LL 语法分析中完成翻译过程，需要扩展语法分析栈来存放语义动作和属性求值所需的某些数据项。额外保存动作记录 (action-record) 和综合记录 (synthesize-record)，其中前者是即将执行的语义动作，而后者保存的是非终结符的综合属性。
- 非终结符 A 的继承属性放在表示这个非终结符的栈记录中，对这些属性求值的代码通常在仅靠 A 的上面。
- 非终结符 A 的综合属性单独的存放在仅靠 A 的下面。
还是用 while 的例子来说明
对于 while 我们可以回到计算综合属性 S.next，来构建新的语法分析栈
L 属性的 SDD 的自底向上语法分析
使用自底向上的方法来完成任何可以用自顶向下的方式完成翻译过程。更准确地说，给定一个 LL 文法为基础的 L 属性 SDD，可以修改为 LR 语法分析为基础的 SDD：
- 按照 L 属性定义的 SDT 方法构造的 SDT 为起点，在各个非终结符之前计算其继承属性，并在产生式后端动作中计算综合属性
- 对每个内嵌的语义动作，向这个文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，任意标记 M 都有一个产生式 \(M\rightarrow{}\varepsilon\)
- 如果标记非终结符在某个产生式 \(A\rightarrow{}\alpha{}\,\{a\}\,\beta\) 中替换了语义动作 \(a\)，对 \(a\) 进行修改得到 \(a^{’}\)，且将 \(a^{’}\) 关联到 \(M\rightarrow{}\varepsilon\) 上。这个动作 \(a^{’}\) a. 将动作 a 需要的 A 或 \(\alpha\) 中符号的任何属性作为 M 的继承属性进行拷贝 b. 按照 a 中的方法计算各个属性，但计算得到的属性作为 M 的综合属性
简单地说，假设有产生式 \(A\rightarrow{}BC\)，继承属性 \(B.i\) 由 \(A.i\) 计算得到。则有 SDT 片段 \(A\rightarrow{}\{\,B.i=f(A.i);\,\}\ B\ C\)。用上述规则修改 SDT，将其修改为 \[\begin{aligned} A &\rightarrow{} M B C\\ M &\rightarrow{} \{\,M.i=A.i;\ M.s=f(M.i);\,\} \end{aligned}\]
那么对于之前 C 语言的 while 示例，可以改写为 \[\begin{aligned} S &\rightarrow{} \textbf{while} (\,M\,C\,) N S_{1}\\ M &\rightarrow{} \varepsilon\\ N &\rightarrow{} \varepsilon \end{aligned}\]