2025-07-15 · algorithms
正则表达式理论：从形式语言到自动机实现
从乔姆斯基层级、Thompson 构造到 NFA/DFA 与代码实现，系统理解正则表达式背后的理论与工程。
正则表达式（Regex）是文本处理的强大工具，但如果使用不当，它也可能成为系统的隐患。在 Web 服务中，一个设计拙劣的正则表达式可能导致 CPU 飙升至 100%，甚至引发服务雪崩。这种现象通常被称为 ReDOS (Regular Expression Denial of Service)。
本文将从原理出发，结合我在生产环境中遇到的真实案例，探讨如何优化正则性能以及如何防御 ReDOS 攻击。
大多数主流语言（Java, Python, JavaScript, C#, PHP）默认使用的正则引擎都是基于 NFA（非确定性有限自动机） 的回溯算法。
简单来说，当正则引擎在匹配过程中遇到“选择”或“量词”时，它会尝试一条路径。如果这条路径走不通，它会退回到上一个分叉点，尝试另一条路径。
考虑正则表达式 (a+)+b 匹配字符串
aaaaaaaaaaaaaaaaaaaa (20个 a，后面没有 b)。
(a+) 吃掉所有
a。+ 尝试重复，但没字符了。b，但没有
b。a+ 吐出一个
a，外层的 + 尝试再匹配一次…这就是 ReDOS 的原理：攻击者构造一个特定的“恶意字符串”，利用存在缺陷的正则表达式，让服务器陷入死循环般的计算中。
某天下午，我们的日志分析服务突然报警，CPU 持续 100%，处理延迟从毫秒级飙升到分钟级。重启服务后，运行几分钟又重现。
perf
(Linux) 或 pprof (Go) 查看 CPU 热点。发现 CPU
主要消耗在正则匹配函数上。User-Agent: .*(\w+-\w+)+.*意图是匹配类似 Product-Name 这样的字段。
abc-def abc-def ...
但结尾不符合预期。(\w+-\w+)+
是典型的嵌套量词（Nested
Quantifiers）。改为非嵌套形式。.*
换成更具体的 [^ ]*，减少尝试范围。google-re2 库)。RE2
不支持回溯，保证线性时间复杂度，彻底根除了 ReDOS 风险。除了更换引擎，我们在编写正则时也可以遵循以下原则来提升性能：
坏味道： - (a+)+ -
(\w*)* - (a|b)+ (如果 a 和 b
有重叠)
优化： 尽量展开，或者确保内层和外层不会对同一个字符进行“争抢”。
如果你确定匹配了就不需要回吐，可以使用独占模式（Java/PHP
等支持）。 - a++：匹配尽可能多的
a，绝不回溯。 -
(?>...)：原子组，组内的匹配一旦完成，就锁定，不回溯。
注意：Python re
模块默认不支持这些特性，需要第三方库
regex。
尽量使用 ^ (开始) 和 $ (结束)
锚点。
如果正则引擎知道必须从字符串开头匹配，它这就不会在字符串的每个位置都尝试一遍。
.*?
是懒惰匹配。虽然它看起来“匹配得少”，但它可能导致引擎频繁地“匹配-暂停-检查后面-回溯-继续匹配”。在某些情况下，贪婪匹配
.*
配合回溯反而更快（因为它一次性吃掉所有，只在最后回溯一次）。
关键在于：你要匹配的内容在字符串中出现的概率和位置。
正则表达式是强大的，但也是危险的。作为开发者，我们不能只关注“能不能匹配上”，更要关注“匹配失败时会发生什么”。理解回溯原理，是写出高性能、高安全正则的第一步。
把当前热点继续串成多页阅读，而不是停在单篇消费。
2025-07-15 · algorithms
从乔姆斯基层级、Thompson 构造到 NFA/DFA 与代码实现，系统理解正则表达式背后的理论与工程。
2025-11-29 · algorithms
通过交互式动画，直观演示非确定性有限自动机（NFA）匹配字符串的步进过程，揭示正则引擎的内部奥秘。
2025-07-15 · algorithms
现代 CPU 的分支预测器已经非常精准，但当预测失败时代价高昂。无分支编程用算术和位运算消除条件跳转，在特定场景下带来数倍加速。
2025-07-15 · algorithms
补齐可直接执行的 benchmark 代码后，在当前环境重跑 12 种排序算法，并用真实 CSV 数据重画图表。
正则表达式（Regex）是文本处理的强大工具，但如果使用不当，它也可能成为系统的隐患。在 Web 服务中，一个设计拙劣的正则表达式可能导致 CPU 飙升至 100%，甚至引发服务雪崩。这种现象通常被称为 ReDOS (Regular Expression Denial of Service)。
本文将从原理出发，结合我在生产环境中遇到的真实案例，探讨如何优化正则性能以及如何防御 ReDOS 攻击。
大多数主流语言（Java, Python, JavaScript, C#, PHP）默认使用的正则引擎都是基于 NFA（非确定性有限自动机） 的回溯算法。
简单来说，当正则引擎在匹配过程中遇到“选择”或“量词”时，它会尝试一条路径。如果这条路径走不通，它会退回到上一个分叉点，尝试另一条路径。
考虑正则表达式 (a+)+b 匹配字符串
aaaaaaaaaaaaaaaaaaaa (20个 a，后面没有 b)。
(a+) 吃掉所有
a。+ 尝试重复，但没字符了。b，但没有
b。a+ 吐出一个
a，外层的 + 尝试再匹配一次…这就是 ReDOS 的原理：攻击者构造一个特定的“恶意字符串”，利用存在缺陷的正则表达式，让服务器陷入死循环般的计算中。
某天下午，我们的日志分析服务突然报警，CPU 持续 100%，处理延迟从毫秒级飙升到分钟级。重启服务后，运行几分钟又重现。
perf
(Linux) 或 pprof (Go) 查看 CPU 热点。发现 CPU
主要消耗在正则匹配函数上。User-Agent: .*(\w+-\w+)+.*意图是匹配类似 Product-Name 这样的字段。
abc-def abc-def ...
但结尾不符合预期。(\w+-\w+)+
是典型的嵌套量词（Nested
Quantifiers）。改为非嵌套形式。.*
换成更具体的 [^ ]*，减少尝试范围。google-re2 库)。RE2
不支持回溯，保证线性时间复杂度，彻底根除了 ReDOS 风险。除了更换引擎，我们在编写正则时也可以遵循以下原则来提升性能：
坏味道： - (a+)+ -
(\w*)* - (a|b)+ (如果 a 和 b
有重叠)
优化： 尽量展开，或者确保内层和外层不会对同一个字符进行“争抢”。
如果你确定匹配了就不需要回吐，可以使用独占模式（Java/PHP
等支持）。 - a++：匹配尽可能多的
a，绝不回溯。 -
(?>...)：原子组，组内的匹配一旦完成，就锁定，不回溯。
注意：Python re
模块默认不支持这些特性，需要第三方库
regex。
尽量使用 ^ (开始) 和 $ (结束)
锚点。
如果正则引擎知道必须从字符串开头匹配，它这就不会在字符串的每个位置都尝试一遍。
.*?
是懒惰匹配。虽然它看起来“匹配得少”，但它可能导致引擎频繁地“匹配-暂停-检查后面-回溯-继续匹配”。在某些情况下，贪婪匹配
.*
配合回溯反而更快（因为它一次性吃掉所有，只在最后回溯一次）。
关键在于：你要匹配的内容在字符串中出现的概率和位置。
正则表达式是强大的，但也是危险的。作为开发者，我们不能只关注“能不能匹配上”，更要关注“匹配失败时会发生什么”。理解回溯原理，是写出高性能、高安全正则的第一步。
把当前热点继续串成多页阅读，而不是停在单篇消费。
2025-07-15 · algorithms
从乔姆斯基层级、Thompson 构造到 NFA/DFA 与代码实现，系统理解正则表达式背后的理论与工程。
2025-11-29 · algorithms
通过交互式动画，直观演示非确定性有限自动机（NFA）匹配字符串的步进过程，揭示正则引擎的内部奥秘。
2025-07-15 · algorithms
现代 CPU 的分支预测器已经非常精准，但当预测失败时代价高昂。无分支编程用算术和位运算消除条件跳转，在特定场景下带来数倍加速。
2025-07-15 · algorithms
补齐可直接执行的 benchmark 代码后，在当前环境重跑 12 种排序算法，并用真实 CSV 数据重画图表。