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

    В статье 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, т. к. без этого ключа точка. не матчит символ новая-строка.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 21
    • 0
      Отличное дополнение к первой статье :).
      Спасибо.
      • +2
        Хм, я думал что неплохо разбираюсь в PCRE, но вот про «сверхжадные квантификаторы» не знал.
        Спасибо за труд
        • +3
          На здоровье :)
          Если будет спрос, следующую заметку напишу про «бесконечный» бэктрекинг (откат), т. е. ситуацию, когда откат приводит к проверке миллионов вариантов и регекс кажется «зациклившимся», и то, как откат предотвратить (атомарную группировку). Собственно, сверхжадные квантификаторы — это частный случай атомарной группировки.
          • 0
            Присоеденяюсь!
            Давно регспы юзаю и очень уважаю за их лакончиность, но вот про сверх-жадность не знал.

            Огромное спасибо за интересный материал!
          • 0
            Спасибо за статью. Добавил кармы, теперь можете перенести в блог по Regexp
            • –2
              А что, парсеры уже отменили?
              • НЛО прилетело и опубликовало эту надпись здесь
              • +3
                Можно еще такой вариант решения (php 5.2.8)
                /"((?<=\\\)"|[^"])*"/
                Это сделано с помощью позитивной ретроспективной проверки, фактически: Кавычка, (сколько угодно символов, которые являются или не-кавычкой, или кавычкой, но имеющей перед собой обратный слэш), кавычка
                • 0
                  Данный вариант не будет работать в 100% случаев. Например:
                  "abc\\" — строка из 4х символов (последний: слэш) — не будет отпарсена правильно

                  А вот вариант, приведённый автором в конце статьи, будет работать корректно.
                  • 0
                    Прочтите ниже вопрос netlink и мой ответ на него. Вариант korvin0 корректен, а цепочка
                    "abc\\"
                    не содержит текст в кавычках, если строго следовать описанным в статье правилам.
                • 0
                  Отлично! Все подробно и по полочкам. Сейчас в PHP экспериментировать буду.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • +3
                      Там 3 разных «решения», вы про какое?

                      Впрочем, про какое бы решение ни шла речь, вы заметили тонкость: решение с *+ и решение в конце статьи работают просто-напросто по-разному. Цепочка
                      aaa="bbb\\"
                      не соответствует регексу
                      / " ( \\" | [^"] )*+ " /x
                      однако соответствует регексу
                      / " ( [^"\\] | \\. )* " /x

                      В первом случае бэкслэш экранирует исключительно кавычку, и это "корректно", т. к. согласуется с условиями нашей задачи. Мы ничего не говорили о том, что бэкслэш может экранировать что бы то ни было кроме кавычки. Поэтому 1-й бэкслэш воспринимается как обычный одиночный символ, 2-й бэкслэш экранирует следующую за ним кавычку, а… а закрывающей-то кавычки нет! Поэтому соответствия (матча) регексу нет.

                      Во втором случае бэкслэш экранирует любой символ (а не только кавычку), и это "корректно", потому что это то, к чему мы все привыкли. 1-й бэкслэш в цепочке экранирует 2-й бэкслэш, а за ними идёт закрывающая кавычка… всё в порядке, есть матч.

                      Т. е. в обоих случаях всё «корректно», только переменная «корректно» меняет значение между случаями ;-)
                      С другой стороны, наполовину полный стакан всегда наполовину пуст, поэтому, если у вас плохое настроение, то у вас есть полное право сказать, что тут всё в дюпель не правильно: либо 2-е решение не решает задачу, либо сама задача поставлена криво ;-)

                      В общем, на самом деле всё не так, как в действительности ;-)

                      И спасибо за комментарий. На одном из моих любимых телеканалов есть лозунг: «Question everything». So thank you for questioning my regexes, mate :-)
                    • 0
                      Весьма любопытный материал, спасибо. А можете привести более иллюстративный пример регулярки, где эта фича будет наиболее красивым решением?
                      • 0
                        Мне кажется, что «сверхжадность» — это, скорее, необходимое зло, чем что-то красивое. Это как каска на голове или страховка: с ними неудобно, но они предотвращают «бааальшие» проблемы.
                        В качестве «иллюстративного» примера: попробуйте написать регекс, который матчит текст в скобках, причем внутри скобок могут быть вложенные скобки, например:
                        log((4 + k/3) * tan(2*phi) + sin((psi - theta)/2))
                        тут регекс должен найти аргумент функции log.
                        Если вы напишете этот регекс без сверхжадных квантификаторов (и без атомарной группировки, которая их обобщение), то, скорее всего, ваш регекс умрёт (будет матчить невыносимо долго) уже на «невалидной» цепочке в 30-40-80 символов.
                        Но давайте я об этом напишу в следующей заметке через ~ неделю, ок?
                      • 0
                        Очень познавательно, но сама по себе фича ужасна, так как разрушает декларативность языка регэкспов. Результат начинает зависеть, например, от порядка, в котором перечислены альтернативы — в общем, применять такое надо только если больше ничего не помогает.
                        • 0
                          В порядке альтернативы есть свои плюсы.
                        • 0
                          Отличная статья! Автору спасибо.
                          • +1
                            Интересная статья, спасибо.
                            К информации, в статье на Википедии посвященной регуляркам — Регулярное_выражение наткнулся еще на одно определение сверхжадных квантификаторов — «Ревнивая квантификация»
                            • 0
                              «Ревнивая» — это забавно :)
                              Такие термины обычно получаются, когда люди пользуются двуязычными словарями.
                              В русском языке просто нет аналога английского слова possessive, которое означает
                              possessive (adjective)
                              1 wanting someone to have feelings of love or friendship for you and no one else
                              possessive of/about
                              She was terribly possessive of our eldest son.
                              2 unwilling to let other people use something you own
                              possessive of/about
                              He's so possessive about his new car.
                              3 technical used in grammar to show that something belongs to someone or something
                              possessive pronoun/form/case etc
                              the possessive pronouns 'ours' and 'mine'

                              Значение 1, действительно, близко по смыслу к русскому «ревнивый». Но в possessive quantifier используется, естественно, 2-е значение («владея» куском строки, оно не хочет отдавать его другим частям регекса), для которого в русском аналога нет, разве что «жадина», но слово «жадный» уже занято другим термином. При написании заметки я думал над синонимами «жадины», от которых можно образовать прилагательные. Но увы, получалась полная жесть: скряжные и сквалыжные квантификаторы 8-)
                              Можно извратиться также, использовав 3-е значение: притяжательные квантификаторы. А если кто-то возразит, то «неопровержимо» «доказать» свое мнение ссылкой на двуязычный словарь
                              8-)
                            • 0
                              Автор — ты молодец.
                              Спасибо что не пожалел времени написать!
                              +1

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.