FSM Explorer：学习正则表达式引擎和有限自动机

• 下载源代码 - 120.3 KB

引言

请参阅我的后续文章 此链接，了解此库的新版本，它支持编译，并解释了所有工作原理。

很久以前，我写了一篇关于正则表达式引擎工作原理的文章。这是第二次尝试。部分内容是从另一篇文章中 übernommen的。除了在此处进行解释外，还提供了一个包含正则表达式引擎和可视化应用程序的解决方案，该应用程序可以自动运行Graphviz来向您展示其工作原理。

必备组件

• 一台装有Windows和最新版Visual Studio的PC
• 已安装并添加到PATH的Graphviz

更新：在应用程序中添加了查看优化DFA的选项

更新2：FA引擎改进和错误修复

概念化这个混乱

本文假定您对常见的正则表达式符号有一定的了解。您不必是专家，但知道?、*、+、|、[]和()的作用会很有帮助。如果您只了解其中的一部分，也没关系，只要您理解正则表达式的基本概念及其用途即可。

您可能不知道的是其工作背后的理论，我们将在本文中介绍。

本质上，正则表达式是基于有向图的有限状态机。也就是说，它是一个由节点组成的网络，通过有向路径连接到其他节点。这比用语言描述更容易可视化。

这个正则表达式图匹配“foo”或“bar”。对应的正则表达式是foo|bar。

工作原理如下：我们总是从**q0**开始。从那里，有一系列指向外部的黑色箭头。每个箭头都标有一个字符。嗯，我们检查要匹配的字符串的第一个字符。如果它是“f”，我们就移到**q1**。如果它是“b”，我们就移到**q4**。每当我们沿着黑色箭头移动时，输入字符串的游标位置都会增加一。在**q1**或**q4**，我们将检查*下一个*输入字符，依此类推。这会一直持续到我们无法再匹配任何字符为止。如果此时，我们处于一个带有双圆圈的状态（“接受状态”），则表示匹配成功。如果此时我们处于某个单圆圈状态，则表示不匹配。

我们可以通过解析正则表达式来创建这些图，然后使用代码“运行”这些图，以便它们可以匹配输入字符串。

说到匹配，使用正则表达式引擎有两种截然不同的方法。第一种，也是最常见的一种，是在长文本字符串中扫描以查找特定模式。例如，如果您在Visual Studio的“搜索和替换”对话框中启用正则表达式匹配，您就会进行这样的操作。对于微软的正则表达式引擎来说，这已经是一个很成熟的领域了，而且在这种情况下通常最好使用它。对于长字符串，它的性能可能比我们的库要好，因为它实现了诸如Boyer-Moore搜索之类的算法，而我们的库则没有。通常，在这种匹配风格下依赖微软的引擎是个好主意。

使用正则表达式引擎的另一种方法称为*标记化*。这基本上是通过输入流进行移动，并尝试将光标下的字符串与特定模式匹配，然后报告匹配的模式，再进行前进。基本上，它使用一个复合正则表达式（与or组合）将文本匹配到特定的表达式之一——并告诉您是哪个表达式匹配了。这对于由解析器使用的词法分析器/标记化器非常有用。微软的正则表达式引擎不适合此任务，尝试将其用于此任务存在许多缺点，包括额外的代码复杂性和相当大的性能损失。这种功能上的差距足以证明，如果您出于其他原因需要创建解析器或进行标记化，那么定制正则表达式引擎是值得的。

与微软的正则表达式引擎不同，此引擎不会回溯。也就是说，它永远不会检查一个字符超过一次。这带来了更好的性能，但非回溯表达式不如回溯表达式那样具有表现力/强大。诸如原子零宽度断言之类的东西无法使用此引擎实现，但权衡是值得的，尤其是在用于标记化时。

回到图表，如前所述，每个图表代表一个有限状态机。状态机总是有一个以**q0**为根。如果我们取图表的任意子集，例如从**q4**开始，并忽略**q4**直接或间接指向的任何内容，那么这*也是*一个状态机。基本上，有限状态机是一组相互连接的状态机！

要从您当前所在的节点找到整个状态机，您需要获取状态的*闭包*。闭包是指从某个状态直接或间接可达的所有状态的集合，包括该状态本身。**q0**的闭包始终是整个图。在这种情况下，**q4**的闭包是{ **q4**，**q5**，**q3** }。请注意，我们从不沿箭头向后移动。图是有向的。获取闭包是几乎任何有限状态机代码的核心操作。

让我们来看一个稍微复杂一点的例子：(foo|bar)+。基本上，我们只是在机器中添加了一个循环，这样它就可以匹配“foobarfoo”或“foofoobar”或“barbarfoofoobar”等。

这个图看起来完全不同！不过，如果您仔细观察，就会明白。另外请注意，我们从双圆圈的接受状态有向外箭头。这意味着我们不会在到达接受状态后停止，直到我们无法继续为止——因为我们找不到下一个字符匹配，或者因为我们输入耗尽了。我们只关心在尽可能多的匹配之后，它是否是接受状态。这被称为*贪婪匹配*。您可以通过更复杂的表达式来模拟*懒惰匹配*，但在非回溯正则表达式中没有内置的设施。

构建这些图有点技巧。上面的图称为*DFA*，但以编程方式使用*NFA*构建图要容易得多。为了实现NFA，我们在图中添加了一种额外的线条——虚线，我们称之为*epsilon转移*。与输入转移不同，epsilon转移不消耗任何输入或前进输入游标。一旦您处于一个状态，您*也*处于所有通过虚线连接到该状态的状态。是的，我们现在可以同时处于多个状态。

立即引起注意的是灰色的虚线以及图表是如何更直观的。还记得我说过您会自动进入由epsilon转移连接的状态，这意味着一旦您处于**q0**，您*也*处于**q1**、**q2**和**q8**。可以说，**q0**的*epsilon闭包*是{ **q0**、**q1**、**q2**、**q8** }。这是因为从相关状态中的每个状态都有指向外的虚线。

上面的图表比它前面的图表对于计算机来说导航起来更耗费资源。原因是epsilon转移引入了同时处于多个状态的可能性。这被称为*非确定性*。

前者图表是*确定性的*。它一次只能处于一个状态，这使得计算机能够更快地导航它。

这些非确定性图表的一个有趣的属性是，存在一个本质上等价的确定性图表。也就是说，存在一个等价的、没有虚线/epsilon转移的图表。换句话说，对于任何NFA，都存在一个等价的DFA。我们将在稍后利用这个属性。

既然我们知道可以创建这些NFA（带epsilon转移），并且稍后可以将它们转换为DFA（不带epsilon转移），那么我们将使用NFA图来构建我们所有的状态机，直到完成，才会将其转换为DFA。

我们将使用Thompson构造算法的一个变体来构建我们的图。它通过定义几个基本子图，然后将它们组合成更大的图来工作。

首先，我们有一个**文字** - 正则表达式为ABC

接下来，我们有一个**字符集** - 正则表达式为[ABC]

接下来，我们有**连接** - 正则表达式为ABC(DEF)：（这通常是隐式的）

现在，我们有**或** - 正则表达式为ABC|DEF

接下来是**可选** - 正则表达式为(ABC)?

最后，我们有**重复** - 正则表达式为(ABC)+

您可以实现的任何其他模式都可以由这些组成。我们将它们像乐高积木一样组合起来构建图。唯一的问题是，当我们组合它们时，必须将前一个接受状态变为非接受状态，然后为最终机器创建一个新的接受状态。重复此过程，嵌套以组合图。

注意那些灰色的状态，它们只有一个指向外部的虚线。这些是*中性*状态。它们实际上不会改变机器接受的内容，但在Thompson构造过程中引入了它们。没关系，因为一旦我们将其转换为DFA，它们就会被消除。

*最终*状态是指没有外向转移的状态。通常，这些状态也是接受状态。

这些有限状态机是我们正则表达式引擎的核心。

子集构造，再次强调，是将NFA转换为DFA的方法。我们喜欢这样做，因为DFA更有效率，我们稍后会看到。基本上，我们需要找出所有可能的状态组合。每个可能的状态集合大致对应一个DFA状态。例外情况是当不可能的情况下，两个状态在相同的输入上转移到不同的目标状态。这时，我们将需要将路径克隆N-1次，其中N是冲突的数量。这不容易解释，也不是特别容易编写。希望几张图能有所帮助。

图表显示了右侧的NFA，左侧显示了DFA状态由哪些源状态组成。您会看到每个状态都包含其他几个状态。但有时，在正确——或者说错误——的情况下，几个状态可能会产生更多状态。请注意，子集构造有时会产生重复的状态，可以通过优化过程将其删除。

使用应用程序

安装GraphViz（确保将其添加到PATH）后，您可以启动FSM Explorer应用程序。

在顶部的文本框中输入正则表达式。然后，正则表达式将分别转换为NFA和DFA，并在应用程序中显示。当前状态（或状态）会以绿色高亮显示。随着您输入内容，当前状态（或状态）会发生变化。

请注意，DFA未经过优化。由于所使用的算法，消除重复状态会阻止显示子集构造。子集构造是上图的状态列表，它们构成了下图中的状态。每个集合都列在与之关联的DFA状态中。

您可以选择查看优化后的DFA，而不是同时查看NFA和DFA。

历史

• 2023年12月21日 - 首次提交
• 2023年12月22日 - 添加了查看优化DFA的选项
• 2024年1月2日 - API改进和错误修复