gpt4 book ai didi

正则表达式调试

转载 作者:行者123 更新时间:2023-12-03 03:19:14 27 4
gpt4 key购买 nike

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

  1. regex101.com
  2. RegexBuddy v4

下面是结果(左侧为 regex101):

tool outps (regex101 on the left)

我的问题主要不是步骤的数量(这对我来说也很重要),而是如何完成回溯。为什么我们会看到差异? (regex101使用PCRE lib,我将RegexBuddy lib设置为相同)

全面的逐步解释确实对我有利。

最佳答案

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 )。

关于正则表达式调试,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37912224/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com