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

Моя главная проблема связана с 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>"

Ответы

Ответ 1

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

Очевидно, что в конце строки нет ни одного элемента, поэтому группа # 1 возвращает символы назад один за другим, пока = в регулярном выражении не сможет соответствовать = в целевом объекте. Затем двигатель regex начинает пытаться соответствовать (\1|\2|\3)+$, и начинается настоящая забава.

Группа 1 отказывается от d, а группа 2 (которая все еще пуста) принимает ее, но остальная часть регулярного выражения все еще не может совпадать. Группа 1 отдает значения o и group 2 od, но остальное регулярное выражение все еще не может совпадать. И так оно и происходит, с участием третьей группы, и три из них нарезают входной сигнал всеми возможными способами до достижения общего соответствия. RegexBuddy сообщает, что для этого требуется 13 426 шагов.

В первом примере жадность (или ее отсутствие) на самом деле не является фактором; единственный способ совпадения может заключаться в том, что слова Oh, My и God фиксируются в отдельных группах, поэтому в итоге это происходит. Даже не имеет значения, какая группа фиксирует какое слово - это то, что только что произошло, прежде всего, как я сказал ранее.

Во втором и третьем примерах необходимо только разбить префикс на два куска: Oh и MyGod. Группа 2 захватывает MyGod во втором примере, потому что она следующая в строке и она жадная, как в первом примере. В третьем примере каждый раз, когда группа 1 бросает символ, группа 2 (неохотно) позволяет группе 3 взять ее вместо этого, так что та, которая попадает во владение MyGod.

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

Ответ 2

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

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

объяснение обратного отслеживания и жадности для меня очень важно, я бы предложил friedl Освоение регулярных выражений

Ответ 3

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

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

Устранение второй точки-звезды не меняет ничего, но переключает первый. Недостаточный квантификатор начинается с сопоставления только столько, сколько ему нужно, а затем отрывается до следующей части. Итак, первая группа из (.*?)(.*)(.*) начинается, ничего не сопоставляя, затем вторая группа поглощает все, а третья группа плачет "weee weee weee" до конца.

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

Ответ 4

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

Ответ 5

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