Foreword
国庆前夕，编译原理的老师留了一个论文Research并制作slides展示的作业，这篇论文是2007年Russ Cox的大作，大概讲的是正则表达式的安全、效率、兼容性等问题之间的权衡。他对Perl、Python以及Java使用的正则语言匹配算法感到十分的不满，并且提出一个融合两种算法的解决方案，令人不禁联想到年迈且威严的白发老教授。一搜才了解到，Russ Cox在2008年才在MIT获得博士学位，也就是说他在校期间提出了如此深刻的问题。对于笔者而言，笔者最震撼的点就是这篇论文像是一记回旋镖，让人不得不佩服其前瞻性的科研视野。
slides都做出来了，笔者干脆物尽其用产出一篇分享博客吧，同时笔者会持续拜读，因为一天短时间内的阅读深度肯定是不够的，如有偏颇，欢迎指正。
实际上无论您是否从事这个行业，我们每个人每天都在与正则表达式打交道，用它验证邮箱、提取URL、清理数据……它就像是字符串处理领域的瑞士军刀，强大而便捷。但笔者如果说就是在这种场景下的一个看上去简单的正则表达式会让你的程序卡死、CPU飙升，您会怎么想？这其实就是这个经典故事的序章。
Suspense：60s vs 20μs？
这是来自RSC论文中真实的测试：用同一个“病态”的正则表达式（形如 a?ⁿaⁿ）去匹配一个不到30个字符的字符串。
- 在Perl（以及Python、Java等多数主流语言）的回溯引擎中，这个任务耗时超过60秒。
- 而在一个基于Thompson NFA理论的引擎中，完成它仅需20微秒。
这不是简单的性能差异，这是百万倍量级的鸿沟。是什么导致了如此戏剧化的结果？答案在于，驱动这两种场景的，是两种思想截然不同的算法引擎。
Two Approaches: Explorer vs. Flood
主角登场（当当当当）（大声
左边是回溯法 (Backtracking Engine)，我们可以把它想象成一个在复杂迷宫中探索的探险家。当遇到岔路口（比如 | 或 ?），他只能选择一条路前进。如果这条路是死胡同，他唯一的选择就是原路返回（Backtrack），然后尝试下一条未走过的路。这是一种“试错与回退”的策略，其核心是追踪路径。
右边是有限自动机法 (Finite Automata Engine)，它的思维方式如同洪水。从入口开始，洪水会同时涌入所有相连的通道，并行地探索所有可能性。它不关心“哪条路径是正确的”，只关心在任何时刻“水淹没了哪些地方”。这是一种“并行推进”的策略，其核心是追踪状态。
The Nightmare of Backtracking: The Trap of Exponential Paths
那么，探险家式的回溯法为什么会陷入困境？让我们通过一个简化的例子来看看它的工作流程。
假设我们用正则表达式 a?a?a?a 去匹配字符串
a。回溯法的引擎天性“贪婪”，它会优先尝试匹配尽可能多的字符。
- 第一次尝试：引擎遇到第一个
a?，它会选择匹配字符a。此时，字符串a被消耗完毕。但正则表达式后面还有a?a?a需要匹配，此路不通，宣告失败。 - 回溯与再尝试：引擎不会放弃。它会退回到上一个选择点，做出不同的选择。它会尝试“第一个
a?不匹配，第二个a?匹配a”，结果再次失败。 - 最终的成功：在经历了多次失败的回溯后，引擎最终会找到那条唯一正确的路径：前两个
a?都不匹配任何字符，最后的a与字符串a成功匹配。
在这个简单的例子中，引擎需要探索多种可能性。而当我们面对像 a?¹⁵a¹⁵ 这样的表达式时，需要尝试的错误路径数量会暴增到 2¹⁵-1，即 32,767 条！这就是所谓的“灾难性回溯”，也是指数级复杂度的根源。
God's-eye view of automata: One traversal, tracking all possibilities
相比之下，有限自动机（NFA）引擎的处理方式则显得优雅而高效。
它从不猜测，也从不回头。在读取输入字符串的每一个字符时，它都会并行地计算出从当前所有可能的状态，能够转移到的下一组全新的状态集。
整个过程就像动画里展示的那样，状态被一波一波地“点亮”。无论有多少条路径汇合到同一个状态，NFA引擎都只将其视为状态集中的一个元素。
这种方法的关键优势在于：
- 文本只被读取一遍。
- 计算的复杂度只与状态的数量（与正则表达式长度成正比）有关，而与路径的数量（可能是指数级）无关。
Core Difference: Path vs. State
现在，我们可以清晰地总结这两种算法的根本区别了。
- 回溯法 关注的是“如何到达？”。它通过探索一条条独立的路径来寻找答案，因此受限于路径数量的爆炸式增长，最坏情况下的时间复杂度是 O(2ⁿ)。
- 有限自动机法 关注的是“能到达哪里？”。它通过维护一个状态集合来追踪所有可能性，因此性能稳定可预测，时间复杂度始终在多项式级别，如 O(n²)。
The Cost of Trade-offs: Functionality vs. Performance
看到这里，你一定会问：既然自动机法如此高效和稳定，为什么我们日常使用的Python、Java等主流语言，反而都选择了那个“慢速”的回溯引擎呢？
答案在于一个功能与性能之间的经典权衡。这个权衡的核心，是一个叫做反向引用 (Backreferences) 的强大功能。
反向引用（如
\1）允许正则表达式引用前面捕获组匹配到的具体文本内容。例如，\b(\w+)\s+\1\b
可以精确地匹配到重复的单词，如 "the
the"。这种能力需要引擎“记住”任意长度的字符串，这超出了有限自动机“状态有限”的数学模型能力。
然而，回溯引擎的程序化搜索机制，可以轻易地用变量来存储和比较这些捕获到的文本。
因此，现代主流语言的设计者们做出了一次历史性的权衡：为了获得反向引用等强大的功能（如同瑞士军刀），他们牺牲了引擎在最坏情况下的性能与安全（如同火箭的速度）。
Reflections and Insights: Rebuilding on the Ruins of “Good Enough”
至此，我们已经清晰地看到了正则表达式背后那两条截然不同的技术路径。一条是充满妥协、背负着历史包袱但功能强大的“回溯之路”；另一条则是理论完美、性能如磐石般稳固的“自动机之路”。
我们不禁要问，为什么像Python、Java这些拥有庞大生态的语言巨头，明知“自动机之路”在安全和性能上更优，却依然选择在“回溯之路”上蹒跚前行？
答案复杂而沉重：向后兼容性的枷锁。在一个拥有数百万行存量代码、无数开发者已经习惯了现有行为的“屎山”生态中，任何颠覆性的改变都无异于一场地震。推倒重来的成本是如此之高，以至于“足够好”的现状成了无法撼动的铁律。我们似乎陷入了一个工程上的“局部最优解”，为了维护过去的兼容性，而牺牲了未来的可能性。
然而，这真的是唯一的答案吗？
让我们把目光投向这篇文章的作者——Russ Cox。作为贝尔实验室的传承者，Plan 9的开发者，以及后来Go语言的技术领袖，他的职业生涯本身就是对这个问题的一种回答。他与Ken Thompson, Rob Pike等前辈一样，深受Unix哲学的熏陶：做一件事，并把它做好；追求简单、清晰和可预测性。
当他们从零开始创造Go语言时，他们没有历史的包袱。在设计Go的regexp库时，Russ Cox毫不犹豫地选择了那条“少有人走的路”——基于RE2和有限自动机理论，确保了所有正则表达式的线性时间性能，默认免疫ReDoS攻击。他没有为了迎合所谓的“事实标准”而去支持反向引用，而是做出了一个基于第一性原理的、在技术上“正确”的选择。
这不仅仅是一个技术决策，这是一种勇气。一种敢于对历史惯例说“不”的勇气，一种相信“更好的设计”终将被认可的勇气，一种在看似“足够好”的废墟之上，推倒重来、构建更坚固大厦的勇气。
我们中的大多数人，或许没有机会去创造一门新的语言。我们日常的工作，就是在已有的庞大系统中添砖加瓦。但是，Russ Cox和Go语言的故事提醒我们：
- 永远不要停止对“第一性原理”的思考。 当我们面对一个“约定俗成”的实践时，要敢于追问：它在今天，在我们的场景下，依然是最好的选择吗？
- 在自己的能力范围内，做出“正确”而非“容易”的选择。 也许我们无法改变整个生态，但我们可以在项目中选择使用更安全的第三方库（如Python的re2），可以在代码审查中指出潜在的性能风险，可以在团队内部分享这些被遗忘的“简单而快速”的智慧。
- 认识到“屎山”并非永恒。 技术的演进总是在不断地“扬弃”中前行。新的语言（如Rust）、新的框架、新的工具正在涌现，它们之所以能获得青睐，正是因为它们在某些关键问题上，勇敢地抛弃了历史包袱。
正则表达式的故事，从一个“理论指导实践”的光辉典范，到后来“无视理论导致坏程序”的普遍现实，再到如今新一代工具的“价值回归”，它就像一面镜子，映照出软件工程领域永恒的博弈：在复杂性、兼容性、性能和简单性之间，我们究竟该如何抉择？
或许，并没有唯一的答案。但下一次，当你面对一个看似无法撼动的“历史问题”时，希望你能想起那个关于正则表达式的古老智慧，和那份推倒重来的勇气。
没错，坚持到底是勇气，从头来过也是勇气，而站在科学边缘的年轻人们——我们从不缺乏勇气。
感谢阅读。
话说Russ Cox也是神人，个人网页简洁得像张A4纸的情况下，最上面的是两个冷笑话，放在最后一起品味一下：
A C, an E-flat, and a G walk into a bar. The bartender says, “Sorry, but we don't serve minors.”
What's grey? A melted penguin.
If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !