C#词法分析器之转换DFA详解

在上一篇文章中，已经得到了与正则表达式等价的 NFA，本篇文章会说明如何从 NFA 转换为 DFA，以及对 DFA 和字符类进行化简。
 一、DFA 的表示

DFA 的表示与 NFA 比较类似，不过要简单的多，只需要一个添加新状态的方法即可。Dfa 类的代码如下所示：

符号索引表示当前的接受状态对应的是哪个正则表达式。不过 DFA 的一个状态可能对应于 NFA 的多个状态（详见下面的子集构造法），所以 DFA 状态的符号索引是一个数组。对于普通状态，符号索引是空数组。

状态转移表示如何从当前状态转移到下一状态，由于在构造 NFA 时已经划分好了字符类，所以在 DFA 中直接使用数组记录下不同字符类对应的转移（DFA 中是不存在 ϵ 转移的，而且对每个字符类有且只有一条转移）。

在 NFA 的状态定义中，还有一个状态类型属性，但是在 DFA 状态中却没有这个属性，是因为 Trailing 类型的状态会在 DFA 匹配字符串的时候处理（会在下篇文章中说明），TrailingHead 类型的状态会在构造 DFA 的时候与 Normal 类型的状态合并（详见 2.4 节）。

下面是 DfaState 类的定义：

将 NFA 转换为 DFA，采用的是子集构造（subset construction）算法。该算法的过程与《C# 词法分析器（三）正则表达式》的 3.1 节中提到的 NFA 匹配过程比较相似。在 NFA 的匹配过程中，使用的都是 NFA 的一个状态集合，那么子集构造法就是用 DFA 的一个状态来对应 NFA 的一个状态集合，即 DFA 读入输入字符串 a1a2⋯an 之后到达的状态，就对应于 NFA 读入同样的字符串 a1a2⋯an 之后到达的状态的集合。

子集构造算法需要用到的操作有：