为正则表达式编写解析器

Answer 1

This paper采用了一种有趣的方法。这个实现是在Haskell中给出的，但至少已经reimplemented in Python过一次。

Answer 2

编写正则表达式引擎的实现确实是一项相当复杂的任务。

但是，如果您对如何实现它感兴趣，即使您无法理解足够的细节来实际实现它，我建议您至少看看这篇文章：

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)

它解释了有多少流行的编程语言以一种对某些正则表达式来说可能非常慢的方式实现正则表达式，并解释了一种稍有不同但速度更快的方法。本文详细介绍了所提出的实现的工作原理，包括C语言中的一些源代码。如果您刚刚开始学习正则表达式，可能会读得比较重，但我认为了解这两种方法之间的区别是非常值得的。

Answer 3

我已经给了Mark Byers一个+1，但据我所知，除了解释为什么一种算法不好，另一种算法好得多之外，这篇论文并没有真正说明正则表达式匹配是如何工作的。也许有什么联系？

我将重点介绍好的方法——创建有限自动机。如果你把自己限制在没有最小化的确定性自动机上，这并不太困难。

我将（很快）描述在Modern Compiler Design中采用的方法。

假设您有以下正则表达式。。。

a (b c)* d

字母表示要匹配的文字字符。*是通常的零次或多次重复匹配。基本思想是基于点规则导出状态。状态0，我们将把它作为还没有匹配的状态，所以点在前面。。。

0 : .a (b c)* d

唯一可能的匹配是“a”，所以我们得到的下一个状态是。。。

1 : a.(b c)* d

我们现在有两种可能-匹配“b”（如果至少有一个重复的“b c”）或匹配“d”。注意-我们基本上在这里做有向图搜索（深度优先或广度优先或其他），但我们在搜索时发现了有向图。假设采用广度优先的策略，我们需要将其中一个案例排成一个队列，以便以后考虑，但从现在开始，我将忽略这个问题。不管怎样，我们发现了两个新的州。。。

2 : a (b.c)* d
3 : a (b c)* d.

状态3是结束状态（可能有多个）。对于状态2，我们只能匹配“c”，但之后需要小心点的位置。我们得到“a（b c）*d”-这与状态1相同，所以我们不需要新的状态。

IIRC，现代编译器设计中的方法是在你碰到一个操作符时翻译一个规则，以简化对点的处理。状态1将转换为。。。

1 : a.b c (b c)* d
    a.d

也就是说，您的下一个选择是匹配第一个重复或跳过重复。接下来的状态相当于状态2和3。这种方法的一个优点是，您可以丢弃所有过去的匹配项（在“.”之前的所有项），因为您只关心将来的匹配项。这通常会给出一个较小的状态模型（但不一定是最小的）。

编辑如果确实放弃已匹配的详细信息，则状态描述是从此时开始可能出现的字符串集的表示。

就抽象代数而言，这是一种集闭包。代数基本上是一个有一个（或多个）算子的集合。我们的集合是状态描述，我们的操作符是转换（字符匹配）。闭集是将任何运算符应用于该集中的任何成员时，始终生成该集中的另一个成员的集合。集合的闭包是被闭包的最小的大集合。因此，基本上，从明显的开始状态开始，我们正在构造相对于我们的转移算子集是封闭的最小状态集-最小可达状态集。

这里Minimal指的是闭包过程-可能有一个较小的等价自动机，通常称为Minimal。

考虑到这一基本思想，不难说“如果我有两个状态机代表两组字符串，如何派生出第三个表示并集”（或交集，或集合差分…）。与点式规则不同，状态表示将是来自每个输入自动机的当前状态（或一组当前状态），可能还有其他详细信息。

如果你的常规语法变得复杂，你可以最小化。这里的基本思想相对简单。你把所有的状态归为一个等价类或“块”。然后，您反复测试是否需要针对特定的转换类型拆分块（状态实际上并不相等）。如果一个特定块中的所有状态都可以接受相同字符的匹配，并且在这样做时，到达相同的下一个块，则它们是eq单价。

Hopcrofts算法是处理这一基本思想的有效方法。

关于最小化的一个特别有趣的事情是，每一个确定性有限自动机都有一个精确的最小形式。此外，Hopcrofts算法将生成该最小形式的相同表示，无论它从哪个更大的情况开始的表示。也就是说，这是一个“规范”表示，可用于派生散列或任意但一致的顺序。这意味着可以使用最小自动机作为容器的键。

上面的WRT定义可能有点草率，所以在自己使用之前一定要自己查找任何术语，但是如果运气好的话，这会很快介绍基本概念。

顺便说一下-看看Dick Grunes site的其余部分-他有一本关于解析技术的免费PDF书籍。现代编译器设计的第一版在IMO中相当不错，但是正如您将看到的，第二版即将推出。