《编译原理第三版》（张素琴）第四章学习札记

何为确定的自顶向下分析方法？

确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。

如何理解 $\text{FIRST()}$？

设 $G = (V_T, V_N, P, S)$ 是上下文无关文法。

\[ \text{FIRST}(\alpha) = \{a|\alpha \stackrel{*}{\Rightarrow} \alpha \beta, \quad a \in V_T, \alpha, \beta \in V^*\} \]

若 $\alpha \stackrel{*}{\Rightarrow} \epsilon$，则规定 $\epsilon \in \text{FIRST}(\alpha)$。称 $\text{FIRST}(\alpha)$ 为 $\alpha$ 的开始符号集或首符号集。

如何理解 $\text{FOLLOW()}$？

设 $G = (V_T, V_N, P, S)$ 是上下文无关文法，$A \in V_N$，$S$ 是开始符号。

\[ \text{FOLLOW}(A) = \{a|S \stackrel{*}{\Rightarrow} \mu A \beta \; 且 \; a \in V_T, a \in \text{FIRST}(\beta), \mu \in V_T^*, \beta \in V^{+}\} \]

若 $S \stackrel{*}{\Rightarrow} \mu A \beta$，且 $\beta \stackrel{*}{\Rightarrow} \epsilon$，则 $＃ \in \text{FOLLOW}(A)$。

\[ \text{FOLLOW}(A) = \{a|S \stackrel{*}{\Rightarrow} \cdots Aa \cdots, \; a \in V_T\} \]

若有 $S \stackrel{*}{\Rightarrow} \cdots A$，则规定 $＃ \in \text{FOLLOW}(A)$。

这里用 $＃$ 作为输入串的结束符，也称为输入串符号。

因此当文法中含有形如

\[ \begin{split} A \rightarrow \alpha \\ A \rightarrow \beta \end{split} \]

的产生式时，其中 $A \in V_N, \alpha、\beta \in V^*$，若 $\alpha$ 和 $\beta$ 不能同时推导出空，假定 $\alpha \stackrel{*}{\nRightarrow} \epsilon$ $, \beta \stackrel{*}{\Rightarrow} \epsilon$，则当 $\text{FIRST}(\alpha)$ $\cap$ $(\text{FIRST}(\beta)$ $\cup$ $\text{FOLLOW}(A)) = \varnothing$ 时，对于非终结符 $A$ 的替换仍可唯一地确定候选。

如何理解 $\text{SELECT()}$？

给定上下文无关文法的产生式 $A \rightarrow \alpha$ $, $ $A \in V_N, \alpha \in V^*$，

若 $\alpha \stackrel{*}{\nRightarrow} \varepsilon$，则 $\text{SELECT}(A \rightarrow \alpha)$ $=$ $\text{FIRST}(\alpha)$。
若 $\alpha \stackrel{*}{\Rightarrow} \varepsilon$，则 $\text{SELECT}(A \rightarrow \alpha)$ $=$ $(\text{FIRST}(\alpha) - \{\varepsilon\})$ $\cup$ $\text{FOLLOW}(A)$。

何为 $\text{LL}(1)$ 文法？

一个上下文无关文法是 $\text{LL}(1)$ 的充分必要条件是,

对每个非终结符 $A$ 的两个不同产生式，$A \rightarrow \alpha$ $,$ $A \rightarrow \beta$，满足

\[ \text{SELECT}(A \rightarrow \alpha) \cap \text{SELECT}(A \rightarrow \beta) = \varnothing \]

其中 $\alpha、\beta$ 不同时能 $\stackrel{*}{\Rightarrow} \epsilon$。

$\text{LL}(1)$ 的含义是：第 1 个 $\text{L}$ 表明自顶向下分析是从左向右扫描输入串，第 2 个 $\text{L}$ 表明分析过程中将用最左推导，1 表明只需要向右看一个符号便可决定如何推导，即选择哪个产生式（规则）进行推导。

如何判别某文法是否是 $\text{LL}(1)$ 文法？

首先计算 $\text{FIRST}$、$\text{FOLLOW}$、$\text{SELECT}$ 集合，然后根据定义判别文法是否是 $\text{LL}(1)$ 文法。

如何计算一个文法符号 $X \in V$ 的 $\text{FIRST}$ 集 $\text{FIRST}(X)$？

① 若 $X \in V_T$，则 $\text{FIRST}(X) = \{X\}$。
② 若 $X \in V_N$，且有产生式 $X \rightarrow a \cdots$ $,$ $a \in V_T$，则 $a \in \text{FIRST}(X)$。
③ 若 $X \in V_N$，$X \rightarrow \varepsilon$，则 $\varepsilon \in \text{FIRST}(X)$。
④ 若 $X, Y_1, Y_2,$ $\cdots$ $, Y_n \in V_N$，而有产生式 $X \rightarrow Y_1Y_2 \cdots Y_n$。当 $Y_1, Y_2, \cdots, Y_{i - 1}$ $\stackrel{*}{\Rightarrow} \varepsilon$ 时（其中 $1 \leqslant i \leqslant n$），则 $\text{FIRST}(Y_1) - \{\varepsilon\},$ $\text{FIRST}(Y_2) - \{\varepsilon\},$ $\cdots$ $, \text{FIRST}(Y_{i - 1}) - \{\varepsilon\},$ $\text{FIRST}(Y_i)$ 都包含在 $\text{FIRST}(X)$ 中，即

\[ \text{FIRST}(X) = (\text{FIRST}(Y_1) \cup \text{FIRST}(Y_2) \cdots \cup \text{FIRST}(Y_i)) - \{\varepsilon\} \]

⑤ 当 ④ 中所有 $Y_i \stackrel{*}{\Rightarrow} \varepsilon$ $,$ $(i = 1, 2, \cdots, n)$，则

\[ \text{FIRST}(X) = (\text{FIRST}(Y_1) \cup \text{FIRST}(Y_2) \cdots \cup \text{FIRST}(Y_n)) \cup \{\varepsilon\} \]

反复使用上述 ②~⑤ 步，直到每个符号的 $\text{FIRST}$ 集合不再增大为止。

如何计算一个符号串的 $\text{FIRST}$ 集合？

若符号串 $\alpha \in V^*$ $,$ $\alpha = X_1 X_2 \cdots X_n$，当 $X_1$ 不能 $\stackrel{*}{\Rightarrow} \varepsilon$，则置 $\text{FIRST}(\alpha) = \text{FIRST}(X_1)$。

若对任何 $j(1 \leqslant j \leqslant i - 1,$ $2 \leqslant i \leqslant n)$ $,$ $\varepsilon \in \text{FIRST}(X_j)$ $,$ $\varepsilon \notin \text{FIRST}(X_i)$，则

\[ \text{FIRST}(\alpha) = \bigcup_{j = 1}^{i - 1}(\text{FIRST}(X_j) - \{\varepsilon\}) \cup \text{FIRST}(X_i) \]

当对任何 $j(1 \leqslant j \leqslant n)$，$\text{FIRST}(X_j)$ 都含有 $\varepsilon$ 时，则

\[ \text{FIRST}(\alpha) = \bigcup_{j = 1}^{n}(\text{FIRST}(X_j) - \{\varepsilon\}) \cup \{\varepsilon\} \]

按：这里最后一个公式书上的写法似乎有点问题。

如何计算 $\text{FOLLOW}$ 集？

对文法中的每一个 $A \in V_N$，根据定义计算 $\text{FOLLOW}(A)$。

① 设 $S$ 为文法的开始符号，把 $\{＃\}$ 加入 $\text{FOLLOW}(S)$ 中（这里＃为句子括号）。

按：＃似为句子结束符号。

② 若 $A \rightarrow \alpha B \beta$ 是一个产生式，则把 $\text{FIRST}(\beta)$ 的非空元素加入 $\text{FOLLOW}(B)$ 中。
如果 $\beta \stackrel{*}{\Rightarrow} \varepsilon$，则把 $\text{FOLLOW}(A)$ 也加入 $\text{FOLLOW}(B)$ 中，因为当有形如

\[ \begin{split} D &\rightarrow \alpha_{1} A \beta_{1} \\ A &\rightarrow \alpha B \beta \end{split} \]

的产生式时，$A, B, D \in V_N$，$\alpha, \alpha_{1}, \beta, \beta_{1} \in V^*$，在推导过程中可能出现如下的句型序列：

\[ S \stackrel{*}{\Rightarrow} \cdots \alpha_{1} A \beta_{1} \cdots \Rightarrow \alpha_{1} \alpha B \beta \beta{1} \cdots \Rightarrow \cdots \alpha_{1} \alpha B \beta_{1} \cdots \]

因此，有 $\text{FOLLOW}(A)$ $\subseteq$ $\text{FOLLOW}(B)$。

③ 反复使用 ② 直到每个非终结符的 $\text{FOLLOW}$ 集不再增大为止。

如何计算某一文法中的每一个产生式的 $\text{SELECT}$ 集？

直接根据定义来判断：

给定上下文无关文法的产生式 $A \rightarrow \alpha$ $, $ $A \in V_N, \alpha \in V^*$，

若 $\alpha \stackrel{*}{\nRightarrow} \varepsilon$，则 $\text{SELECT}(A \rightarrow \alpha)$ $=$ $\text{FIRST}(\alpha)$。
若 $\alpha \stackrel{*}{\Rightarrow} \varepsilon$，则 $\text{SELECT}(A \rightarrow \alpha)$ $=$ $(\text{FIRST}(\alpha) - \{\varepsilon\})$ $\cup$ $\text{FOLLOW}(A)$。