В чем разница между квантификаторами регулярных выражений `Greedy` и` Reluctant`?

Question

Из Pattern Javadocs:

Greedy quantifiers:
X?      X, once or not at all  
X*      X, zero or more times  
X+      X, one or more times  
X{n}    X, exactly n times  
X{n,}   X, at least n times  
X{n,m}  X, at least n but not more than m times

Reluctant quantifiers:
X??     X, once or not at all  
X*?     X, zero or more times  
X+?     X, one or more times  
X{n}?   X, exactly n times  
X{n,}?  X, at least n times  
X{n,m}? X, at least n but not more than m times

Описание того, что они делают, одно и то же ... так в чем же разница?

Буду очень признателен за некоторые примеры.

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

Answer 1

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

Пример:

"The red fox jumped over the red fence"
/(.*)red/ => \1 = "The red fox jumped over the "
/(.*?)red/ => \1 = "The "

"aaa"
/a?a*/ => \1 = "a", \2 = "aa"
/a??a*/ => \1 = "", \2 = "aaa"

"Mr. Doe, John"
/^(?:Mrs?.)?.*\b(.*)$/ => \1 = "John"
/^(?:Mrs?.)?.*?\b(.*)$/ => \1 = "Doe, John"

Answer 2

С по этой ссылке , где автор урока признает дух вашего вопроса:

На первый взгляд может показаться, что квантификаторы X ?, X ?? и X? + сделать точно так же, так как все они обещать совпадать с "X", один раз или нет все ". Есть тонкая реализация различия, которые будут объяснены в конце этого раздела.

Они продолжают собирать примеры и предлагают объяснение:

Жадные квантификаторы считаются «жадный», потому что они заставляют совпадение, чтобы прочитать или съесть, весь входная строка до попытки Первый матч Если первый матч попытка (вся входная строка) терпит неудачу, сопоставитель отступает от входа строка на один символ и пытается снова, повторяя процесс до совпадение найдено или больше нет символы слева от. В зависимости от используемого в выражение, последнее, что будет попробуйте сопоставить с 1 или 0 символы.

Однако неохотные квантификаторы принять противоположный подход: они начинают в начале входной строки, затем неохотно съесть одного персонажа в время в поисках матча. Последний что они пытаются это весь вход строка.

И для дополнительного кредита, притяжательное объяснение:

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

Answer 3

скажем, у вас есть регулярное выражение "a\w*b", и используйте его на "abab" Жадное совпадение будет совпадать с "abab" (оно ищет a, максимально возможное число вхождений \w и b), а сопоставление с неохотой совпадет с "ab" (как можно меньшим \w)

Answer 4

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

например, учитывая строку

ABCDEF

жадный классификатор

ab [a-z] * [a-z] будет соответствовать abcdef

неохотный классификатор

ab [a-z] *? [A-z] будет соответствовать abc

Answer 5

Есть документация о том, как Perl обрабатывает эти квантификаторы perldoc perlre.

По умолчанию квантифицированный подшаблон является «жадным», то есть он будет совпадать столько раз, сколько это возможно (учитывая конкретное начальное местоположение), но при этом все остальные паттерны будут совпадать. Если вы хотите, чтобы он совпадал с минимально возможным числом раз, следуйте квантификатору с «?». Обратите внимание, что значения не меняются, только «жадность»: *? Match 0 or more times, not greedily +? Match 1 or more times, not greedily ?? Match 0 or 1 time, not greedily {n}? Match exactly n times, not greedily {n,}? Match at least n times, not greedily {n,m}? Match at least n but not more than m times, not greedily По умолчанию, когда квантифицированный подшаблон не позволяет сопоставить остальную часть общего шаблона, 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 подсказки о том, куда она не должна возвращаться. Например, типичная проблема «сопоставить строку в двойных кавычках» может быть наиболее эффективно выполнена, когда она записана в виде: /"(?:[^"\\]++|\\.)*+"/ так как мы знаем, что если окончательная цитата не совпадает, возврат не поможет. См. Независимое подвыражение (?>...) для получения более подробной информации; притяжательные кванторы являются просто синтаксическим сахаром для этой конструкции. Например, приведенный выше пример также может быть записан следующим образом: /"(?>(?:(?>[^"\\]+)|\\.)*)"/