# 语法制导翻译

## 语法制导定义

1. 编译程序的目标：将源程序翻译成为 **语义等价** 的目标程序，**具有不同的语法结构**，表达结果却相同

2. 语法制导翻译：使用 **上下文无关文法引导对语言的翻译**，一种面向文法的翻译

3. 语法制导定义 Syntax-Directed Definition, SDD
   - 基础的上下文无关文法
   - 每个文法符号有一组 **属性**
   - 每个文法产生式 $A\to\alpha$ 有一组形式为 $b=f(c_1,\ldots,c_k)$ 的 **语义规则**，其中 $f$ 是函数，$b$ 和 $c_1,\ldots,c_k$ 是文法符号的属性
   - *综合属性 synthesized attribute*：如果 $b$ 是 $A$ 的属性，$c_1,c_2,\ldots,c_k$ 是产生式右部文法符号的属性或是 $A$ 的其他属性。终结符只能有综合属性，属性值无需计算，由词法分析给定
   - *继承属性 inherited attribute*：如果 $b$ 是右部某文法符号 $X$ 的属性，$c_1,c_2,\ldots,c_k$ 是 $A$ 和产生式右部文法符号的属性

4. 可以在语法分析构造分析树 (parse tree)之后计算每个节点的属性，也可以在分析树构造过程中计算属性，得到节点属性值都被标注出来的分析树，也就是注释分析树 (annotated parse tree)，综合属性的计算要自底向上完成

5. 属性依赖图 dependency graph 是要给描述了分析树中节点属性间依赖关系的有向图
   - 属性值为点，每个节点的每个属性都对应一个节点
   - 属性依赖关系为边，属性 $X.a$ 依赖于 $Y.b$ 的值，则有一条从 $Y.b$ 指向 $X.a$ 的有向边

6. 属性的计算次序为依赖图的拓扑排序
   - 当图中出现环的时候，也就是 SDD 的属性间存在循环依赖关系时，无法进行拓扑排序，解决方法是使用依赖图不存在环的特定的 SDD

## S/L 属性的定义

1. S-SDD：仅使用综合属性的语法制导定义
   - 可以按照语法分析树节点的任何自底向上顺序来计算各个属性值
   - 可在自底向上的语法分析过程中实现属性计算，对非左递归文法也可以自顶向下实现计算

2. L-SDD：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左
   - 可以在 LR 分析器或 LL 分析器中实现

3. L 属性的定义：对任意产生式 $A\to X_1\ldots X_n$，右部符号 $X_i(1\leqslant i\leqslant n)$ 的继承属性仅依赖于
   - $A$ 的 **继承属性**
     - 不能依赖于 $A$ 的综合属性，因为 $A$ 的综合属性可能依赖于 $X_i$ 的继承属性，可能形成环路
   - $X_1,\ldots,X_{i-1}$ 的属性
   - $X_i$ 本身的属性，但 $X_i$ 的全部属性不能在依赖图里形成环路

4. 抽象语法树 abstract syntax tree, AST
   - 简称语法树，是分析树的浓缩表示，**算符** 和 **关键字** 是内部节点
   - 语法制导翻译可基于分析树，也可以基于语法树

5. 建立算符表达式的语法树
   - 对 **基本预算对象节点**
     - 一个域存放运算对象类别
     - 另一个域存放其值 (也可以保存其他属性或者指向属性值的指针)
   - 对 **算符节点**
     - 一个域存放算符并作为该节点的标记
     - 令两个域存放指向运算对象的指针

6. S-SDD 和 L-SDD 的抽象语法树是一样的，但分析树却不同
   - S-SDD 的分析树与抽象语法树较接近
   - L-SDD 的分析树与抽象语法树结构不同

## 语法制导翻译方案

1. 语法制导翻译方案 Syntax Directed Translation, SDT
   - 在产生式右部中嵌入了程序片段 (语义动作) 的 CFG
   - 可看作是 SDD 的具体实施方案

2. 将 S-SDD 转换为 SDT
   - 将每个语义动作都放在产生式的最后
   - 后缀翻译方案

3. 扩展的语法分析栈
   - 在分析栈中使用一个附加的域来存放综合属性值，若支持多个属性，可以尝试在栈中存放指针
   - 每个栈元素包含状态、文法符号、综合属性三个域；也可以看成三个平行的栈，因为入栈出栈并不完全同步
   - 语义动作修改为对栈中文法符号属性的计算

## L 属性定义的翻译方案

1. L 属性定义的 SDT
   - 如果每个产生式 $A\to X_1\ldots X_{j-1}X_j\ldots X_n$ 的每条语义规则计算的属性是 $A$ 的综合属性，或者是 $X_j$ 的继承属性且仅依赖 $A$ 的继承属性或 $X_j$ 左边的属性或者 $X_j$ 的属性且不成环
   - S 属性定义属于 L 属性定义

2. 后缀分析方案不适用于 L-SDD

3. 将 L-SDD 转换为 SDT 的规则
   - 将产生式左部符号的综合属性的动作放在产生式右部的最右端
   - 将计算某个非终结符号 A 的继承属性的动作插入到产生式右部中紧靠在 A 的本次出现之前的位置上
   - 多个继承属性则要考虑次序，防止形成环

4. L-SDD 的计算
   - 自顶向下：递归下降
   - 自底向上：考虑结合 LR 分析器，删除翻译方案中嵌入的动作，继承属性在分析栈中的计算

5. 递归下降翻译器的设计
   - 为每个非终结符 A 设计一个函数，每个继承属性对应一个形参，返回值是 A 的综合属性
   - 函数体中，选择适当的产生式，用局部变量保存产生式中文法符号的属性，对终结符号，读入符号并获取综合属性，对非终结符，调用相应函数，记录返回值

6. 不能直接将带有继承属性的 L-SDD 和 LR 结合起来，因为在没有看到整个产生式右部之前，无法确定使用哪个产生式，因此要把嵌入的动作挪到产生式的最右端

7. 对一个产生式 $A\to\alpha\{a\}\beta$，其中 $a$ 为语义动作，引入新的非终结符 $M$，代替 $\{a\}$，得到 $A\to\alpha M\beta$，引入新的产生式 $M\to\varepsilon$，修改 $a$ 为 $a'$，将 $a$ 中需要的 $A$ 或 $\alpha$ 的属性作为 $M$ 的继承属性复制，再按照 $a$ 中的方法计算各属性作为 $M$ 的综合属性保存