C#词法分析器（五）转换 DFA

C#词法分析器（五）转换 DFA2014-04-14在上一篇文章中，已经得到了与正则表达式等价的 NFA，本篇文章会说明如何从 NFA 转换为 DFA，以及对 DFA 和字符类进行化简。

一、DFA 的表示

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

namespace Cyjb.Compilers.Lexers { class Dfa : IList<DfaState> { // 在当前 DFA 中创建一个新状态。 DfaState NewState（） {} } }

DFA 的状态也比较简单，必要的属性只有两个：符号索引和状态转移。

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

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

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

下面是 DfaState 类的定义：

namespace Cyjb.Compilers.Lexers { class DfaState { // 获取包含当前状态的 DFA。 Dfa Dfa { get; private set; } // 获取或设置当前状态的索引。 int Index { get; set; } // 获取或设置当前状态的符号索引。 int[] SymbolIndex { get; set; } // 获取或设置特定字符类转移到的状态。 DfaState this[int charClass] { get; set; } } }

DFA 的状态中额外定义的两个属性 Dfa 和 Index 同样是为了方便状态的使用。

二、NFA 转换为 DFA

2.1 子集构造法

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

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