1. 分析引言¶
1.1. 引言¶
分析（parsing）： 判断对于某个 CFG \(G\) ，串 \(x \in \Sigma^*\) 是否属于语言 \(L(G)\) 。
回顾（review）：到目前为止我们都做了什么
考虑如下 CFG \(G\) ：
\(ba\) 在 \(L(G)\) 中吗？运行时间呢？
如何确定一个串是否属于 \(L(G)\) ？
注意，对于这个 \(G\) ， \(ba\) 不在 \(L(G)\) 中！
尝试所有可能的推导，但不知道何时停止。 这会永远运行下去！
去掉 lambda 规则后的同一个文法：
从上面的文法 \(G\) 中去掉 \(\lambda\) 规则，再去掉单位产生式和 无用产生式。新的文法 \(G'\) 为：
\(ba\) 在 \(L(G)\) 中吗？运行时间呢？
备注
之前我说这是线性时间。
尝试所有可能的推导，最多有 \(|w|\) 轮。 注意这不是线性时间，它需要很长时间。 实际时间为 \(|w|*p\) ，其中 \(p\) 是任意变量的规则数上限。
备注
给定表示 C 程序设计语言的文法， 我们会想知道 C 程序在语法上是否正确。 这是编译器中的一个阶段。
我们希望它运行得越快越好，不想坐在那里 等待你的程序永远编译下去。
我们将研究编写编译器时使用的分析方法。 我们想知道下一步应该应用哪条规则。
考虑串 \(baa\) 。 我们希望只尝试能给出推导的那些规则，并忽略错误的路径。这样会很快！ \(S \Rightarrow Aa \Rightarrow Baa \Rightarrow baa\)
1.1.1. 自顶向下分析器（Top-down Parser）：¶
从 \(S\) 开始，尝试推导出该串。
\(S \rightarrow aS \mid b\)
例子：LL 分析器、递归下降（Recursive Descent）
自底向上分析器（Bottom-up Parser）：
从串开始，反向工作，尝试推导出 \(S\) 。
例子：移进-归约（Shift-reduce）、算符优先（Operator-Precedence）、LR 分析器
当文法含有 \(\lambda\) 规则时， 计算分析表可能很困难。 在上面的例子中， \(A\) 可能消失 （由于 \(A \rightarrow \lambda\) ）， 所以当 \(S\) 在栈上时，如果向前看符号是 "a" 或 "c" ， 则可以用 \(Ac\) 替换；如果向前看符号是 "b" ， 则可以用 \(Bc\) 替换。
我们将使用 FIRST 和 FOLLOW 这两个函数来帮助 计算分析表。
1.1.2. 函数 FIRST¶
定义 FIRST 和 FOLLOW 时使用的一些记号。
\(G=(V, T, S, P)\)\(w, v \in (V \cup T)^*\)\(a \in T\)\(X, A, B \in V\)\(X_I \in (V \cup T)^+\)
定义（definition）： \(\mbox{FIRST}(w) =\) 由 \(w\) 推导出的串的开头出现的终结符集合。
如果 \(w \buildrel * \over \Rightarrow av\) ，则\(a\) 属于 \(\mbox{FIRST}(w)\)如果 \(w \buildrel * \over \Rightarrow \lambda\) ，则\(\lambda\) 属于 \(\mbox{FIRST}(w)\)
上一个文法的例子： \(\mbox{FIRST}(aAb) = \{a\}\) ， 因为 \(aAb \Rightarrow a...b\) ，且 \(\mbox{FIRST}(Ac) = \{a, c\}\)
计算 FIRST：
\(\mbox{FIRST}(a) = \{a\}\) 其中 a 是终结符。
\(\mbox{FIRST}(X)\) ，其中 \(X\) 是变量。
如果 \(X \rightarrow aw\) ，则
\(a\) 属于 \(\mbox{FIRST}(X)\)
如果 \(X \rightarrow \lambda\) ，则
\(\lambda\) 属于 \(\mbox{FIRST}(X)\)
如果 \(X \rightarrow Aw\) 且 \(\lambda \in \mbox{FIRST}(A)\) ，
则 \(\mbox{FIRST}(w)\) 中的所有元素都属于 \(\mbox{FIRST}(X)\)
一般地， \(\mbox{FIRST}(X_1X_2X_3...X_K) =\)
\(\mbox{FIRST}(X_1)\)
\(\cup\ \mbox{FIRST}(X_2)\) ，如果 \(\lambda\) 属于 \(\mbox{FIRST}(X_1)\)
\(\cup\ \mbox{FIRST}(X_3)\) ，如果 \(\lambda\) 属于 \(\mbox{FIRST}(X_1)\)
且 \(\lambda\) 属于 \(\mbox{FIRST}(X_2)\)
...
\(\cup\ \mbox{FIRST}(X_K)\) ，如果 \(\lambda\) 属于 \(\mbox{FIRST}(X_1)\)
且 \(\lambda\) 属于 \(\mbox{FIRST}(X_2)\)
... 且 \(\lambda\) 属于 \(\mbox{FIRST}(X_{K-1})\)
\(-\ \{\lambda\}\) ，如果对所有 \(J\) 都有 \(\lambda \notin \mbox{FIRST}(X_J)\)
（其中 \(X_I\) 表示终结符或变量）
我们将计算 \(\mbox{FIRST}(w)\) ，其中 \(w\) 是规则的 右端（right hand side）。 因此，我们需要对规则右端出现的每个符号 \(X\) （终结符或变量）计算 \(\mbox{FIRST}(X)\) 。
1.1.3. 函数 FOLLOW¶
定义（definition）： \(\mbox{FOLLOW}(X) =\) 在某个推导中可能出现在 \(X\) 右侧的终结符集合。 （我们只为变量计算 FOLLOW。）
如果 \(S \buildrel * \over \Rightarrow wAav\) ，则\(a\) 属于 \(\mbox{FOLLOW}(A)\)（其中 \(w\) 和 \(v\) 是终结符和变量组成的串， \(a\) 是终结符， \(A\) 是变量）
计算 FOLLOW：
\(\$\) 属于 \(\mbox{FOLLOW}(S)\)
如果 \(A \rightarrow wBv\) 且 \(v \ne \lambda\) ，则
\(\mbox{FIRST}(v) - \{ \lambda \}\) 属于 \(\mbox{FOLLOW}(B)\)
如果 \(A \rightarrow wB\) ，或 \(A \rightarrow wBv\) 且 \(\lambda\) 属于 \(\mbox{FIRST}(v)\) ，则
\(\mbox{FOLLOW}(A)\) 属于 \(\mbox{FOLLOW}(B)\)
\(\lambda\) 永远不在 FOLLOW 中
