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

有了上一节中得到的正则表达式，那么就可以用来构造 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$ 转移的。

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索正则表达式
， 词法分析器
， 字符
， 状态
， 获取状态
， 一个
， 正则表达式获取
， 转移
， NFA
当前状态
c站、c语言、cf、ch、c罗，以便于您获取更多的相关知识。