语法制导翻译

语义分析定位

语义分析是编译器前端（词法/语法分析）与后端（中间代码生成/优化/目标代码生成）的桥梁。

• 前端完成语法正确性检查 → 语义分析进行上下文相关检查 → 后端生成目标代码

语义错误类型

• 未声明标识符
• 重复定义
• 数组越界
• 类型不兼容
• break/continue 出现在错误位置

语义分析任务

• 作用域检查
• 类型检查
• 中间代码生成

语法制导翻译

每个产生式配备一个语义子程序，在语法分析的同时调用语义子程序完成翻译。

• 语法分析驱动 → 语义子程序执行 → 中间代码生成
• 语义信息通过属性附着在文法符号上传递

属性文法

属性文法 = 上下文无关文法 + 属性 + 语义规则

• 每个文法符号 $X$ 可以关联若干属性 $X.a$
• 每个产生式 $A\to \alpha$ 关联一组语义规则

综合属性

子结点→父结点 传递。

• 在产生式 $A\to X_1{X}_2\dots X_n$ 中，$A$ 的综合属性由子结点 $X_i$ 的属性计算得到
• 语法树自底向上传递信息

示例：表达式 $3\times 5+4$ 的值向上综合

    E.val=19
   /        \
  T.val=15   +
 /     \      \
F.val=3 *      F.val=4
         \
        F.val=5

• $T.val=F_1.val\times F_2.val=3\times 5=15$
• $E.val=T.val+F_3.val=15+4=19$

重点 综合属性自底向上传递，在自下而上分析中天然适用。

继承属性

父结点/兄弟结点→子结点 传递。

• 在产生式 $A\to X_1{X}_2\dots X_n$ 中，$X_i$ 的继承属性由 $A$ 或 $X_j(j<i)$ 的属性计算得到
• 语法树自上而下/从左到右传递信息

示例：float id1, id2 的类型传递

        D
       / \
   type   L
  float  / \
       id1  L
           / \
         id2  ε

• $L.in$ = 继承自 $D.type$ 的类型信息
• $L_1.in\to L_2.in$ 沿链表传递同一类型

重点 继承属性自顶向下传递，在自上而下分析中天然适用。

综合 vs 继承对比

类型	传递方向	适用分析方式
综合属性	子→父	自下而上
继承属性	父/兄→子	自上而下

语法制导翻译方案（SDTS）

SDTS 是属性文法的具体实现框架，定义为五元组 $T=(V_T,V_N,\Delta ,R,S)$：

• $V_T$：终结符集
• $V_N$：非终结符集
• $\Delta$：输出符号集（中间代码/目标代码）
• $R$：规则集，每条规则形如 $A\to \alpha ,\beta$，其中 $\alpha \in (V_T\cup V_N{)}^{\ast }$，$\beta \in {\Delta }^{\ast }$
• $S$：开始符号

翻译对偶

翻译过程通过翻译对偶 $(\alpha ,\beta )$ 的推导描述：

$(S,S){\Rightarrow }^{\ast }(\alpha ,\beta )$

其中 $\alpha$ 是源文法串，$\beta$ 是输出串。

示例：$E\to E+T$ 对应翻译规则 $E\to E+T,ET+$，输入 $i+i$ 的翻译对偶推导：

$(E,E)\Rightarrow (E+T,ET+)\Rightarrow (i+T,iT+)\Rightarrow (i+i,ii+)$

简单 SDTS（Simple SDTS）

非终结符在规则中的出现顺序在源文法和翻译文法中相同。

S- 属性文法（S-Attributed Grammar）

仅含综合属性的属性文法，适合 LR 自下而上分析。

在规约时计算综合属性：$A.val=f(X_1.val,\dots ,X_n.val)$

L- 属性文法（L-Attributed Grammar）

继承属性仅依赖于左边兄弟或父结点的属性，即每个继承属性可沿语法树从左到右传递。

对比：

属性文法	属性类型	适用分析	计算时机
S- 属性	仅综合	自下而上（LR）	规约时
L- 属性	综合 + 继承（受限）	自上而下（LL）	推导时

LL(1) 消除左递归后的 SDT

消除左递归后需用继承属性传递信息：

消除前：$E\to E+T\mid T$

消除后：

• $E\to T\{R.i=T.val\}R\{E.val=R.s\}$
• $R\to +T\{R_1.i=R.i+T.val\}{R}_1\{R.s=R_1.s\}$
• $R\to \epsilon \{R.s=R.i\}$

其中 $R.i$ 为继承属性（传递已计算部分），$R.s$ 为综合属性（返回最终结果）。

带语义动作的 LL(1) 分析算法

LL(1) 分析栈中混入语义符号（用 # 标记），处理规则：

1. 终结符：匹配输入
2. 非终结符：查表展开，将产生式右部（含语义动作符号）逆序入栈
3. 语义动作符号：执行对应语义子程序

LR 分析中的 SDT 实现

LR 分析在规约时执行语义动作：规约到 $A\to \alpha$ 时，栈顶 $\alpha$ 对应的属性值已计算完毕，此时执行 $A$ 的语义规则。

这种方式天然适合 S- 属性文法——综合属性在规约时自底向上计算，无需额外机制。

AST 构建

语法分析结果可组织为抽象语法树（AST），相比语法树：

• 运算符提升为内部节点
• 单继承产生式折叠
• 省略括号、分隔符等语法细节
• 便于后续语义分析和代码生成

类型检查

类型等价

• 名字等价（Name Equivalence）：两类型当且仅当名字相同才等价（如 typedef）
• 结构等价（Structural Equivalence）：两类型当结构组成相同即等价

类型转换

• 类型提升（Promotion）：向超集的自动转换（如 int → float）
• 强制转换（Coercion）：隐式类型转换，编译器自动插入
• 显式转换（Casting）：程序员显式写出（如 (float) i）

类型检查规则

类型检查的形式化表述：$\Gamma ⊢exp:\tau$（在环境 $\Gamma$ 中，表达式 $exp$ 的类型为 $\tau$）

• if 语句：条件必须为 bool，then/else 分支类型一致
• 函数调用：实参类型与形参类型匹配，返回值类型一致
• 赋值：左值类型与右值类型兼容