一个编译器的实现（04）——词法分析(3.最小化DFA)

檀凤琴1998[3]中的算法是比较简单的，但那个算法有错误——有些情况的NFA并不能用她的算法来进行最小化，可能某些构造NFA的方法可以保证不会出现那些不适用于这个算法的NFA，但她没有证明，也没看到其它人证明过，我也没打算去证明它，所以我们这里不用她的算法。但可以借鉴参考，那个算法实现起来要比下面AMRJ2010[1]和MLS2007[2]要简单得多，如果能够解决不适用的部分，那么这个算法还是挺好用的。（我的反例是这样的：假设某NFA的有三个终态a,b,c，a输入x到b，b输入x到c，c输入x到a，这样的情况不能满足算法1步骤3的任何一个规则，但这三个状态是等价的。）

AMRJ2010[1]与MLS2007[2]中的算法是一样的，MLS2007[2]中只是一小段话就带过了，没有详细讲，所以下面我引用AMRJ2010[1]中的内容：

算法：最小化一个DFA的状态数量。

输入：一个DFA D，其状态集合为S，输入字母表为Σ，开始状态为s0，接受状态为F。

输出：一个DFA D'，它和D接受相同的语言，且状态数量最少。

方法：

1. 首先构造包含两个组F和S-F的初始划分∏，这两个组分别是D的接受状态组和非接爱状态组。
2. 应用下图的过程来构造新的分划∏new。

   最初，令∏new = ∏;
   for(∏中的每个组G){
       将G分为更小的组，使得两个状态s和t在同一小组中当且仅当对所有的输入符号a，状态s和t在a上的转换都到达∏中的同一组;
       /*在最坏情况下，每个状态各自组成一个组*/
       在∏new中将G替换为G进行分划得到的那些小组;
   }

3. 如果∏new = ∏，令∏final = ∏并接着执行步骤4；否则，用∏new替换∏并重复步骤2。
4. 在分划∏final的每个组中选取一个状态作为该组的代表。这些代表构成了状态最少DFA D'的状态。D'的其它部分接如下步骤构建：
1. D'的开始状态是包含了D的开始状态的组的代表。
2. D‘的接受状态是那些包含了D的接受状态的组的代表。请注意，每个组中要么只包含接受状态，要么只包含非接受状态，因为我们一开始就将这两类状态分开了，而上面图中的过程总是通过分解已经构造得到的组来得到新的组。
3. 令s是∏final中某个组G的代表，并令DFA D中在输入a上离开s转换到达状态t。令r为t所在的组H的代表。那么在D'中存在一个从s到r在输入a上的转换。注意， 在D中，组G中的每一个状态必然在输入a上进入组H中的某个状态，否则，组G应该已经被 上图的过程分割成更小的组了。

书中的算法就是这样，下面我们举一个例子，运行一下这个算法：

一个识别注释块的正则表达式：/\*(\*[^/]|[^*])*\*/

其对应的NFA为：

用上一节的算法转换成DFA为：

下面我们来执行一下算法，来简化这个DFA：

1. 第一步初始划分，这里只有一个接受状态，那么划分就为两个集合：{s, 1, 2, 3, 4, 5}和{f}，我们用sets表示。
2. 定义一个sets_new来表示划分后的集合。初始值为sets。
3. for(sets中的每个组set)，即：遍历sets中的每一个集合，遍历过程中的当前集合用set表示。
4. 划分set为更小的集合，使得每个集合中的状态的输入都到达sets中的同一个组中。如：现在sets为两个组，即{s, 1, 2, 3, 4, 5}和{f}，我们用s1和s2表示它们，s2只有一个状态，没得分了，所以我们假设当前遍历到s1，s1中只有状态3的输出有时在s2中，有时在s1中，其它状态的输出都在s1中，那么我们这次之后的划分就把状态3分出来，这样就变成了{s, 1, 2, 4, 5}和{3}和{f}，即为sets_new。
5. 如果sets_new与sets是一样的，那么划分就停止，开始执行下一步，否则回到步骤3。
6. 到了这步，最终sets会是这样的：{s}, {1}, {2, 4, 5}, {3}, {f}。这些集合就是我们最终的DFA的状态，此时我们还要确定三个东西：第一个是开始状态。这些集合中，哪一个包含了未简化前的开始状态，哪个就是新的DFA的开始状态，那就是{s}了（因为原来的DFA的开始状态只有一个，所以我们简化之后也只会有一个）。第二个是接受状态。只要哪个集合中包含了原来的任意一个接受状态，那么这个集合就是简化后的DFA的接受状态，那就是{f}了（如果未简化前有多个接受状态，那么简化后也可能有多个，也可能只有一个）。第三个是转换的边。这个只要在那个集合中任选一个状态，看一下这个状态的输出状态在哪个集合中，那么就有一个边从当前集合指向那个集合。如{2, 4, 5}，我们任选一个，比如4，4有一个边输入*输出到3，那么{2, 4, 5}就会有一条边输入*，输出到{3}，4还有一个边输入^*输出到4，那么{2, 4, 5}就会有一个边输入^*输出到自己。这就确定了{2, 4, 5}的所有输出了。以此类推就可以确定所有的边。
7. 到此，简化的DFA出来了，如图（若要好看一点，也可以改一下状态名字）：。

这个算法只是对于一个正则表达试来说的，但如果我们要匹配多个正则表达式呢？即，每个词素一个表达式的情况：

只需要把上面的算法改动一点点。在第一步做初始划分的时候，把不同的接受状态分别划到不同的组中即可（当然，我们要有一个标记来区分不同的接受状态），算法的其它部分不变。

至此，最小化DFA的工作就结束了。

下一步就是执行扫描过程了。

本节参考资料

1. Alfred V.Aho、Monica S.Lam、Ravi Sethi、Jeffrey D.Ullman著，赵建华、郑滔、戴新宇译，《编译原理》，机械工业出版社，2010年4月。
2. Michael L.Scoot著，裘宗燕译，《程序设计语言-实践之路》第2版，电子工业出版社，2007年6月。
3. 檀凤琴，《构造正则表达式的简化DFA算法》，1998年。

我的代码

同前一篇文章。