Квантификаторы в Java Regex

Квантификатор указывает, сколько раз предшествующий элемент может повторяться. * означает «ноль или более», + — «один или более», ? — «ноль или один», а {n,m} задаёт точный диапазон. Это общее для всех разновидностей регулярных выражений. Что сбивает с толку в Java — это то, что каждый квантификатор существует в трёх режимах — жадном, ленивом и собственническом — и именно режим, а не счётчик, определяет, как движок регулярных выражений в java.util.regex обходит входную строку.

На этой странице рассмотрены четыре базовых квантификатора, три режима сопоставления, причины сверхсовпадений жадных шаблонов и то, как собственнические квантификаторы защищают от катастрофического возврата. Предполагается, что вы уже знаете, как скомпилировать Pattern и запустить Matcher; если нет — начните со страницы Pattern и Matcher. О метасимволах, которые будут повторяться, читайте в разделе символьные классы, а о захвате повторяющегося текста — в разделе группы.

Четыре базовых квантификатора

Прикрепите квантификатор к одному символу, символьному классу или группе, и он будет управлять повторением элемента, стоящего непосредственно перед ним:

Pattern.matches("ab*c", "abbbc");   // true  — three b's
Pattern.matches("ab+c", "ac");      // false — '+' needs at least one b
Pattern.matches("colou?r", "color");// true  — the 'u' is optional
Pattern.matches("\\d{3,5}", "1234");// true  — four digits is within 3..5

Жадный режим по умолчанию

Квантификатор без дополнительного суффикса является жадным: он потребляет как можно больше входных данных, затем откатывается назад — отдавая символы по одному, — пока остаток шаблона не сможет совпасть. Именно поэтому наивный шаблон <.+> применительно к HTML захватывает гораздо больше одного тега:

String html = "<b>one</b>";
Matcher m = Pattern.compile("<.+>").matcher(html);
m.find();
m.group(); // "<b>one</b>"  — '.+' ate everything, then backed up to the last '>'

Движок сначала захватил всю строку, не нашёл завершающего > и пошёл назад, пока не встретил > — оказавшись на самом последнем из них.

Ленивый режим: добавьте ?, чтобы захватывать как можно меньше

Добавьте ? к любому квантификатору (*?, +?, ??, {n,m}?), и он станет ленивым (также называемым reluctant): он сопоставляет минимальное число повторений и расширяется только при необходимости. Это именно то, что обычно нужно при сканировании ограниченных токенов:

String html = "<b>one</b>";
Matcher m = Pattern.compile("<.+?>").matcher(html);
m.find();
m.group(); // "<b>"  — stopped at the first '>'

Тот же шаблон, один лишний символ, противоположное поведение: жадный <.+> возвращает всю строку, а ленивый <.+?> — только первый тег.

Собственнический режим: добавьте + и не отдавайте ничего обратно

Добавьте + (*+, ++, ?+, {n,m}+), и квантификатор станет собственническим: он захватывает столько, сколько может, как жадный, но никогда не выполняет откат. Если остаток шаблона при этом не совпадает, всё сопоставление завершается неудачей — нет никакого «хода назад», чтобы спасти ситуацию.

// Possessive '.++' eats the final '>' too and won't return it, so no '>' is left
Pattern.compile("<.++>").matcher("<b>one</b>").find(); // false

Зачем отказываться от гибкости? Ради скорости и безопасности. Поскольку собственнический квантификатор никогда не пересматривает своё решение, он не может впасть в катастрофический откат — экспоненциальное замедление, которое зависает в потоке на шаблонах вроде (a+)+b при длинной последовательности a без b. Собственнический a++b отвечает «нет совпадения» практически мгновенно.

Практический пример: все три режима рядом

Следующая программа применяет одни и те же входные данные к жадному, ленивому и собственническому квантификаторам, а затем демонстрирует диапазон {n,m} и квантификатор группы. Всё это — чистый java.util.regex из JDK.

Что можно извлечь из этого примера:

• Жадный <.+> вывел <b>one</b><i>two</i> — всю строку. Он потребил всё, затем откатился до последнего > — именно поэтому жадные шаблоны сверхсовпадают через разделители.
• Ленивый <.+?> вывел <b> на тех же входных данных. Единственный ? переключил стратегию с «максимум» на «минимум», остановившись на первом > — решение для посекундного сканирования тегов.
• Собственнический <.++> вывел matches=false. Он поглотил завершающий > и отказался его вернуть, поэтому для > в конце шаблона ничего не осталось, и вся попытка провалилась — цена отсутствия отката.
• \d{3,5} отклонил 12 (no match, слишком мало цифр), принял 123 и 12345 целиком, а на 1234567 совпал только 12345 (длина 5) — верхняя граница 5 ограничила его, даже несмотря на наличие большего числа цифр.
• Шаблон группы (\w+\s*){2,3} совпал с alpha beta gamma — три слова, максимум, — доказав, что квантификатор применяется ко всей группе в скобках, а a++b мгновенно вернул false при длинной последовательности a без b, демонстрируя, как собственнические квантификаторы обходят катастрофический откат.

Какой режим использовать?

• Используйте ленивый (*?, +?), когда сопоставляете содержимое между разделителями — кавычками, тегами, скобками, ограниченными блоками. Он останавливается на первом закрывающем разделителе, а не на последнем, что почти всегда и нужно.
• Оставайтесь в жадном режиме (по умолчанию), когда вам действительно нужно наидлиннейшее совпадение или когда существует только один возможный вариант совпадения и дополнительный ?/+ был бы просто лишним.
• Используйте собственнический (*+, ++) как инструмент производительности и безопасности при работе с неконтролируемыми входными данными. Поскольку он никогда не выполняет откат, он не может спровоцировать катастрофический откат, однако будет завершаться неудачей там, где жадный квантификатор смог бы спасти ситуацию — поэтому применяйте его только там, где вы уверены, что откат не нужен.

Распространённое реальное исправление: регулярное выражение, которое работает на малых входных данных, но зависает на больших, — это обычно жадный квантификатор внутри группы, например (\w+)+. Замена внутреннего квантификатора на собственнический ((\w++)+ или реструктуризация шаблона) устраняет экспоненциальное замедление.

Практика