4. 语义制导翻译技术

1. 动机 (Motivation)

在编译器的前两个阶段（词法分析和语法分析）之后，我们已经检查了程序“长得对不对”（是否符合语法结构），生成了一棵分析树。但是，编译器还不知道这棵树代表什么含义。

核心目标：把“语法结构”和“语义”联系起来。
具体任务：
1. 计算值：比如算出表达式的结果是 17。
2. 类型检查：比如确认 int a 和 real b 能不能相加。
3. 生成代码：将高级语言结构翻译成中间代码或机器指令。
一句话总结：如果是语法分析是搭建骨架，语法制导翻译就是给骨架填肉（语义信息）。

2. 概念 (Concept)：核心术语与分类

要描述翻译过程，我们需要一套形式化的工具。

2.1 语法制导定义 (SDD)

这是对上下文无关文法的扩充。我们给每个文法符号加几个“属性” (Attributes)，给每个产生式加几条“规则” (Rules)。

2.2 两种关键属性 (Attributes)

这就像数据在分析树上的流动方向：

综合属性 (Synthesized Attribute) —— 自底向上 (Bottom-up)
- 含义：我的值由我的孩子决定。
- 例子：表达式求值。。的值等于孩子和的值相加。
- 比喻：像是盖楼，底层的砖头砌好了，上层才能盖好。
继承属性 (Inherited Attribute) —— 自顶向下 (Top-down) 或从左向右
- 含义：我的值由我的父亲或者哥哥（左兄弟）决定。
- 例子：类型声明 int a, b, c。关键字 int 在最上面/最左边，它需要把“整数类型”这个信息传给后面的 a, b, c。
- 比喻：像是家族传承，父亲把姓氏传给孩子，或者大哥把消息传给二弟。

2.3 依赖图 (Dependency Graph)

属性之间是有依赖关系的（比如依赖才能算出）。依赖图就是把这些依赖关系画出来。计算属性的顺序必须符合依赖图的拓扑排序 (Topological Sort)，也就是先算被依赖的，再算依赖别人的。

2.4 两类重要的 SDD

根据只用哪种属性，我们将 SDD 分类，这决定了实现的难易程度：

S-属性定义 (S-Attributed Definitions)：
- 特点：只使用综合属性。
- 评价：最简单，完美契合 LR 分析（自底向上分析）。
L-属性定义 (L-Attributed Definitions)：
- 特点：可以使用综合属性，也可以使用受限的继承属性。
- 受限条件：计算某个符号的继承属性时，只能依赖它左边的兄弟或父亲（不能依赖右边的弟弟，因为还没分析到那里）。
- 评价：比较灵活，覆盖了大多数编程语言的需求。

3. 方法 (Method)：如何实现？

知道了概念，怎么把它们写进编译器里？

3.1 翻译方案 (Translation Schemes)

这是 SDD 的具体代码实现形式。我们将语义动作（用花括号 {} 包起来的代码段）直接插入到产生式的右部。

S-属性：把动作都放在产生式的最末尾。
L-属性：把动作插在属性刚刚被计算出来的地方（通常是符号中间或后面）。

3.2 S-属性的自底向上实现 (最常用)

因为 LR 分析器本身就是自底向上的（归约时才处理），S-属性也是自底向上的，所以两者是天作之合。

做法：改造分析栈。原来的栈只存状态，现在增加一列存属性值 (val)。
执行：每当进行归约 (Reduction) 时，执行代码。比如，就弹出和的 val，算出的 val 并压栈。

3.3 L-属性的自底向上实现 (难点)

LR 分析是自底向上的，但 L-属性包含自顶向下的继承属性。这就像是“逆水行舟”，需要特殊技巧。

技巧 1：移除嵌入动作（引入标记非终结符）
- 如果动作在产生式中间（例如），LR 分析器不知道什么时候执行。
- 方法：加一个空产生式，把动作挂在上。变成。这样分析器遇到就会归约空串，顺便执行动作。
技巧 2：复用栈上的信息
- 有时候，继承属性的值（比如父亲的类型）其实已经在栈里某个位置了。
- 方法：直接通过栈指针（如 val[top-k]）去“偷看”那个值。
技巧 3：改写文法
- 如果信息流向和分析方向冲突（比如类型在最后 id list : type），就改写文法，把类型提到前面或者让它顺着分析流走。

4. 典型例题 (Examples)：实战演练

这里总结刚刚讲过的两道重点题（源自作业 5.16 和 5.17），它们完美对应了上述两种属性定义。

例题 A：括号配对与深度 (对应作业 5.16)

文法：,

(1) 统计配对括号个数 —— S-属性 (自底向上)

思路：我们要“数数”。只有这一步才产生一对新括号。
逻辑：
- 遇到：个数为 0。
- 遇到：个数相加。
- 遇到：内部的个数 + 1。
特点：值从下往上传。

(2) 输出嵌套深度 —— L-属性 (自顶向下)

思路：我们要“传递环境”。外层要告诉内层“你现在在第几层”。
逻辑：
- 最外层：深度 0。
- 进入：把当前深度 + 1 传给里面的。
- 列表：把深度原封不动地传给子节点和。
- 遇到：打印当前接收到的深度。
特点：值从上往下、从左往右传。

例题 B：二进制小数转十进制 (对应作业 5.17)

文法： (表示整数.小数)，，

输入：101.101

难点：
- 整数部分（左边）：101 = 。逻辑是 val * 2 + bit。
- 小数部分（右边）：.101 = 。我们需要知道“总位数”才能算出除以多少。
解法 (S-属性)：
1. 左子树：算出数值 val=5。
2. 右子树：算出数值 val=5，同时记录一个长度属性 len=3。
3. 根节点合并：
  $整数小数小数$
  即。

总结心得：

第五章其实就讲了两件事：

定义规则 (SDD)：用“综合属性”解决自底向上的计算（如求值），用“继承属性”解决依赖上下文的计算（如类型检查）。
实现规则 (Method)：把这些计算逻辑塞进 LR 分析器里。S-属性直接算；L-属性要么改文法，要么用技巧（空产生式）让分析器在正确的时候执行代码。