C#词法分析器（四）构造 NFA

C#词法分析器（四）构造 NFA2014-04-14有了上一节中得到的正则表达式，那么就可以用来构造 NFA 了。NFA 可以很容易的从正则表达式转换而来，也有助于理解正则表达式表示的模式。

一、NFA 的表示方法

在这里，一个 NFA 至少具有两个状态：首状态和尾状态，如图 1 所示，正则表达式 t 对应的 NFA 是 N（t），它的首状态是 H，尾状态是 T。图中仅仅画出了首尾两个状态，其它的状态和状态间的转移都没有表示出来，这是因为在下面介绍的递归算法中，仅需要知道 NFA 的首尾状态，其它的信息并不需要关心。

图 1 NFA 的表示

我使用下面的 Nfa 类来表示一个 NFA，只包含首状态、尾状态和一个添加新状态的方法。

namespace Cyjb.Compilers.Lexers {class Nfa : IList<NfaState> {// 获取或设置 NFA 的首状态。NfaState HeadState { get; set; }// 获取或设置 NFA 的尾状态。NfaState TailState { get; set; }// 在当前 NFA 中创建一个新状态。NfaState NewState（） {}}}

NFA 的状态中，必要的属性只有三个：符号索引、状态转移和状态类型。只有接受状态的符号索引才有意义，它表示当前的接受状态对应的是哪个正则表达式，对于其它状态，都会被设为 -1。

状态转移表示如何从当前状态转移到下一状态，虽然 NFA 的定义中，每个节点都可能包含多个 $epsilon$转移和多个字符转移（就是边上标有字符的转移）。但在这里，字符转移至多有一个，这是由之后给出的 NFA 构造算法的特点所决定的。

状态类型则是为了支持向前看符号而定义的，它可能是 Normal、TrailingHead 和 Trailing 三个枚举值之一，这个属性将在处理向前看符号的部分详细说明。

下面是 NfaState 类的定义：

namespace Cyjb.Compilers.Lexers {class NfaState {// 获取包含当前状态的 NFA。Nfa Nfa;// 获取当前状态的索引。int Index;// 获取或设置当前状态的符号索引。int SymbolIndex;// 获取或设置当前状态的类型。NfaStateType StateType;// 获取字符类的转移对应的字符类列表。ISet<int> CharClassTransition;// 获取字符类转移的目标状态。NfaState CharClassTarget;// 获取转移的集合。IList<NfaState> EpsilonTransitions;// 添加一个到特定状态的转移。void Add（NfaState state, char ch）;// 添加一个到特定状态的转移。void Add（NfaState state, string charClass）;// 添加一个到特定状态的ε转移。void Add（NfaState state）;}}

我在 NfaState 类中额外定义的两个属性 Nfa 和 Index 单纯是为了方便状态的使用。$epsilon$ 转移直接被定义为一个列表，而字符转移则被定义为两个属性：CharClassTarget 和 CharClassTransition，CharClassTarget 表示目标状态，CharClassTransition 表示字符类，字符类会在下面详细解释。

NfaState 类中还定义了三个 Add 方法，分别是用来添加单个字符的转移、字符类的转移和 $epsilon$ 转移的。