Pull to refresh

Сверхжадные квантификаторы

Reading time 4 min
Views 15K
В статье Regexp — это «язык программирования». Основы была поставлена задача: написать регулярное выражение, находящее в цепочке символов текст в двойных кавычках, причем внутри кавычек "..." могут быть и сами символы ", если они экранированы обратным слэшем, например:
one two "foo:=\"quux\"; print" three "four"
Здесь наш регекс должен найти соответствие цепочке
"foo:=\"quux\"; print"
Автором (той статьи) было предложено такое решение:
/ " ( \\" | [^"] )* " /x
(здесь и далее синтаксис Perl; ключ /x означает, что пробелы в регексе не учитываются, мы добавили их лишь для наглядности, чтобы части регекса не слились в единый «модемный шум»).
Этот регекс работает в том случае, когда есть совпадение (текст в кавычках). Проблема же в том, что он находит текст в кавычках даже тогда, когда текста в кавычках (согласно нашим правилам экранирования обратным слэшем) просто нет. Например, в цепочке "\" регекс находит соответствие (равное всей строке "\" ), хотя его быть не должно: кавычка открыта, экранированная кавычка… а вот закрывающей-то кавычки нет.
Ситуацию легко исправить, исходную задачу решить несложно, внеся несколько простых изменений в регекс… но речь не об этом, а о том, что если у вас в руках современный инструмент, т. е. движок регексов (свежая версия Perl, Java или PHP с PCRE), то вы можете «исправить» описанный регекс, добавив в него всего лишь 1 символ. Какой? Куда? Почему? Если знаете ответы, то читать дальше вам не стОит ;-)

Сначала разберемся, почему же исходная версия
/ " ( \\" | [^"] )* " /x
матчит строку "\"
События развиваются (очень примерно) так:
  1. " (в регексе) матчит " (в проверяемой цепочке)
  2. \\" (1-й вариант в альтернативе (… | ...) в регексе) матчит \" (в цепочке)
  3. Мы пришли к концу цепочки. В регексе еще осталась закрывающая кавычка " (либо еще раз содержимое альтернативы (...|...) ), а в цепочке — пусто, матчить " нечему. Движок регексов видит, что матча (соответствия) нет.
    Тут вроде бы и сказке конец… но не тут-то было! Тут только начинается интересное. Движок регексов откатывается назад к началу шага 2. И на этот раз пытается матчить проверяемой цепочке следующую, 2-ю альтернативу: [^"]. И — чудненько! — у него это получается.
  4. [^"] в регексе матчит \ в цепочке. Бэкслеш — это не кавычка? Не кавычка. Стало быть, матч.
  5. Движок регексов будет пытаться найти (...|...) еще раз, т. к. * — это жадный квантификатор (A* означает «найди как можно больше штуковин, соответствующих A»). У него это не получится: в цепочке осталась только кавычка, которая не является ни сочетанием \", ни не-кавычкой [^"]
  6. Тогда движок регексов сопоставит оставшуюся часть цепочки, одинокую кавычку ", оставшейся части регекса, одинокой кавычке ". Матч! Совпадение найдено.

В общем, всё дело в «волшебных пузырьках», точнее, в откате назад движка регулярных выражений. Он откатывается после того, как альтернатива с квантификатором (...|...)* захватывает всю оставшуюся часть цепочки до конца, и оставшейся части регекса «ничего не достаётся». А можно ли попросить движок регексов не откатываться? Оказывается, в современных движках регексов (в частности, в Perl 5.10, в относительно свежих версиях Java и PHP со свежим PCRE) это возможно. На помощь приходят… Чип и Дэйл Спасатели Малибу

… Сверхжадные квантификаторы



А что это вообще за фрукты? Все знают обычные квантификаторы:
* + ? {m, n}
Они жадные (greedy), т. е. они «захватывают» как можно больше из проверяемой цепочки. Также есть нежадные (non-greedy, lazy, reluctant, ленивые) квантификаторы
*? +? ?? {m, n}?
которые захватывают как можно меньше из цепочки.
В современных движках регексов, помимо этих двух «классических» типов квантификаторов, реализованы также possessive quantifiers:
*+ ++ ?+ {m, n}+
Нам не известен для этого термина устоявшийся русский перевод, поэтому они были названы, как показалось разумным: сверхжадные квантификаторы. Почему «сверхжадные»? Потому что они, во-первых, ведут себя как жадные, т. е. захватывают как можно больше из цепочки. Во-вторых, они, в каком-то смысле, ещё «жаднее» жадных и идут дальше них: один раз что-то «схватив», они никогда не откатываются назад, они не «отдают» кусочки схваченного ими следующим частям регекса.
Пример. Регекс
/ " .* " /x
при обработке строки
one "two" three "four"
Найдет соответствие:
"two" three "four"
поскольку * жадный и «съедает» все кавычки, какие только может съесть (в том числе он съедает и кавычку после four, но затем он «отдаёт» её обратно, т. к. движок регексов не видит, чему матчить последнюю " из регекса).
А вот «сверхжадный» вариант
/ " .*+ " /x
вообще ничего в той же цепочке не найдёт! (т. е. не будет матча). Почему? Потому что .*+ скушает всю оставшуюся часть цепочки после открывающей кавычки, и ему всё равно, будет ли, чему матчить закрывающую " из регекса. Он всё равно не отдаст часть «съеденного» им куска цепочки.
Зачем же нужны такие странные квантификаторы? Оказывается, они очень полезны тогда, когда «откат» движка регексов назад для нас нежелателен. А как показывает практика, откат не всегда желателен… если, конечно, речь не идёт о растрате казенных денег ;-)

Так ведь у нас с первоначальной задачей — поиском текста в кавычках — была именно такая проблема, срабатывал откат, который приводил к матчу в «ненужных» цепочках вроде "\" Добавим в исходный регекс
/ " ( \\" | [^"] )* " /x
Ма-аленький плюсик:
/ " ( \\" | [^"] )*+ " /x
и задача решена! Такой вариант регекса не будет матчить строки вроде
"\"
или
who "\"the\"heck\" is quux anyway

Из пушки по воробьям



На самом деле, для столь простой задачи как поиск «закавыченного» текста никакие продвинутые возможности вроде possessive quantifiers не нужны. Следующий регекс замечательно справится с этой задачей:
/" ( \\. | [^"\\] )* "/x
Т. е. буквально «открывающая кавычка, ( бэкслэш, за которым следует любой символ ЛИБО любой символ кроме бэкслеша и кавычки) нуль или более раз, закрывающая кавычка».
Если символ новая-строка может встретиться после \ и мы считаем это допустимым, то необходимо добавить ключ /s, т. к. без этого ключа точка. не матчит символ новая-строка.
Tags:
Hubs:
+55
Comments 22
Comments Comments 22

Articles