Регулярное выражение: кто жаднее?

Question

Меня больше всего интересует вкус 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>"

Answer 1

\1 будет иметь приоритет, \2 и \3 всегда будут ничего не соответствовать. \2 будет иметь приоритет над \3.

Как правило, думайте об этом следующим образом: обратное отслеживание будет только , чтобы удовлетворить совпадение, оно не будет происходить, чтобы удовлетворить жадность, поэтому лучше всего оставить :)

объяснение обратного слежения и жадности - это многое для меня, я бы посоветовал Мастеринг Регулярных выражений Фридла

Answer 2

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

Очевидно, что в конце строки нет ни одного, поэтому группа # 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

Answer 3

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

В этом случае нет необходимости, потому что все остальное может юридически соответствовать нулевым символам. Если бы квантификаторы были действительно жадными, три группы будут торговаться, пока они не разделят входные данные настолько равномерно, насколько это возможно; вместо этого вторая и третья группы позволяют первой сохранить то, что нужно. Они возьмут это, если это поставят перед ними, но они не будут бороться за это. (Это было бы верно, даже если бы у них были собственнические квантификаторы, т.е. (.*)(.*+)(.*+).)

Создание второй точки с неохотой не меняет ничего, но переключение первого делает. Нежелательный квантификатор начинается с сопоставления только того количества, которое необходимо, а затем переходит к следующей части. Таким образом, первая группа в (.*?)(.*)(.*) начинается с того, что ничего не соответствует, затем вторая группа все проглатывает, а третья группа кричит «пи-пи-пи» всю дорогу домой.

Вот бонусный вопрос для вас : Что произойдет, если вы сделаете все три квантификатора неохотными? (Подсказка: в Java это такой же вопрос API, как и вопрос регулярных выражений.)

Answer 4

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

Answer 5

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