Регулярное выражение: кто жаднее?
Моя основная забота связана с Java-вкусом, но я также хотел бы получить информацию о других.
Допустим, у вас есть подшаблон вроде этого:
(.*)(.*)
Не очень полезно как есть, но скажем, эти две группы захвата (скажем, \1 а также \2) являются частью большего шаблона, который соответствует обратным ссылкам на эти группы и т. д.
Так что оба жадны тем, что пытаются захватить как можно больше, беря меньше, когда им нужно.
Мой вопрос: кто жаднее? Есть ли \1 получить первый приоритет, давая \2 свою долю только если это надо?
Как насчет:
(.*)(.*)(.*)
Давайте предположим, что \1 действительно получает первый приоритет. Допустим, он стал слишком жадным, а затем выплюнул персонажа. Кто получит это первым? Это всегда \2 или это может быть \3?
Давайте предположим, что это \2 что получает \1Отказ. Если это все еще не работает, кто сейчас выплевывает? Есть ли \2 плевать на \3или делает \1 выплюнуть другой, чтобы \2 первый?
Бонусный вопрос
Что произойдет, если вы напишите что-то вроде этого:
(.*)(.*?)(.*)
Сейчас \2 неохотно Это значит \1 выплевывает \3, а также \2 только неохотно принимает \3Отказ?
пример
Возможно, для меня было ошибкой не приводить конкретные примеры, показывающие, как я использую эти шаблоны, но вот некоторые из них:
System.out.println(
"OhMyGod=MyMyMyOhGodOhGodOhGod"
.replaceAll("^(.*)(.*)(.*)=(\\1|\\2|\\3)+$", "<$1><$2><$3>")
); // prints "<Oh><My><God>"
// same pattern, different input string
System.out.println(
"OhMyGod=OhMyGodOhOhOh"
.replaceAll("^(.*)(.*)(.*)=(\\1|\\2|\\3)+$", "<$1><$2><$3>")
); // prints "<Oh><MyGod><>"
// now \2 is reluctant
System.out.println(
"OhMyGod=OhMyGodOhOhOh"
.replaceAll("^(.*)(.*?)(.*)=(\\1|\\2|\\3)+$", "<$1><$2><$3>")
); // prints "<Oh><><MyGod>"
5 ответов
Добавление ваших конкретных примеров кардинально меняет природу вопроса. Это все еще начинается, как я описал в моем первом ответе, с первым (.*) сожрать всех персонажей, а вторая и третья группы позволят им иметь их, но тогда он должен совпадать со знаком равенства.
Очевидно, что в конце строки нет ни одного, поэтому группа #1 возвращает символы один за другим, пока = в регулярном выражении может соответствовать = в цель. Затем двигатель регулярных выражений начинает пытаться сопоставить (\1|\2|\3)+$ и начинается настоящее веселье.
Группа 1 отказывается от d и группа 2 (которая все еще пуста) берет это, но остальная часть регулярного выражения все еще не может соответствовать. Группа 1 отказывается от o и группа 2 матча od, но остальные регулярные выражения по-прежнему не могут соответствовать. И так далее, с вовлечением третьей группы, и все трое всячески разделяют входные данные, пока не будет достигнуто полное соответствие. RegexBuddy сообщает, что для этого требуется 13 426 шагов.
В первом примере жадность (или ее отсутствие) на самом деле не является фактором; единственный способ достичь соответствия - это если слова Oh, My а также God захвачены в отдельные группы, так что в конечном итоге это то, что происходит. Даже не имеет значения, какая группа запечатлела какое слово - это просто первым пришел, первым обслужен, как я уже говорил.
Во втором и третьем примерах префикс необходимо разбить только на две части: Oh а также MyGod, Группа 2 захватывает MyGod во втором примере, потому что он следующий в очереди и он жадный, как в первом примере. В третьем примере каждый раз, когда группа 1 отбрасывает персонажа, группа 2 (неохотно) позволяет группе 3 взять его вместо себя, так что это тот, который в конечном итоге получает MyGod,
Конечно, это сложнее (и утомительнее), но я надеюсь, что это ответит на ваш вопрос. И я должен сказать, что вы выбрали интересную целевую строку; если бы у движка регулярных выражений был оргазм, я думаю, что эти регулярные выражения могли бы его вызвать.:D
\1 будет иметь приоритет, \2 а также \3 никогда не будет соответствовать ничего. \2 будет иметь приоритет над \3,
Как правило, думайте об этом так: обратное отслеживание будет происходить только для того, чтобы удовлетворить совпадение, оно не будет происходить для удовлетворения жадности, поэтому лучше всего оставить:)
объяснение обратного слежения и жадности - это многое для меня, я бы посоветовал освоить регулярные выражения Friedl.
Квантификаторы по умолчанию не являются жадными, они просто поспешные. В вашем примере первый (.*) начнем с того, что пожираем все, что можем, без учета потребностей регулярного выражения в целом. Только тогда он передает управление следующей части, и при необходимости он возвращает часть или все то, что он только что взял (то есть, возвращает), чтобы остальная часть регулярного выражения могла выполнять свою работу.
Это не обязательно в этом случае, потому что все остальное может юридически соответствовать нулевым символам. Если бы квантификаторы были действительно жадными, три группы торговались бы до тех пор, пока не разделили входные данные как можно более равномерно; вместо этого вторая и третья группы позволяют первой сохранить то, что нужно. Они возьмут это, если это поставят перед ними, но они не будут бороться за это. (Это было бы верно, даже если бы они имели собственнические квантификаторы, т.е. (.*)(.*+)(.*+).)
Создание второй точки-звезды неохотно ничего не меняет, но переключение первой делает. Нежелательный квантификатор начинается с сопоставления только того количества, которое ему необходимо, затем переходит к следующей части. Итак, первая группа в (.*?)(.*)(.*) Вначале ничего не сопоставляется, затем вторая группа все проглатывает, а третья группа кричит "пиаааааааа" всю дорогу домой.
Вот бонусный вопрос для вас: что произойдет, если вы сделаете все три квантификатора неохотными? (Подсказка: в Java это такой же вопрос API, как и вопрос регулярных выражений.)
Регулярные выражения работают в последовательности, это означает, что Regex-оценщик покинет группу только тогда, когда он больше не сможет найти решение для этой группы, и в конечном итоге выполнит некоторый возврат, чтобы привести строку в соответствие следующей группе. Если вы выполните это регулярное выражение, вы получите все свои символы, оцененные в первой группе, но не в следующих (знак вопроса также не имеет значения).
Как простое общее правило: выигрывает самый левый квантификатор. Таким образом, до тех пор, пока следующие квантификаторы идентифицируют чисто необязательные подшаблоны (независимо от того, являются ли они несвязными), первый берет все.