3

一点背景知识：我正在实现一个正则表达式匹配引擎（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 的回溯特定行为的建议很可能是错误的......

4

2 回答 2

1

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

阅读这本书的定义正则表达式食谱：

(?(1)then|else)是检查第一个捕获组是否已经匹配的条件。如果有，那么正则表达式引擎会尝试匹配。如果捕获组到目前为止还没有参与匹配尝试，则尝试其他部分。

  • 有了这个主题： <a href="abcd xyz pqr" cats

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

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

  • 有了这个主题：<a href="abcd

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

    正则表达式引擎并没有在这里停止，你已经使用过([\"\'])?，引擎可能会再试一次，因为"字符是可选的，并且它继续进行，就好像第一个捕获组没有匹配（确实有回溯）。因此，现在引擎达到条件，第一个捕获组不匹配，尝试 else 部分并设法匹配字符串"abcd（"由于回溯，第一个捕获组不匹配该字符，现在它匹配else 部分中的第三个捕获组）正则表达式可能会成功完成。

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

于 2014-01-16T19:49:02.840 回答
0

我在这里不完全理解您的问题，但非贪婪量词允许搜索模式的第一次出现。使用 pcretest，您可以在相同的输入上尝试贪婪和非贪婪形式。

非贪心形式：

  re> /<a[\s]+href[\s]*=[\s]*([\"\'])?(?(1)(.*?)\1|([^\s]+))/i
  data> <a href="ab"cd"
    0: <a href="ab"
    1: "
    2: ab

贪心形式：

 re> /<a[\s]+href[\s]*=[\s]*([\"\'])?(?(1)(.*)\1|([^\s]+))/i
 data> <a href="ab"cd"
    0: <a href="ab"cd"
    1: "
    2: ab"cd
于 2014-01-17T21:59:08.483 回答