浅谈编译原理——语法制导翻译篇

综合属性#

综合属性：通过子节点符号的属性或通过自身的属性计算得到。

• 通常用于从下往上传递信息。
• $b$ 是 $A$ 的一个综合属性，且 $c_1,c_2,\cdots,c_k$ 为产生式右部符号的属性（即 $A$ 的子节点的属性），或 $A$ 的继承属性；
• 向上看继承，向下看子节点

还有一类比较特殊的属性，一般用于拓广文法的起始符号 $S^\prime$，其不依赖任何属性，仅用于在属性计算完成后输出某个值或完成一项功能，例如 Print(E.val)，所以称其为虚拟综合属性。

继承属性#

继承属性：某节点的继承属性由它兄弟、父亲或者自己的属性计算得到。

• 通常用于自上而下，或横向传递信息。
• 如果 $b$ 是产生式右部某个符号 $X_i$ 的一个继承属性，那么 $c_1,c_2,\cdots,c_k$ 是 $A$（它爹） 或任何产生式右部符号 $X_j$（兄弟或它自己）的属性；
• 属性 $b$ 依赖于属性 $c_1,c_2,\cdots,c_k$；

依赖图#

分析树中不同的节点间的属性存在依赖关系，可以用依赖图表示。

表示方法：

• 分析树中，为符号的每个属性设置一个结点，一般画在符号旁边
• 如果属性 b 依赖于 c，那么存在一条 c -> b 的有向边（被依赖者指向依赖者，因为只有 c 先算了才能算 b）；

因此，属性的计算次序可以由依赖图的拓扑排序确定。

引入 2 种特殊的语法制导定义，这两种 SDD 的依赖图一定无环，因此可以通过拓扑排序计算出所有属性的属性值。

S属性定义翻译#

1. 为每一个语义规则建立一个包含赋值的动作；
2. 把这个动作放在相应的产生式右边末尾；

这是比较显然的，因为都是综合属性，而父节点的综合属性依赖于子节点，因此需要等子节点先都分析完才能计算。例如，以产生式 $T\rightarrow T_1*F$ 和语义规则 $T.val=T_1.val*F.val$ 为例，将语义动作如下插入：

S 属性定义的基础文法是 LR 文法，其与 LR 分析过程是兼容的，当归约发生时，即可执行对应语义动作。

L属性定义翻译#

L 属性定义既有综合属性又有继承属性，因此需要遵守以下原则：

• 一个动作不能引用这个动作右边的文法符号的综合属性；
  • 因为是处理过程是从左到右的，右边文法符号的综合属性还没有计算出来；
• 对于产生式左部符号的综合属性：
  • 只有在它所引用的所有属性都计算出来之后才能计算；
  • 因此放在产生式右端末尾；（与 S 属性文法要求一致）
• 对于产生式右部符号的继承属性：
  • 必须在这个符号以前的动作中计算出来；
  • 因此放在该文法符号前面；
  • 即对于右部符号 $A$ 的继承属性的动作，插入到右部紧靠 $A$ 之前的位置上（$A$ 的左边）；

语法树 vs. 分析树#

具体语法树 vs. 抽象语法树 vs. 分析树：

抽象语法树将节点按照以下操作抽象：

1. 对于叶子节点：用一个附加域存储此叶子结点的词法值/符号表入口
   • makeleaf(id, entry)：建立一个标识符节点，标号为 id，附加域指向该标识符在符号表中条目的入口；
   • makeleaf(num, val)：建立一个数节点，标号为 num，附加域直接存词法值；
2. 对于内部节点：附加字段数量等于结点的子结点数量，通过构造函数连接子节点
   • makenode(op, left, right)：op 表示运算操作，left/right 分别指向左右孩子；

构造 AST 及其语法制导定义#

对于 AST，产生式的语义应该是创建与产生式左部符号代表的子表达式对应的子树，即创建子树的根结点。

因此，文法符号的属性应包括 nptr 表示指向创建的子树的根节点，例如，对于产生式 $E\rightarrow E_1+T$，对应的语义规则为：

分析和翻译过程形如：

有向非循环图dag#

简单来说， 在语法树的基础上，公共表达式可以有多个父亲节点，节省了存储开销。

自底向上的翻译过程实现（LR）#

修改分析栈：使其能保存综合属性。

改写语义规则：使之变成具体可执行的栈操作。

简单来说，当要执行归约操作 $A\rightarrow XYZ\cdot$前，执行对应代码，先改写对应的符号栈，然后计算对应的综合属性栈。然后在执行归约操作，将 $A$ 入栈，$X,Y,Z$ 出栈，栈顶变化为 $top\rightarrow top - 2$。因此，综合属性刚好在每次归约前计算。

对于终结符，其在移进时，综合属性值（由词法分析程序提供）随状态一起入栈。

1. 移走翻译方案中嵌入的语义规则#

只要把嵌入（除产生式右部最右侧）在产生式右部之中的语义动作想办法移动到最右边，那么之后的分析思路与 S属性的翻译过程就类似了。

因此，针对嵌入在产生式右部的语义规则，例如 $R\rightarrow +T\{print('+')\}R$：

• 引入一个新的非终结符 $M$；
• 以及对应产生式 $M\rightarrow\varepsilon\{print('+')\}$

2. 直接使用分析栈中的继承属性#

使用该方法的前提是：

• 继承属性在栈中
• 位置已知

3. 变换继承属性的计算规则#

前一种方法中，虽然我们知道 LR 分析过程中，属性值都放在分析栈 val 中，但是无法知道继承属性的值在栈中的位置。

例如，如果同时包含产生式 $A\rightarrow aXZ$ 和 $A\rightarrow bXYZ$，对应的语义动作均为 $Z.i = X.s$，即继承属性 $Z.i$ 依赖之前的 $X$，当问题是，在到达 $Z$ 并使用 $Z\rightarrow z$ 进行归约时，无法知道 $Z.i$ 该取 val[top-1] 还是 val[top-2]，即无法知道 $Z$ 离 $X$ 有多远。

个人理解，解决的思路是想办法区分语义动作相同的产生式，例如如果产生式 $A\rightarrow aXZ$ 以及语义动作均不变，我们在希望使用它时，$Z.i$ 需要的就是 val[top-1]。而对于产生式 $A\rightarrow bXYZ$，我们引入一个新的符号，并中转属性的继承关系：

1. 在 $Z$ 前面添加一个非终结符 $M$ 及产生式 $M\rightarrow\varepsilon$，使之紧挨着 $Z$；
2. 产生式 $A\rightarrow bXYMZ$ 对应的语义规则修改为 $M.i=X.s,Z.i=M.s$；
3. 产生式 $M\rightarrow\varepsilon$ 对应的语义规则为 $M.s = M.i$；

因此，如果我们希望 $Z.i$ 继承自 val[top-2]，进行上述修改后，分析过程变成：当分析到 $M$ 之前，让 $M.i$ 去接收本来要继承给 $Z$ 的 $X.s$，分析到 $M$ 时，计算 $M.s = M.i$，接下来分析到 $Z$，此时 $M.s$ 就位于 val[top-1]，$Z.i$ 能确定继承 $M.s$。

上面只是针对“复制规则”，即直接等于，进一步可以考虑对所有继承属性的“非复制规则“进行改造，将其改造为复制规则，考虑：

• $A \rightarrow a X Y,Y.i = f(X.s)$（非复制规则）
• $Y → y,Y.s = g(Y.i)$

同样，引入非终结符 $N$ 和对应产生式 $N\rightarrow\varepsilon$，将以上文法改写为：

• $A → a X N Y,N.i = X.s,Y.i = N.s$
• $N\rightarrow\varepsilon,N.s = f(N.i)$
• $Y → y,Y.s = g(Y.i)$

和复制规则基本一致，只是 $N\rightarrow\varepsilon$ 中执行的计算改变。

在归约 $N\rightarrow\varepsilon$ 前，栈中状态形如：

1
a       X(top)
2
a.lex   X.s

当归约 $N\rightarrow\varepsilon$ 时，N 入栈，且 $N.i$ 来自当前栈顶 $X$ 对应的综合属性值处，因此 N.s: val[top+1]=f(val[top])。栈中状态变为：

1
a       X     N
2

3
a.lex   X.s   N.s

$y$ 入栈：

1
a       X     N(top-1)  y(top)
2

3
a.lex   X.s   N.s       y.lex

随后归约 $Y\rightarrow y$，$y$ 出栈而 $Y$ 入栈，$Y.i$ 来自于 $N.s$，因此对应的执行过程为 Y.s: val[top]=g(val[top-1])。栈中状态变为：

1
a       X     N     Y
2

3
a.lex   X.s   N.s   Y.i

事实上按照上述方法构造，基本可以得出以下归约时执行动作的结论：

4. 改写语法制导定义为S属性定义#

• 改写文法
• 让信息传递方向与 LR 归约方向一致

😄依旧似懂非懂。