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

Question

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

(<select([^>]*>))(.*?)(</select\s*>)

Так как он использует ленивый повторяющий квантификатор, для более длинных строк (с опциями больше 500) он возвращается более 100 000 раз и завершается ошибкой.Пожалуйста, помогите мне найти лучшее регулярное выражение, которое не использует ленивый повторный квантификатор

Answer 1

<select[^>]*>[^<]*(?:<(?!/select>)[^<]*)*</select>

... или в читаемой человеком форме:

<select[^>]*>    # start tag
[^<]*            # anything except opening bracket
(?:              # if you find an open bracket
  <(?!/select>)  #   match it if it's not part of end tag
  [^<]*          #   consume any more non-brackets
)*               # repeat as needed
</select>        # end tag

Это пример техники "развернутой петли", которую Фридл развивает в своей книге Освоение регулярных выражений . Я провел быстрый тест в RegexBuddy, используя шаблон, основанный на неохотных квантификаторах:

(?s)<select[^>]*>.*?</select>

... и понадобилось около 6000 шагов, чтобы найти совпадение. Шаблон unrolled-loop занял всего 500 шагов. И когда я удалил закрывающую скобку из конечного тега (</select), сделав сопоставление невозможным, потребовалось всего 800 шагов, чтобы сообщить об ошибке.

Если ваш тип регулярных выражений поддерживает собственнические квантификаторы, используйте их также:

<select[^>]*+>[^<]*+(?:<(?!/select>)[^<]*+)*+</select>

Требуется примерно такое же количество шагов для достижения соответствия, но он может использовать намного меньше памяти в процессе. И если совпадение невозможно, оно проваливается еще быстрее; в моих тестах потребовалось около 500 шагов, столько же, сколько и для поиска соответствия.

Answer 2

К сожалению, это не сработает, см. Ответ Алана Мура для правильного примера!

(<select([^>]*>))(.*+)(</select\s*>)

На странице perl regexp:

Byпо умолчанию, когда квантифицированный подшаблон не позволяет сопоставить остальную часть общего шаблона, Perl будет возвращаться назад.Однако такое поведение иногда нежелательно.Таким образом, Perl также предоставляет «притяжательную» форму квантификатора.

       *+     Match 0 or more times and give nothing back
       ++     Match 1 or more times and give nothing back
       ?+     Match 0 or 1 time and give nothing back
       {n}+   Match exactly n times and give nothing back (redundant)
       {n,}+  Match at least n times and give nothing back
       {n,m}+ Match at least n but not more than m times and give nothing back

Например,

      'aaaa' =~ /a++a/

никогда не совпадет, так как«a ++» сожрет все «a» в строке и не оставит их для оставшейся части шаблона.Эта функция может быть чрезвычайно полезна, чтобы дать Perl подсказки о том, куда она не должна возвращаться.Например, типичная проблема «сопоставить строку в двойных кавычках» может быть наиболее эффективно выполнена, если она записана в виде:

      /"(?:[^"\\]++|\\.)*+"/