source: https://swtch.com/~rsc/regexp/regexp1.html
translated by trav, travmymail@gmail.com
下图是两种正则匹配算法的对比图，其中左边的是许多语言都作为标准使用的算法，而右边的算法则鲜为人知，它是多个版本的awk和grep程序所使用的算法。这两种算法有着惊人的不同表现：
注意到Perl需要大约60秒的时间来匹配长度为29的字符串，而Thompson NFA算法只需要20微秒，两者相差了上百万倍。不仅如此，两者的差距还在继续增长，Thompson NFA算法处理长度为100的字符串只需要不到200微秒，而Perl则需要超过10^15年。（Perl语言只是诸多语言的一个典例，其他包括Python、PHP或Ruby等更多语言的表现都是如此）
这可能非常令人难以置信，也许你在使用Perl的时候并没有发现它表现得如此糟糕。实际上，Perl在大多数情况下已经足够快了，但是当我们拿出丧心病狂的正则表达式来测试Perl的时候，它可以变得异常的慢。相比之下，Thompson NFA算法并感觉不到任何不适。看到这样的对比，你很可能会产生疑问：“为什么Perl不使用Thompson NFA算法呢？”其实Perl可以这样做，也应该这样做，这就是本篇文章要探讨的。
在历史上，正则表达式是一个展示“好的理论产生好的程序”的好例子。计算机理论学家们原本只是将正则表达式作为验证理论的计算模型，但是Ken Thompson在他为CTSS编写的QED文本编辑器里实现了正则表达式，并且把它带入了程序员的世界。Dennis Ritchie同样也在他为GE-TSS编写的QED里实现了正则表达式。Thompson和Ritchie在他们合作制造的Unix里也不忘携带着正则表达式。正则表达式作为Unix系统的关键成员，存在于ed, sed, grep, egrep, awk和lex这些著名的工具中。
在今天，正则表达式同样也是一个展示“忽视理论能做出多差的程序”的典例。今天大多数实现正则表达式的算法比起许多已存在30多年的Unix工具不知道要慢几个数量级。
本文回顾了一些很好的理论：正则表达式、有限自动机以及Thompson于19世纪60年代中期提出的正则表达式搜索算法，并且理论联系实际，描述了一个少于400行的C语言的Thompson算法的实现，这个版本就是上图与Perl进行比较的版本。本文最后讨论了如何在现实世界中将理论转化为实践。 正则表达式 正则表达式描述了一组符合某种特定形式的字符串，当一个字符串满足这种特定形式，我们就称其匹配：
最简单的正则表达式是单个字符，字符可以自我匹配，其中有六个操作符*+?()|需要添加反斜杠\进行转义才能匹配。
两个正则表达式可以合并或连接来组成一个新的正则表达式：若e1匹配s，e2匹配t，则e1|e2匹配s或t，则e1e2匹配st。
* + ?是重复操作符：e1*匹配0个或多个e1，e1+匹配1个或多个e1，e1?匹配0个或1个e1。
操作符的优先级为 * > + > ? > 连接 > 合并，其中括号的优先级最高，例如ab|cd等价于(ab)|(cd)，ab*等价于a(b*)。
以上描述的规则是传统的Unix egrep正则表达式规则的最小子集，这个子集已经能够描述所有的正则表达式，当然现在出现了许多新的操作符，这些新的操作符同样能被上述子集描述。本文内容只涉及上述操作符。
有限自动机 另一种描述字符串特征的方式就是有限自动机，有限自动机有时又被称为状态机。以下是描述a(bb)+a的有限自动机：有限自动机由两部分组成，一部分是图中由圆圈表示的状态，另一个部分是连接状态的箭头与箭头上的字符。当有限自动机读入一串字符串时，它会从一个状态转入另一个状态。这种状态机有两种特殊的状态：开始状态s0和终止状态s4。终止状态由双圆圈表示，开始状态由箭头头部指出。
状态机每次从字符串输入流中读取一个字符，并根据箭头方向从一个状态转移到另一个状态。假设读入字符串abbbba，那么状态转移的过程如下：
状态机的结束状态为s4，是终结状态，因此这个字符串被匹配了。如果状态机最终结束的状态不是终结状态，那么就不匹配。如果在字符串匹配过程中，出现了意外的字符导致状态不能继续转移，那么也是不匹配，此时状态机会提早结束了事。
我们上述讨论的是确定的有限自动机（DFA），其特征就是对于某个特定的输入，只有至多一个确定的转移状态。我们也可以制作出不确定的有限自动机（NFA），其特征是对某个特定的输入，其转移状态可能有多个。下图给出一个与之前DFA等价的NFA：
在状态s2时，读入一个字符b，其转移状态可能为s1，也可能为s3，所以这就是不确定自动机。因为自动机无法预测未来，因此它不知道转移到哪种状态才有最正确的选择。在这种情况下，一个有趣的事情就是如何让自动机总是做出正确的选择，或者说是每次都猜对答案。总之，这样的自动机就被称为不确定的有限自动机。
有时候，在NFA中设置无字符的箭头是一件好事。在一个NFA中，一个状态在任何时候都可以顺着无字符的箭头转移到另一个状态。例如下图等价的NFA：
状态s3指向s1的无符号箭头能够更清晰更简单的描述a(bb)+a 正则表达式转为NFA 正则表达式与NFA是完全等价的，一个正则表达式一定有对应的NFA，反之亦然。历史上有非常多种将正则表达式转化为NFA的方法，我们这里描述的方法是由Thompson在1968年的CACM论文中提出的。 一个最终的NFA是由多个部分的局部NFA组合而成的，局部的NFA没有状态转移，而是由一个或多个空箭头表示。最终我们会把这些局部的NFA通过他们的空箭头连接起来。