Подтвердить что ты не робот

Почему вы не можете использовать кванторы повторения в нулевой ширине за утверждениями

Мне всегда казалось, что вы не можете использовать кванторы повторения в утверждениях с нулевой шириной (Perl Compatible Regular Equions [PCRE]). Однако недавно я понял, что вы можете использовать их в ожидании утверждений.

Итак, мой вопрос:

Как работает механизм регулярных выражений PCRE при поиске с нулевой шириной, который исключает использование кванторов повторения?

Вот простой пример из PCRE в R:

# 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)'
4b9b3361

Ответ 1

Окончательный ответ на такой вопрос содержится в коде двигателя, а в нижней части ответа вы сможете погрузиться в раздел кода двигателя PCRE, отвечающего за обеспечение фиксированной длины в lookbehinds, интересно узнать самые тонкие детали. В то же время, пусть постепенно увеличит масштаб вопроса с более высоких уровней.

Variable-Width Lookbehind vs. Infinite-Width Lookbehind

Во-первых, быстрое разъяснение условий. Все большее число двигателей (включая PCRE) поддерживают некоторую форму вида с переменной шириной, где изменение зависит от определенного диапазона, например:

  • движок знает, что ширина предшествующего значения должна быть внутри от 5 до десяти символов (не поддерживается в PCRE)
  • движок знает, что ширина предшествующего символа должна быть или 5 или десять символов (поддерживается в PCRE)

Напротив, в режиме бесконечной ширины вы можете использовать квантованные токены, такие как a+

Двигатели, поддерживающие бесконечную ширину Lookbehind

Для записи эти двигатели поддерживают бесконечный lookbehind:

  • .NET(С#, VB.NET и т.д.)
  • Модуль Matthew Barnett regex для Python
  • JGSoft (EditPad и т.д., недоступен на языке программирования).

Насколько я знаю, они единственные.

Переменная Lookbehind в PCRE

В PCRE наиболее релевантным разделом в документации является следующее:

Содержимое утверждения lookbehind ограничено таким образом, что все строки, которые он соответствует, должны иметь фиксированную длину. Однако, если есть несколько альтернатив высшего уровня, они не все должны иметь одинаковые фиксированная длина.

Следовательно, справедлив следующий вид:

(?<=a |big )cat

Однако ни один из них:

  • (?<=a\s?|big )cat (стороны чередования не имеют фиксированной ширины)
  • (?<[email protected]{1,10})cat (переменная ширина)
  • (?<=\R)cat (\R не имеет фиксированной ширины, поскольку она может соответствовать \n, \r\n и т.д.)
  • (?<=\X)cat (\X не имеет фиксированной ширины, поскольку кластер граф Unicode может содержать переменное количество байтов.)
  • (?<=a+)cat (явно не исправлено)

Lookbehind с совпадением нулевой ширины, но бесконечное повторение

Теперь рассмотрим следующее:

(?<=([email protected]+))(cat#+)

На первый взгляд, это вид с фиксированной шириной, потому что он может только найти совпадение нулевой ширины (определяемое lookahead ([email protected]++)). Это трюк, чтобы обойти бесконечное ограничение на вид?

Нет. PCRE задохнется от этого. Несмотря на то, что содержимое lookbehind имеет нулевую ширину, PCRE не позволит бесконечного повторения в lookbehind. В любом месте. Когда в документации указано, что все строки, которые он соответствует, должны иметь фиксированную длину, это должно быть действительно:

Все строки, которые соответствуют любому из его компонентов, должны иметь фиксированный длина.

Обходные пути: жизнь без бесконечного Lookbehind

В PCRE два основных решения проблем, в которых нуждаются бесконечные образы, - это \K и группы захвата.

Обходной путь №1: \K

Утверждение \K сообщает движку опускать то, что было согласовано так далеко от окончательного соответствия, которое оно возвращает.

Предположим, вы хотите (?<[email protected]+)cat#+, что не является законным в PCRE. Вместо этого вы можете использовать:

@+\Kcat#+

Обходной путь №2: группы захвата

Другой способ продолжить - сопоставить то, что вы бы разместили в lookbehind, и захватить контент, представляющий интерес в группе захвата. Затем вы извлекаете совпадение из группы захвата.

Например, вместо незаконного (?<[email protected]+)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, убедитесь, что эта ветка соответствует строке с фиксированной длиной

Вы обнаружите, что работа grunt выполняется с помощью функции 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 a ket it is the end of a nested call.
    If it ALT it is an alternation in a nested call. An ACCEPT is effectively
    an ALT. If it is END it 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 */
}

Ответ 2

Двигатели Regex предназначены для работы слева направо.

Для взглядов двигатель соответствует всему тексту справа от текущей позиции. Однако для lookbehind механизм regex определяет длину строки для возврата назад, а затем проверяет соответствие (снова слева направо).

Итак, если вы предоставляете некоторые бесконечные кванторы, такие как * или +, lookbehind не будет работать, потому что движок не знает, сколько шагов для возврата назад.

Я приведу пример того, как выглядит lookbehind (пример довольно глупый, хотя).

Предположим, вы хотите совместить фамилию Panta, только если имя имеет длину 5-7 символов.

Возьмем строку:

Full name is Subigya Panta.

Рассмотрим регулярное выражение:

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

Как работает двигатель

Двигатель признает наличие положительного lookbehind и поэтому сначала ищет слово Panta (перед ним пробельный символ). Это матч.

Теперь двигатель выглядит так, чтобы соответствовать регулярному выражению внутри lookbehind. Он отбрасывает 7 символов (поскольку квантификатор является жадным). Граница слова соответствует положению между пространством и S. Затем он соответствует всем 7 символам, а затем следующая граница слова соответствует позиции между a и пробелом.

Регулярное выражение внутри lookbehind является совпадением, и, таким образом, все регулярное выражение возвращает true, потому что строка с сочетанием содержит Panta. (Обратите внимание, что утверждения поиска имеют нулевую ширину и не потребляют никаких символов.)

Ответ 3

справочная страница pcrepattern документирует ограничение, в котором утверждения lookbehind должны быть либо фиксированными, либо несколькими шаблонами фиксированной ширины, разделенными |, а затем объясняет, что это происходит потому, что:

Реализация утверждений lookbehind для каждой альтернативы, временно переместить текущую позицию на фиксированную длину и затем попробуйте сопоставить. Если перед символом недостаточно символов текущая позиция, утверждение не выполняется.

Я не уверен, почему они делают это таким образом, но я предполагаю, что они потратили много времени на создание хорошего механизма RE-соответствия с возвратом назад, и они не хотели дублировать все эти усилия, чтобы напишите другое, которое бежит назад. Очевидный подход состоял бы в том, чтобы прокручивать строку назад - это легко - при сопоставлении "обратной" версии вашего утверждения lookbehind. Возможна реверсивная "реальная" (совместимая с DFA) RE - реверс обычного языка является обычным языком, но PCRE "расширенный" RE завершен, и возможно даже невозможно перевернуть его вокруг эффективно работать в обратном направлении. И даже если бы это было так, вероятно, никто не заботился бы о себе. В конце концов, утверждения lookbehind - довольно незначительная особенность в великой схеме вещей.