编译技术

---

• 编译技术
  • 1　词法分析（lexical analysis）
    • 1.1　串和语言
    • 1.2　正规式（Regular Expression）
    • 1.3　有限自动机
      • 1.3.1　确定的有限自动机（DFA）
      • 1.3.2　不确定的有限自动机（NFA）
      • 1.3.3　NFA -> DFA（子集构造法）
      • 1.3.4　DFA 的化简
    • 1.4　词法分析器的生成器（Lex）
  • 2　语法分析
    • 2.1　语言和文法
    • 2.2　上下文无关文法
      • 2.2.1　消除左递归
      • 2.2.2　提取左因子
    • 2.3　自上而下分析
      • 2.3.1　$FIRST$ 集和 $FOLLOW$ 集
      • 2.3.2　$LL(1)$ 文法
      • 2.3.3　递归下降的预测分析
      • 2.3.4　非递归的预测分析
      • 2.3.5　预测分析的错误恢复
    • 2.4　自下而上分析
      • 2.4.1　$LR$ 分析器
      • 2.4.2　构造 $SLR$ 分析表
      • 2.4.3　构造规范的 $LR$ 分析表
      • 2.4.4　构造 $LALR$ 分析表
      • 2.4.5　$LR$ 分析的错误恢复
    • 2.5　语法分析器的生成器（Yacc）
  • 3　语法制导翻译
    • 3.1　语法制导定义
    • 3.2　S 属性定义的自下而上计算
      • 3.2.1　构造语法树的语法制导定义
      • 3.2.2　S 属性的自下而上计算
    • 3.3　L 属性定义的自上而下计算
      • 3.3.1　L 属性定义
      • 3.3.2　翻译方案
      • 3.3.3　预测翻译器的设计
    • 3.4　L 属性的自下而上计算
      • 3.4.1　删除翻译方案中嵌入的动作
      • 3.4.2　分析栈上的继承属性
  • 4　类型检查
  • 5　运行时存储空间的组织和管理
  • 6　中间代码生成
  • 7　代码生成

---

1　词法分析（lexical analysis）

1.1　串和语言

字母表（alphabet）：符号的有限集合 $\Sigma$
串：符号的有穷序列
语言：字母表上的一个串集

1.2　正规式（Regular Expression）

正规式	定义的语言
ε	{ε}
a	{a}
(r)|(s)	L(r)∪L(s)
(r)(s)	L(r)L(s)
(r)*	(L(r))*
(r)	L(r)

运算符优先级：* > 连接运算 > |

1.3　有限自动机

1.3.1　确定的有限自动机（DFA）

• 状态集合 $S$
• 输入字母表 $\Sigma$
• 转换函数 $move: S \times \Sigma \rightarrow S$
• 唯一的初态 $s \in S$
• 终态集合 $F$

1.3.2　不确定的有限自动机（NFA）

• 状态集合 $S$
• 输入字母表 $\Sigma$
• 转换函数 $move: S \times (\Sigma \cup \{ \varepsilon \}) \rightarrow P(S)$，其中 $P(S)$ 是 $S$ 的幂集
• 唯一的初态 $s \in S$
• 终态集合 $F$

1.3.3　NFA -> DFA（子集构造法）

• DFA 的一个状态，是 NFA 的一个状态集合
• 当读入了 $a_1, a_2, \dots, a_n$ 后，若 NFA 能到达的所有状态为 $s_1, s_2, \dots, s_k$，则 DFA 到达状态 $\{s_1, s_2, \dots, s_k\}$

1.3.4　DFA 的化简

DFA 是否最简的判断依据：状态的可区分性.

对于 DFA $M$，如果存在串 $w$，使得 $M$ 从状态 $s$ 出发，在面临 $w$ 时，最终停在一个接受状态，而从状态 $t$ 出发，在面临 $w$ 时，却最终停在一个非接受状态，则称串 $w$ 可用来区别状态 $s$ 和状态 $t$。

如果找不到任何的串来区别 $s$ 和 $t$，则称状态 $s$ 和状态 $t$ 是不可区别的，反之则称状态 $s$ 和状态 $t$ 是可区别的。

DFA 化简步骤（要求 $move$ 是全函数，为此可先给 DFA 增加死状态，化简后再去除）：

• 构造状态集合的初始划分 $\varPi$：将状态集合划分为接受状态集合 $F$ 和非接受状态集合 $S-F$。
• 反复应用以下过程，直到 $\varPi$ 不再变化：
  对于 $\varPi$ 中的每个集合 $G$，把 $\varPi$ 中的 $G$ 替换为 $G$ 的一个划分，该划分满足：对于 $G$ 中的任意两个状态 $s$ 和 $t$，划分后它们在同一个集合中，当且仅当对任意的符号 $a$， $s$ 和 $t$ 的 $a$ 转换是到 $\varPi$ 中的同一个集合中。
• 从 $\varPi$ 中的每个集合中选一个状态来代表它，这些状态就是最简 DFA 的状态。若 $s$ 是这样一个代表，则若在化简前的 DFA 中，状态 $s$ 的 $a$ 转换到状态 $t$，且 $t$ 所在的集合的代表是 $r$，则在化简后的 DFA 中，$s$ 的 $a$ 转换到 $r$。

1.4　词法分析器的生成器（Lex）

略

2　语法分析

2.1　语言和文法

一个 0 型文法（短语文法） $G$ 是一个四元组 $(V_{T}, V_{N}, S, P)$，其中：

• $V_{T}$ 是非空有限的终结符集合；
• $V_{N}$ 是非空有限的非终结符集合；
• $S$ 是一个非终结符，称作开始符号；
• $P$ 是产生式的有限集合，每个产生式的形式是 $\alpha \rightarrow \beta$，其中 $\alpha \in (V_{T} \cup V_{N})^{ * } V_{N} (V_{T} \cup V_{N})^{ * }, \beta \in (V_{T} \cup V_{N})^{ * }$。

0 型文法 $G$ 是 1 型文法（上下文有关文法），如果 $G$ 的任何产生式 $\alpha \rightarrow \beta$ 或者满足 $|\alpha| \le |\beta|$，或者形如 $S \rightarrow \varepsilon$，且 $S$ 没有出现在任何产生式的右部；

0 型文法 $G$ 是 2 型文法（上下文无关文法），如果 $G$ 的任何产生式都形如 $A \rightarrow \alpha$，其中 $A \in V_{N}, \alpha \in (V_{T} \cup V_{N})^{*}$。

0 型文法 $G$ 是 3 型文法（正规文法），如果 $G$ 的任何产生式都形如 $A \rightarrow aB$ 或 $A \rightarrow a$，其中 $A, B \in V_{N}, a \in V_{T}$。

后面均只涉及上下文无关文法，因此将其简称为文法。

2.2　上下文无关文法

定义见上文。

2.2.1　消除左递归

直接左递归 $A \rightarrow A\alpha | \beta$ 可以用非左递归的

• $A \rightarrow \beta A'$
• $A' \rightarrow \alpha A'|\varepsilon$

来代替。

而非直接左递归

• $S \rightarrow Aa | b$
• $A \rightarrow Sd | \varepsilon$

则可先变换成直接左递归

• $S \rightarrow Aa | b$
• $S \rightarrow Aad | bd | \varepsilon$

再消除左递归

• $S \rightarrow Aa | b$
• $A \rightarrow bdA' | A'$
• $A' \rightarrow adA'| \varepsilon$

2.2.2　提取左因子

文法 $A \rightarrow \alpha \beta_{1} | \alpha \beta_{2}$ 可替换为

• $A \rightarrow \alpha A'$
• $A' \rightarrow \beta_{1} | \beta_{2}$

2.3　自上而下分析

要求：

• 消除左递归
• 避免回溯

2.3.1　$FIRST$ 集和 $FOLLOW$ 集

一个文法符号串$\alpha$ 的开始符号集合 $FIRST(\alpha)$ 是从 $\alpha$ 推导出的串的起始终结符的集合：

$FIRST(\alpha) = \left\{ a | \alpha \Rightarrow^{*} a \dots, a \in V_{T} \right\}$

特别地，当 $\alpha \Rightarrow^{*} \varepsilon$ 时，规定 $\varepsilon \in FIRST(\alpha)$。

非终结符 $A$ 的后继符号集合 $FOLLOW(A)$ 是所有在句型中可以直接出现在 $A$ 后面的终结符集合：

$FOLLOW(A) = \left\{ a | S \Rightarrow^{*} \dots A a \dots, a \in V_{T} \right\}$

约定如果 $A$ 是某个句型的最右符号（即 $S \Rightarrow^{*} aA$），那么 $\$$ 也属于 $FOLLOW(A)$。

$FIRST$ 集的计算方法

• 若 $X \rightarrow a\dots$，则将终结符 $a$ 加入 $FIRST(X)$ 中；
• 若 $X \rightarrow \varepsilon$，则将 $\varepsilon$ 加入 $FIRST(X)$ 中；
• 若 $X \rightarrow Y\dots$，其中 $Y$ 是非终结符，则将 $FIRST(Y) \backslash \left\{ \varepsilon \right\}$ 加入到 $FIRST(X)$ 中；
• 若 $X \rightarrow Y_{1}Y_{2} \dots Y_{k}$，其中 $Y_{1}Y_{2} \dots Y_{i - 1} \; (2 \le i \le k)$ 都是非终结符，且 $Y_{1}Y_{2} \dots Y_{i - 1}$ 的 $FIRST$ 集合中均包含 $\varepsilon$，则将 $FIRST(Y_{j}) \; (j = 1, 2, \dots , i)$ 中的所有非 $\varepsilon$ 元素加入到 $FIRST(X)$ 中，特别地，若 $Y_{1}, Y_{2}, \dots, Y_{k}$ 均有 $\varepsilon$ 产生式，则将 $\varepsilon$ 加入 $FIRST(X)$ 中。

$FOLLOW$ 集的计算方法

• 对于文法开始符号 $S$，将 $\$$ 加入 $FOLLOW(S)$ 中；
• 对产生式 $A \rightarrow \alpha B \beta$，将 $FIRST(\beta) \backslash \left\{\varepsilon\right\}$ 中的元素加入 $FOLLOW(B)$ 中；若 $\beta \rightarrow \varepsilon$，则将 $FOLLOW(A)$ 中的元素加入 $FOLLOW(B)$ 中。

2.3.2　$LL(1)$ 文法

若文法 $G$ 满足，对于文法的任何两个产生式 $A \rightarrow \alpha | \beta$，都有

• $FIRST(\alpha) \cap FIRST(\beta) = \varnothing$；
• 若 $\beta \Rightarrow^{*} \varepsilon$，则 $FIRST(\alpha) \cap FOLLOW(A) = \varnothing$，

则称文法 $G$ 是 $LL(1)$ 文法。

2.3.3　递归下降的预测分析

计算 $SELECT$ 集：给定上下文无关文法的产生式 $A \rightarrow \alpha$， 若 $\alpha$ 不能推导出 $\varepsilon$，则 $SELECT(A \rightarrow \alpha) = FIRST(\alpha)$；若 $\alpha$ 能推导出 $\varepsilon$，则 $SELECT(A \rightarrow \alpha) = \left( FIRST(\alpha) \backslash \left\{\varepsilon \right\}\right) \cup FOLLOW(A)$。

为每一个非终结符写一个分析过程。

2.3.4　非递归的预测分析

表驱动的预测分析器有一个输入缓冲区、一个栈、一张分析表和一个输出流。输入缓冲区包含被分析的串 $w$，后面跟一个符号 $\$$ 作为输入串的结束标记；栈中存放文法符号串，栈底符号是 $\$$；分析表 $M$ 是一个二维数组 $M[A,a]$，$A$ 是非终结符，$a$ 是终结符或 $\$$。

初始时，$\$S$ 在栈中，其中 $S$ 是开始符号且在栈顶，$w\$$ 在输入缓冲区中，输入指针指向 $w\$$ 的第一个符号。

预测分析器根据当前的栈顶符号 $X$ 和输入符号 $a$ 来决定分析器的动作，有四种可能：

1. 如果 $X=a=\$$，分析器宣布分析完全成功而停机；
2. 如果 $X=a\ne\$$，分析器弹出栈顶符号 $X$，并推进输入指针使其指向下一个符号；
3. 如果 $X$ 是非终结符，且 $M[X,a]$ 是 $X$ 的产生式，即 $M[X,a] = X \rightarrow Y_{1}Y_{2} \dots Y_{k}$，则分析器弹出栈顶符号 $X$，并把 $Y_{k}Y_{k-1} \dots Y_{1}$ 依次压入栈，使 $Y_{1}$ 在栈顶；
4. 其他情况，出错。

预测分析表 $M$ 的构建

对于文法的每个产生式 $A \rightarrow \alpha$，执行：

1. 对 $FIRST(\alpha)$ 的每个终结符 $a$，把 $A \rightarrow \alpha$ 加入 $M[A, a]$ 中；
2. 如果 $\varepsilon \in FIRST(\alpha)$，对 $FOLLOW(A)$ 中的每个终结符 $b$（包括 $\$$），把 $A \rightarrow \alpha$ 加入 $M[A, b]$ 中。

这等价于：

对于文法的每个产生式 $A \rightarrow \alpha$，对所有的 $a \in SELECT(A \rightarrow \alpha)$，把 $A \rightarrow \alpha$ 加入 $M[A, a]$ 中。

2.3.5　预测分析的错误恢复

紧急方式的错误恢复：发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个特定的同步记号集合为止。

2.4　自下而上分析

2.4.1　$LR$ 分析器

右句型：最右推导可得到的句型

句柄：右句型 $\gamma$ 的句柄是一个产生式 $A \rightarrow \beta$ 的右部 $\beta$ 以及 $\gamma$ 中的一个位置，在这个位置可找到串 $\beta$，且用 $A$ 替换这里的 $\beta$ 得到最右推导的前一个右句型。

1. 句柄是句型的一个子串；
2. 把句柄归约成非终结符代表了某一步最右推导的逆过程。

$LR$ 分析器包含一个输入缓冲区、一个栈、一张分析表和一个输出流，其中：

1. 输入缓冲区包含以 $\$$ 结束的被分析的串 $w\$$；
2. 栈中存放过去的状态符号和文法符号（真正实现时文法符号不是必需的），栈底符号是 $\$$；
3. 分析表 $M$ 由两部分组成：动作表 $action$ 和转移表 $goto$。

$LR$ 分析器根据栈顶的状态和当前的输入符号检索分析表 $M$ 以决定接下来的动作。具体地将，分析器根据栈顶状态 $s$ 和当前的输入符号 $a$ 访问 $action[s, a]$，并执行相应的动作：

1. 若 $action[s, a] =$ 移进 $t$，则分析器执行移进动作，将当前输入符号 $a$ 和状态 $t$ 压入栈，并移动输入指针使其指向下一个输入符号；
2. 若 $action[s, a] =$ 归约 $A \rightarrow \beta$，则分析器执行归约动作，从栈中弹出 $2r$ 个符号（其中 $r$ 是 $\beta$ 的长度），即弹出 $r$ 个文法符号和 $r$ 个状态符号（这 $r$ 个文法符号恰好构成 $\beta$），此时栈顶暴露出过去的某个状态 $t$。分析器接下来访问 $goto$ 表，把产生式左部的文法符号 $A$ 和新状态 $goto[t, A]$ 压入栈（注意当前输入符号没有改变）。
3. 若 $action[s, a] =$ 接受，则分析成功完成；
4. 若 $action[s, a] =$ 出错，则分析器发现错误。

$LR$ 分析方法的特点：

1. 栈中的文法符号总是形成一个活前缀；
2. 分析表的转移表本质上是识别活前缀的 DFA。

2.4.2　构造 $SLR$ 分析表

项目：文法 $G$ 的 $LR(0)$ 项目（简称项目）是在其产生式右部的某个地方加点的产生式。如从产生式 $A \rightarrow XYZ$ 可得到如下四个项目：

$A \rightarrow \boldsymbol{\cdot} X Y Z \\ A \rightarrow X \boldsymbol{\cdot} Y Z \\ A \rightarrow X Y \boldsymbol{\cdot} Z \\ A \rightarrow X Y Z \boldsymbol{\cdot} \\$

规定对于产生式 $A \rightarrow \varepsilon$，只能得到项目 $A \rightarrow \boldsymbol{\cdot}$。

拓广文法：如果文法 $G$ 的开始符号是 $S$，那么 $G$ 的拓广文法 $G'$ 是在 $G$ 的基础上增加新的文法符号 $S'$ 和产生式 $S' \rightarrow S$。

闭包函数 $closure$：如果 $I$ 是文法 $G$ 的一个项目集，那么 $closure(I)$ 是应用如下两条规则从 $I$ 构造的项目集：

1. 初始时，将 $I$ 的每个项目都加入 $closure(I)$；
2. 如果 $A \rightarrow \alpha \boldsymbol{\cdot} B \beta$ 在 $closure(I)$ 中，且 $B \rightarrow \gamma$ 是产生式，则将 $B \rightarrow \boldsymbol{\cdot} \gamma$ 加入 $closure(I)$ 中。反复应用此规则，直到没有新的项目加入 $closure(I)$ 为止。

转移函数 $goto$：如果 $I$ 是文法 $G$ 的一个项目集，$X$ 是文法符号，$goto(I, X)$ 是满足 $A \rightarrow \alpha \boldsymbol{\cdot} X \beta$ 属于 $I$ 的所有项目 $A \rightarrow \alpha X \boldsymbol{\cdot} \beta$ 的集合的闭包。

项目集规范族：拓广文法 $G'$ 的 $LR(0)$ 项目集规范族 $C = \left\{I_{0}, I_{1}, \dots, I_{n} \right\}$ 是项目集的集合，其构建方法如下：

1. 将项目集 $closure(\left\{S \rightarrow \boldsymbol{\cdot} S \right\})$ 加入 $C$ 中；
2. 对于 $C$ 中的每个项目集 $I$ 和 $G$ 的每个文法符号 $X$，如果 $goto(I, X)$ 非空且不在 $C$ 中，则将其加入 $C$ 中。重复这一步直到没有新的项目集加入 $C$。

项目集规范族和 $goto$ 函数构成了识别 $G'$ 的活前缀的 DFA。

构造拓广文法 $G'$ 的 $SLR(1)$ 分析表

1. 构造 $G'$ 的 $LR(0)$ 项目集规范族 $C = \left\{I_{0}, I_{1}, \dots, I_{n} \right\}$。

2. 对于 $C$ 中的每个项目集 $I$ 构造一个状态 $i$，且 $action$ 表的值按下列规则确定：

   1. 如果 $A \rightarrow \alpha \boldsymbol{\cdot} a \beta$ 在 $I_{i}$ 中，且 $goto(I_{i}, a) = I_{j}$，则令 $action[i, a] =$ 移进 $j$；
   2. 如果 $S' \rightarrow S \boldsymbol{\cdot}$ 在 $I_{i}$ 中，那么令 $action[i, \$] =$ 接受；
   3. 如果 $A \rightarrow \alpha \boldsymbol{\cdot}$ 在 $I_{i}$ 中，那么对 $FOLLOW(A)$ 中的所有 $a$，令 $action[i, a] =$ 归约 $A \rightarrow \alpha$，此时 $A$ 不能为 $S'$。

   如果在应用上述规则时产生冲突，则该文法就不是 $SLR(1)$ 的，算法流产，不产生分析器；

3. 对所有的非终结符 $A$，如果 $goto(I_{i}, A) = I_{j}$，令 $goto[i, A] = j$；

4. 不能由规则 2. 和 3. 定义的表项均为空白，表示出错；

5. 分析器的初始状态是包含项目 $S' \rightarrow \boldsymbol{\cdot}S$ 的项目集 $I_{0}$ 所代表的状态。

2.4.3　构造规范的 $LR$ 分析表

$LR(1)$ 项目：$[A \rightarrow \alpha \boldsymbol{\cdot} \beta, a]$，其中 $A \rightarrow \alpha \beta$ 是产生式，$A \rightarrow \alpha \boldsymbol{\cdot} \beta$ 称作项目的心，$a$ 是终结符或 $\$$，称作项目的搜索符。项目 $[A \rightarrow \alpha \boldsymbol{\cdot} \beta, a]$ 和 $[A \rightarrow \alpha \boldsymbol{\cdot} \beta, b]$ 可简写成 $[A \rightarrow \alpha \boldsymbol{\cdot} \beta, a/b]$

闭包函数 $closure$：

1. 初始时，将 $I$ 的每个项目都加入 $closure(I)$；
2. 如果 $[A \rightarrow \alpha \boldsymbol{\cdot} B \beta, a]$ 在 $closure(I)$ 中，且 $B \rightarrow \gamma$ 是产生式，则对于 $FIRST(\beta a)$ 中的每个终结符 $b$，将 $[B \rightarrow \boldsymbol{\cdot} \gamma, b]$ 加入 $closure(I)$ 中。反复应用此规则，直到没有新的项目加入 $closure(I)$ 为止。

转移函数 $goto$：$goto(I, X)$ 是满足 $[A \rightarrow \alpha \boldsymbol{\cdot} X \beta, a]$ 属于 $I$ 的所有项目 $[A \rightarrow \alpha X \boldsymbol{\cdot} \beta, a]$ 的集合的闭包。

LR(1) 项目集规范族 $C$：

1. 初始时将项目集 $closure(\left\{[S' \rightarrow \boldsymbol{\cdot}S, \$]\right\})$ 加入 $C$ 中；
2. 对于 $C$ 中的每个项目集 $I$ 和 $G$ 中的每个文法符号 $X$，如果 $goto(I, X)$ 非空且不在 $C$ 中，则将其加入 $C$ 中。重复这一步直到没有新的项目集加入 $C$ 中。

构造拓广文法 $G'$ 的规范的 $LR$ 分析表

1. 构造 $G'$ 的 $LR(1)$ 项目集规范族 $C = \left\{I_{0}, I_{1}, \dots, I_{n} \right\}$。

2. 对于 $C$ 中的每个项目集 $I$ 构造一个状态 $i$，且 $action$ 表的值按下列规则确定：

   1. 如果 $[A \rightarrow \alpha \boldsymbol{\cdot} a \beta, b]$ 在 $I_{i}$ 中，且 $goto(I_{i}, a) = I_{j}$，则令 $action[i, a] =$ 移进 $j$；
   2. 如果 [$S' \rightarrow S \boldsymbol{\cdot}, \$]$ 在 $I_{i}$ 中，那么令 $action[i, \$] =$ 接受；
   3. 如果 $[A \rightarrow \alpha \boldsymbol{\cdot}, a]$ 在 $I_{i}$ 中，令 $action[i, a] =$ 归约 $A \rightarrow \alpha$，此时 $A$ 不能为 $S'$。

   如果在应用上述规则时产生冲突，则该文法就不是 $LR(1)$ 的，算法流产，不产生分析器；

3. 对所有的非终结符 $A$，如果 $goto(I_{i}, A) = I_{j}$，令 $goto[i, A] = j$；

4. 不能由规则 2. 和 3. 定义的表项均为空白，表示出错；

5. 分析器的初始状态是包含项目 $[S' \rightarrow \boldsymbol{\cdot}S, \$]$ 的项目集 $I_{0}$ 所代表的状态。

2.4.4　构造 $LALR$ 分析表

同心的 $LR(1)$ 项目集：略去搜索符后相同的项目集。

构造拓广文法 $G'$ 的 $LALR$ 分析表

1. 构造 $G'$ 的 $LR(1)$ 项目集规范族 $C = \left\{I_{0}, I_{1}, \dots, I_{n} \right\}$。

2. 寻找 $LR(1)$ 项目集规范族中同心的项目集，用它们的并集代替他们，构成 $LALR(1)$ 项目集规范族 $C' = \left\{J_{0}, J_{1}, \dots, J_{m} \right\}$。

3. 在 $C'$ 上应用构造 $LR(1)$ 分析表的算法构造 $LALR$ 分析表。

2.4.5　$LR$ 分析的错误恢复

1. $LR$ 分析器在访问转移表时绝不会遇到出错条目，即决不会把不正确的后继移进栈；

2. 规范的 $LR$ 分析器甚至在报告错误之前决不做任何无效归约

紧急方式错误恢复

1. 退栈，直至出现状态 $s$，它有预先确定的非终结符 $A$ 的转移（即 $goto[s, A]$ 有定义）；
2. 抛弃若干个输入符号，直到找到 $a$，它是 $A$ 的合法后继；
3. 把 $A$ 和状态 $goto[s, A]$ 压入栈，恢复正常分析。

$A$ 的选择一般是代表主要语法构造的非终结符，如表达式、语句或程序块。

短语级恢复：对剩余输入作局部修正，如用分号代替逗号，删去多余的分号，或插入遗漏的分号等。

2.5　语法分析器的生成器（Yacc）

略

3　语法制导翻译

3.1　语法制导定义

语法制导定义（Syntax-Directed Definition，SDD）是带属性和语义规则的上下文无关文法，其中每个文法符号有一组属性，每个产生式有一组语义规则，其中的文法成为基础文法，文法符号 $X$ 的属性 $a$ 记作 $X.a$。

在一个语法制导定义中，$A \rightarrow \alpha$ 是文法产生式，$b = f(c_{1}, c_{2}, \dots, c_{k})$ 是该产生式的一个语义规则，其中 $f$ 是函数，$b$ 和 $c_{1}, c_{2}, \dots, c_{k}$ 是该产生式的文法符号的属性，该产生式定义属性 $b$，则称属性 $b$ 依赖于属性 $c_{1}, c_{2}, \dots, c_{k}$，且：

1. 如果 $b$ 是 $A$ 的属性，$b$ 和 $c_{1}, c_{2}, \dots, c_{k}$ 是产生式右部文法符号的属性或 $A$ 的其他属性，则称 $b$ 为 $A$ 的综合属性；

2. 如果 $b$ 是产生式右部某个文法符号 $X$ 的属性，$c_{1}, c_{2}, \dots, c_{k}$ 是产生式右部文法符号的属性或 $A$ 的属性，则称 $b$ 为 $X$ 的继承属性。

属性文法是指语义规则函数无副作用的语法制导定义。

仅使用综合属性的语法制导定义称为 S 属性定义。

每个结点的属性值都标注出来的分析树称作注释分析树，计算各结点的属性值的过程称作分析数的注释或修饰。

属性依赖图：分析树上每个结点的每个属性在依赖图上都有一个结点，如果属性 $b$ 依赖于属性 $c$，则从 $c$ 的结点到 $b$ 的结点有一条有向边。

显然，依赖图的任何一个拓扑排序都是分析树中结点的属性计算的一个正确次序。

至此，由语法制导定义所规范的翻译可以准确地按照下述步骤完成：

1. 根据基础文法构造输入的分析树；
2. 构造属性依赖图；
3. 对依赖图的结点进行拓扑排序；
4. 按拓扑排序的次序计算属性。

这种计算方法称作分析树方法。

对语义规则进行分析，对每个产生式得到与其相关联的一组语义规则的计算次序，据此把计算次序在编译前就确定下来的方法称作基于规则的方法。

不是根据语义规则的特点来选取计算策略，而是根据事先确定的计算策略来限定编译器设计者所提供的语义规则的形式的计算方法称作忽略规则的方法。

3.2　S 属性定义的自下而上计算

仅使用综合属性的语法制导定义称为 S 属性定义。

3.2.1　构造语法树的语法制导定义

语法树是分析树的浓缩表示，算符和关键字不是作为叶结点而是分支节点。

数据结构：语法树的结点可用有若干域的记录来实现，其中，对于算符结点，一个域存放算符，作为该节点的标记，其余的域存放指向运算对象的指针；对于基本运算对象结点，一个域存放其类型，另一个域存放其值。真正用于翻译时语法树的结点还可能有其他域来存储附加在该节点的其他属性值或指向其他属性值的指针。

3.2.2　S 属性的自下而上计算

分析器把文法符号的综合属性放在栈中，每当归约时，根据出现在栈顶的产生式右部符号的属性来计算左部符号的综合属性。

3.3　L 属性定义的自上而下计算

3.3.1　L 属性定义

语法制导定义是 L 属性的，如果每个产生式 $A \rightarrow X_{1} X_{2} \dots X_{n}$ 的每条语义规则计算的是 $A$ 的综合属性，或者计算的是 $X_{j}$ 的继承属性（$1 \le j \le n$）且它仅依赖（1）该产生式中 $X_{j}$ 左边符号 $X_{1}, X_{2}, \dots, X_{j - 1}$ 的属性；和（2）$A$ 的继承属性。

显然，$S$ 属性定义是 $L$ 属性定义。

3.3.2　翻译方案

语法制导翻译方案（Syntax-Directed Translation scheme，SDT）是语法制导定义的一种补充，区别是将语义动作插入在产生式右部的任何地方。这是一种分析和动作交错的方法，以表示动作的执行时机。

如 $A \rightarrow \alpha \{ \dots \} \beta$ 中的语义动作 $\{ \dots \}$ 应当在 $\alpha$ 的推导（或向 $\alpha$ 的归约）结束以后，$\beta$ 的推导（或向 $\beta$ 的归约）开始之前执行。

3.3.3　预测翻译器的设计

从语法制导翻译方案构造语法制导的递归下降预测翻译器

1. 为每个非终结符 $A$ 构造一个函数，$A$ 的每个继承属性声明为该函数的一个形式参数，$A$ 的综合属性作为该函数的返回值，对 $A$ 的产生式的其他每个文法符号的每个属性，在该函数中声明一个对应的局部变量；

2. 非终结符 $A$ 对应的函数中，根据当前的输入符号决定使用哪一个产生式；

3. 每个产生式对应的程序代码中，按照从左到右的次序，对于产生式右部的记号（终结符）、非终结符和语义动作分别作以下工作：

   1. 对于带有综合属性 $x$ 的终结符 $X$（为于属性区分，这里终结符也用大写字母表示），把 $x$ 的值存入为 $X.x$ 设置的变量中，然后产生一个匹配 $X$ 的调用，并推进输入指针；

   2. 对于非终结符 $B$，产生赋值语句 $c = B(b_{1}, b_{2}, \dots, b_{n})$，其中，$B$ 是与非终结符 $B$ 相对应的函数，$b_{1}, b_{2}, \dots, b_{n}$ 是为非终结符 $B$ 的继承属性设置的变量，$c$ 是为非终结符 $B$ 的综合属性设置的变量；

   3. 对于每个语义动作，把语义动作的代码复制到函数代码中，将其中对于属性的引用改为对函数中相应的局部变量的引用。

3.4　L 属性的自下而上计算

在自下而上分析的框架中实现 L 属性定义。

能实现任何基于 $LL(1)$ 文法的 L 属性定义，也能实现许多（但不是全部）基于 $LR(1)$ 文法的 L 属性定义。

为此，需要对翻译方案进行修改。要删除翻译方案中嵌入的动作，以使语义动作都出现在产生式右端，在归约时执行；还需要处理继承属性。

3.4.1　删除翻译方案中嵌入的动作

对于每个嵌入的语义动作，在文法中嵌入一个对应的推出空串的标记非终结符 $M$ 来代表它，并将该语义动作加入到产生式 $M \rightarrow \varepsilon$ 的右端。

如翻译方案

$\ \ \begin{aligned} &E \rightarrow T R \\ &R \rightarrow + T \ \{ print('+'); \} \ R_{1} \ | \ - T \ \{ print('-'); \} \ R_{1} \ | \ \varepsilon \\ &T \rightarrow \mathbf{num} \ \{ print(\mathbf{num}.val); \} \end{aligned}$

可变换成

$\ \ \begin{aligned} &E \rightarrow T R \\ &R \rightarrow + T M R_{1} \ | \ - T N R_{1} \ | \ \varepsilon \\ &T \rightarrow \mathbf{num} \ \{ print(\mathbf{num}.val); \} \\ &M \rightarrow \varepsilon \ \{ print('+'); \} \\ &N \rightarrow \varepsilon \ \{ print('-'); \} \end{aligned}$

3.4.2　分析栈上的继承属性

对于能够静态确定其所依赖的属性在分析栈中的位置的继承属性，直接增加对应的语义动作即可。

对于不能确定位置的属性，可尝试增加标记非终结符，使属性的位置可以静态确定。如对于语法制导定义

$\ \ \begin{array} { l l } { \text{产生式} } & { \text{语义规则} }\\ { S \rightarrow a A C } & { C.i = A.s } \\ { S \rightarrow b A B C } & { C.i = A.s } \\ { C \rightarrow c } & { C.s = g( C.i ) } \end{array}$

可变换为

$\ \ \begin{array} { l l } { \text{产生式} } & { \text{语义规则} } \\ { S \rightarrow a A C } & { C.i = A.s } \\ { S \rightarrow b A B M C } & { M.i = A.s , \ C.i = M.s } \\ { C \rightarrow c } & { C.s = g( C.i ) } \\ { M \rightarrow \varepsilon } & { M.s = M.i } \end{array}$

从而对于非终结符 $C$，不论是在 $a A C$ 还是 $b A B M C$ 的情况下使用 $C \rightarrow c$ 时，$C.i$ 的值都可从 $stack[top - 1].val$ 找到。

对于需要计算的继承属性（即该继承属性是某个综合属性的一个函数），也可通过增加标记非终结符来模拟继承属性的计算。如对于语法制导定义

$\ \ \begin{array} { l l } { \text{产生式} } & { \text{语义规则} } \\ { S \rightarrow a A C} & {C.i = f(A.s)} \\ { C \rightarrow c} & { C.s = g( C.i ) } \end{array}$

可变换为

$\ \ \begin{array} { l l } { \text{产生式} } & { \text{语义规则} } \\ { S \rightarrow a A N C} & {N.i = A.s, \ C.i = N.s} \\ { N \rightarrow \varepsilon } & { N.s = f(N.i) }\\ { C \rightarrow c} & { C.s = g( C.i ) } \end{array}$

从而把 $f(A.s)$ 的计算移到对标记非终结符 $N$ 归约时（推导 $C$ 之前）进行。

可以证明，对于基于 $LL(1)$ 文法的 L 属性定义，总可以通过系统地引入标记非终结符，以在 $LR$ 分析期间完成属性计算，且因为每个标记非终结符只有一个产生式，因此引入标记非终结符后的文法仍然是 $LL(1)$ 的，进而是 $LR(1)$ 的，从而不会引起 $LR$ 分析动作的冲突。

但对于 $LR(1)$ 文法的 L 属性定义，引入标记非终结符可能使文法不再是 $LR(1)$ 的。

4　类型检查

5　运行时存储空间的组织和管理

6　中间代码生成

7　代码生成

---

© 2019 倪可塑 保留所有权利。