正则表达式存在最大长度吗？匹配过长的字符串会不会爆炸？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 1065 天前的主题，其中的信息可能已经有所发展或是发生改变。

如题，比如用|分隔了 2000 种情况。。

串会

字符

分隔

长度

14 条回复 • 2021-12-17 10:11:30 +08:00

justnull

2021-12-16 13:06:29 +08:00 via Android

正则表达式实现一般是编译到状态机，所以

justnull

2021-12-16 13:07:10 +08:00 via Android

所以如果状态机遇到死循环是有可能超时的

justnull

2021-12-16 13:12:25 +08:00 via Android

至于状态太多，那得看具体实现，如果说|分隔 2000 种情况我觉得不会出问题

justnull

2021-12-16 13:20:58 +08:00 via Android

自动机的类型可以分为 DFA 和 NFA ，一般来说正则表达式引擎会选择 NFA ，因为 DFA 会存在状态爆炸的问题；但是 NFA 如果错误使用正则表达式，有可能因为回溯导致 CPU 满载
如：blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

justnull

2021-12-16 13:25:14 +08:00 via Android

此外，使用 NFA 而不是 DFA 还有一个重要原因是为了支持更多的特性

justnull

2021-12-16 13:27:37 +08:00 via Android

TLDR：是的，滥用正则表达式可以造成机器瘫痪，如灾难性回溯(Catastrophic Backtracking)导致耗尽 CPU 资源，要触发这种陷阱只需很短的输入即可，不需要构造很长的表达式和输入

dingwen07

2021-12-16 13:28:09 +08:00 via iPhone

正则只要编译成确定有限状态自动机（ DFA ）之后，匹配字符串就只需要线性时间。
至于 regex 如何转换成 DFA ，常见的算法是先转 NFA 然后再转 DFA ，似乎需要指数时间。

justnull

2021-12-16 13:29:07 +08:00 via Android

如果正确使用正则表达式，理想情况下编译好的正则表达式的匹配时间与输入字符串长度成正比

lithiumii

2021-12-16 13:32:20 +08:00

cloudflare 就被自己的一条正则打趴下过

https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

那条正则是

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

efaun

2021-12-16 14:57:48 +08:00

@justnull #6 好家伙, 你这是给楼主送铜币啊

justnull

2021-12-16 19:56:26 +08:00 via Android

@efaun 送铜币是什么？不太懂这个

justnull

2021-12-16 19:57:12 +08:00 via Android

@efaun 发这么多条是因为手滑不小心点了回复

justnull

2021-12-16 20:00:59 +08:00 via Android

@efaun 好吧，理解了这个系统。注册账户只是顺手回复一些力所能及的问题而已，没有关注过本站机制

LeeReamond

2021-12-17 10:11:30 +08:00

@justnull 感谢答疑