正则表达式调试

Question

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

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 则记录了。不过，最终，只要最终得到相同的结果，回溯的确切顺序(爬回树上的顺序)并不重要。

邪恶的正则表达式

您已经知道这一点，但为了其他碰巧遇到的人的利益，您的正则表达式被编写为演示“catastrophic backtracking”(又名“邪恶的正则表达式”)，其中回溯尝试的次数随着输入增加。这些正则表达式可用于执行 DoS attacks ，因此您必须小心不要将它们引入到您的模式中(如 I found out )。