regex - 为什么我在 BBEdit 中的搜索会导致 "stack overflow"错误？

Question

我对“堆栈溢出”错误感到困惑——“堆栈空间不足(应用程序错误代码:12246)——当我执行“全部替换”时进入 BBEdit，搜索

(@article(((?!eprint|@article|@book).)*\r)*)pmid = {(.+)}((((?!eprint|@article|@book).)*\r)*(@|\r*\z))

并替换为

\1eprinttype = {pubmed}, eprint = {\4}\5

我可以手动使用这些相同的模式，一次查找和替换一个，没有任何错误，即使匹配不再发生。我还可以通过处理较小的文件来避免错误。

我怀疑应该归咎于我低效和草率的正则表达式编码，并且希望专家帮助更有效地完成这项工作。我试图在 BibLaTeX 引用书目中找到所有条目，这些条目还没有 eprint 字段，但是有 pmid 字段，并替换 pmid 字段和相应的 e-print 规范(使用 eprint 和 eprinttype)。

---

更新:经过一些实验，我发现 a different approach是我唯一可以开始工作的东西。正在寻找

(?(?=@article(.+\r)+eprint = {(.+\r)+}\r*)(?!)|(@article(.+\r)+)pmid = {(.+)}((.+\r)+}\r*))

并替换为

\3eprinttype = {pubmed}, eprint = {\5}\6

成功了。唯一的问题是反向引用很脆弱，但我无法获得 named backreferences在 BBEdit 中工作。

Answer 1

可能是catastrophic backtracking由最后一部分引起:

.)*\r)*(@|\r*\z))

如果你分解并简化它，你基本上有一个 .*，一个 \r*，和另一个 \r*就在彼此旁边。现在想象一下输入末尾的一串 \r 字符:每个 \r 应该如何分布？这些小子句中的哪一个会吸收每个 \r 字符？如果你有 \r\r\r\r\r，你可以用 .* 部分吃掉所有五个 \r 并且一个都不吃完全使用 \r* 部分...或者，您可以组成任意数量的仍然匹配的排列。由于 * 是贪心的，它会首先尝试填充 .*，但如果失败，它必须继续尝试排列，直到其中一个排列有效。因此，它可能会通过不必要的回溯占用大量资源，直到最终崩溃。

我不是正则表达式优化技术方面的专家，但如果我是你，我会从那里开始。

更新:

查看 Wikipedia article on PCRE :

Unless the "NoRecurse" PCRE build option (aka "--disable-stack-for-recursion") is chosen, adequate stack space must be allocated to PCRE by the calling application or operating system. ... While PCRE's documentation cautions that the "NoRecurse" build option makes PCRE slower than the alternative, using it avoids entirely the issue of stack overflows.

所以我认为灾难性回溯是一个不错的选择。在更改 PCRE 上的构建选项之前，我会尝试通过调整您的正则表达式来解决它。