为什么不能在零宽度回顾断言中使用重复量词？

Question

我一直以为在零宽度断言中（Perl兼容的正则表达式[PCRE]），您不能使用重复量词。然而，最近我发现您可以在向前查看断言中使用它们。

当使用零宽度向后查找并且防止使用重复量词时，PCRE正则表达式引擎是如何工作的？

这是R中PCRE的一个简单示例：

# Our string
x <- 'MaaabcccM'

##  Does it contain a 'b', preceeded by an 'a' and followed by zero or more 'c',
##  then an 'M'?
grepl( '(?<=a)b(?=c*M)' , x , perl=T )
# [1] TRUE

##  Does it contain a 'b': (1) preceeded by an 'M' and then zero or more 'a' and
##                         (2) followed by zero or more 'c' then an 'M'?
grepl( '(?<=Ma*)b(?=c*M)' , x , perl = TRUE )
# Error in grepl("(?<=Ma*)b(?=c*M)", x, perl = TRUE) :
#   invalid regular expression '(?<M=a*)b(?=c*M)'
# In addition: Warning message:
# In grepl("(?<=Ma*)b(?=c*M)", x, perl = TRUE) : PCRE pattern compilation error
#         'lookbehind assertion is not fixed length'
#         at ')b(?=c*M)'

- Simon O'Hanlon

---

是的，只有前瞻断言可以是可变长度的。唯一的例外是特殊的\K代码，它是一个特殊形式的后顾断言，可以是可变的。因此，在您的第二个示例中，以下内容将在perl中起作用：/a*\Kb(?=c*)/。显然，使用可以为零宽度的断言有点毫无意义，因此也许使用+会更好一些。 - Miller

因为变长的向后断言在正则表达式引擎需要回溯时非常麻烦。 - mob

@mob，你能解释一下为什么它们比变长前瞻断言更难处理吗？从一个幼稚的角度来看，这两种操作都需要查看相同数量的字符，对吧。(我知道这肯定是错的，但是为什么呢？) - Josh O'Brien

这段话可能暗示了原因。它似乎表明正则表达式引擎只能向前工作，所以回顾断言实际上是通过向后跨越“n”个字符，并从它们的第一个字符开始检查它们来匹配的。对于长度可变的回顾断言，你无法事先知道“n”，这意味着你必须为字符串中每个可能的开头字符重复测试多次。请问有没有一些正则表达式高手能够确认这是否正确？ - Josh O'Brien

“'0个或多个a'之前的'b'”这个概念相当荒谬，因为它总是被满足的。 "b" 要么至少被一个 "a" 之前的，要么不是，所以被零个 "a" 之前的情况是无意义的。同样，对于其后跟着零个或多个 "c" 的情况也是如此。 - IRTFM

Answer 1

The ultimate answer to such a question is in the engine's code, and at the bottom of the answer you'll be able to dive into the section of the PCRE engine's code responsible for ensuring fixed-length in lookbehinds—if you're interested in knowing the finest details. In the meantime, let's gradually zoom into the question from higher levels.

Variable-Width Lookbehind vs. Infinite-Width Lookbehind

First off, a quick clarification on terms. A growing number of engines (including PCRE) support some form of variable-width lookbehind, where the variation falls within a determined range, for instance:

- the engine knows that the width of what precedes must be within 5 to ten characters (not supported in PCRE) - the engine knows that the width of what precedes must be either 5 or ten character (supported in PCRE)

In contrast, in infinite-width lookbehind, you can use quantified tokens such as "a+".

Engines that Support Infinite-Width Lookbehind

For the record, these engines support infinite lookbehind:

• .NET (C＃，VB.NET等)
• Matthew Barnett的Python正则表达式模块
• JGSoft（EditPad等；不适用于编程语言）。

据我所知，它们是唯一的。

PCRE中的可变后向引用

在PCRE中，文档中最相关的部分如下：

后向引用断言的内容受到限制，以使其匹配的所有字符串都必须具有固定长度。但是，如果有多个顶级替代方案，则它们并不都必须具有相同的固定长度。

因此，以下后向引用是有效的：

(?<=a |big )cat

然而，这些都不是固定宽度的：

• (?<=a\s?|big )cat（选择的两端没有固定的宽度）
• (?<=@{1,10})cat（宽度可变）
• (?<=\R)cat（\R 没有固定宽度，因为它可以匹配 \n、\r\n 等）
• (?<=\X)cat（\X 没有固定宽度，因为 Unicode 图形簇可以包含可变数量的字节。）
• (?<=a+)cat（显然不是固定的）

具有零宽度匹配但无限重复的向后查找

现在考虑这个：

(?<=(?=@+))(cat#+)

表面上看，这是一个固定宽度的后顾断言，因为它只能找到零宽度匹配（由前瞻 (?=@++) 定义）。这是绕过无限后顾限制的技巧吗？

不是。PCRE 会卡住。即使后顾的内容是零宽度，PCRE 也不允许在后顾中进行无限重复。任何地方都不行。当文档说它匹配的所有字符串必须具有固定长度时，实际上应该是：

所有组件匹配的字符串都必须具有固定长度。

解决办法：没有无限后顾的生活

在 PCRE 中，解决无限后顾无法帮助的问题的两个主要方法是 \K 和捕获组。

解决办法 #1：\K

\K 断言告诉引擎从它返回的最终匹配中删除到目前为止匹配的内容。

假设你想要 (?<=@+)cat#+，这在 PCRE 中是不合法的。相反，您可以使用：

@+\Kcat#+

解决方法 #2: 捕获组

另一种解决方法是匹配您原本想要放在回顾后面的内容，并在捕获组中捕获感兴趣的内容。然后从捕获组中检索匹配项。

例如，您可以使用以下代码而不是非法的 (?<=@+)cat#+:

@+(cat#+)

在R中，这可能看起来像这样：

matches <- regexpr("@+(cat#+)", subject, perl=TRUE);
result <- attr(matches, "capture.start")[,1]
attr(result, "match.length") <- attr(matches, "capture.length")[,1]
regmatches(subject, result)

在不支持\K的语言中，这通常是唯一的解决方案。

引擎内部：PCRE代码说了什么？

最终的答案可以在pcre_compile.c中找到。如果您检查以以下注释开头的代码块：

如果是lookbehind，则检查此分支是否与固定长度字符串匹配

您会发现繁重的工作由find_fixedlength()函数完成。

我在此为想要深入了解的任何人复制它。

static int
find_fixedlength(pcre_uchar *code, BOOL utf, BOOL atend, compile_data *cd)
{
int length = -1;

register int branchlength = 0;
register pcre_uchar *cc = code + 1 + LINK_SIZE;

/* Scan along the opcodes for this branch. If we get to the end of the
branch, check the length against that of the other branches. */

for (;;)
  {
  int d;
  pcre_uchar *ce, *cs;
  register pcre_uchar op = *cc;

  switch (op)
    {
    /* We only need to continue for OP_CBRA (normal capturing bracket) and
    OP_BRA (normal non-capturing bracket) because the other variants of these
    opcodes are all concerned with unlimited repeated groups, which of course
    are not of fixed length. */

    case OP_CBRA:
    case OP_BRA:
    case OP_ONCE:
    case OP_ONCE_NC:
    case OP_COND:
    d = find_fixedlength(cc + ((op == OP_CBRA)? IMM2_SIZE : 0), utf, atend, cd);
    if (d < 0) return d;
    branchlength += d;
    do cc += GET(cc, 1); while (*cc == OP_ALT);
    cc += 1 + LINK_SIZE;
    break;

    /* Reached end of a branch; if it's a ket it is the end of a nested call.
    If it's ALT it is an alternation in a nested call. An ACCEPT is effectively
    an ALT. If it is END it's the end of the outer call. All can be handled by
    the same code. Note that we must not include the OP_KETRxxx opcodes here,
    because they all imply an unlimited repeat. */

    case OP_ALT:
    case OP_KET:
    case OP_END:
    case OP_ACCEPT:
    case OP_ASSERT_ACCEPT:
    if (length < 0) length = branchlength;
      else if (length != branchlength) return -1;
    if (*cc != OP_ALT) return length;
    cc += 1 + LINK_SIZE;
    branchlength = 0;
    break;

    /* A true recursion implies not fixed length, but a subroutine call may
    be OK. If the subroutine is a forward reference, we can't deal with
    it until the end of the pattern, so return -3. */

    case OP_RECURSE:
    if (!atend) return -3;
    cs = ce = (pcre_uchar *)cd->start_code + GET(cc, 1);  /* Start subpattern */
    do ce += GET(ce, 1); while (*ce == OP_ALT);           /* End subpattern */
    if (cc > cs && cc < ce) return -1;                    /* Recursion */
    d = find_fixedlength(cs + IMM2_SIZE, utf, atend, cd);
    if (d < 0) return d;
    branchlength += d;
    cc += 1 + LINK_SIZE;
    break;

    /* Skip over assertive subpatterns */

    case OP_ASSERT:
    case OP_ASSERT_NOT:
    case OP_ASSERTBACK:
    case OP_ASSERTBACK_NOT:
    do cc += GET(cc, 1); while (*cc == OP_ALT);
    cc += PRIV(OP_lengths)[*cc];
    break;

    /* Skip over things that don't match chars */

    case OP_MARK:
    case OP_PRUNE_ARG:
    case OP_SKIP_ARG:
    case OP_THEN_ARG:
    cc += cc[1] + PRIV(OP_lengths)[*cc];
    break;

    case OP_CALLOUT:
    case OP_CIRC:
    case OP_CIRCM:
    case OP_CLOSE:
    case OP_COMMIT:
    case OP_CREF:
    case OP_DEF:
    case OP_DNCREF:
    case OP_DNRREF:
    case OP_DOLL:
    case OP_DOLLM:
    case OP_EOD:
    case OP_EODN:
    case OP_FAIL:
    case OP_NOT_WORD_BOUNDARY:
    case OP_PRUNE:
    case OP_REVERSE:
    case OP_RREF:
    case OP_SET_SOM:
    case OP_SKIP:
    case OP_SOD:
    case OP_SOM:
    case OP_THEN:
    case OP_WORD_BOUNDARY:
    cc += PRIV(OP_lengths)[*cc];
    break;

    /* Handle literal characters */

    case OP_CHAR:
    case OP_CHARI:
    case OP_NOT:
    case OP_NOTI:
    branchlength++;
    cc += 2;
#ifdef SUPPORT_UTF
    if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
#endif
    break;

    /* Handle exact repetitions. The count is already in characters, but we
    need to skip over a multibyte character in UTF8 mode.  */

    case OP_EXACT:
    case OP_EXACTI:
    case OP_NOTEXACT:
    case OP_NOTEXACTI:
    branchlength += (int)GET2(cc,1);
    cc += 2 + IMM2_SIZE;
#ifdef SUPPORT_UTF
    if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
#endif
    break;

    case OP_TYPEEXACT:
    branchlength += GET2(cc,1);
    if (cc[1 + IMM2_SIZE] == OP_PROP || cc[1 + IMM2_SIZE] == OP_NOTPROP)
      cc += 2;
    cc += 1 + IMM2_SIZE + 1;
    break;

    /* Handle single-char matchers */

    case OP_PROP:
    case OP_NOTPROP:
    cc += 2;
    /* Fall through */

    case OP_HSPACE:
    case OP_VSPACE:
    case OP_NOT_HSPACE:
    case OP_NOT_VSPACE:
    case OP_NOT_DIGIT:
    case OP_DIGIT:
    case OP_NOT_WHITESPACE:
    case OP_WHITESPACE:
    case OP_NOT_WORDCHAR:
    case OP_WORDCHAR:
    case OP_ANY:
    case OP_ALLANY:
    branchlength++;
    cc++;
    break;

    /* The single-byte matcher isn't allowed. This only happens in UTF-8 mode;
    otherwise \C is coded as OP_ALLANY. */

    case OP_ANYBYTE:
    return -2;

    /* Check a class for variable quantification */

    case OP_CLASS:
    case OP_NCLASS:
#if defined SUPPORT_UTF || defined COMPILE_PCRE16 || defined COMPILE_PCRE32
    case OP_XCLASS:
    /* The original code caused an unsigned overflow in 64 bit systems,
    so now we use a conditional statement. */
    if (op == OP_XCLASS)
      cc += GET(cc, 1);
    else
      cc += PRIV(OP_lengths)[OP_CLASS];
#else
    cc += PRIV(OP_lengths)[OP_CLASS];
#endif

    switch (*cc)
      {
      case OP_CRSTAR:
      case OP_CRMINSTAR:
      case OP_CRPLUS:
      case OP_CRMINPLUS:
      case OP_CRQUERY:
      case OP_CRMINQUERY:
      case OP_CRPOSSTAR:
      case OP_CRPOSPLUS:
      case OP_CRPOSQUERY:
      return -1;

      case OP_CRRANGE:
      case OP_CRMINRANGE:
      case OP_CRPOSRANGE:
      if (GET2(cc,1) != GET2(cc,1+IMM2_SIZE)) return -1;
      branchlength += (int)GET2(cc,1);
      cc += 1 + 2 * IMM2_SIZE;
      break;

      default:
      branchlength++;
      }
    break;

    /* Anything else is variable length */

    case OP_ANYNL:
    case OP_BRAMINZERO:
    case OP_BRAPOS:
    case OP_BRAPOSZERO:
    case OP_BRAZERO:
    case OP_CBRAPOS:
    case OP_EXTUNI:
    case OP_KETRMAX:
    case OP_KETRMIN:
    case OP_KETRPOS:
    case OP_MINPLUS:
    case OP_MINPLUSI:
    case OP_MINQUERY:
    case OP_MINQUERYI:
    case OP_MINSTAR:
    case OP_MINSTARI:
    case OP_MINUPTO:
    case OP_MINUPTOI:
    case OP_NOTMINPLUS:
    case OP_NOTMINPLUSI:
    case OP_NOTMINQUERY:
    case OP_NOTMINQUERYI:
    case OP_NOTMINSTAR:
    case OP_NOTMINSTARI:
    case OP_NOTMINUPTO:
    case OP_NOTMINUPTOI:
    case OP_NOTPLUS:
    case OP_NOTPLUSI:
    case OP_NOTPOSPLUS:
    case OP_NOTPOSPLUSI:
    case OP_NOTPOSQUERY:
    case OP_NOTPOSQUERYI:
    case OP_NOTPOSSTAR:
    case OP_NOTPOSSTARI:
    case OP_NOTPOSUPTO:
    case OP_NOTPOSUPTOI:
    case OP_NOTQUERY:
    case OP_NOTQUERYI:
    case OP_NOTSTAR:
    case OP_NOTSTARI:
    case OP_NOTUPTO:
    case OP_NOTUPTOI:
    case OP_PLUS:
    case OP_PLUSI:
    case OP_POSPLUS:
    case OP_POSPLUSI:
    case OP_POSQUERY:
    case OP_POSQUERYI:
    case OP_POSSTAR:
    case OP_POSSTARI:
    case OP_POSUPTO:
    case OP_POSUPTOI:
    case OP_QUERY:
    case OP_QUERYI:
    case OP_REF:
    case OP_REFI:
    case OP_DNREF:
    case OP_DNREFI:
    case OP_SBRA:
    case OP_SBRAPOS:
    case OP_SCBRA:
    case OP_SCBRAPOS:
    case OP_SCOND:
    case OP_SKIPZERO:
    case OP_STAR:
    case OP_STARI:
    case OP_TYPEMINPLUS:
    case OP_TYPEMINQUERY:
    case OP_TYPEMINSTAR:
    case OP_TYPEMINUPTO:
    case OP_TYPEPLUS:
    case OP_TYPEPOSPLUS:
    case OP_TYPEPOSQUERY:
    case OP_TYPEPOSSTAR:
    case OP_TYPEPOSUPTO:
    case OP_TYPEQUERY:
    case OP_TYPESTAR:
    case OP_TYPEUPTO:
    case OP_UPTO:
    case OP_UPTOI:
    return -1;

    /* Catch unrecognized opcodes so that when new ones are added they
    are not forgotten, as has happened in the past. */

    default:
    return -4;
    }
  }
/* Control never gets here */
}

- zx81

---

有很多有趣的信息，但仍然没有回答问题：当使用零宽度回溯（排除重复量词）进行搜索时，PCRE正则表达式引擎是如何工作的？ - HamZa

@HamZa 很高兴收到你的来信。我添加了一个部分 零宽度匹配，但是具有无限重复的后行环视 ，其中考虑了一个包含无限重复的零宽度匹配的后行环视: (?<=(?=@+))这是你想要的吗？不确定，因为从Simon的例子中我无法确定是否这是一般的想法（起初似乎并非如此，这就是为什么我没有考虑那个有趣的情况）。 - zx81

@HamZa 另外，对于任何有兴趣查看引擎内部的人，我找到了 pcre_compile.c 负责检查向后查找字符串固定长度的部分。它调用了 find_fixedlength() 函数，我将其代码粘贴在此，以便有人想要最终答案的最细节层次。 - zx81

就此而言，PCRE2中已经实现了可变长度的回顾后发表（Variable length lookbehinds）链接。 - undefined

Answer 2

正则表达式引擎是从左到右设计的。

对于前瞻，引擎会匹配当前位置右侧的整个文本。然而，对于后顾，正则表达式引擎确定要向后跨越的字符串长度，然后检查匹配（同样是从左到右）。

因此，如果您提供一些无限定符，例如*或+，则后顾将不起作用，因为引擎不知道要向后走多少步。

我将举一个后顾工作的示例（尽管这个示例非常愚蠢）。

假设您想匹配姓Panta，仅当名字长度为5-7个字符时。

让我们取字符串：

Full name is Subigya Panta.

考虑以下正则表达式：

(?<=\b\w{5,7}\b)\sPanta

引擎的工作原理

引擎识别了存在一个正向先行断言，因此它首先搜索带有空格字符的单词Panta。这是一个匹配。

现在，引擎查找要匹配的正则表达式。由于量词是贪婪的，所以它向后移动7个字符。单词边界匹配空格和S之间的位置。然后它匹配所有7个字符，接着下一个单词边界匹配a和空格之间的位置。

正向先行断言内的正则表达式匹配成功，因此整个正则表达式返回true，因为匹配的字符串包含Panta。（请注意，环视断言是零宽度的，不会消耗任何字符。）

- DrGeneral

---

你在那里有一个语法错误：{5-7} 应该是 {5,7}。但是你的解释只适用于Java和ICU风格，如果在正则表达式编译时可以确定最大可能长度，则支持可变长度回溯。你的示例也适用于.NET、JGSoft和Perl 6（它们没有任何限制），但在大多数风格中，只能使用固定长度回溯。 - Alan Moore

@AlanMoore 谢谢，我已经进行了编辑。同意，它也适用于 PCRE，而问题与 PCRE 相关。 - DrGeneral

PCRE库（这是R在指定perl=TRUE时使用的库）模仿了Perl 5的行为。因此，它支持由多个固定长度替代项组成的回顾后发断言（如其他答案中所提到的），但不允许在回顾后发断言中使用限定符。 - Alan Moore

Answer 3

pcrepattern man page记录了回溯断言必须是固定宽度或由多个固定宽度模式用|分隔的限制，并解释了这是因为：

“对于每个可选项，回溯断言的实现是暂时将当前位置向后移动固定长度，然后尝试匹配。如果当前位置之前的字符不足，则断言失败。”

我不确定他们为什么要这样做，但我猜想他们花了很多时间编写一个良好的回溯正则表达式匹配引擎，该引擎向前运行，他们不想复制所有这些工作来编写另一个向后运行的引擎。明显的方法是向后扫描字符串-那很容易-同时匹配您的回溯断言的“反向”版本。反转“真实”的（DFA-matchable）RE是可能的-正则语言的反转是正则语言-但是PCRE的“扩展”RE是IIRC图灵完备的，并且通常甚至无法有效地将其翻转以向后运行。即使可以，也可能没有人真正关心。毕竟，在大局中，回溯断言是一个相当次要的功能。

- Nathaniel J. Smith