编译原理

这是清华大学计算机系 2024 年秋季课程《编译原理》的期末复习笔记。

第一讲：课程概述

T 型图

T 型图用于表示一个编译程序，其中

• S 是编译的源语言
• T 是编译的目标语言
• I 是用来实现编译程序的语言

当 I 与 T 相同时，称为（M 机器上运行的）本地编译器；当 I 与 T 不同时，称为（M 机器上运行的）交叉编译器。

多个 T 型图可以进行叠加，只需要保证相邻的 T-I 或者 I-S 相同即可。 L-(A)-B 加上 A-(M)-N 可以得到 L-(N)-B。

例：将机器 A 上的语言 L 移植到机器 B。即，我们现在有 L-(A)-A，我们需要构造一个 L-(B)-B。

在上图中，红框部分不是必要相邻的。

第二讲：词法分析

我认为很有意思的是以下题目：

已知 Java 中的“注释”以 /* 开始，以 */ 结束，在 /* 和 */ 之间，除了 */ 序列外，可以出现任意字符。请构造一个正则表达式来匹配所有此类注释。

直接设计正则表达式是困难的；所以我先构造了一个 DFA，再转为正则表达式。

graph LR



style Start fill:none,stroke-width:0px



Start --> A(( ))

A --> |others| A

A --> |/*| B(( ))

B --> |$\Sigma$ - *| B

B --> |*| C(( ))

C --> |*| C

C --> |$\Sigma$ - * - /| B

C --> |/| D((( )))

可以写出正则表达式为： $$/*\left(\left(\Sigma - \{*\}\right) + **^*\left(\Sigma - \{*, /\}\right)\right)^* **^*/$$

第三讲：自顶向下语法分析

带回溯的自顶向下语法分析过程中存在两类非确定性：

1. 选择对哪一个非终结符进行展开；
2. 如果选定的非终结符是多个产生式的左部，那么应该选择使用哪一个产生式。

对于第一类非确定性而言，我们可以考虑只允许最左推导或最右推导来避免；对于第二类非确定性而言，我们可以考虑使用自顶向下预测分析：向前查看确定树木的单词符号，然后确定应该选择哪一个产生式进行最左推导。

LL(1) 分析

LL(1) 是指，Left-to-right, Leftmost derivation with 1 token of look-ahead。

对于 CFG $G = \{V_N, V_T, P, S\}$ 而言，我们一般想要研究 $$X_G = V_N \cup V_T \cup \{\varepsilon\} \cup \{v \mid A \to u, v \text{ is a suffix of } u\}.$$

First 集合

对于 CFG $G = \{V_N, V_T, P, S\}$ 而言，$\alpha \in (V_N \cup V_T)^*$ 的 First 集合的定义为 $$\text{First}(\alpha) = \{a \mid \alpha \overset{*}{\implies}a\beta, a \in V_T, \beta \in (V_N \cup V_T)^*, \text{or } a = \varepsilon \text{ when } \alpha \overset{*}{\implies} \varepsilon\}.$$ 直观上来说，一个句型 $\alpha$ 若能够推导出另一个以终结符 $a$ 开头的句型，则 $a \in \text{First}(\alpha)$；若 $\alpha$ 可以推导出 $\varepsilon$，则 $\varepsilon \in \text{First}(\alpha)$。

步骤

• 初始化：对于所有 $x \in V_T\cup\{\varepsilon\}$，都有 $\text{First}(x) = \{x\}$；对于其他 $x$，都有 $\text{First}(x) = \varnothing$。
• 迭代：重复以下步骤，直至所有 First 集合均不变。
  • 对于 $y_1y_2\cdots y_k \in \{v \mid A \to u \in P, v \text{ is a suffix of } u\}$ 而言，
    • 若能找到 $i \in [1, k]$ 使得对于 $\forall j \in [1, i - 1]$ 都有 $\varepsilon \in \text{First}(y_j)$，且 $\varepsilon \notin \text{First}(y_i)$，则 $$\text{First}(y_1y_2\cdots y_k) = \left(\bigcup_{1 \le j \le i}\text{First}(y_j)\right) - \{\varepsilon\}.$$
    • 否则 $$\text{First}(y_1y_2\cdots y_k) = \bigcup_{1 \le j \le k}\text{First}(y_j).$$
  • 对所有 $A \to y_1y_2\cdots y_k \in P$，置 $$\text{First}(A) \gets \text{First}(A) \cup \text{First}(y_1y_2\cdots y_k).$$

关键在于找到第一个满足 $\varepsilon \notin \text{First}(y_i)$ 的 $i$。它不能推导出 $\varepsilon$，说明从 $y_1y_2 \cdots y_k$ 推导出的句型的首字母：

• 前面的 $y_j$，不全推导为 $\varepsilon$，得到 $\bigcup_{1 \le j \le i - 1}\text{First}(y_j)$。
• 前面的 $y_j$ 全推导为 $\varepsilon$，得到 $\text{First}(y_i)$。

在 $y_i$ 的时候截断了——对于 $y_j, \forall j \ge i + 1$ 而言，它不会再对 $y_1y_2 \cdots y_k$ 的 First 集合产生贡献。

Follow 集合

对于 CFG $G = \{V_N, V_T, P, S\}$ 而言，$A \in V_N$ 的 Follow 集合的定义为 $$\text{Follow}(A) = \{a \mid S\# \overset{*}{\implies} \alpha A \beta\#, a \in \text{First}(\beta\#), \alpha, \beta \in (V_N \cup V_T)^*\}.$$

直观上来说，若 $G$ 中存在一个包含子串 $Aa$ 的句型，则 $a \in \text{Follow}(A)$；若 $G$ 中存在一个以 $A$ 结尾的句型，则 $\# \in \text{Follow}(A)$。

显然，一定有 $\# \in \text{Follow}(S)$。

步骤

• 初始化：$\text{Follow}(S) = \{\#\}$；对于其他的 $A \in V_N$，都有 $\text{Follow}(A) = \varnothing$。
• 迭代：重复以下步骤，直至所有 Follow 集合均不变。 若有 $A \to \alpha B \beta \in P, \alpha, \beta \in (V_N \cup V_T)^*, B \in V_N$，则
  • $\text{Follow}(B) \gets \text{Follow}(B) \cup \left(\text{First}(\beta) - \{\varepsilon\}\right)$。
  • 若 $\varepsilon \in \text{First}(\beta)$，则 $\text{Follow}(B) \gets \text{Follow}(B) \cup \text{Follow}(A)$。

也就是说，对于所有产生式的右部的非终结符 $B$ 而言，设 $B$ 后面接着的是 $\beta$，那么 $\text{Follow}(B)$ 肯定要包含 $\text{First}(\beta) - \{\varepsilon\}$。另外，如果 $\varepsilon \in \text{First}(\beta)$，这说明 $A$ 可以推导出以 $B$ 为后缀的句型（此时让 $\beta \overset{*}{\implies}\varepsilon$）。那么，$A$ 后面能立即跟着的终结符，也能跟在 $B$ 的后面，所以 $\text{Follow}(B)$ 还需要包含 $\text{Follow}(A)$。

预测集合 PS

对于 CFG $G = \{V_N, V_T, P, S\}$ 而言，$A \to \alpha \in P$ 的预测集合的定义为：

• 若 $\varepsilon \notin \text{First}(\alpha)$，则 $\text{PS}(A \to \alpha) = \text{First}(\alpha)$；
• 若 $\varepsilon \in \text{First}(\alpha)$，则 $\text{PS}(A \to \alpha) = (\text{First}(\alpha) - \{\varepsilon\}) \cup \text{Follow}(A)$。

直观上来说，$\text{PS}(A \to \alpha)$ 中的元素表示的是 LL(1) 分析过程中 $A$ 能和哪些终结符匹配：要么是匹配不含 $\varepsilon$ 的 $\text{First}(\alpha)$，要么是 $\alpha \overset{*}{\implies}\varepsilon$ 后匹配 $\text{Follow}(A)$。

$G$ 是 LL(1) 的，当且仅当对于 $G$ 中任意两个有相同左部的产生式 $A \to \alpha$ 和 $A \to \beta$，都满足 $\text{PS}(A \to \alpha) \cap \text{PS}(A \to \beta) = \varnothing$。

预测分析表

如果 $A \to \alpha \in P$，则在 $S$ 行 $\text{PS}(A \to \alpha)$ 列的单元中写下 $\alpha$。

表驱动 LL(1) 分析程序

• 初始时栈中仅含 $\#$。然后将文法初始符号 $S$ 入栈。
• 迭代：重复以下步骤，直至栈顶为 $\#$ 且串当前字符也为 $\#$。
  • 若栈顶为非终结符，则弹出该终结符，依据串当前字符，在预测分析表中找到相应的产生式，从上到下将产生式右部放置于栈中。
  • 若栈顶为终结符，则检查是否与串当前字符匹配。

消除左递归

消除直接左递归

对于文法 $$P \to P\alpha_1 \mid P\alpha_2 \mid \cdots \mid P\alpha_m \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_n$$ 而言，可以消除直接左递归，将产生式改写为： $$\begin{align*} P & \to \beta_1Q \mid \beta_2Q \mid \cdots \mid \beta_n Q \\ Q & \to \alpha_1Q \mid \alpha_2Q \mid \cdots \mid \alpha_mQ \mid \varepsilon \end{align*}$$

一定不要忘记最后的 $\varepsilon$。

消除间接左递归

假设所有的非终结符有排序：$A_1, A_2, \cdots, A_k$，按照以下步骤消除所有的间接左递归：

• 对于每个 $A_i$，考虑位于它前面的 $A_j(1 \le j < i)$。用 $A_i \to \alpha_1r \mid \alpha_2r \mid \cdots \mid \alpha_tr$ 来反复替代 $A_i \to A_j r$ 的产生式，其中 $A_j \to \alpha_1 \mid \alpha_2 \mid \cdots \mid \alpha_t$。
• 消除关于 $A_i$ 的直接左递归。

例：设文法 $G[S]$ 为 $$\begin{align*} S & \to PQ \mid a \\ P & \to QS \mid b \\ Q & \to SP \mid c \end{align*}$$ 试变换该文法，得到一个等价的不含左递归的文法。假设非终结符排序为 $S, P, Q$。

顺序为：$P$ 被 $S$ 替换，$Q$ 被 $S$ 替换，$Q$ 被 $P$ 替换。

第一轮对 $S$ 进行操作后（实际上未发生变化）为： $$\begin{align*} S & \to PQ \mid a \\ P & \to QS \mid b \\ Q & \to SP \mid c \end{align*}$$

第二轮对 $P$ 进行操作后（实际上未发生变化）为： $$\begin{align*} S & \to PQ \mid a \\ P & \to QS \mid b \\ Q & \to SP \mid c \end{align*}$$

第三轮对 $Q$ 进行操作后（先替换 $S$，再替换 $P$）为：

• 先替换 $S$ $$\begin{align*} S & \to PQ \mid a \\ P & \to QS \mid b \\ Q & \to PQP \mid aP \mid c \end{align*}$$
• 再替换 $P$ $$\begin{align*} S & \to PQ \mid a \\ P & \to QS \mid b \\ Q & \to QSQP \mid bQP \mid aP \mid c \end{align*}$$
• 再消除直接左递归 $$\begin{align*} S & \to PQ \mid a \\ P & \to QS \mid b \\ Q & \to bQPR \mid aPR \mid cR \\ R & \to SQPR \mid \varepsilon \end{align*}$$

提取左公因子

对于文法 $$P \to \alpha\beta_1 \mid \alpha\beta_2 \mid \cdots \mid \alpha\beta_m \mid \gamma_1 \mid \gamma_2 \mid \cdots \mid \gamma_n$$ 而言，可以提取左公因子，将产生式改写为： $$\begin{align*} P & \to \alpha Q \mid \gamma_1 \mid \gamma_2 \mid \cdots \mid \gamma_n \\ Q & \to \beta_1 \mid \beta_2 \mid \cdots \mid \beta_m \end{align*}$$

第四讲：符号表

开作用域和闭作用域

• 该点作用域为当前作用域，
• 当前作用域与包含它的程序单元所构成的作用域称为开作用域，
• 不属于开作用域的作用域称为闭作用域。

单符号表与多符号表

 1const a = 25;
 2
 3var x, y; // (1)
 4
 5procedure p;
 6
 7    var z;
 8
 9    begin
10
11        ...
12
13    end;
14
15procedure r;
16
17    var x, s; // (2)
18
19    procedure t;
20
21        var v, x, y; // (3)
22
23        begin
24
25            ...
26
27            end;
28
29    begin
30
31        ... // here
32
33        end;
34
35begin
36
37    ...
38
39end;
40

对于单符号表而言，所有的嵌套的定义域共用一个全局符号表。此时符号表中有 a、(2) 处的 x、(1) 处的 y、p、r、x、s、t。

对于多符号表而言，每个作用域都有各自的符号表，用一个栈来维护。此时符号表的组织为：

不在符号表中的作用域有：

第五讲：自底向上语法分析

短语、直接短语、句柄

直观上来说，

• 短语是指分析树中非叶节点对应的果实；
• 直接短语是指高度（注意：高度是指到子树中最远叶节点的距离，而非深度）为 $1$ 的节点对应的果实；
• 句柄是指分析树中最左侧的直接短语。

例：已知文法 $G[S]$： $$\begin{align*} S & \to AB \\ A & \to aA \mid \varepsilon \\ B & \to b \mid bB \end{align*}$$ 试指出句型 $aaAb$ 的全部短语、直接短语、句柄。

画出 $aaAb$ 的分析树如下：

graph TD



S[S] --- A1[A]

S --- B[B]

A1 --- a1[a]

A1 --- A2[A]

B --- b[b]

A2 --- a2[a]

A2 --- A3[A]



classDef yellow fill:#FF0;

class A2,B yellow

每个非叶节点对应果实对应一个短语，所以所有的短语如下： $$aaA, aA, b, aaAb$$ 高度为 $1$ 的为非叶节点（图中高亮的节点）对应直接短语： $$aA, b$$ 最左侧的直接短语为句柄： $$aA$$ 如果分析树不唯一，则短语、直接短语和句柄是所有分析树对应结果的并集。

移进-归约分析

移进-归约分析借助一个栈（称为下推栈或分析栈）来实现，拥有两种动作：移进（Shift）和归约（Reduce）。移进是指从输入序列中将一个单词符号移入分析栈，归约是指按照确定的方式对位于分析栈栈顶的短语进行归约。

移进-归约分析中的冲突

• 移进-归约冲突：不能确定下一步应该移进，还是应该归约。
• 归约-归约冲突：不能确定下一步应该对栈顶的哪一个短语进行归约。

LR 分析方法

LR 是指，Left-to-right, Rightmost derivation。在 LR 分析中，归约是对栈顶句柄进行归约。在设计 LR 分析程序时，通常是做法是在分析栈中存放分析引擎的当前状态，这样的分析栈，我们称之为状态栈。

ACTION 表和 GOTO 表

• $\text{ACTION}[k, a] = \text{s}i$，Shift：将状态 $i$ 移进栈顶，且输入串指针指向下一输入符号。
• $\text{ACTION}[k, a] = \text{r}j$，Reduce：按第 $j$ 条产生式归约。
• $\text{GOTO}[i, A] = j$：若按照 $A \to \alpha$ 进行归约，则需要将栈顶的 $|\alpha|$ 个状态弹出，此时栈顶状态为 $i$，不将其弹出，再将状态 $j$ 移进栈顶。

如果同时含有状态栈和符号栈，则需要

• $\text{ACTION}[k, a] = \text{s}i$，Shift：将输入符号也移进符号栈栈顶。
• $\text{ACTION}[k, a] = \text{r}j$，Reduce：按第 $j$ 条产生式修改符号栈栈顶的符号。
• $\text{GOTO}[i, A] = j$：此时将符号 $A$ 伴随着状态 $j$ 移进栈顶。

LR(0) 分析

LL(1) 是指，Left-to-right, Leftmost derivation with 0 token of look-ahead。

增广文法

对于 $G[S]$ 而言，构造 $G[S']$，添加 $S'\to S$ 使得开始符号不会出现在任何产生式的右部。可以证明，$G[S'] = G[S]$。

活前缀

对于 CFG $G = \{V_N, V_T, P, S\}$ 而言，若 $S \overset{*}{\underset{\text{rm}}{\implies}} \alpha A w$ 且 $A \implies \beta$，其中 $\alpha, \beta \in (V_N \cup V_T)^*, w \in V_T^*$，即 $\beta$ 是右句型 $\alpha\beta w$ 的一个相对于非终结符 $A$ 的句柄，则 $\alpha\beta$ 的任何前缀 $\gamma$ 都是文法 $G$ 的活前缀。

直观上来说，$\gamma \in (V_N \cup V_T)^*$ 是活前缀，当且仅当存在 $w \in L(G)$，使得 $\gamma$ 恰好是针对 $w$ 的分析过程中，某个时刻分析栈上的符号串（$\#$ 除外）。活前缀是某个右句型的前缀，且这个前缀的右侧不超过该句型的某个句柄。它们的关系如下：

• 活前缀已经含有该句柄的全部符号：表明该句柄对应的产生式 $A \to \alpha$ 的右部 $\alpha$ 已经出现在栈顶。
• 活前缀只含该句柄的一部分符号：表明该句柄对应的产生式 $A \to \alpha_1\alpha_2$ 的右部的子串 $\alpha_1$ 已经出现在栈顶，期待从输入串中看到可以由 $\alpha_2$ 推导出的字符串。
• 活前缀不含有该句柄的任何符号：此时期待从输入串中看到该句柄对应的产生式 $A \to \alpha$ 的右部所推导出的符号串。

LR(0) 有限状态机

项目

项目（item）是指由产生式 $A \to xyz$ 得到的形如 $A \to x.yz$ 的式子，圆点标志着已分析过的串与该产生式匹配的位置。若 $A \to \varepsilon$，则唯一的 LR(0) 项目记作 $A \to .$。

根据圆点所在的位置和圆点后是终结符、非终结符或为空，把项目分为以下几种：

• 移进项目：形如 $A \to \alpha.a\beta$，其中 $a \in V_T, \alpha, \beta \in (V_N \cup V_T)^*$。
• 待约项目：形如 $A \to \alpha.B\beta$。
• 归约项目：形如 $A \to \alpha.$。
• 接受项目：形如 $S' \to S$。

闭包

LR(0) 有限状态机的每个状态是某个 LR(0) 项目集合 $I$ 的闭包 $\text{CLOSURE}(I)$。构造闭包的算法如下：

1. 设 $J \gets I$。
2. 迭代：重复以下步骤，直至 $J$ 不再变化： 对于 $J$ 中的每个项目 $A \to \alpha.B\beta$ 和 $G$ 中的每个产生式 $B \to \gamma$，进行 $J \gets J \cup\{B \to .\gamma\}$。
3. $\text{CLOSURE}(I) = J$。

也就是对于 $I$ 中的每个项目而言，把紧邻圆点右侧的非终结符对应的所有产生式（将右部放在圆点右侧）都加进 $\text{CLOSURE}(I)$。

初态

初态为 $\text{CLOSURE}(\{S' \to S\})$。

转移函数

转移函数为 $$\text{GO}(I, X) = \text{CLOSURE}(J),$$ 其中 $I$ 为某个由 LR(0) 有限状态机的状态，$X \in V_N \cup V_T$，$J = \{A \to \alpha X.\beta \mid A \to \alpha.X\beta \in I\}$。也就是说，$J$ 中的产生式，是 $I$ 中的产生式圆点向右移动一个文法符号 $X$ 得到的。而这条转移边的边权，即为 $X$。

所有状态的集合

求出 LR(0) 有限状态机的所有状态的集合 $C$ 的算法如下：

• 初始化 $C \gets \text{CLOSURE}(\{S' \to S\})$。
• 迭代：重复以下步骤，直至 $C$ 不再变化： 对于 $C$ 中的每个项目集合 $I$ 和 $G$ 的文法符号 $X$，进行 $C \gets C \cup \text{GO}(I, X)$。

总结

使用该方法构造的 LR(0) 有限状态机可以看做是一个以 $V_N \cup V_T$ 为字母表的（省略了死状态的）DFA。该 DFA 的语言是增广文法 $G[S']$ 的所有活前缀的集合。

LR(0) 分析表

对于 ACTION 表而言：

• 若项目 $A \to \alpha.a\beta$ 属于 $I_k$，$\text{GO}(I_k, a) = I_j$，则置 $\text{ACTION}[k, a] = \text{s}j$。
• 若项目 $A \to \alpha.$ 属于 $I_k$，则对任意终结符 $a$，置 $\text{ACTION}[k, a] = \text{r}j$，其中 $A \to \alpha$ 是第 $j$ 个产生式（注意：$S'\to S$ 是第 $0$ 个产生式）。
• 若项目 $S' \to S.$ 属于 $I_k$，则置 $\text{ACTION}[k, \#] = \text{acc}$，表示接受。

对于 GOTO 表而言：

• 如果 $\text{GO}(I_k, A) = I_j$，则记 $\text{GOTO}[k, A] = j$。

终结符 $a$ 对应列为 $\text{ACTION}[k, a]$，非终结符 $A$ 对应列为 $\text{GOTO}[k, A]$。

值得注意的是，由于每次对 $\text{r}j$ 的赋值都是“对任意终结符”而言的，所以，如果出现 $\text{r}j$，则是一行全部为 $\text{r}j$。

LR(0) 文法

如果 LR(0) 分析表中各个表项均无多重定义，则称该文法为一个 LR(0) 文法。或者，从 LR(0) 有限自动机的角度来看，每个状态（项目闭包）均需要满足：

• 不同时含有移进项目和归约项目（无移进-归约冲突）
• 不含有两个或两个以上归约项目（无归约-归约冲突）

需要额外注意的是，$S'\to S.$ 是接受项目，并非归约项目，它不会和其他归约项目或移进项目产生冲突。

SLR(1) 分析

SLR(1) 是指，Simple Left-to-right, Rightmost derivation with 1 token of look-ahead。

向前查看一个符号，利用 Follow 集合，可解决部分冲突：

• 如果每个状态的所有归约项中要归约的非终结符的 Follow 集合互不相交，则可以解决归约-归约冲突。
• 如果每个状态的所有归约项的非终结符的 Follow 集合与该状态的所有移进项目要移进的符号集互不相交，则可以解决移进-归约冲突。

SLR(1) 分析表

只需要修改构造 SLR(1) 分析表中对于归约项目的构造部分：

• 若项目 $A \to \alpha.$ 属于 $I_k$，则对 $a \in \text{Follow}(A)$，置 $\text{ACTION}[k, a] = \text{r}j$，其中 $A \to \alpha$ 是第 $j$ 个产生式（注意：$S'\to S$ 是第 $0$ 个产生式）。

此时就不一定会出现整行全为 $\text{r}j$ 的情况了——$\text{r}j$ 只会出现在 $\text{Follow}(A)$ 对应的终结符列，而且一行中可以既有 $\text{r}j$ 又有 $\text{s}i$。

SLR(1) 文法

如果 SLR(1) 分析表中各个表项均无多重定义，则称该文法为一个 SLR(1) 文法。或者，从 LR(0) 有限自动机的角度来看，每个状态（项目闭包）均需要满足：

• 对该状态的任何项目 $A \to \alpha.a\beta$，不存在 $B \to \gamma.$，使得 $a \in \text{Follow}(B)$，即不存在移进-归约冲突。
• 对该状态的任意两个项目 $A \to \alpha.$ 和 $B \to \beta.$，满足 $\text{Follow}(A) \cap \text{Follow}(B) = \varnothing$，即不存在归约-归约冲突。

直观上来说，前者是说，对于一个终结符，要么归约它，要么依据这个终结符进行移进；后者是说，对于一个终结符，不存在两种对于它的规约。其实移进-归约和归约-归约并不一定冲突——它们只会在对于相同终结符有不同解释的时候才会冲突。

LR(1) 分析

LR(1) 是指，Left-to-right, Rightmost derivation with 1 token of look-ahead。

Follow 集合缩小了归约范围，但它仍然不精确：一个输入符号属于所归约非终结符的 Follow 集合，未必就是句柄后可以跟的符号。

LR(1) 有限状态机

项目

LR(1) 项目是在 LR(0) 项目的基础上增加一个终结符（称为向前搜索符）得到的，形如 $$A \to \alpha.\beta, a$$ 其中 $A \to \alpha.\beta$ 是一个 LR(0) 项目，$a \in V_T \cup \{\#\}$。向前搜索符表示产生式右端完全匹配后所允许在余留符号串中的首个终结符。

形如 $A \to \alpha., a$ 的 LR(1) 项目相当于 LR(0) 中的归约项目，但是只有当余留符号串的首个终结符是 $a$ 的时候才可以进行归约。

对于 $$\begin{align*} A & \to \alpha.\beta, a_1 \\ A & \to \alpha.\beta, a_2 \\ \vdots \\ A & \to \alpha.\beta, a_m \\ \end{align*}$$ 而言，可以简记为 $A \to \alpha.\beta, a_1/a_2/\cdots/a_m$。

闭包

LR(0) 有限状态机的每个状态是某个 LR(0) 项目集合 $I$ 的闭包 $\text{CLOSURE}(I)$。构造闭包的算法如下：

1. 设 $J \gets I$。
2. 迭代：重复以下步骤，直至 $J$ 不再变化： 对于 $J$ 中的每个项目 $[A \to \alpha.B\beta, a]$ 和 $G$ 中的每个产生式 $B \to \gamma$，进行 $J \gets J \cup\{[B \to .\gamma, b]\}$，这里 $b \in \text{First}(\beta a)$。
3. $\text{CLOSURE}(I) = J$。

也就是对于 $I$ 中的每个项目而言，把紧邻圆点右侧的非终结符对应的所有产生式（将右部放在圆点右侧）都加进 $\text{CLOSURE}(I)$，这些产生式的向前搜索符是非终结符后的句型 $\beta$ 和向前搜索符 $a$ 构成的句型 $\beta a$ 的 First 集合。

初态

初态为 $\text{CLOSURE}(\{[S' \to S, \#]\})$。

转移函数

转移函数为 $$\text{GO}(I, X) = \text{CLOSURE}(J),$$ 其中 $I$ 为某个由 LR(1) 有限状态机的状态，$X \in V_N \cup V_T$，$J = \{[A \to \alpha X.\beta, a] \mid [A \to \alpha.X\beta, a] \in I\}$。也就是说，$J$ 中的产生式，是 $I$ 中的产生式圆点向右移动一个文法符号 $X$ 得到的。而这条转移边的边权，即为 $X$。

所有状态的集合

求出 LR(1) 有限状态机的所有状态的集合 $C$ 的算法如下：

• 初始化 $C \gets \text{CLOSURE}(\{[S' \to S, \#]\})$。
• 迭代：重复以下步骤，直至 $C$ 不再变化： 对于 $C$ 中的每个项目集合 $I$ 和 $G$ 的文法符号 $X$，进行 $C \gets C \cup \text{GO}(I, X)$。

LR(1) 分析表

对于 ACTION 表而言：

• 若项目 $[A \to \alpha.a\beta, b]$ 属于 $I_k$，$\text{GO}(I_k, a) = I_j$，则置 $\text{ACTION}[k, a] = \text{s}j$。
• 若项目 $[A \to \alpha., b]$ 属于 $I_k$，则置 $\text{ACTION}[k, b] = \text{r}j$，其中 $A \to \alpha$ 是第 $j$ 个产生式（注意：$S'\to S$ 是第 $0$ 个产生式）。
• 若项目 $[S' \to S., \#]$ 属于 $I_k$，则置 $\text{ACTION}[k, \#] = \text{acc}$，表示接受。

对于 GOTO 表而言：

• 如果 $\text{GO}(I_k, A) = I_j$，则记 $\text{GOTO}[k, A] = j$。

LR(1) 文法

如果 LR(1) 分析表中各个表项均无多重定义，则称该文法为一个 LR(1) 文法。或者，从 LR(1) 有限自动机的角度来看，每个状态（项目闭包）均需要满足：

• 对于每个状态，不能同时含有项目 $[A \to \alpha.a\beta, b]$ 和项目 $[B \to \gamma., a]$，即不存在移进-归约冲突；
• 对于每个状态，不能同时含有项目 $[A \to \alpha., a]$ 和项目 $[B \to \beta., a]$，即不存在归约-归约冲突。

LALR(1) 分析

LALR(1) 是指，Look-Ahead, Left-to-right, Rightmost derivation with 1 token of look-ahead。

芯和同芯状态

对于 LR(1) 项目 $[A \to \alpha.a\beta, b]$ 而言，把 $A \to \alpha.a\beta$ 称为它的芯。如果对于两个状态，它们各自所有项目的芯分别构成的集合是相同的，那么就称这两个状态为同芯状态。

LALR(1) 有限状态机

对于 LR(1) 有限状态机中的两个同芯状态，由 GO 函数得到的针对任何符号的状态仍然是同芯的，因此，我们可以对 GO 函数进行修改。

合并 LR(1) 有限状态机中的同芯状态，结合修改后的 GO 函数，即得 LALR(1) 有限状态机。

构造 LALR(1) 有限状态机并不需要先构造出 LR(1) 有限状态机，因为可以边构造边合并状态。

LALR(1) 分析表

LALR(1) 分析表的构造过程与 LR(1) 分析表的构造过程一样。

LALR(1) 文法

一个 LR(1) 文法，如果将其 LR(1) 有限状态机的同芯状态合并后所得到的 LALR(1) 有限状态机中的全部状态无归约-归约冲突，则该文法是一个 LALR(1) 文法。

只需要检查归约-归约冲突的原因是，合并同芯状态不会产生新的移进-归约冲突（因为移进项目和归约项目一定不同芯——它们圆点的位置都不同），但会产生新的归约-归约冲突。

二义文法的 LR 分析

可以手动规定一些符号的优先级和结合性，使得文法分析可以进行下去。具体而言，可以手动规定某些移进-归约冲突时应该是移进还是归约，手动规定某些归约-归约冲突时应该按照哪个产生式进行归约。

LR 分析中的错误处理

将分析表中的每个空白项赋值为 $\text{e}j$，表示报第 $j$ 种错误，运行第 $j$ 种错误处理程序。

第六讲：语法制导的语义计算基础

属性文法

在文法 $G[S]$ 的基础上，可以为文法符号关联有特定意义的属性，并为产生式关联对应的语义动作，这样的拓展后的文法称为属性文法。 $$\begin{align*} S & \to ABC & \{\text{if } (A.\text{num} = B.\text{num}) \text{ and } (B.\text{num} = C.\text{num}) \\ & & \text{then } \text{print}(\text{``Accepted!''}) \\ & & \text{else } \text{print}(\text{``Refused!''})\} \\ A & \to A_1 a & \{A.\text{num} := A_1.\text{num} + 1\} \\ A & \to a & \{A.\text{num} := 1\} \\ B & \to B_1b & \{B.\text{num} := B_1.\text{num} + 1\} \\ B & \to b & \{B.\text{num} := 1\} \\ C & \to C_1 c & \{C.\text{num} := C_1.\text{num} + 1\} \\ C & \to c & \{C.\text{num} := 1\} \\ \end{align*}$$ 形如 $b := f(c_1, c_2, \cdots, c_k)$ 的称为语义动作，其中 $f$ 是语义函数。语义动作也可以只含一个函数，例如 $f(c_1, c_2, \cdots, c_k)$。

形如 $X.a := Y.b$ 的语义动作称为复写规则。

综合属性和继承属性

对于关联于产生式 $A \to \alpha B\beta$ 的语义动作 $X.v := f(\cdots)$ 而言：

• 若 $X$ 是 $A$，则称 $A.v$ 为综合属性，
• 若 $X$ 是 $B$，则称 $B.v$ 为继承属性。

从分析树的角度来看，综合属性由子节点向父节点转移；继承属性由父节点向子节点转移。

在遍历分析树进行语义计算的时候，通常可以构造一个依赖图（依赖于别人结果的属性，指向被依赖的属性），如果这个图是一个 DAG（Directed Acyclic Graph，有向无圈图），则可以按照任意一个拓扑排序的顺序进行计算。

S-属性文法

仅包含综合属性的属性文法称为 S-属性文法。

基于 S-属性文法的语义计算

基于 S-属性文法的语义计算是简单的，只需要每次对符号进行归约的时候，同时计算综合属性的值即可。

L-属性文法

一个属性文法称为 L-属性文法，当且仅当其中每一个产生式 $A \to X_1X_2 \cdots X_n$，其每个语义动作所涉及的属性或者是综合属性，或者是某个 $X_i(1 \le i \le n)$ 的继承属性，而这个继承属性只能依赖于：

1. $X_i$ 左边的符号 $X_1, X_2, \cdots, X_{i-1}$ 的属性；
2. $A$ 的继承属性。

可以看出，S-属性文法是一种特殊的 L-属性文法。直观上来说，属性信息按照以下方式进行传递：

基于 L-属性文法的语义计算

 1void visit(Node u) {
 2
 3    for (Node v : children(u)) { // 从左到右遍历 u 的每个子节点
 4
 5        v.calculate_INHERITED_attribute(); // 计算 v 的继承属性
 6
 7        visit(v);
 8
 9    }
10
11    u.calculate_SYNTHESIZED_attribute(); // 计算 u 的综合属性
12
13}
14

经过一遍深度优先搜索即可得到所有的综合属性和继承属性的值。

翻译模式

翻译模式在形式上类似于属性文法，但是它允许 $\{\cdots\}$ 括起来的语义动作出现在产生式右端的任何位置，以此显式地表达属性计算的次序。

S-翻译模式

S-翻译模式仅涉及综合属性，通常将语义动作集合置于相应产生式的末尾。

基于 S-翻译模式的语义计算

假设语义栈由向量 $v$ 表示，归约前栈顶位置为 $\text{top}$，栈上第 $i$ 个位置所对应符号的综合属性值 $x$ 用 $v[i].x$ 表示。为了明确表达语义栈上的操作，将 $$A \to XYZ \quad \{A.a:= f(X.x, Y.y, Z.z)\}$$ 变换为 $$A \to XYZ \quad \{v[\text{top} - 2].a := f(v[\text{top} - 2].x, v[\text{top} - 1].y, v[\text{top}].z)\}$$

注意：归约时，产生式右端从左到右在栈中是按照自顶到底的顺序排列的。

L-翻译模式

L-翻译模式既可以包含综合属性，又可以包含继承属性，但需要满足：

1. 产生式右部某个符号的继承属性的计算必须位于该符号之前，且语义动作不访问位于该语义动作右侧的符号的属性，仅依赖于该语义动作左侧的符号的属性（如果依赖于产生式左部的符号，则只能依赖于它的继承属性）。
2. 产生式左部非终结符的综合属性的计算只能在所用到的属性都已计算出来之后进行，通常将相应的语义动作置于产生式的末尾。

直观上来说，这是为了保证 DFS 遍历语法分析树的正确性。

递归下降语义计算程序

将 ParseX( ) 修改一下，以 $X$ 的继承属性作为形式参数，综合属性作为返回值（不妨设 $X$ 仅有一个综合属性）。

假设 $B.\text{val}, S.\text{val}$ 是综合属性，$B.f, S.f$ 是继承属性。则 $$\begin{align*} S & \to \{B.f := S.f\} \quad B \quad \{S_1.f := S.f + 1\} \quad S_1 \quad \{S.\text{val} := B.\text{val} + S_1.\text{val}\}\\ S & \to \varepsilon \end{align*}$$ 对应的语义计算子函数可以设计为：

 1float ParseS(int f) {
 2
 3    Sv;
 4
 5    if (lookahead == '0' || lookahead == '1') {
 6
 7        Bf = f;
 8
 9        Bv = ParseB(Bf);
10
11        S1f = f + 1;
12
13        S1v = ParseS(S1f);
14
15        Sv = Bv + S1v;
16
17    } else if (lookahead == '#') {
18
19        Sv = 0;
20
21    } else {
22
23        printf("Syntex error!");
24
25    }
26
27    return Sv;
28
29}
30

消除基础文法左递归

假设有如下翻译模式： $$\begin{align*} A & \to A_1 Y & \{A.a := g(A_1.a, Y.y)\} \\ A & \to X & \{A.a := f(X.x)\} \end{align*}$$ 消去关于 $A$ 的左递归，得： $$\begin{align*} A & \to XR \\ R & \to YR \mid \varepsilon \end{align*}$$ 再考虑语义动作，可以给 $R$ 一个综合属性 $R.s$ 和一个继承属性 $R.i$，翻译模式可以变换为 $$\begin{align*} A & \to X \quad \{R.i := f(X.x)\} \quad R \quad \{A.a := R.s\} \\ R & \to Y \quad \{R_1.i := g(R.i, Y.y)\} \quad R_1 \quad \{R.s := R_1.s\} \\ R & \to \varepsilon \quad \{R.s := R.i\} \end{align*}$$

基于 L-翻译模式的自底向上语义计算

如果语义动作集中仅包含综合属性的访问或赋值，则只需要处理好嵌入在产生式中间的语义动作。对此，一种处理方法是：引入新的非终结符 $N$ 和产生式 $N \to \varepsilon$；把嵌入在产生式中间的语义动作集用 $N$ 代替，并把该动作集放在产生式 $N \to \varepsilon$ 后面。

例如，对于下列翻译模式： $$\begin{align*} E & \to TR \\ R & \to +T \quad \{\text{print}(\text{``+''})\} \quad R_1 \\ R & \to -T \quad \{\text{print}(\text{``-''})\} \quad R_1 \\ R & \to \varepsilon \\ T & \to \underline{\text{num}} \quad \{\text{print}(\underline{\text{num}}.\text{val})\}\\ \end{align*}$$ 可以变换为 $$\begin{align*} E & \to TR \\ R & \to +TMR_1 \\ R & \to -TNR_1 \\ R & \to \varepsilon \\ T & \to \underline{\text{num}} \quad \{\text{print}(\underline{\text{num}}.\text{val})\}\\ M & \to \varepsilon \quad \{\text{print}(\text{``+''})\} \\ N & \to \varepsilon \quad \{\text{print}(\text{``-''})\} \end{align*}$$

然而，如果语义动作集中有继承属性的访问或赋值，情况则会复杂一些。由于在自底向上的语义计算过程中，只有综合属性会出现在语义栈上，所以继承属性的访问最终要落实到对某个综合属性值的访问。

例如，对于下列翻译模式： $$S \to aA \quad \{C.i := f(A.s)\} \quad C$$ 其中 $A.s$ 是 $A$ 的综合属性，$C.i$ 是 $C$ 的继承属性。此时 $A.s$ 固然在语义栈中——但是 $f(A.s)$ 并不在。所以需要引入新的非终结符 $M$，将以上翻译模式改写为： $$\begin{align*} S & \to aA \quad \{M.i: = A.s\} \quad M \quad \{C.i := M.s\} \quad C \\ M & \to \varepsilon \quad \{M.s = f(M.i)\} \end{align*}$$ 可以把 $M$ 看做成一个函数，它负责计算 $M.s \gets f(M.i)$，将一个继承属性转换为了综合属性，并存放在语义栈上。

但是，此时还需要再解决一个问题：避免不一致访问。考虑以下翻译模式： $$\begin{align*} S & \to aA \quad \{C.i := A.s\} \quad C \\ S & \to bAB \quad \{C.i := A.s\} \quad C \\ C & \to c \quad \{C.s := g(C.i)\} \end{align*}$$

这里出现的问题是，当使用 $C \to c$ 进行归约的时候：

• $C.i$ 要么位于次栈顶，这是从第一个产生式得来的，$C$ 位于 $\text{top}$，$A$ 位于 $\text{top} - 1$。此时 $A.s$ 是 $v[\text{top} - 1].s$，位于次栈顶。
• $C.i$ 要么位于次次栈顶，这是从第二个产生式得来的，$C$ 位于 $\text{top}$，$B$ 位于 $\text{top} - 1$，$A$ 位于 $\text{top} - 2$。此时 $A.s$ 是 $v[\text{top} - 2].s$，位于次次栈顶。

这样就不知道在显式写出语义栈访问的时候，最后一句产生式对应的语义动作究竟是 $v[\text{top}].s := g(v[\text{top} - 1].s)$ 还是 $v[\text{top}].s := g(v[\text{top} - 2].s)$ 了。

注意：这里赋值式的左式为 $v[\text{top}].s$，是因为第三个产生式中归约前的 $c$ 位于 $\text{top}$，则 $C$ 位于 $\text{top}$。如果是 $C \to \varepsilon$，则归约后 $C$ 应位于 $\text{top} + 1$，需要写成 $v[\text{top} + 1].s := \cdots$。

一种可行的做法是引入新的非终结符 $M$，将以上翻译模式改写为 $$\begin{align*} S & \to aA \quad \{C.i := A.s\} \quad C \\ S & \to bAB \quad \{M.i := A.s\} \quad M \quad \{C.i := M.s\} \quad C \\ C & \to c \quad \{C.s := g(C.i)\} \\ M & \to \varepsilon \quad \{M.s := M.i\} \end{align*}$$

这样就将 $C.i$ 的位置统一于 $\text{top} - 1$ 处。

第七讲：静态语义分析与中间代码生成

静态语义分析

静态语义分析最基本的工作是检查程序结构的一致性或完整性，例如：

• 控制流检查（例如 break 语句必须在循环中等）
• 唯一性检查（例如标识符、枚举类型的元素是唯一的等）
• 名字的上下文相关性检查（例如变量在使用前必须经过声明、在外部不能访问私有变量等）
• 类型检查（例如 void f(int *a); 的函数在调用时不允许 f(10); 等）

类型检查

{ 和 } 需要加引号以区别于元符号： $$S \to \text{`\{'} \quad \{S_1.\text{inloop}:=S.\text{inloop}\} \quad S_1 \quad \text{`\}'} \quad \{S.\text{type} := S_1.\text{type}\}$$

中间代码生成

综合属性 $D.\text{width}$ 和 $P.\text{width}$ 表示所申明变量所占的字节数。继承属性 $P.\text{offset}$ 和 $D.\text{offset}$ 表示相应程序单元起始位置在全局空间中的偏移量。

综合属性 $\underline{\text{id}}.\text{place}$ 表示相应的名字对应的存储位置，这更像是“引用”，而不是指针或地址。综合属性 $E.\text{code}$ 表示对 $E$ 进行求值的 TAC 语句序列。

语义函数 $\text{gen}$ 的结果是生成一条 TAC 语句。语义函数 $\text{newtemp}$ 的作用是在符号表中新建一个从未使用过的名字，并返回该位置的存储位置。

$\mid\mid$ 是 TAC 语句序列之间的链接运算。

$$E \to R \quad \{E.\text{place} := \text{newtemp}; E.\text{code}:=R.\text{code} \mid\mid \text{gen}(E.\text{place} \;\text{`}:=\text{'}\;R.\text{base}\;\text{`}[\text{'}\;R.\text{offs}\;\text{`}]\text{'})\}$$

继承属性 $E.\text{true}$ 和 $E.\text{false}$ 分别代表 $E$ 为真核假时控制要转移到的程序位置，即标号。

拉链

至此，已经有 L-翻译模式可以将布尔表达式和控制语句翻译为 TAC 语句序列；现在，介绍一种可以处理同样问题的 S-翻译模式。这种翻译模式用到以下树型和语义函数：

• 综合属性 $E.\text{truelist}$（真链）：链表中的元素表示一系列跳转语句的地址，这些跳转语句的目标语句标号是体现 $E$ 为真的标号。
• 综合属性 $E.\text{falselist}$（假链）：链表中的元素表示一系列跳转语句的地址，这些跳转语句的目标语句标号是体现 $E$ 为假的标号。
• 综合属性 $S.\text{nextlist}$（next 链）：链表中的元素表示一系列跳转语句的地址，这些跳转语句的目标语句标号是在执行序列中紧跟在 $S$ 之后的下一条 TAC 语句的地址。
• 综合属性 $N.\text{nextlist}$：仅含一个语句地址的链表，对应于处理到 $N$ 时的跳转语句。
• 综合属性 $S.\text{breaklist}$（break 链）：链表中的元素表示一系列跳转语句的地址，这些跳转语句的目标语句标号是跳出直接包围 $S$ 的 while 语句后的下一条 TAC 语句的地址。
• 综合属性 $M.\text{gotostm}$ 中记录处理到 $M$ 时下一条待生成语句的标号。
• 语义函数 $\text{makelist}(i)$，创建只有一个节点 $i$ 的表，对应于一条跳转语句的地址。
• 语义函数 $\text{merge}(p_1, p_2)$：链接两个链表 $p_1, p_2$，返回结果链表。
• 语义函数 $\text{backpatch}(p, i)$：将链表 $p$ 中每个元素所指向的跳转语句的标号置为 $i$。
• 语义函数 $\text{nextstm}$：返回下一条 TAC 语句的地址。
• 语义函数 $\text{emit}(\cdots)$：输出一条 TAC 语句，并使 $\text{nextstm}$ 加 $1$。