1

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

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

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

我不认为期望我最喜欢的 powertools（正则表达式）之一来帮助我进行这种搜索是不合理的，但很明显，解析第二段代码所需的表达式会有些复杂，因为有两个级别嵌套的括号。

我对理论非常精通，知道这种解析正是上下文无关语法解析器的用途，并且构建正则表达式可能会占用更多的内存和时间（可能是指数而不是 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

这很好用！但我需要多一层嵌套。

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

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

我的问题有两个。

  1. 构建任意级别正则表达式的好方法是什么？这是只有人类模式识别才能实现的目标吗？在我看来，对于如何使正则表达式能够根据前两者之间的相似性匹配两级嵌套，我可以得到很多直觉。我认为这可以简化为一些“指南”。

  2. 为什么对非大量正则表达式进行正则表达式解析会阻塞或冻结这么长时间？

我知道 O(n) 线性时间是针对 n 的，其中 n 是运行正则表达式的输入长度（即我的测试字符串）。但是在每次我输入一个新字符时它都会重新编译正则表达式的系统中，什么会导致它冻结？这是否一定是正则表达式代码中的错误（我希望不是，我认为 Javascript 正则表达式 impl 非常可靠）？我从编辑器转向不同的正则表达式测试器的部分原因是，我将不再在所有约 2000 行源代码上运行它（在每个按键上），但它并没有阻止整个环境锁定，因为我编辑了我的正则表达式。如果正则表达式中更改的每个字符都对应于代表该表达式的 DFA 中的一些简单转换，那将是有意义的。但情况似乎并非如此。

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

4

2 回答 2

1

要匹配任意数量的嵌套()，每个嵌套级别只有一对，您可以使用以下内容，更改为您需要2的任何数量的嵌套()

/(?:\([^)(]*){2}(?:[^)(]*\)){2}/

为避免过度回溯，您需要避免使用嵌套量词，尤其是当内部交替两侧的子模式能够匹配相同的子字符串时。

于 2013-04-17T19:55:00.927 回答
1

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

回溯

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

我的问题第一部分的答案：

两嵌套表达式如下：

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

[^)(]*制作下一个嵌套表达式的转换是替换with的实例((\([^)(]*\))|[^)(])*，或者，作为元正则表达式（其中 replace-with 部分不需要转义）：

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

这在概念上很简单：在匹配 N 层嵌套的表达式中，如果我们将禁止更多嵌套的部分替换为匹配更多嵌套层的内容，那么我们将得到 N+1 层嵌套的表达式！

于 2013-04-17T19:44:08.780 回答