Сопоставление текста между разделителями: жадное или ленивое регулярное выражение?

Для общей проблемы сопоставления текста между разделителями (например, < и >) Существует два общих паттерна:

  • с использованием жадного * или + квантора в виде START [^END]* END, например <[^>]*>, или
  • с использованием квантора lazy *? или +? в виде START .*? END, например <.*?>.
Есть ли особая причина отдавать предпочтение одному перед другим?
3 17
regex language-agnostic regex-greedy

3 ответа:

Некоторые преимущества:

[^>]*:

  • более выразительно.
  • захватывает новые строки независимо от флага /s.
  • считается быстрее, потому что движок не должен отступать, чтобы найти удачное совпадение (с [^>] движок не делает выбор - мы даем ему только один способ сопоставить шаблон со строкой).

.*?

  • нет "дублирования кода" - конечный символ появляется только один раз.
  • проще в случаях конца разделитель-это больше, чем символ. (класс символов не будет работать в этом случае) распространенной альтернативой является (?:(?!END).)*. Это еще хуже, если конечным разделителем является другой шаблон.
12

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

Пример: если вы попытаетесь сопоставить <tag1><tag2>Hello! с <.*?>Hello!, регулярное выражение будет соответствовать 

<tag1><tag2>Hello!

Тогда как <[^>]*>Hello! будет соответствовать 

<tag2>Hello!
7

То, что большинство людей не учитывают при подходе к подобным вопросам, - это то, что происходит, когда регулярное выражение не может найти совпадение. это когда наиболее вероятно появление воронки убийственной производительности. Например, возьмем пример Тима, где вы ищете что-то вроде <tag>Hello!. Рассмотрим, что происходит с: 

<.*?>Hello!
Движок регулярных выражений находит < и быстро находит закрывающее >, но не >Hello!. Поэтому .*? продолжает искать >, что За следует Hello!. Если его нет, то он пройдет весь путь до конца документа, прежде чем сдастся. Затем механизм регулярных выражений возобновляет сканирование, пока не найдет другой <, и повторяет попытку. Мы уже знаем, как это произойдет, но механизм регулярных выражений, как правило, этого не делает; он проходит через ту же самую ригамароль с каждым < в документе. Теперь рассмотрим другое регулярное выражение: 
<[^>]*>Hello!

Как и раньше, он быстро совпадает с < в >, но не соответствует Hello!. Он вернется к <, затем завершит работу и начнет сканирование для другого <. Он по-прежнему будет проверять каждое <, как и первое регулярное выражение, но он не будет искать весь путь до конца документа каждый раз, когда он находит его.

Но все еще хуже, чем это. Если вы подумаете об этом, .*? фактически эквивалентно отрицательному lookahead. Он говорит: "прежде чем использовать следующий символ, убедитесь, что остаток регулярного выражения не может совпадать в этой позиции." В другими словами, 
/<.*?>Hello!/

... эквивалентно: 

/<(?:(?!>Hello!).)*(?:>Hello!|\z(*FAIL))/
Таким образом, на каждой позиции, которую вы выполняете, не просто нормальная попытка матча, но гораздо более дорогой взгляд. (Это, по крайней мере, вдвое дороже, потому что lookahead должен сканировать по крайней мере один символ, тогда . идет вперед и потребляет символ.)

((*FAIL) является одним из глаголов управления обратным отслеживанием Perl (также поддерживается в PHP). |\z(*FAIL) означает "или дойти до конца документа и дать вверх".)

Наконец, есть еще одно преимущество подхода с отрицанием класса символов. Хотя он не действует (как указал @Bart), как будто Квантор является притяжательным, ничто не мешает вам сделать его притяжательным, если ваш вкус поддерживает его: 
/<[^>]*+>Hello!/

...или оберните его в атомную группу: 

/(?><[^>]*>)Hello!/
Эти регексы не только никогда не будут возвращаться без необходимости, но и не должны сохранять информацию о состоянии, которая делает возможным обратное отслеживание.
6