理论 – 从正则表达式创建NFA的步骤

一般方法的简短版本。
有一个算法叫做汤普森麦克纳顿山田建设算法，有时只是“汤普森建筑”。一个构建中间的NFAs，沿着路径填充这些片段，同时尊重运算符优先级：第一个括号，然后是Kleene Star(例如a *)，然后连接(例如，ab)，随后交替(例如a | b)。

这是一个深入的演练(b | a)* b(a | b)的NFA

建设顶级

>处理括号。注意：在实际实现中，通过对其内容的递归调用来处理括号是有意义的。为了清楚起见，我将推迟对括号内的任何内容的评估。
> Kleene明星：只有一个*在那里，所以我们建立一个名为P的占位符Kleene Star机器(稍后将包含b | a)。
中间结果：

>连接：将P附加到b，并将b附加到名为Q的占位符机器(将包含(a | b))中间结果：

>括号外没有任何交替，所以我们跳过它。

现在我们坐在一台P * bQ机上。 (请注意，我们的占位符P和Q只是级联机器。)我们将P边缘替换为b | a的NFA，并通过上述步骤的递归应用将Q边与NFA替换为| b。

建筑P

>跳过。没有括号。
>跳过。没有克莱恩星。
>跳过。没有混合。
>为b | a构建交替机器。中级成绩：

整合P

接下来，我们回到那个P * bQ机器，我们撕掉了P边。我们将P边缘的源作为P机的起始状态，P边的目的地作为P机的目的地状态。我们也使国家拒绝(剥夺其成为接受国家的财产)。结果如下：

建设Q

>跳过。没有括号。
>跳过。没有克莱恩星。
>跳过。没有混合。
>构建一个| b的交替机器。顺便说一下，交替是可交换的，所以a |在逻辑上等同于b | a。 (阅读：从懒惰中跳过这个小脚注图)

整合Q

我们用P做的，除了用我们构建的机器代替Q边。这是结果：

田田！呃，我的意思是QED。

想了解更多？

以上所有图像都是使用an online tool for automatically converting regular expressions to non-deterministic finite automata生成的。您可以在线找到它的source code for the Thompson-McNaughton-Yamada Construction algorithm。

该算法在Aho’s Compilers: Principles,Techniques,and Tools中也得到了解决，尽管其解释在实现细节上很少。你也可以从an implementation of the Thompson Construction in C的优秀的Russ Cox学习，他在一篇关于regular expression matching的热门文章中描述了一些细节。