6.2.1. 文法转换¶

我们用文法来表示一种编程语言。想要知道的是：给定的字符串（或程序 \(x\)）是否合法（语法是否正确）？这等同于问它是否在语言中（这也就是成员问题）。

上一次我们说明了：如果我们能把一个 CFG 转换成没有 \(\lambda\)-产生式、也没有 \(A \rightarrow B\) 这类规则的 CFG，那么我们就能在 \(2|w|\) 轮内确定 \(w\) 在不在 \(L(G)\) 中，每一步要么增加一个终结符，要么增加长度。

这样做是可行的，但并不快，也就是说，不是线性的！

我们将研究许多转换文法的方法。其中一些是更容易处理的形式，另一些则更容易用于证明。

具体来说，我们将研究对产生式规则右侧的限制。我们希望能够自动地将任意 CFG 转换成等价的受限 CFG。

我们只考虑不含 \(\lambda\) 的 CFL。要向任何文法中添加 \(\lambda\) 很容易：只需添加一个新的 起始符号 \(S_0\)，

\(S_0 \rightarrow S \mid \lambda\)

代入定理 设 \(G\) 是一个 CFG。假设 \(G\) 包含

\(A \rightarrow x_1Bx_2\)

其中 \(x_i \in (V \cup T)^{*}\)， \(A\) 和 \(B\) 是不同的变元，并且 \(B\) 有产生式

\(B \rightarrow y_1|y_2|\ldots|y_n\)。

那么，我们可以从 \(G\) 构造出 \(G'\)：删除

\(A \rightarrow x_1Bx_2\)

从 \(P\) 中加入

\(A \rightarrow x_1y_1x_2|x_1y_2x_2|\ldots | x_1y_nx_2\)。

于是，\(L(G) = L(G')\)。

问题：为什么不同时删除 \(B\) 的规则？

答案：它们可能被其他产生式使用。

问题：如果 \(A\) 和 \(B\) 相同会怎样？

那么 B 的产生式就变成了无用产生式。

定义： 形如 \(A \rightarrow Ax\) （\(A \in V, x \in (V \cup T)^*\)）的产生式是 左递归的。

例： 之前的表达式文法就是左递归的。（来自第 5 章的笔记）

它是左递归的，因为它有 一些 左递归的产生式。并不是所有的产生式都是左递归的。

\(E \rightarrow E+T \mid T\)

\(T \rightarrow T*F \mid F\)

\(F \rightarrow I \mid (E)\)

\(I \rightarrow a \mid b\)

自顶向下分析器（如 LL 分析）希望尽早推导出最左边的终结符。但在上面这个左递归文法中，为了推导出含有最左边终结符的句型，我们必须先推导出含有其他终结符的句型。

\(a+b+a+a\) 的推导是：

注意：如果文法能先推导出 \(a\)，而不附带其他所有的 +，那就更好了。

我们将消除左递归，这样我们就能推导出含有最左边终结符、而不含其他终结符的句型。

定理（消除左递归） 设 \(G = (V,T,S,P)\) 是一个 CFG。把变元 \(A\) 的产生式分成左递归的和非左递归的：

\(A \rightarrow Ax_1 \mid Ax_2 \mid \ldots \mid Ax_n\)

\(A \rightarrow y_1 \mid y_2 \mid \ldots \mid y_m\)

其中 \(x_i\)、\(y_i\) 都在 \((V \cup T)^*\) 中。

任何推导都会以 \(y_i\) 开头。

\(A\) 不是第二类产生式中任何一个的前缀。

那么 \(G = (V \cup \{Z\}, T, S, P')\)，其中 \(P'\) 把上述形式的规则替换为

\(A \rightarrow y_i \mid y_iZ, i = 1, 2, \ldots, m\)

\(Z \rightarrow x_i \mid x_iZ, i = 1, 2, \ldots, n\)

消除左递归之后，文法就处于适合自顶向下分析器的形式了，但文法会多出一些变元和产生式。

现在，\(a+b+a+a\) 的推导是：

\(E \Rightarrow TZ \Rightarrow FZ \Rightarrow IZ \Rightarrow aZ\)

还不需要先看其他任何终结符！

无用产生式

\(S \rightarrow aB \mid bA\)

\(A \rightarrow aA\)

\(B \rightarrow Sa\)

\(C \rightarrow cBc \mid a\)

关于这个文法，你能说出些什么？

\(A\)、\(S\) 和 \(B\) 是无用变元，因为它们无法推导出全由终结符组成的字符串。 \(C\) 是无用的，因为你无法得到 \(S \stackrel{*}{\Rightarrow} xCy \stackrel{*}{\Rightarrow} w\)，其中 \(w \in T^*\)。

定理：（无用产生式） 设 \(G\) 是一个 CFG。那么 \(\exists\ G'\) 不含任何无用变元或无用产生式，使得 \(L(G) = L(G')\)。

如何删除无用产生式：

设 \(G = (V,T,S,P)\)。

那么 \(G_1 = (V_1, T, S, P_1)\) 就不含无法推导出字符串的变元。

现在我们需要删除那些我们用不到的产生式。

2. 画出变元依赖图

对于 \(A \rightarrow xBy\)，画出 \(A \rightarrow B\)。

把 \(A\) 画在一个圆圈里，\(B\) 画在一个圆圈里，并画一条从 \(A\) 指向 \(B\) 的弧。

如果在依赖图中没有从 \(S\) 到 \(V\) 的路径，就删除 \(V\) 的产生式。得到的文法 \(G'\) 满足 \(L(G) = L(G')\)，并且 \(G'\) 没有无用产生式。

Settings

Saving...
Server Error
Resubmit

Q：你会如何实现 II？你如何知道哪些结点能从 S 到达？用 DFS 或 BFS。

注意：上一次我们讨论的是没有 \(\lambda\)-产生式的更简单的 CFG，现在我们将说明如何删除它们。

定理 （删除 \(\lambda\) 产生式）设 \(G\) 是一个 \(\lambda\) 不在 \(L(G)\) 中的 CFG。那么 \(\exists\) 一个没有 \(\lambda\)-产生式的 CFG \(G'\)，使得 \(L(G) = L(G')\)。

如何删除 \(\lambda\) 产生式

Settings

Saving...
Server Error
Resubmit

定义： 单元产生式

\(A \rightarrow B\)

其中 \(A, B \in V\)。

考虑删除单元产生式：

假设我们有

\[\begin{split}\begin{array}{lll} A \rightarrow B & \ \ \ \ \ \mbox{becomes} \ \ \ \ \ & A \rightarrow a \mid ab \\ B \rightarrow a \mid ab \\ \end{array}\end{split}\]

但如果我们有

\[\begin{split}\begin{array}{lll} A \rightarrow B & \ \ \ \ \ \mbox{becomes} \ \ \ \ \ & A \rightarrow C \\ B \rightarrow C & & B \rightarrow A \\ C \rightarrow A & & C \rightarrow B \\ \end{array}\end{split}\]

但我们并没有去掉单元产生式！

定理 （删除单元产生式）设 \(G = (V, T, S, P)\) 是一个没有 \(\lambda\)-产生式的 CFG。那么 \(\exists\) CFG \(G = (V', T', S, P')\)，它没有任何单元产生式，使得 \(L(G) = L(G')\)。

如何删除单元产生式：

1. 为每个 \(A\) 找出所有满足 \(A \stackrel{*}{\Rightarrow} B\) 的 \(B\)

（画一个依赖图来表示单元产生式之间的关系。 只要为每条 \(A \rightarrow B\) 规则画一条弧。

把 \(A\) 画在一个圆圈里，\(B\) 画在一个圆圈里， 并画一条从 \(A\) 指向 \(B\) 的弧。）

2. 按如下方式构造 \(G' = (V', T', S, P')\)：

(a) 把所有非单元产生式放入 \(P'\)

(b) 对所有满足 \(B \rightarrow y_1 \mid y_2 \mid \ldots y_n \in P'\) 的 \(A \stackrel{*}{\Rightarrow} B\)， 把 \(A \rightarrow y_1 \mid y_2 \mid \ldots y_n \in P'\)

以 \(A\) 为根运行 DFS。

注意 \(A \stackrel{*}{\Rightarrow} B\) 中的星号

千万不要把单元产生式放入 \(P'\)。

Settings

Saving...
Server Error
Resubmit

定理： 设 \(L\) 是一个不含 \(\lambda\) 的 CFL。那么 \(\exists\) 一个 \(L\) 的 CFG，它没有任何无用产生式、\(\lambda\)-产生式或单元产生式。

证明：

1. 删除 \(\lambda\)-产生式

2. 删除单元产生式

3. 删除无用产生式

注意顺序非常重要。删除 \(\lambda\)-产生式可能会产生单元产生式！证毕。

书中还有更多的例子。

定义： 如果一个 CFG 的所有产生式都具有如下形式，它就处于乔姆斯基范式（Chomsky Normal Form，CNF）中

\(A \rightarrow BC \ \ or A \rightarrow a\)

其中 \(A, B, C \in V\)，\(a \in T\)。

为什么要把文法转换成这种形式？因为在证明中更容易处理。

Settings

Saving...
Server Error
Resubmit

定义： 如果一个 CFG 的所有产生式都具有如下形式，它就处于格雷巴赫范式（Greibach normal form，GNF）中

\(A \rightarrow ax\)

其中 \(a \in T\)，\(x \in V^*\)

这类似于 s-文法（或简单文法），只不过 s-文法的定义还包含一个进一步的限制：任何一对 \((A, a)\) 至多可以出现在一条规则中。

这样做的目的是让你不必回溯（匹配字符串的推导时只有一个选择）。所以它的限制非常严格。

你应该掌握的内容：熟悉各种形式，如 GNF、CNF、单元产生式、左递归等等。不需要死记转换的规则，但应该理解该怎么做。