RegEx调试

Question

我正在通过两个单独的调试工具调试^(A+)*B一个字符串上的正则表达式AAAC(例如来自rexegg.com):我有权访问:

1. regex101.com
2. RegexBuddy v4

以下是结果(左侧的regex101):

我的问题主要不在于对我来说同样重要的步骤数量,而是回溯的方式.为什么我们看到差异？(regex101使用PCRE lib并且我将RegexBuddy lib设置为相同)

全面的逐步解释对我有利.

Answer 1

TL; DR

简而言之,"回溯"是指正则表达式引擎返回"灵活"匹配,尝试不同路径以获得成功匹配.

用交替回溯

例如,在以下模式和输入中:

foo(bar|baz)

foobaz

正则表达式引擎将匹配"foo",然后尝试两个选项中的第一个,匹配"b"然后匹配"a",但是在"r"处失败.然而,它不会使整个比赛失败,而是"倒带"并从第二个选择开始,匹配"b"然后"a"然后"z"......成功!

用量词回溯

这也适用于量词.量词是任何鼓励发动机以匹配重复图案,其中包括?,*,+和{n,m}(取决于发动机).

贪婪量词(默认值)将匹配尽可能多的重复次数,然后再转到模式的其余部分.例如,给定下面的模式和输入:

\w+bar

foobar

模式\w+将通过匹配整个字符串开始:"foobar".但是,当它移动到时b,正则表达式引擎已到达输入的末尾并且匹配失败.引擎将不再简单地放弃,而是要求最后一个贪婪的量词放弃其中一个重复,现在匹配"fooba".匹配仍然失败,因此引擎要求\w+放弃"a"(失败),然后是"b".放弃"b"后,引擎现在可以匹配bar,并且匹配成功.

树木和回溯

另一种思考正则表达式的方式是作为"树",并且回溯正在返回节点并尝试另一条路径.鉴于模式foo(bar|baz)和输入"foobaz",引擎将尝试类似以下内容:

foo(bar|baz)
|\
| \
|  : f (match)
|  : o (match)
|  : o (match)
|  | (bar|baz)
|  |\
|  | \
|  |  : b (match)
|  |  : a (match)
|  |  : r (FAIL: go back up a level)
|  |  ^
|  |\
|  | \
|  |  : b (match)
|  |  : a (match)
|  |  : z (match)
|  | /
|  |/
| /
|/
SUCCESS

计算"回溯"

至于为什么你看到回溯的"数量"的差异......这可能与内部优化和日志记录级别有很大关系.例如,RegexBuddy似乎没有将匹配记录到空字符串之前^,而regex101确实如此.但是,最后,只要你得到相同的结果,你回溯的确切顺序(你爬回树的顺序)并不重要.

邪恶的正则表达

你已经知道了这一点,但为了其他任何人的利益,你的正则表达式被编写为演示" 灾难性的回溯 "(又名"邪恶的正则表达式"),其中回溯尝试的数量随着输入的长度增加而呈指数增长.这些正则表达式可以被利用来执行DoS攻击,所以你必须小心不要将这些引入你的模式(我发现).

Answer 2

我不会依赖于步数或任何调试作为
回溯或失败的测试.

一般来说,远离简单的构造,例如(A+)*不仅要
回溯内部,A+还要回溯到外部(..)*.外线的
每次传球都会产生一个新的(新)内部回溯系列.

获得一个很好的基准软件,如RegexFormat,
并测试一系列的指数时间结果.
当内容增加相同的
量时,线性结果就是您要查找的内容.

以下是(A+)?vs的一个例子(A+)*.我们将目标设置为已知故障
并稳定地增加长度以扩展该故障的处理.

如果你看一下正则表达式2,(A+)*你会注意到只有
三个目标增长的指数增长.
最后,我们吹出目标来重载引擎的内部资源.

编辑:经过一些分析后,我在回溯步骤上发布了一个微薄的结论.
通过分析下面的基准时间,回溯似乎是一个 2 ^ N的过程.
其中 N是失败时回溯的字符文字数.

鉴于Revo的简单案例,隔离回溯更容易一些.
因为看起来总时间的%98只涉及回溯.

给定该假设,可以从2个点获取时间结果,并生成方程.

我使用的等式的形式是f(x) = a * r^x.
给定坐标('A'与时间的对应关系),使用
生成这个的点(7,1.13),(9,4.43),这f(x) = 0.009475 * 1.9799 ^ x
实际上就是# sec's = 0.009475 * 1.9799 ^ # letters
我将下面基准的所有字母'A'运行到这个公式中.

#LTR's   Bench Time
 7         1.13
 9         4.43
13        70.51

这产生了确切的基准时间(+/- .1%).

然后我看到1.9799非常接近2.0,所以我将'a'因子调低到.009并再次运行它,得到这个:

f(7 letters) = 2 ^ 7 * .009 =  1.152 sec’s
f(9 letters) = 2 ^ 9 * .009 =  4.608 sec’s
f(13 letters) = 2 ^ 13 * .009 =  73.728 sec’s
f(27 letters) = 2 ^ 27 * .009 =  1207959.552 sec’s = 335 hours  

现在看来很清楚,回溯步骤与2 ^ N关系中
回溯的字母数量相关.

我也认为这是一个公平的赌注,一些引擎
只能在这样的简单场景中做这个简单的2 ^ N数学运算.这些似乎是
发动机立即回来的时代,并说太复杂了!.
这里的翻译是正则表达式足够简单,引擎可以
检测到它.其他时候,发动机永远不会回来,
它会挂起,并且可能在一两年内(或十年......)回来.

因此,如果引擎会回溯,那么结论就不是,但是
你的目标字符串将如何影响回溯.

因此,在编写正则表达式时需要保持警惕,并且必须防范
嵌套的开放式量词.

我认为最好的选择总是打到一个真正的正则表达式,让它失败.
我在谈论可疑地方过多的重复文字.
结束编辑

基准应用程序

目标:AAAAAAAC

基准

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.07 s,   72.04 ms,   72040 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    1.13 s,   1126.44 ms,   1126444 µs

目标:AAAAAAAAAC

基准

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.08 s,   82.43 ms,   82426 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    4.43 s,   4433.19 ms,   4433188 µs

目标:AAAAAAAAAAAAAC

基准

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.10 s,   104.02 ms,   104023 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    70.51 s,   70509.32 ms,   70509321 µs

目标:AAAAAAAAAAAAAAAAAAAAAAAAAAAC

基准

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.18 s,   184.05 ms,   184047 µs


Regex2:   ^(A+)*B
Options:  < none >
Error:  Regex Runtime Error !!   
Completed iterations:   0  /  50     ( x 1000 )
Matches found per iteration:   -1
Elapsed Time:    0.01 s,   7.38 ms,   7384 µs


Error item 2 :  Target Operation .. 

The complexity of matching the regular expression exceeded predefined
bounds. Try refactoring the regular expression to make each choice made by
the state machine unambiguous. This exception is thrown to prevent
"eternal" matches that take an indefinite period time to locate.