javascript - 写了一个假的正则验证URL , 可以卡掉浏览器-PHP中文网问答

微信公众号讲师中心

首页

文章

后端开发 web前端数据库开发工具 php框架常见问题科技 Java 系统教程电脑教程硬件教程手机教程软件教程游戏教程自媒体新闻

专题

后端开发 web前端数据库开发工具 php框架科技 Java 系统教程电脑教程硬件教程手机教程软件教程游戏教程新闻

AI工具

AI 聊天问答 Agent智能体 AI 文本写作 AI 绘画作图 AI 设计工具 AI 视频创作 AI 音频制作 AI 办公学习 AI 编程开发 Prompt指令

学习

大前端后端开发数据库移动端运维开发计算机基础

编程手册

大前端后端开发数据库移动端运维开发计算机基础

下载

js特效网站源码工具下载类库下载网站素材学习资源插件扩展手机/移动开发手机游戏

最近更新

搜索

后端开发 web前端数据库开发工具 php框架常见问题科技 Java 系统教程电脑教程硬件教程手机教程软件教程游戏教程

javascript - 写了一个假的正则验证URL , 可以卡掉浏览器

黄舟 2017-04-11 12:12:24

[JavaScript讨论组]

483

var reg = /^(https?:\/\/)([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/

var url = "https://www.amazon.com/Kipling-BP3872-Ravier-Houndstooth-Multi/dp/B00RUBLS58/ref=s9u_simh_gw_i5?_encoding=UTF8&fpl=fresh&pf_rd_m=ATVPDKIKX0DER&pf_rd_s=&pf_rd_r=8A9F9XHY539KKRA96135&pf_rd_t=36701&pf_rd_p=a6aaf593-1ba4-4f4e-bdcc-0febe090b8ed&pf_rd_i=desktop";


reg.test(url)

在谷歌浏览器下运行

有大神可以指导一下，为什么会卡掉吗？

黄舟

人生最曼妙的风景，竟是内心的淡定与从容！

全部回复(4)

巴扎黑2017-04-11 12:14:24 4楼

console.time('/X(.+)+X/ test');
"==XX=============================".match(/X(.+)+X/);
console.timeEnd('/X(.+)+X/ test');

试试这个，也会卡住。

当然现在我还解释不了，只能先告诉你这个貌似是 NFA 引擎的回溯失控导致的。所以才能用这个方法检测 NFA 和 DFA 了。

NFA 是表达式主导引擎，DFA 则是文本主导引擎，js是传统型NFA。

正则引擎主要可以分为两大类：一种是DFA，一种是NFA。这两种引擎都有了很久的历史(至今二十多年)，当中也由这两种引擎产生了很多变体！于是POSIX的出台产生规范了不必要变体的继续产生。这样一来，目前的主流正则引擎又分为3类：一、DFA，二、传统型NFA，三、POSIX NFA。
DFA 引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。DFA 引擎还可以确保匹配最长的可能的字符串。但是，因为 DFA 引擎只包含有限的状态，所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式。
传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法，以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。