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

Из 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, но я слышал, что эта концепция для большинства современных реализаций регулярных выражений одинакова.

Ответ 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"

Ответ 2

От эта ссылка, где автор учебника подтверждает дух вашего вопроса:

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

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

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

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

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

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

Ответ 3

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

например, для строки

ABCDEF

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

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

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

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

Ответ 4

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

Ответ 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 подсказки о том, где она не должна возвращаться. Например, типичная проблема "совпадение с двойной кавычкой" может быть наиболее эффективно выполнена при написании как:
   /"(?:[^"\\]++|\\.)*+"/
поскольку мы знаем, что если окончательная цитата не соответствует, то возврат не поможет. Дополнительную информацию см. В разделе независимого подвыражения (?>...); Притяжательные кванторы - это просто синтаксический сахар для этой конструкции. Например, приведенный выше пример также можно записать следующим образом:
   /"(?>(?:(?>[^"\\]+)|\\.)*)"/