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中的语法。注意,生成εEmptyScale,的两个规则仍在,只是不在使用了。

图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 清理语法

尽管我们的数字语法不包含非生成性非终结符,但它确实包含不可达到的非终结符,在消除ε规则时产生的:RealScaleEmpty。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中的数字语法。