从正则表达式创建 NFA 时，我遇到了“描述每个步骤”的问题。问题如下：
将以下正则表达式转换为非确定性有限状态自动机 (NFA)，清楚地描述您使用的算法的步骤：(b|a)*b(a|b)
我已经制作了一个简单的三态机器，但它很大程度上来自直觉。这是我的讲师写的过去考试中的一个问题，他还写了对汤普森算法的以下解释：http ://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html
谁能弄清楚如何“清楚地描述每个步骤”？它似乎只是一组基本规则，而不是一个需要遵循的步骤的算法。
也许有一种算法我已经在某处掩盖了，但到目前为止，我只是用有根据的猜测创建了它们。
一般方法的简短版本。
有一种算法称为 Thompson-McNaughton-Yamada 构造算法，有时也称为“Thompson 构造”。一个构建中间 NFA，沿途填充片段，同时尊重运算符优先级：首先是括号，然后是 Kleene Star（例如，a*），然后是串联（例如，ab），然后是交替（例如，a|b）。
这是构建 (b|a)*b(a|b) 的 NFA 的深入演练
构建顶层
处理括号。注意：在实际实现中，通过对其内容的递归调用来处理括号是有意义的。为了清楚起见，我将推迟评估括号内的任何内容。
Kleene Stars：那里只有一个 *，所以我们构建了一个名为 P 的占位符 Kleene Star 机器（稍后将包含 b|a）。中间结果：
连接：将 P 附加到 b，并将 b 附加到称为 Q 的占位符机器（将包含 (a|b)。中间结果：
括号外没有交替，所以我们跳过它。
现在我们坐在 P*bQ 机器上。（请注意，我们的占位符 P 和 Q 只是连接机器。）我们将 P 边替换为 b|a 的 NFA，并通过上述步骤的递归应用将 Q 边替换为 a|b 的 NFA。
P楼
跳过。没有括号。
跳过。没有克莱恩明星。
跳过。没有污染。
为 b|a 构建交替机器。中间结果：
积分 P
接下来，我们回到那个 P*bQ 机器，我们撕掉 P 边。我们将 P 边的源作为 P 机器的起始状态，将 P 边的目的地作为 P 机器的目标状态。我们还使该状态拒绝（取消其作为接受状态的属性）。结果如下所示：
Q楼
跳过。没有括号。
跳过。没有克莱恩明星。
跳过。没有污染。
为 a|b 构建交替机器。顺便说一下，交替是可交换的，所以 a|b 在逻辑上等价于 b|a。（阅读：由于懒惰而跳过这个小脚注图。）
积分 Q
除了用我们构建的中间 b|a 机器替换 Q 边缘之外，我们做了上面对 P 所做的事情。这是结果：
多田！呃，我的意思是，QED。
想知道更多？
上面的所有图像都是使用在线工具生成的，用于将正则表达式自动转换为非确定性有限自动机。您可以在线找到Thompson-McNaughton-Yamada 构造算法的源代码。
该算法在Aho 的编译器：原理、技术和工具中也有介绍，尽管它对实现细节的解释很少。您还可以从优秀的 Russ Cox用 C 语言实现的 Thompson 构造中学习，他在一篇关于正则表达式匹配的热门文章中对其进行了详细描述。
在下面的 GitHub 存储库中，您可以找到 Thompson 构造的 Java 实现，其中首先从正则表达式创建 NFA，然后将输入字符串与该 NFA 匹配：
https://github.com/White-White/RegSwift
没有更多乏味的话。查看这个 repo，它将您的正则表达式转换为 NFA，并直观地向您显示 NFA 的状态转换。