语法制导翻译 I • Arthals' ink

概述

语法分析器
- 用于判断输入在语法上的正确性。
- 语法分析完成后，通常还需将输入的源代码翻译为目标表示形式。
语法制导翻译（Syntax-Directed Translation，SDT）
在产生式体中加入语义动作，并在适当的时候执行这些语义动作
- 编译器在分析过程中执行的工作
- 包含语义分析和正确性检查，若正确，则翻译为中间代码或目标代码
- 文法符号的属性描述其语义（如变量的类型、层次、存储地址等），通过对属性值的计算完成翻译任务
语法制导定义（Syntax-Directed Definition, SDD）
- 将文法符号和某些属性相关联
- 通过语义规则描述如何计算属性的值

SDD 是上下文无关文法和属性 / 规则的结合。

规则定义： 对于 $\forall A \rightarrow X_1 X_2 \ldots X_n \in P$ ，每个规则的一般形式为： $c = f(c_1, c_2, \ldots, c_k)$

综合属性： $c$ 是 $A$ 的一个属性，且 $c_1, c_2, \ldots, c_k$ 是 $A$ 的继承属性或是某个 $X_i$ 的属性（向上看继承的或者向下看子节点属性，综合全局看 ）。
继承属性： $c$ 是某个符号 $X_i$ 的属性，且 $c_1, c_2, \ldots, c_k$ 是 $A$ 或 $X_j$ 的属性（父节点、自己、兄弟节点的属性，向上看 ）。

不允许 $N$ 的继承属性通过 $N$ 的子结点上的属性来定义，但允许 $N$ 的综合属性依赖于 $N$ 本身的继承属性。

定义：只包含综合属性 的 SDD 称为 S 属性的 SDD。

实现：

无副作用：语义规则不应有复杂的副作用。

若存在直接左递归，则无法使用自顶向下分析。

消除左递归后，可能无法直接使用自顶向下分析，比如，我们把一个：

T \rightarrow T + E \mid E

拆成了：

\begin{aligned} T &\rightarrow E T' \\ T' &\rightarrow + E T' \mid \varepsilon \end{aligned}

此时，对于第二个产生式， $+$ 的左侧因子无法直接获得。

为此，我们需要引入继承属性。

\begin{array}{|l|l|} \hline \text{产生式} & \text{语义规则} \\ \hline T \rightarrow FT' & T'.inh = F.val \\ & T.val = T'.syn \\ \hline T' \rightarrow *FT_1' & T_1'.inh = T'.inh * F.val \\ & T'.syn = T_1'.syn \\ \hline T' \rightarrow \varepsilon & T'.syn = T'.inh \\ \hline F \rightarrow digit & F.val = digit.lexval \\ \hline \end{array}

注意看黑实线的属性传递流，同一个产生式的语义动作可能不是同时执行的。

这些黑实线实际上构成了一个依赖图（后面会讲）。

定义：语义规则中的每个属性可以是：

综合属性
继承属性
对于任意产生式 $A \rightarrow X_1 X_2 ... X_n \in P$ ， $X_j$ 的继承属性仅依赖于：
- 产生式中 $X_j$ 左边符号 $X_1, X_2, ..., X_{j-1}$ 的属性
- $A$ 的继承属性

每一个 S 属性的 SDD 都是 L 属性的 SDD。

L 属性的 SDD 可用于按 深度优先 顺序来计算。

对于规则：

A \rightarrow X_1 X_2 ... X_n

在递归子程序中实现 L 属性，则对于每个非终结符号 $A$ 或者 $X_i$ ，其对应的函数的参数为继承属性，返回值为综合属性。

在处理规则时：

注意： 如果所有的文法符号的属性计算按上述方式进行，计算顺序必然和依赖关系一致。

使用 依赖图 表示计算顺序：

若依赖图无环，则存在一个拓扑排序，确定属性值的计算顺序。

特定类型的 SDD 一定不包含环，且有固定的排序模式：

S 属性的 SDD：可用于 自顶向下 和 自底向上 的语法分析
- 每个属性都是综合属性
- 都是根据子构造的属性计算出父构造的属性
- 在依赖图中，总是通过子结点的属性值来计算父结点的属性值
L 属性的 SDD：可用于按 深度优先 顺序来计算