Регулярное выражение PREG_BACKTRACK_LIMIT_ERROR при извлечении действительно длинного текста без жадности - PullRequest
Новая
       9

Регулярное выражение PREG_BACKTRACK_LIMIT_ERROR при извлечении действительно длинного текста без жадности

0 голосов
/ 26 мая 2018

У меня есть строка вида:

Некоторый текст [Открытие] Действительно очень длинный текст ... [Закрытие] Больше текста [Закрытие] Еще больше текста

Я хочу извлечь текст Really Really Long Text ... из строки с помощью регулярного выражения.Вплоть до первого [Закрытие].

Если я сделаю регулярное выражение, подобное этому: 

$pMatch = "'\[Opening\](.+)\[Closing\]'si";

Это дает мне:

Действительно действительно длинный текст... [Закрытие] Больше текста

Я также могу сделать это не жадным, как это: 

$pMatch = "'\[Opening\](.+?)\[Closing\]'si";

Что работает и дает мне правильный вывод:

Действительно Действительно Длинный Текст ...

Однако, если я заменю «Действительно Действительно Длинный Текст ...» на действительно очень длинный текст, он не будет работать, и вместо этого я получуPREG_BACKTRACK_LIMIT_ERROR.Я не получаю ошибку, если я использую жадное регулярное выражение.Я просто получаю неправильный вывод, как в первом случае.

Я работал с регулярными выражениями какое-то время, но это поставило меня в тупик.Есть ли способ заставить это работать с регулярным выражением или регулярное выражение не подходит для этой задачи?

Вот код PHP, чтобы воспроизвести проблему: 

<?php

  $sShortString = "Some Text[Opening]Really Really Long Text...[Closing]More Text[Closing]Even More Text";
  $sLongString = "Some Text[Opening]".str_repeat("BLAH", 1000000)."[Closing]More Text[Closing]Even More Text";

  $pGreedyMatch = "'\[Opening\](.+)\[Closing\]'si";
  $pNonGreedyMatch = "'\[Opening\](.+?)\[Closing\]'si";

  header("Content-Type: text/plain");

  if (preg_match($pGreedyMatch, $sShortString, $aMatch)) {
    echo "Greedy Match:\n";
    print_r($aMatch);
  }

  if (preg_match($pNonGreedyMatch, $sShortString, $aMatch)) {
    echo "Non-Greedy Match:\n";
    print_r($aMatch);
  }

  if (preg_match($pGreedyMatch, $sLongString, $aMatch)) {
    echo "Greedy Match:\n";
    echo "Length: ".strlen($aMatch[1])."\n";
  }

  if (preg_match($pNonGreedyMatch, $sLongString, $aMatch)) {
    echo "Non-Greedy Match:\n";
    echo strlen($aMatch[1]);
  } else {
    echo "Non-Greedy Doesn't Match!\n";
  }

  $iLastError = preg_last_error();
  if ($iLastError == PREG_BACKTRACK_LIMIT_ERROR) {
    echo "It's because the backtrack limit was exceeded!\n";
  }

?>

Я получаювывод: 

Greedy Match:
Array
(
    [0] => [Opening]Really Really Long Text...[Closing]More Text[Closing]
    [1] => Really Really Long Text...[Closing]More Text
)
Non-Greedy Match:
Array
(
    [0] => [Opening]Really Really Long Text...[Closing]
    [1] => Really Really Long Text...
)
Greedy Match:
Length: 4000018
Non-Greedy Doesn't Match!
It's because the backtrack limit was exceeded!

Я получил это, используя жадное регулярное выражение и используя дополнительный код для удаления текста с [Закрытие] и далее.Я хотел бы лучше понять, что происходит за кулисами, почему ему нужно так много откатить назад, и если есть способ изменить регулярное выражение, чтобы оно выполняло задачу.

Я действительно ценю любую проницательность!

1 Ответ

0 голосов
/ 27 мая 2018

У нежадного квантификатора есть стоимость, потому что каждый раз, когда он читает символ, он должен сверяться с концом шаблона.

В приведенном выше шаблоне каждый раз . в (.+?) соответствует, он проверяет соответствие следующих символов [Closing].Каждый раз, когда это происходит, и оно не совпадает, оно должно возвращаться назад и продолжать поиск.Вот почему использовался предел возврата.

Шаблон можно переписать так: 

'\[Opening\]([^\[]*(?:\[(?!Closing)[^\[]*)*)(*SKIP)\[Closing\]'si

Давайте разберем этот шаблон по частям, чтобы понять его.

1) Открываем с \[Opening\].Этот шаблон соответствует открывающему тегу.

2) Поскольку наш шаблон не повторяется внутри себя, директива ()(*SKIP) используется в качестве дальнейшей оптимизации.Это означает, что если мы не соответствуем шаблону, то мы возобновим наш поиск с конца того места, где мы искали.Поведение по умолчанию снова начинает поиск следующего символа.

Чтобы лучше это понять, представьте, что наша строка - sometimes we get [Close to matching.Когда мы добираемся до [, мы сканируем [Clos, прежде чем решим, что на самом деле это не тот шаблон, который нам нужен.Обычно мы возвращаемся, а затем снова начинаем смотреть на Close.Тем не менее, (*SKIP) позволяет нам продолжать поиск на e to matc.

3) Внутри скобок мы начинаем с шаблона [^\[]*, который позволяет нам сопоставить столько символов, сколько мы можем, но не [.^ означает, что нет, \[ для [, а [] окружает его как набор символов.* позволяет повторять столько раз, сколько возможно.

4) Теперь у нас есть (?:)*.() позволяет нам указать строку, а ?: указывает, что она не будет сохранена, а * позволяет повторять ее столько раз, сколько мы захотим (в том числе вообще без).

5) Первый символ в этой строке - \[ или просто [, который мы ожидаем как часть нашего закрывающего тега.

6) Далее у нас есть (?!Closing\]).(?!) является негативным прогнозом .Предварительный просмотр означает, что синтаксический анализатор будет смотреть на следующие символы и либо совпадать, либо не совпадать без использования символов.Это позволяет нам сопоставлять что-либо, пока оно не Closing], фактически не потребляя его.

7) У нас есть еще один [^\[]*, который позволяет нам продолжать есть символы после того, как мы не смогли заглянуть в будущее.Это позволяет нам продолжать использовать строку после того, как мы получим что-то вроде [Clos.

8) Наконец, наше регулярное выражение заканчивается на \[Closing\].

...