一个编译器的实现（03）——词法分析(2.NFA转DFA)

（AMRJ2010[1]）确定有穷自动机（简称DFA）是不确定有穷自动机的一个特例，其中：

1. 没有输入Ɛ之上的转换动作。
2. 对每个状态s和每个输入符号a，有且只有一条标号为a的边离开s。

由NFA构造DFA的算法，我先抄一下AMRJ2010[1]的，再用我的话解释一下：

AMRJ2010[1]的算法描述如下：

算法：由NFA构造DFA的子集构造(subset construction)算法。

输入：一个NFA N。

输出：一个接受同样语言的DFA D。

方法：我们的算法为D构造一个转换表Dtran。D的每个状态 是NFA的状态集合，我们将构造Dtran，使得D“并行地”模拟N在遇到一个给定输入串时可能执行的所有动作。我们面对的第一个问题是正确处理N的Ɛ转换。在下表中我们可以看到一些函数的定义。这些函数描述了一些需要在这个算法执行的N的状态集上的基本操作。请注意，s表示N的单个状态，而T代表N的一个状态集。

操作          描述
Ɛ-closure(s) 能够从NFA的状态s开始只通过Ɛ转换到达的NFA状态集合
Ɛ-closure(T) 能够从T中某个NFA状态s开始只通过Ɛ转换到达的NFA状态集合，即∪(s∈T)Ɛ-closure(s)
move(T, a)   能够从T中某个状态s出发通过标号为a的转换到达的NFA状态集合

注：表中的红色部分应该是下标，但这个博客标签支持不好，所以就用颜色标示一下。

我们必须找出当N读入了某个输入串之后可能位于的所有状态集合。首先，在读入第一个输入符号之前N可以位于集合Ɛ-closure(s0)中的任何状态上，其中s0是N的开始状态。下面进行归纳。假定N在读入输入串x之后可能位于集合T中的状态上。如果下一个输入符号是a，那么N可以立即移动到集合move(T, a)中的任何状态。然而，N可以在读入a后再执行几个Ɛ转换，因此N在读入xa之后可位于Ɛ-closoure(move(T, a))中的任何状态上。根据这些思想，我们可以得到下图中显示的方法，该方法构造了D的状态集合Dstates和D的转换函数Dtran。

一开始，Ɛ-closure(s0)是Dstates中唯一状态，且它未加标记;
while(在Dstates中有一个未标记状态T){
    给T加上标记;
    for(每个输入符号a){
        U = Ɛ-closure(move(T, a));
        if(U不在Dstates中)
            将U加入到Dstates中，且不加标记;
        Dtran[T, a] = U;
    }
}

D的开始状态是Ɛ-closure(s0)，D的妆受状态是所有至少包含了N的一个接受状态的状态集合。我们只需要说明如何对NFA的任何状态集合T计算Ɛ-closure(T)，就可以完整的描述子集构造算法。这个计算过程显示在下图中。它是从一个状态集合开始的一次简单的图搜索过程，不过此时假设这个图中只存在标号为Ɛ的边。

将T的所有状态压入stack中;
将Ɛ-closure(T)初始化为T;
while(stack非空){
    将栈顶元素t弹出栈中;
    for(每个满足如下条件的u:从t出发有一个标号为的转换到达状态u)
        if(u不在Ɛ-closure(T)中){
            将u加入到Ɛ-closure(T)中;
            将u压入栈中;
        }
}

至此AMRJ2010[1]的子集构造算法就描述完了。

可能很多人对这个语言比较偏“官方”的描述感觉不好理解，所以下面我再从一个例子出发来解释一下这个算法，这个例子来源于MLS2007[2]：

匹配0的个数为偶数的0/1串的正则表达式为：(1*01*0)*1*

它转成NFA，如下图所示：

这里稍微解释一下：1到4号状态就是正则表达式中的第一个1*，5到8状态是第二个1*，10到最后的接受状态是第三个1*，这个可以用上节讲的“公式4”来确定；从1号到9号的连接可以用“公式2”，只是四个元素"1*","0","1*","0"的前后连接；从开始到10号是括号后面的型号画出来的，也可以直接套用“公式4”；最后再与最后一个1*连接一下就完成了这个NFA图。

下面我们一步一步的来跟踪一下“子集构造算法”，看看它是如何转换这个NFA(N)到DFA(D)的：

1. 算法中的第一步是找到初始状态集合T0。寻找的方法就是从N的初始状态s0出发，找到所有通过Ɛ转换可以到达的集合（也就是上面所说的Ɛ-closure(s0))。在我们的图中，初始状态通过Ɛ转换可以到达1号和10号，而1号可以通过Ɛ转换到达2号和4号，10号通过Ɛ转换可以到达11号和接受状态（我们用f表示接受状态）。这样我们的初始状态集合T0={s0, 1, 2, 4, 10, 11, f}，到此确定了T0之后开始第二步。
2. 创建一个D的状态集合Dstates。以后我们每发现一个状态，我们就把它加入到Dstates中。现在我们只有一个T0，所以我们把T0加入到Dstates中。
3. for(T in (Dstates中未被标记的集合))做下面的动作。注：这里的标记是为了防止重复访问，我在开发时并没有做标记，而是用C++中的std::list<>做为Dstates的数据结构，用std::list<>::iterator迭代，C++中的迭代器并不会因为在list后面加入新的元素而失效（这点与Java不一样）所以只要iterator一直向后走就行了，前面已经遍历完的不会再被访问，就相当于做了标记。所以在下面我的遍历过程来讲，就不说标记的事儿了。
4. 遍历T中的每个输入符号a。例如，T0中的各个状态只当输入1或0时才会离开T0这个集合（T0中有些状态可以接收Ɛ，但所有这些转换状态都在T0内部），所以这个遍历就是遍历{0, 1}这个集合。
5. 找出T通过a转换到的所有的状态，以及这些状态s的Ɛ-closure(s)。例如：T0={s0, 1, 2, 4, 10, 11, f}，其中2、11在a==1的情况下（a==0时同理）分别转到3、12，而3又可以通过Ɛ转换到4和2，12可以转换到11和f，那么就得到这个T通过1可以到达{2, 3, 4, 11, 12, f}，我们标记这个集合为U，即U={2, 3, 4, 11, 12, f}。
6. 判断U是否在Dstates中，如果不在，则把U加入到Dstates的末尾。这里要注意两点：一个是U是否在Dstates中的判断是判断状态集合所包涵的状态是否一样。另一个是在我们的开发语言中，相等的对象不一定是同一个对象，而在这里的算法描述中，并不这样区分，即如果当前这个判断为是，那么U就是Dstates中的那个对象。所以当我们用这个算法写代码的时候要注意这里可能要清理多余的对象。
7. 把从T通过a的转换指向U。这里的注意问题与上一步是一样的，在实际编码时，如果第6步中判断为是，那么T通过a的转换应该指向的是Dstates中的那个与U相等的对象，否则指向U。
8. 继续遍历T中的每个输入符号a（也就是回到第4步），除非已经遍历完了。
9. 继续遍历Dstates中在T后面的集合，把T指向后面的集合（也就是回到第3步），除非Dstates已经遍历完了。
10. 把所有包含f的状态集合做为D接受状态。

上面的步骤结束之后就形成了一个图，如下：

图中T0为构造的DFA的开始状态，所有包含了原来NFA中f的状态集（图中有三个）都为DFA的接受状态。这样一个DFA就构造完成了，为了看起来放方便，我们把图中的状态名改一下：

这个DFA显然不是最小的，我们很容易就可以构造出如下图所示的DFA：

这个DFA也可以表示(1*01*)*1*这个正则表达式，而且它只有两个状态（更小）。所以“子集构造算法”可以由NFA转换成DFA，但并不能保证转换之后的DFA是最小的。

那么如何最小化一个DFA呢？这是下一节的内容。

在开始下一节前，还有一个问题要解释一下：那就是NFA中一个状态的多个输入之前的相互交叉问题。例如：一个状态S有一条边上的输入是[a-g]，另一条边上的输入是[b-k]，或者一个边的输入是.，另一个边输入是a，那么这两条边是有交叉的（但又不相等）。这时在做上面算法描述中的第四步时，对T所有输入a进行遍历就会有部分交叉，那么转换到达的状态集合也就不对了。必须先化解掉这些交叉，才可以开始算法。那么如何做呢？ 

首先，在NFA中的任何一个状态S，其输入可能有三种情况：

1. 匹配一个确定的字符，如：c。
2. 匹配所有字符，如：.。
3. 匹配一个字符组，如：[abc]或[^a-z]或\w等。注：这里的转义字符组我们都可以用一个真正的字符组替代，如\w可以用[_a-zA-Z0-9]来替换，所以我们在描述算法时就不说转义字符组了。

这三种情况中的任意两个碰到会是什么情况呢？：

• 如果情况1与情况2相遇，如：一条边上是c，另一条边上是.，那么c包含在.之内，则需要把.分解为c和[^c]即可。
• 如果情况1与情况3相遇，且字符组是非排除型的，如：一条边上是c，另一条边上是[bcda-z]，那么对于字符组中没有连字符的就直接拿出来，即变成c和[bda-z]，对于有连字符的来说，可以判断一下c是否在连字符表示的范围之内，如本例就可以判断一下a <= c <= z是否成立，如果成立，那么就把c傻拿出来，并把字母表中c-1与c+1的字母做为连字符中间断开的部分的端点，如本例就可以变成c和[bda-bd-z]。
• 如果情况1与情况3相遇，且字符组是排除型的，如：一条边上是c，另一条边上是[^xyzh-m]，那么先判断一下c是否在字符组[xyzh-m]内（判断方法同上一步），如果在则没有交叉，如果不在，那么就把[^xyzh-m]变成c和[^cxyzh-m]就可以了。
• 如果情况2与情况3相遇，且字符组是非排除型的，如：一条边上是.，另一条边上是[ab-z]，那么把.分解为[ab-z]和[^ab-z]即可。
• 如果情况2与情况3相遇，且字符组是排除型的，如：一条边上是.，另一条边上是[^ab-z]，那么把.分解为[ab-z]和[^ab-z]即可。
• 如果情况3与情况3相遇，且两个字符组都是非排除型的，如：一条边上是[abch-n]，另一条别上是[bdm-z]，那么先二话不说，分别分成[abc]和[h-n]、[bd]和[m-z]（如果一个字符组中有多个连字符，那也分别拆开即可），这样的四组两两去比较拆分，只有[h-n]与[m-z]这一组是以前没讲过的情况，其它都可参考前面的方法。对于类似[h-n]与[m-z]这样的情况常规的做法就是判断前后交叉，互相包含等情况，然后分别拆分即可，更聪明的办法我也没有，所以就不在这里缀述。
• 如果情况3与情况3相遇，且一个是排除型的，一个是非排除型的，如果非排除型的字符组中没有连字符，或只有连字符连接的，而没有单个字符，就比较好处理（单个字符的就循环做比较就行了，连字符的就做范围判断），如果是这样的[^bdn-p]这样的我没想出怎么处理，好在编译器的词法中没有这样的情况。以后我再想一想怎么处理吧。
• 如果情况3与情况3相遇，且两个都是排除型的，同上。

至此，NFA转DFA就没问题了，只是还不够简化。

下一节我们讲一下最小化DFA的方法。

本节参考资料

1. Alfred V.Aho、Monica S.Lam、Ravi Sethi、Jeffrey D.Ullman著，赵建华、郑滔、戴新宇译，《编译原理》，机械工业出版社，2010年4月。
2. Michael L.Scoot著，裘宗燕译，《程序设计语言-实践之路》第2版，电子工业出版社，2007年6月。

我的代码

同前一篇文章。