编写正则表达式解析器
即使编程多年，我也很羞愧地说，我从来没有真正完全理解过正则表达式。一般来说，当遇到需要用到正则表达式的问题时，我通常可以（经过一番查阅语法）想出一个合适的表达式，但我发现自己越来越频繁地使用这种技巧。
所以，为了更好地学习和理解正则表达式，我决定做我每次学习新东西时都会做的事情；也就是尝试写一些雄心勃勃的东西，虽然我可能一旦觉得学得差不多就会放弃。
为此，我想在Python中写一个正则表达式解析器。在这里，“学得差不多”意味着我想实现一个能够完全理解Perl扩展正则语法的解析器。不过，它不需要是最有效的解析器，甚至不一定要在现实中可用。它只需要能够正确匹配字符串中的模式，或者在不匹配时能正确失败。
我的问题是，我该从哪里开始呢？我几乎对正则表达式是如何被解析和解释的了解不多，除了知道它在某种程度上涉及到有限状态自动机。对于如何应对这个看起来很艰巨的问题，任何建议都将非常感谢。
编辑：我应该澄清一下，虽然我打算在Python中实现这个正则解析器，但我对示例或文章使用什么编程语言并不太在意。只要不是Brainfuck，我应该能理解足够的内容，让我觉得值得一试。
5 个回答
这篇文章《正则表达式的一个新玩法：功能珍珠》采用了一种有趣的方法。虽然它的实现是用Haskell语言写的，但至少已经在Python中重新实现过一次。
这个程序是基于一种老技术，把正则表达式转换成有限自动机，这样做让它在最坏情况下的时间和空间使用上都很高效，实际表现也不错。尽管实现很简单，但这个Haskell程序的性能可以和最近发布的专业C++程序相媲美，解决同样的问题。
我之前已经给Mark Byers点赞了，但我记得那篇论文并没有详细说明正则表达式匹配是怎么工作的，只是解释了为什么某个算法不好，而另一个算法更好。也许可以看看链接里的内容？
我会重点讲讲一个好的方法——创建有限自动机。如果你只限于确定性自动机，并且不进行最小化，这其实并不太难。
我将（非常快速地）描述一下《现代编译原理》中的方法。
想象一下你有以下的正则表达式……
a (b c)* d
这些字母代表要匹配的字符。*表示可以匹配零次或多次。基本的想法是根据点状规则推导状态。我们把状态零看作是还没有匹配任何东西的状态，所以点放在最前面……
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是一样的，所以我们不需要一个新状态。
如果我没记错的话，《现代编译原理》中的方法是在遇到操作符时翻译规则，以简化点的处理。状态1会被转换为……
1 : a.b c (b c)* d
a.d
也就是说，你的下一个选择是匹配第一次重复，或者跳过这次重复。从这里得到的下一个状态相当于状态2和状态3。这种方法的一个好处是你可以丢弃所有之前的匹配（点之前的所有内容），因为你只关心未来的匹配。这通常会产生一个更小的状态模型（但不一定是最小的）。
编辑 如果你丢弃了已经匹配的细节，你的状态描述就是从这一点开始可能出现的字符串集合的表示。
从抽象代数的角度来看，这是一种集合闭合。代数基本上是一个带有一个（或多个）操作符的集合。我们的集合是状态描述，而我们的操作符是我们的转换（字符匹配）。闭合集合是指对集合中的任何成员应用任何操作符，总是会产生另一个在集合中的成员。集合的闭合是最小的更大集合，它是闭合的。所以基本上，从明显的起始状态开始，我们正在构建相对于我们的转换操作符的最小闭合状态集合——可达状态的最小集合。
这里的最小是指闭合过程——可能存在一个更小的等价自动机，通常称为最小的。
有了这个基本想法，就不难说“如果我有两个状态机代表两组字符串，我该如何推导出一个代表它们并集的第三个状态机”（或者交集、集合差等……）。你的状态表示将是来自每个输入自动机的当前状态（或当前状态集合）以及可能的额外细节。
如果你的正则文法变得复杂，你可以进行最小化。这里的基本想法相对简单。你将所有状态分组到一个等价类或“块”中。然后你反复测试是否需要根据特定的转换类型拆分块（状态实际上并不等价）。如果某个块中的所有状态都能接受同一个字符的匹配，并且在这样做时到达同一个下一个块，它们就是等价的。
Hopcroft算法是一种高效处理这个基本想法的方法。
关于最小化，有一个特别有趣的地方是，每个确定性有限自动机都有一个精确的最小形式。此外，Hopcroft算法无论从哪个更大的案例开始，都将产生相同的最小形式表示。也就是说，这是一种“规范”表示，可以用于推导哈希值或任意但一致的排序。这意味着你可以使用最小自动机作为容器的键。
以上内容可能在定义上有点粗糙，所以在自己使用之前，确保查阅一下相关术语，但希望这能给你一个基本概念的快速介绍。
顺便说一下，看看Dick Grune的网站，他有一本关于解析技术的免费PDF书。个人认为《现代编译原理》的第一版相当不错，但正如你所看到的，第二版即将发布。
写一个正则表达式引擎的实现确实是个相当复杂的任务。
不过，如果你对怎么做这个感兴趣，即使你对细节理解得不够深入，无法真正实现它，我还是建议你至少看看这篇文章：
正则表达式匹配可以简单又快速 （但在Java、Perl、PHP、Python、Ruby等语言中会比较慢）
这篇文章解释了许多流行编程语言是如何实现正则表达式的，为什么有些正则表达式会运行得很慢，同时也介绍了一种稍微不同的方法，这种方法运行得更快。文章中还包含了一些关于提议实现的细节，包括一些C语言的源代码。如果你刚开始学习正则表达式，可能会觉得这篇文章有点难，但我认为了解这两种方法之间的区别是非常值得的。