javascript - 用于匹配有限深度嵌套字符串的正则表达式——缓慢、崩溃的行为

Question

我今天在我的文本编辑器(Sublime)中写了一些正则表达式，试图快速找到特定的源代码段，这需要有点创意，因为有时函数调用可能包含更多函数调用。例如，我正在寻找 jQuery 选择器:

$("div[class='should_be_using_dot_notation']");

$(escapeJQSelector("[name='crazy{"+getName(object)+"}']"));

我不认为期望我最喜欢的一种 powertools (regex) 帮助我进行这种搜索是不合理的，但很明显，解析第二位代码所需的表达式会有些复杂，因为是两层嵌套的parens。

我非常精通这个理论，知道这种解析正是上下文无关语法解析器的用途，构建正则表达式可能会占用更多的内存和时间(可能呈指数增长，而不是比 O(n^3) 时尚)。然而，我不希望很快在我的文本编辑器或 Web 浏览器中看到这种功能，我只是想用一个大的讨厌的正则表达式。

从此开始(这匹配零层嵌套括号，并且没有琐碎的空括号):

\$\([^)(]+?\)

这是我想出的一级嵌套括号的样子:

\$\(((\([^)(]*\))|[^)(])+?\)

分解:

\$\(                   begin text
    (                  groups the contents of the $() call
        (\(            groups a level 1 nested pair of parens
            [^)(]*     only accept a valid pair of parens (it shall contain anything but parens)
        \))            close level 1 nesting
        |              contents also can be
        [^)(]          anything else that also is not made of parens
    )+?                not sure if this should be plus or star or if can be greedy (the contents are made up of either a level 1 paren group or any other character)
\)                     end

效果很好!但是我需要多一层嵌套。

我开始在我的编辑器中输入两级嵌套表达式，当我输入 * 时它开始暂停 2-3 秒。

所以我放弃了，转到了 regextester.com，不久之后，整个浏览器选项卡都被卡住了。

我的问题有两个方面。

1. 构建任意级别正则表达式的好方法是什么？这是只有人类模式识别才能实现的目标吗？在我看来，我可以获得大量直觉，了解如何根据前两个嵌套的相似性使正则表达式能够匹配两个嵌套级别。我认为这可以提炼成一些“指南”。

2. 为什么对非庞大的正则表达式进行正则表达式解析会阻塞或卡住这么长时间？

我知道 O(n) 线性时间是针对 n 的，其中 n 是运行正则表达式的输入长度(即我的测试字符串)。但是在每次我向其中输入新字符时它都会重新编译正则表达式的系统中，什么会导致它卡住？这一定是 regex 代码中的错误吗(我希望不是，我认为 Javascript regex impl 非常可靠)？我从我的编辑器转移到不同的正则表达式测试器的部分原因是我不再在所有 ~2000 行源代码上运行它(在每个按键上)，但它并没有阻止整个环境锁定，因为我编辑了我的正则表达式。如果正则表达式中更改的每个字符都对应于表示该表达式的 DFA 中的某个简单转换，那将是有意义的。但事实并非如此。如果在正则表达式中添加星号会产生特定的指数时间或空间后果，则可以解释这种超慢更新行为。

与此同时，我将手动处理下一个更高级别的嵌套正则表达式，并在我准备好测试它们时将它们复制到字段中...

Answer 1

嗯。好的，所以没人想写答案，但基本上这里的答案是

Backtracking

当你做某些非贪婪的事情时，它会导致指数级的运行时间。

我问题第一部分的答案:

二嵌套表达式如下:

\$\(((\(((\([^)(]*\))|[^)(])*\))|[^)(])*\)

进行下一个嵌套表达式的转换是用 ((\([^)(]*\))|[^) 替换 [^)(]* 的实例(])*，或者，作为元正则表达式(其中替换部分不需要转义):

s/\[^\)\(\]\*/((\([^)(]*\))|[^)(])*/

这在概念上很简单:在匹配 N 层嵌套的表达式中，如果我们用匹配多一层嵌套的东西替换禁止更多嵌套的部分，那么我们得到 N+ 的表达式1 层嵌套!