4.2.3 将CF语法转换为Chomsky普通形式

上一节中已经表明，将一个CF语法转换为CNF语法是值得的。本节我们将使用数字语法来讲讲这个转换过程。这个过程可以分为几个阶段：

  • 首先，去除ε规则被；

  • 第二，去除单元规则；

  • 第三，如2.9.5节所述，对语法进行整理；

  • 第四也就是最后，修改剩余的语法规则，并添加规则，直到它们都是我们所需的形式，即A → a或者A → BC。

所有的这些更改都不会改变原本语法所定义的语言的最终形式。现在你还体会不到这一点。关于形式语言理论的大多数书籍会更形式的讨论和介绍这一点，各位可以去自行了解；例如Hopcroft和Ullman [391]。

4.2.3.1 去除ε规则

假设我们有一个语法G，有一个ε规则A → ε，然后现在我们想要去掉这个规则。我们当然不能直接删掉规则，这样会改变非终结符A定于的语言，以及语法G所定义的语言也很可能被改变。因此对于语法右侧出现的非终结符A，必须采取一些措施。当语法规则B → αAβ中出现A的时候，我们用两个其他的规则来代替：B → αA'β，其中A'是一个全新的非终结符，然后我们稍后会为它增加新的规则（这些规则将是A的非空语法规则）；以及B → αβ，这个来处理在规则B → αAβ中A生成ε的部分。需要注意的是，上述规则中的α和β也有可能包含A；这样的情况下，必须用同样的方式替换每一个相关规则，直到所有与A相关的都没有了。当我们做完之后，语法中不会在有A出现。

每一个ε规则都必须用这种方法处理。当然，在这个过程中可能会产生新的ε规则。这只是一个预计：这个过程使所有ε生成变成显示。新产生的ε规则必须用一模一样的方式处理。直到最后这个过程会结束，因为生成ε规则的非终结符是有限的，并且，最终在右侧不会在出现这样的非终结符。

去除ε规则的下一步是为新的非终结符添加语法规则。如果A是引入A'的非终结符，我们就为所有的非ε规则A' → α添加一个A → α规则。由于所有ε规则都已经明确了，我们就可以确定，如果一个规则并不直接产出ε，那么它也将不能间接产生。这里可能会出现的一个问题是，A可能没有一个非ε规则。在这种情况下，A将只能产生ε，所以我们可以去掉所有使用*A'*的规则。

这些依然留给我们一个含有ε规则的语法。但是，任何含有ε规则的非终结符都不可以从起始字符到达，但有一个重要的例外：起始字符本身除外。特别是，现在我们就有一个规则S → ε，当且只当ε是语法G所定义的语言的一个成员时。此时所有其他含有ε规则的非终结符可以安全的去除，但对语法的实际清理将会留到稍后。

图1

图Fig4.10的语法是一个让人讨厌的语法，用来检测ε规则去除方案。这个方案将语法转换为图Fig4.11的语法。

图2

这个语法依旧含有ε规则，但是可以通过去掉非生成性的以及/或者不可到达的非终结符来消除掉。将此语法清理到只有一个规则留下：S → a。去掉我们的数字语法中的ε规则，最后会得到图Fig4.12中的语法。注意，生成ε，Empty和Scale，的两个规则仍在，只是不在使用了。

图3

4.2.3.2 去除单元规则

接下来给我们带来麻烦因此要去掉的是单元规则，也就是A → B这样形式的规则。必须认识到，如果在生成中使用A → B这样的规则，那么必须在某个时间后紧接着使用规则B → α。因此，如果有一个规则A → B，并且B的规则是：

B → α1 | α2 | ··· | αn,

我们可以将规则A → B替换为

A → α1 | α2 | ··· | αn.

在这个过程中，我们当然可以引入新的单元规则。尤其是，在重复这个过程时，我们可以在某个时刻再次得到规则A → B。在这样的情况下， 我们就有一个无限模糊的语法了，因为这意味着B生成B。这似乎提出了一个问题，但我们可以将这个单元规则排除出去；结果是我们缩短了生成过程像下面这样：

A → B → ··· → B → ···

此外，A → A形式的规则也被排除在外了。事实上，去除ε规则和单元规则的一个让人开心的地方是，生成的语法再不是模糊的。

在我们的无ε数字语法中去除单元规则，就得到了图Fig4.13的语法。

图4

4.2.3.3 清理语法

尽管我们的数字语法不包含非生成性非终结符，但它确实包含不可达到的非终结符，在消除ε规则时产生的：Real，Scale和Empty。CYK算法无论使用与否都可以正常工作，因此清理语法是可选项并非必须的，如2.9.5所述的。为了概念的理解以及好描述性，我们在这里选择对语法进行清理。但往后进行（4.2.6节）就会发现并不都是有利的。清理后的语法如图Fig4.14。

图5

4.2.3.4 最后，变成Chomsky正则形式

在所有这些语法转换后，我们就得到了一个没有ε规则和单元规则的语法，并且所有非终结符都可到达，并且不存在非生成性非终结符。因此我们就只剩下两种类型的规则了：A → a形式的规则，这种规则正符合我们的要求；以及A → X1X2 ···Xm形式的规则,其中m≥2。对于这样规则中出现的每一个终结符b，我们为之创建了仅包含一个规则Tb → b的非终结符Tb，并且将规则A → X1X2 ···Xm中出现的每一个b都替换为Tb。现在CNF中尚没有的规则是*A → X1X2 ···Xm其中m≥ 3的形式，以及所有Xi*非终结符。

A → X1X2 ···Xm

这些规则现在可以拆分并被替换为以下两个规则：

A → X1X3 ···Xm

A1 → X1X2

其中*A1*是一个新的非终结符。现在我们用一个短一些的规则以及一个CNF算法的规则替换了原有的规则。可以一直重复此拆分直到所有的规则都在CNF中为止。图Fig4.15向我们展示了CNF中的数字语法。