regex - 惰性量词在 PCRE 中究竟是如何工作的？

Question

一些背景知识:我正在实现一个正则表达式匹配引擎 (NFA)，它应该支持 PCRE 兼容模式(我的意思是它应该捕获与 PCRE 具有相同偏移量的子表达式)。

PCRE 的testinput1 中有一个测试，我无法完全理解。它测试惰性量词。

所以，正则表达式是

/<a[\s]+href[\s]*=[\s]*          # find <a href=
 ([\"\'])?                       # find single or double quote
 (?(1) (.*?)\1 | ([^\s]+))       # if quote found, match up to next matching
                                 # quote, otherwise match up to next space
/isx

字符串是

<a href="abcd xyz pqr" cats

PCRE 的匹配是:

<a href="abcd xyz pqr"

而且它显然使用了惰性量词。

据我所知，除非另一种“贪婪”方式根本不可能，否则不应使用惰性量词。现在这是一个可能的贪婪匹配:

<a href="abcd

它使用条件子模式的否定分支，没有惰性量词。

因此，我正在寻找对此 PCRE 行为的解释或惰性量词为何在此测试中匹配的任何详细信息/建议。谢谢!

编辑:我还检查了 TRE图书馆作品。它是一个 POSIX 兼容的 NFA 引擎。我稍微修改了原始正则表达式以适应 TRE 的语法:

#include <stdlib.h>
#include <stdio.h>
#include <tre/tre.h>

int main()
{
    regex_t preg;
    const char * regex = "<a[ ]+href[ ]*=[ ]*(?:(')(.*?)'|[^ ]+)";
    const char * string = "<a href='abcd xyz pqr' cats";
    int cflags = REG_EXTENDED;
    int eflags = 0;
    size_t nmatch = 3;
    regmatch_t pmatch[100];

    tre_regcomp(&preg, regex, cflags);
    tre_regexec(&preg, string, nmatch, pmatch, eflags);

    for (int i = 0; i < nmatch; i++) {
        printf("%d: (%d, %d)\n", i, pmatch[i].rm_so, pmatch[i].rm_eo - pmatch[i].rm_so);
    }

    return 0;
}

输出(使用长度而不是结束偏移量)是:

0: (0, 22)
1: (8, 1)
2: (9, 12)

所以关于 PCRE 回溯特定行为的建议很可能是错误的...

Answer 1

首先，我只是 REGEX 世界的初学者。所以，如果这个答案有误或者我误解了这个问题，我很抱歉。

阅读此书的定义Regular Expressions Cookbook :

(?(1)then|else) is a conditional that checks whether the first capturing group has already matched something. If it has, the regex engine attempts to match then. If the capturing group has not participated in the match attempt thus far, the else part is attempted.

• 关于这个主题:<a href="abcd xyz pqr" cats

  第一个捕获组匹配了第一个 "特点。因此，预期的行为是尝试匹配 then 部分。 then 部分中的第二个捕获组设法匹配字符串 abcd xyz pqr与 (.*?)最后 then 部分设法匹配 abcd xyz pqr"与 (.*?)\1 . REGEX 可能会成功完成。

  因此，不需要带有 greddy 量词的 else 部分，实际上它没有被使用。就好像 greddy 量词从未存在过一样。

• 关于这个主题:<a href="abcd

  第一个捕获组匹配了"特点。现在 then 部分设法匹配字符串 abcd与 (.*?)但它永远不会匹配最后一个 "字符，因为在主题末尾没有这样的字符。条件失败。

  REGEX引擎不止于此，你用过([\"\'])?因此，引擎可能会再次尝试，因为 "字符是可选的，它会继续进行，就好像第一个捕获组不匹配一样(实际上有回溯)。因此，现在引擎达到第一个捕获组不匹配的条件，尝试 else 部分并设法匹配字符串 "abcd。 (由于回溯，" 字符未与第一个捕获组匹配，现在它与 else 部分中的第三个捕获组匹配)REGEX 可能会成功完成。

PS:我正在学习有关正则表达式的有趣内容，所以这个答案可能是完全错误的。等待更好的答案。