我刚刚在Quamina中提交了一个相当大的 PR ，它的作用是启用+和*正则表达式功能。就像我上一章写的那样，这与其说是一篇论文，不如说是一场混乱的战争故事，而且可能不会引起大众的兴趣。但正如我当时所说，那些关心如何让有限自动机大规模地执行有用任务的人，正是我的同道中人（我们有几十个人）。
2014-2026
此刻，我正坐在萨斯喀彻温省母亲家客厅的同一张沙发上，当年我加入 AWS 后的第一个圣诞节，就是在这里，我完成了这款软件的第一个版本。如今，它的雏形已经成熟，以aws/event-ruler 的形式面向全球发布。（感谢 AWS！）Quamina 是它的直接后代，这意味着这个故事已经走过了十二个年头。
妈妈现在95岁了，虽然记忆力衰退，但她仍然是个很好的陪伴。我的人生阶段也比2014年晚了很多，但我仍然想从这片光线昏暗、时常令人痛苦的土地上汇报一下：即使上了年纪，创作抽象作品仍然充满乐趣。
总之，我写这些东西的原因不是为了阐述有限自动机或正则表达式的本质，而是为了分享实现它们的经验教训。
教训：寻找样本
在之前的节目中，我用“样本驱动开发”这个词来形容我找到992个正则表达式测试用例的幸运经历，这让原本令人望而生畏的任务变得触手可及。我以前从未有过这样的好运，能带着大量别人编写的测试用例去投入大型软件开发项目，我强烈推荐大家也这样做。当然，你不可能总是找到这类资源，但一定要尽力去做。
教训：将交付成果拆分
我将正则表达式分解为十个独特的特征，创建了一个枚举类型来标识它们，并逐个实现了这些特征。在后续功能中，一些早期版本采用的技术被证明效率低下甚至完全错误。但它们确实有效，也很有用，而且我的错误几乎都让我吸取了宝贵的经验教训。
话虽如此，这里有一些很棒的输出，它结合了本课和上面的内容，来自运行这些测试用例的单元测试。每个用例都包含一个正则表达式，以及一个或多个应该匹配和不应该匹配的字符串样本。我为测试添加了插桩，以便报告匹配和不匹配情况下正则表达式功能的使用情况。
特征匹配测试计数：
32 '*' 零个或多个匹配器
27 () 括号内的组
48 [] 封闭的字符类匹配器
7'.'单字符匹配器
29 个用 | 分隔的逻辑选项
16'？'可选匹配器
29 '+' 一个或多个匹配器
特征不匹配测试计数：
45'+'一个或多个匹配器
24 '*' 零个或多个匹配器
31 () 括号组
49 [] 封闭的字符类匹配器
6'.”单字符匹配器
32 个用 | 分隔的逻辑选项
21 '?' 可选匹配器
当然，由于大多数测试都结合了多个特征，所以每次我添加新特征时，所有特征的数值都会增加。这非常令人信服。
课程：汤普森构造
这是 Ken Thompson 在 20 世纪 60 年代实现的经典正则表达式，维基百科在此处有相关描述，而 Russ Cox 则以讲故事的方式（至少对我来说）在此处进行了更有用的描述。
有好几次，我都没查阅相关资料就贸然实现了某个功能，心想这能有多难？几乎每次都是初次尝试就出了问题，后来查阅了权威资料后，才发现错在哪里，以及如何改正。
非常感谢Ken和Russ。
课程：列表粉碎
在一些特别棘手的正则表达式中，如果将[]和?和+和*组合在一起，就可以得到多个状态，它们通过 epsilon 连接以复杂的方式连接起来。
在汤普森构造中，遍历一个NFA（非有限自动机）不仅会从一个状态转换到另一个状态，还会从当前状态集转换到下一个状态集，如此循环往复，直到匹配或失败为止。同时，你还会计算ε闭包；这里我略过细节。问题在于，使用足够长的字符串遍历这些极其复杂的正则表达式会导致当前状态和下一个状态的大小呈指数级增长——这不是比喻，而是O(2 N ) 。尽管上面使用了“集合”一词，但实际上它们并非集合，其中包含无数重复项。
最佳方案是研究遍历算法并对其进行改进，使其不再产生大量重复数据。但这很难。次优方案是将这些数据转换为去重后的数据集，但这需要在遍历的关键区域放置一个哈希表，成本会很高。
所以我所做的就是检测后续步骤列表的长度何时超过 N，然后对其进行排序并删除所有重复项。在我撰写本文时，根据基准测试结果并找到一个能使列表长度下降的值，N 现在是 500。
之所以说这是个好的工程设计，是因为需要销毁列表的情况几乎不会发生，所以在绝大多数情况下，唯一的开销就是 ` if len(nextSteps)>N比较。有些人可能会觉得这种方法不够纯粹，他们的观点也有道理。我以后可能会回头寻找更好的上游方案。但就目前而言，它在实践中仍然非常快，所以我可以安心入睡。
教训：地狱的基准
我之前写过关于合并 12,959 个通配符模式的基准测试中遇到的困难。在我正确处理 epsilon 之前，我用了一个蹩脚的实现方法，可以在合并后的 FA 中以 Quamina 的典型速度（每秒数十万个模式）进行匹配。即使有了正确的通用 epsilon 处理方法，我至今也没能找到保持这种性能的方法。使用完整的 13,000 个模式时，Quamina 的匹配速度不到每秒 2,000 个；即使只用一千个模式，速度也只有每秒 16,000 个。我花了整整几天时间试图获得更好的结果，但最终认为，对于 Quamina 来说，正确处理大部分正则表达式比以全速运行极其庞大的合并操作更有价值。
我很确定，只要有足够的时间和精力，我一定能把它做得更好。或许比我更聪明的人能做到。
问：接下来呢？
尚未实现的正则表达式功能包括：
{lo,hi}：出现次数匹配器
~p{}：Unicode 属性匹配器
~P{}：Unicode 属性补码匹配器
[^] : 互补字符类匹配器
现在我在想接下来该做什么。 [^]我觉得挺简单的，而且也挺实用，还能反转状态转换表。 {lo,hi}这个惯用法应该也不难，但我用正则表达式的时间比你们大多数人的年龄都长，从来没觉得需要用到它，所以也没觉得太急。我觉得 Unicode 属性挺有意思的，因为处理 Unicode 字符数据库表挺酷的。而且，我也用过它们。
经验教训：老年人也能编程
我跟别人说我坚持写代码是为了保持精神健康。但其实主要是为了好玩。写代码相关的文章也是一样。谢谢阅读。
原文： https://www.tbray.org/ongoing/When/202x/2026/01/01/Quamina-2026