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

Question

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

• с использованием жадного алгоритма * или + вформа START [^END]* END, например <[^>]*> или
• с использованием ленивого квантификатора *? или +? в форме START .*? END, например <.*?>.

Есть ли конкретная причина отдать предпочтение одному над другим?

Answer 1

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

[^>]*:

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

.*?

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

Answer 2

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

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

<tag1><tag2>Hello!

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

<tag2>Hello!

Answer 3

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

<.*?>Hello!

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

<[^>]*>Hello!

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

Но это даже хуже, чем это.Если вы думаете об этом, .*? фактически эквивалентно негативному прогнозу.Он говорит: «Прежде чем использовать следующий символ, убедитесь, что остаток регулярного выражения не может совпадать в этой позиции».Другими словами,

/<.*?>Hello!/

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

/<(?:(?!>Hello!).)*(?:>Hello!|\z(*FAIL))/

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

((*FAIL) является одним из откатов Perl-control verbs (также поддерживается в PHP). |\z(*FAIL) означает «или дойти до конца документа и сдаться».)

Наконец, есть еще одно преимущество подхода класса отрицанных символов,Хотя он (как указал @Bart) не действует как квантификатор собственнический, ничто не мешает вам сделать притяжательным, если ваш аромат поддерживает это:

/<[^>]*+>Hello!/

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

/(?><[^>]*>)Hello!/

Мало того, что эти регулярные выражения никогда не будут возвращаться без необходимости, им не нужно сохранять информацию о состоянии, которая делает возможным возврат.