这是一个创建于 866 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题，比如用|分隔了 2000 种情况。。
 |
1
justnull 2021-12-16 13:06:29 +08:00 via Android
正则表达式实现一般是编译到状态机，所以
|
|
2
justnull 2021-12-16 13:07:10 +08:00 via Android
所以如果状态机遇到死循环是有可能超时的
|
|
3
justnull 2021-12-16 13:12:25 +08:00 via Android
至于状态太多，那得看具体实现，如果说|分隔 2000 种情况我觉得不会出问题
|
|
4
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/ |
|
5
justnull 2021-12-16 13:25:14 +08:00 via Android
此外，使用 NFA 而不是 DFA 还有一个重要原因是为了支持更多的特性
|
|
6
justnull 2021-12-16 13:27:37 +08:00 via Android
TLDR：是的，滥用正则表达式可以造成机器瘫痪，如灾难性回溯(Catastrophic Backtracking)导致耗尽 CPU 资源，要触发这种陷阱只需很短的输入即可，不需要构造很长的表达式和输入
|
 |
7
dingwen07 2021-12-16 13:28:09 +08:00 via iPhone
正则只要编译成确定有限状态自动机（ DFA ）之后，匹配字符串就只需要线性时间。
至于 regex 如何转换成 DFA ，常见的算法是先转 NFA 然后再转 DFA ，似乎需要指数时间。 |
|
8
justnull 2021-12-16 13:29:07 +08:00 via Android
如果正确使用正则表达式，理想情况下编译好的正则表达式的匹配时间与输入字符串长度成正比
|
 |
9
lithiumii 2021-12-16 13:32:20 +08:00  2
cloudflare 就被自己的一条正则打趴下过
https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/ 那条正则是 (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) |
|
13
justnull 2021-12-16 20:00:59 +08:00 via Android 2
@efaun 好吧，理解了这个系统。注册账户只是顺手回复一些力所能及的问题而已，没有关注过本站机制
|
 |
14
LeeReamond OP @justnull 感谢答疑
|
Select Language