有了上一节中得到的正则表达式，那么就可以用来构造 NFA 了。NFA 可以很容易的从正则表达式转换而来，也有助于理解正则表达式表示的模式。
一、NFA 的表示方法在这里，一个 NFA 至少具有两个状态：首状态和尾状态，如图 1 所示，正则表达式 $t$ 对应的 NFA 是 N(t)，它的首状态是 $H$，尾状态是 $T$。图中仅仅画出了首尾两个状态，其它的状态和状态间的转移都没有表示出来，这是因为在下面介绍的递归算法中，仅需要知道 NFA 的首尾状态，其它的信息并不需要关心。
图 1 NFA 的表示
我使用下面的 Nfa 类来表示一个 NFA，只包含首状态、尾状态和一个添加新状态的方法。
状态转移表示如何从当前状态转移到下一状态，虽然 NFA 的定义中，每个节点都可能包含多个 ϵ 转移和多个字符转移（就是边上标有字符的转移）。但在这里，字符转移至多有一个，这是由之后给出的 NFA 构造算法的特点所决定的。
状态类型则是为了支持向前看符号而定义的，它可能是 Normal、TrailingHead 和 Trailing 三个枚举值之一，这个属性将在处理向前看符号的部分详细说明。
下面是 NfaState 类的定义：
NfaState 类中还定义了三个 Add 方法，分别是用来添加单个字符的转移、字符类的转移和 $\epsilon$ 转移的。
二、从正则表达式构造 NFA
这里使用的递归算法是 McMaughton-Yamada-Thompson 算法（或者叫做 Thompson 构造法），它比 Glushkov 构造法更加简单易懂。
2.1 基本规则
- 对于正则表达式 $\epsilon$，构造如图 2(a) 的 NFA。对于包含单个字符 $a$ 的正则表达式 $\bf{a}$，构造如图 2(b) 的 NFA。
图 2 基本规则
上面的第一个基本规则在这里其实是用不到的，因为在正则表达式的定义中，并没有定义 $\epsilon$。第二个规则则在表示字符类的正则表达式 CharClassExp 类中使用，代码如下：
假设正则表达式 s 和 t 的 NFA 分别为 N(s) 和 N(t) 。
1. 对于 r=s|t ，构造如图 3 的 NFA，添加一个新的首状态 H 和新的尾状态 T ，然后从 H 到 N(s) 和 N(t) 的首状态各有一个 ϵ 转移，从 H 到 N(s) 和 N(t) 的尾状态各有一个 ϵ 转移到新的尾状态 T 。很显然，到了 H 后，可以选择是匹配 N(s) 或者是 N(t) ，并最终一定到达 T 。
图 3 归纳规则 AlternationExp
这里必须要注意的是，$N(s)$ 和 $N(t)$ 中的状态不能够相互影响，也不能存在任何转移，否则可能会导致识别的结果不是预期的。
AlternationExp 类中的代码如下：
图 4 归纳规则 ConcatenationExp