编译原理 4：句法制导翻译

在完成语法分析后，我们得到了源代码对应的语法树，但这样的东西距离能用来运行的机器码显然还有不少的距离。具体地，我们即使有了语法树，我们还是不知道代码的语义——代码「要做什么」。句法制导翻译关注的就是读懂代码的「语义」，使用 CFG 来引导对语言的翻译。

基本思想 #

我们为 CFG 中的文法符号设置语义属性，用来表示语法成分对应的语义信息。文法符号的语义属性值，是用与文法符号所在产生式相关联的语义规则来计算的。

需要引入句法制导定义（SDD）和句法制导翻译方案（SDT）。

句法制导定义 #

SDD 是对 CFG 的推广，它将每个文法符号和一个语义属性集合相关联，将每个产生式和一组语义规则相关联。

如果 $X$ 是一个文法符号，$a$ 是 $X$ 的一个属性，则用 $X.a$ 表示属性 $a$ 在某个符号为 $X$ 的分析树结点上的值。语义规则则是在产生式中，对某一语法变元的某个属性进行计算的规则。例如，对于 C 语言变量类型 $T\to\mathrm{int}$，它对应的语义规则就是 $T.type=\mathrm{int}$（将 $T$ 的 $type$ 字段设置成 $\mathrm{int}$）。

句法制导翻译方案 #

将语义规则（语义动作）嵌入 CFG，我们就得到句法制导翻译方案 SDT。我们把语义动作放在花括号内，如：

语法符号的属性 #

综合属性 #

综合属性是指只能通过一个语法符号（非终结符或者终结符）自身或者（非终结符）它的子结点属性值来定义的属性。例如，对于产生式 $E\to E+T$，对应语义规则 $E.val = E.val + T.val$，这里的 $val$ 就是综合属性。

继承属性 #

继承发生是指只能通过非终结符的父结点、兄弟结点或者它本身属性值来定义的属性。例如，对于产生式 $D\to TL$，对应语义规则 $L.inh=T.type$（即 $L$ 的类型是 $T$ 给出的），$inh$ 就是继承属性。

分析树和依赖图 #

在语法分析树中，如果将结点（语法符号）的属性和属性之间的依赖关系画在树上，其中综合属性画在结点的左边，继承属性画在右边，我们就可以得到一个有向图，称为「依赖图」。如果属性 $X.a$ 的值依赖于 $Y.b$ 的值，则依赖图中有一条从 $Y.b$ 到 $X.a$ 的边。如：

​

S-SDD #

仅仅使用综合属性的 SDD 称为 S-属性的 SDD，或 S-属性定义、S-SDD。由于综合属性只能通过节点自己或者子节点计算，对于这样的 SDD，可以按照分析树结点自底向上计算各个属性值。例如：

​

S-SDD 定义的制导方案（SDT），只要将对应的语义规则放置在对应的产生式末尾，例如：

​

如果这个文法可以使用 LR 分析，那么它的 SDT 可以在 LR 句法分析过程中实现：在规约发生时，执行相应的语义动作。在原有的状态栈和符号栈之上，我们增加一个「综合属性」栈，用来存放对应符号的综合属性值，即可实现 SDT 的 LR 分析。

具体地，我们还要将语义规则中的 ${A.a=f(X.x, Y.y, Z.z)}$ 这样的抽象定义，更改为具体可执行的栈操作。例如：

stack[top - 2].symb = A
stack[top - 2].val = f(stack[top - 2].val, stack[top - 1].val, stack[top].val)
top = top - 2

当规约动作发生时，按这些栈操作进行即能实现 S-SDT 的语义分析。
​

L-SDD #

使用了部分继承属性的 SDD 称为 L-SDD，其中 L 的意思是「从左到右」，即这种 SDD 依赖图的边可以从左到右，但不能从右到左。L-SDD 的属性要么是综合属性，要么是这样的继承属性：假设存在产生式 $A\to X_1X_2\cdots X_n$，其右部符号 $X_i$ 的继承属性仅依赖于 (a) $A$ 的继承属性，或 (b) $X_1X_2\cdots X_{n-1}$ 的属性，或 (c) $X_i$ 本身的属性，且不构成环路。

例如：

​

对于 L-SDD 的 SDT，需要：

• 将计算某个非终结符号 $A$ 的继承属性的动作插入到产生式右部紧靠 A 的本次出现之前的位置。
• 将计算左部综合属性的动作放在最后。

例如：

​

得到：

​

在非递归的预测分析中进行翻译 #

「非递归的预测分析」即 LL(1) 的分析法。在编译原理 2：自顶向下的语法分析中，我们使用「语法分析栈」记录已经分析出来的语法变元。现在，我们需要对这个栈中的元素进行扩充，将原先的单个文法符号 $A$ 变成下面的结构：

​

以上面的乘法文法为例。首先，将所有的语义动作用指针指代，得到下面的 SDT：

​

尝试分析式子 3 * 5。首先，按照 LL(1) 分析表的构造文法，先写出这个文法的 LL(1) 分析表。

然后开始分析。

• 启动时，分析栈为初始符号 $T$ 的综合属性和继承属性。

  T   Tsyn   #
      (val)
  

• 读入 3，使用 $T\to FT’$，将 $T’$ 和 $F$ 先后入栈。

  F   Fsyn  {a1}   T'    T'syn  {a2}  Tsyn  #
      (val)        (inh) (syn)  ===>  (val)
  

• 使用 $F\to\mathbf{digit}$，将 $\mathbf{digit}$ 入栈，消去 3。

  digit  {a6}  Fsyn     {a1}   T'      T'syn  {a2}  Tsyn  #
  (3)    ===>  (val=3)  ====>  (inh=3) (syn)  ===>  (val)
  

• 读入 *，使用 $T’\to FT_1’$，将 $T_1’$、$F$ 和 $$ 先后入栈，消去 *。

  *  F  Fsyn  {a3}   T1'  T1'syn  {a4}  T'syn  {a2}  Tsyn  #
        (val)       (inh) (syn)   ===>  (syn)  ===>  (val)
             (T'inh=3)
  

• 读入 5，使用 $F\to\mathbf{digit}$，消去 5。

  digit  {a6}  Fsyn  {a3}  T1'  T1'syn  {a4}  T'syn  {a2}  Tsyn  #
  (5)   ====> (val=5) 3*5=> (inh=15) => ...
  

L-SDD 的 LR 翻译 #

给定一个 LL 文法为基础的 L-SDD，可以修改这个文法来对它进行 LR 分析中的句法制导翻译。我们将每个产生式右部中间的语义动作移出，改为用产生 $\varepsilon$ 的标记非终结符替代。这样在修改后的 SDT 中，所有语义动作都在产生式的末尾。如：

然后，重新设计 LR 分析表，在规约动作发生时，执行相应的语义动作。

本节笔记到此结束。