写在编译原理考试前

明天还要考最后一门编译原理，正好有一个周末可以准备。今天看了两遍「龙书」，昨天打了一天的《茶杯头》，这个周末恐怕是和龙过不去了：

Chomsky 文法分类体系

从抽象语法树的角度来看：
- 短语（Phrase）是某个子树的叶子节点序列。
- 直接短语（Simple Phrase）是不包含其它子树的子树的叶子节点序列。
- 句柄（Handle, i.e. Left-Most Simple Phrase）是最左直接短语。
句柄 $\in$ 直接短语 $\in$ 短语。

串首终结符：串首第一个符号，并且是终结符。
给定一个文法符号串 $\alpha$，$\alpha$ 的串首终结符集 $FIRST(\alpha)$ 被定义为可以从 $\alpha$ 推导出的所有串首终结符构成的集合。如果 $\alpha \Rightarrow ^{*} \epsilon$，那么 $\epsilon$ 也在 $FIRST(\alpha)$ 中。
- $\epsilon$ 的串首终结符集为空集，即 $FIRST(\epsilon) = \{\}$。
- 如果 $\epsilon \notin FIRST(\alpha)$，那么 $FIRST(\alpha \beta) = FIRST(\alpha)$。
- 如果 $\epsilon \in FIRST(\alpha)$，那么 $FIRST(\alpha \beta) = FIRST(\alpha) \cup FIRST(\beta)$。

非终结符 $A$ 的后续符号集 $FOLLOW(A)$：可能在某个句型中紧跟在 $A$ 后边的终结符 $a$ 的集合。如果 $A$ 是某个句型的最右符号，则将结束符「$」添加到 $FOLLOW(A)$ 中。

产生式 $A \rightarrow \beta$ 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 $SELECT(A \rightarrow \beta)$。
- 条件 $SELECT(A \rightarrow \alpha \beta) = \{ \alpha \}$ 满足。
- 条件 $SELECT(A \rightarrow \epsilon) = FOLLOW(A)$ 满足。
在 $LL(1)$ 文法中，产生式 $A \rightarrow a$ 的可选集：
- 如果 $\epsilon \notin FIRST(\alpha)$，那么 $SELECT(A \rightarrow \alpha) = FIRST(\alpha)$。
- 如果 $\epsilon \in FIRST(\alpha)$，那么 $SELECT(A \rightarrow \alpha) = \left( FIRST(\alpha) - \{ \epsilon \} \right) \cup FOLLOW(A)$。

一个文法 $G$ 是 $LL(1)$ 的，当且仅当 $G$ 的任意两个不同的产生式 $A \rightarrow \alpha \mid \beta$ 满足下面的条件：

如果 $\alpha$ 和 $\beta$ 均不能推导出 $\epsilon$，则 $FIRST(\alpha) \cap FIRST(\beta) = \phi$，这样可以保证 $SELECT(A \rightarrow \alpha) \cap SELECT(A \rightarrow \beta) = \phi$。
$\alpha$ 和 $\beta$ 至多有一个能推导出 $\epsilon$，否则 $FOLLOW(A) \in \left( SELECT(A \rightarrow \alpha) \cap SELECT(A \rightarrow \beta) \right)$，导致 $SELECT(A \rightarrow \alpha)$ 和 $SELECT(A \rightarrow \beta)$ 相交。
如果 $\beta \Rightarrow ^{*} \epsilon$（此时 $FOLLOW(A) \in SELECT(A \rightarrow \beta)$），则 $FIRST(\alpha) \cap FOLLOW(A) = \phi$；如果 $\alpha \Rightarrow ^{*} \epsilon$（此时 $FOLLOW(A) \in SELECT(A \rightarrow \alpha)$），则 $FIRST(\beta) \cap FOLLOW(A) = \phi$。

递归的预测分析法：在递归下降分析中，编写每一个非终结符对应的过程，根据预测分析表进行产生式的选择。

非递归的预测分析法：不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析。

例子：$S \rightarrow bBB$
- $S \rightarrow \cdot b B B$ 为移进项目。
- $S \rightarrow b \cdot BB$ 为待约项目。
- $S \rightarrow bB \cdot B$ 为待约项目。
- $S \rightarrow bBB \cdot$ 为归约项目。
待约项目可能具有等价项目，等价项目可形成项集的闭包。

构造 $G^{'}$ 的规范 $LR(0)$ 项集族 $C = { I_0, I_1, ..., I_n}$。
令 $I_i$ 对应状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定：
- 如果 $A \rightarrow \alpha \cdot a \beta$ 且 $GOTO(I_i, a) = I_j$，则 $ACTION[i, a] = sj$。
- 如果 $A \rightarrow \alpha \cdot B \beta$ 且 $GOTO(I_i, B) = I_j$，则 $GOTO[i, B] = sj$。
- 如果 $A \rightarrow \alpha \cdot \in I_j$ 且 $A \ne S^{'}$，则对于所有 $a \in V_T \cup \{ \$ \}$，有 $ACTION[i, a] = rj$（$j$ 是产生式 $A \rightarrow \alpha$ 的编号）。
- 如果 $S^{'} \rightarrow S \cdot \in I_i$，则 $ACTION[i, \$] = acc$。
没有定义的所有条目都设置为 $error$。

构造 $G^{'}$ 的规范 $LR(0)$ 项集族 $C = { I_0, I_1, ..., I_n}$。
令 $I_i$ 对应状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定：
- 如果 $A \rightarrow \alpha \cdot a \beta$ 且 $GOTO(I_i, a) = I_j$，则 $ACTION[i, a] = sj$。
- 如果 $A \rightarrow \alpha \cdot B \beta$ 且 $GOTO(I_i, B) = I_j$，则 $GOTO[i, B] = sj$。
- ☑️ 如果 $A \rightarrow \alpha \cdot \in I_j$ 且 $A \ne S^{'}$，则对于所有 $a \in FOLLOW(A)$，有 $ACTION[i, a] = rj$（$j$ 是产生式 $A \rightarrow \alpha$ 的编号）。
- 如果 $S^{'} \rightarrow S \cdot \in I_i$，则 $ACTION[i, \$] = acc$。
没有定义的所有条目都设置为 $error$。

构造 $G^{'}$ 的规范 $LR(1)$ 项集族 $C = { I_0, I_1, ..., I_n}$。
令 $I_i$ 对应状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定：
- 如果 $[A \rightarrow \alpha \cdot a \beta, b] \in I_i$ 且 $GOTO(I_i, a) = I_j$，则 $ACTION[i, a] = sj$。
- 如果 $[A \rightarrow \alpha \cdot B \beta, b] \in I_i$ 且 $GOTO(I_i, B) = I_j$，则 $GOTO[i, B] = sj$。
- ☑️ 如果 $[A \rightarrow \alpha \cdot, a] \in I_i$ 且 $A \ne S^{'}$，则有 $ACTION[i, a] = rj$（$j$ 是产生式 $A \rightarrow \alpha$ 的编号）。
- 如果 [$S^{'} \rightarrow S \cdot, \$ ]\in I_i$，则 $ACTION[i, \$] = acc$。
没有定义的所有条目都设置为 $error$。