Атомарная группировка, или Ни шагу назад!

На собеседовании Ивану дали такую задачу. Написать регекс, который матчит выражение в круглых скобках (. ), причем внутри скобок может быть множество выражений в других круглых скобках, вероятно, вложенных. Например: в цепочке sin(2*pi/tan(.7+b*tanh(b/2)))+8*cos(b/4) регекс должен матчить (находить) содержимое 1-й пары скобок: (2*pi/tan(.7+b*tanh(b/2))) Однако, регекс не должен матчить такую часть цепочки, в которой скобки не сбалансированы (открытые скобки не закрываются или, наоборот, закрываются скобки, которые вовсе не были открыты). Например, обрабатывая цепочку (sin(b/2) регекс должен найти (b/2) , проигнорировав 1-ю скобку, т. к. она не закрывается. А в следующей цепочке 2*pi)*(r*r регекс вообще не должен ничего найти, т. к. ни одной пары «правильных» скобок тут нет. И ещё одно ограничение состоит в том, что «пустые» скобки () запрещено матчить, т. е. внутри пары скобок должно быть хоть какое-то содержимое. Короче говоря, нужно матчить «корректное» выражение в скобках, которое может содержать подвыражения с вложенными скобками, причем пустые скобки () не считаются корректными. Иван выписывает примерные выражения и мотает на ус: 1) искомое выражение — это нечто в скобках. 2) Внутри скобок может быть либо нечто без скобок, и тогда всё просто: (3.14 * R * R) … либо нечто в скобках: (2 * sin(pi/2)) Стоп! В последнем случае внутри скобок уже не просто «нечто в скобках», а сначала «нечто без скобок» 2 * sin , и лишь затем «нечто в скобках» (pi/2) ! И становится понятно, что внутри скобок «нечто без скобок» и «нечто в скобках» могут встречаться сколько угодно раз: (2 * (a+8.5) * sin(pi/2) / (b - 1e-8)) . Задать «нечто без скобок» на языке регексов совсем просто: [^)(]+ . Как задать альтернативу (нечто без скобок ЛИБО нечто в скобках) и «сколько угодно раз», тоже просто: метасимволы | и +. Но что же такое «нечто в скобках» и как это написать на языке регексов? «Нечто в скобках»… «Нечто в скобках»… Где-то оно уже встречалось… А-а, вот: пункт 1) искомое выражение — это нечто в скобках. Что же такое это «нечто в скобках»? Если искомое выражение — это нечто в скобках, то нечто в скобках — это… искомое выражение! Эврика! Ивану приходит в голову такая грамматика: искомое-выраж ::= ( < выраж-без-скобок | искомое-выраж >+ ) Где + означает «1 и более раз», < a | b >означает «a или b», выделенные жирным шрифтом скобки означают сами символы скобок, а выраж-без-скобок ::= любой-символ-кроме-скобок + Т. е. определение искомого выражения получается рекурсивным. Но как это написать на языке регексов? Разве может регекс включать сам себя? Иван думал бы, что это невозможно, но вы забыли — он же целый месяц усердно готовился! Он вспомнил, что в современных движках регексов это возможно: в любом месте внутри регекса (?R) означает ссылку на весь регекс целиком. Иван пишет следующий регекс (с ключом /x, который значит, что все пробельные символы, включая переводы строк, не учитываются, а также возможны комментарии после символа # ): / $ # открывающая скобка ( [^)(]+ # выраж-без-скобок | # либо (?R) # ссылка на этот регекс целиком )+ # 1 или более раз $ # закрывающая скобка /x

Иван проверяет регекс на нескольких примерах цепочек (благо, на интервью разрешено прогонять тестовые программы, нельзя лишь заходить в Интернет и читать документацию): there are no parentheses here (a + b) sin((pi/180)*deg + theta) 1+(1+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1)))))))))))) sin)a - b( sin(a - b( sin(a * (b+1) и регекс с ними со всеми справляется как положено. Довольный, Иван показывает решение интервьюеру. Happy end, занавес? Но почему статья названа так, как она названа?? Интервьюер спрашивает, что должен (если должен) найти регекс в следующей цепочке: (you're gonna fail sonny unless you correct it (your regex) Прочитав и побледнев, Ванюша, тем не менее, не моргнув глазом отвечает, что, раз 1-я скобка нигде не закрывается, регекс должен найти 2-ю пару скобок: (your regex) . Его просят проверить. Иван вбивает эту цепочку в свой проверочный скрипт (Perl): #!/usr/bin/perl -wl use strict;

my $string = "(you're gonna fail sonny unless you correct it (your regex)"; print $string;

Проверив синтаксис, Иван запускает скрипт и… и ничего не происходит, скрипт как будто «зависает». Не говорит ни «да», ни «нет». Иван и интервьюер молча смотрят на это секунд 10. За это время Иван из бледного становится ярко-розовым: он уже явно чувствует подвох. Но чтО он сделал не так?? В этот момент лэптоп, на котором был запущен (и до сих пор почему-то не завершился) скрипт, начинает отчетливо гудеть, хотя до тех пор работал бесшумно. Интервьюер, чтобы прервать неловко затянувшуюся паузу, предлагает Ивану чашку чая или кофе. «А пока пьёте, как раз и подумаете, чтО может быть не так», — добавляет он. Проходит еще полчаса, Иван выпивает 2 чашки кофе и одну — чая с лимоном, но идей, почему скрипт ведет себя так загадочно, у него нет. Интервьюер с Иваном расстаются, сотрудники отдела HR царя-батюшки делают у себя пометку: «кандидат отклонен по результатам собеседования». А мы переходим к пункту

2. Катастрофический откат

Скобка в регексе матчит скобку в цепочке
[^)(]+ матчит you're gonna fail sonny unless you correct it и «упирается» в открывающую скобку, которую «скушать» не может
Альтернатива (. |. ) стоит с жадным квантификатором +, поэтому движок регексов пробует найти (. |. ) еще раз. Первая ветвь [^)(]+ альтернативы сразу, увидев открывающую скобку (, говорит «не могу матчить»
Движок переходит ко 2-й альтернативе: (?R) . Это не что иное, как весь регекс сначала. А в цепочке осталось (your regex) . Тут всё просто: скобка ( в регексе матчит скобку ( в цепочке, затем [^)(]+ матчит your regex , затем (других вхождений альтернативы (. |. ) движок в оставшейся части цепочки не обнаруживает: нет ни «не-скобки», ни открывающей скобки) движок переходит к закрывающей скобке ) в регексе. И она матчит скобку ) в цепочке.
Отлично, движку удалось матчить (?R) части исходной цепочки (your regex)
В цепочке мы подошли к концу, больше символов не осталось. Квантификатор в (. |. )+ жаден, и движок регексов пытается найти ещё одну альтернативу (. |. ), но у него это не получается: в пустой оставшейся части цепочки он не находит ни не-скобки, ни открывающей скобки, с которой могла бы начаться ветвь (?R)
Итак, ещё одну альтернативу найти не удаётся. Что ж, у всякой жадности должны быть границы. Движок «довольствуется» уже найденными 2-мя вхождениями альтернативы в цепочку и переходит к следующей части регекса. Это закрывающая скобка ). Но в цепочке скобки нет: в цепочке вообще к этому моменту пусто, всё уже отматчили предыдущие части регекса. Матчить открывающую скобку из регекса нечему.
Что делает движок регексов дальше? Сдаётся и говорит, что матча нет? Ни в коем случае. Он помнит, что последнее выражение с квантификатором [^)(]+ было жадным и, возможно, «съело» слишком много, не оставив ничего следующим частям регекса. Происходит откат движка регексов назад.
Движок помнил, что в предыдущий раз [^)(]+ «съел» цепочку your regex . Он заставляет [^)(]+ «отдать» 1 символ, x, для следующих частей регекса. Т. е. в цепочке остается: x) . А в регексе мы внутри альтернативы (. |. )+
Т. к. + жаден, движок пытается найти ещё 1 альтернативу (. |. ), и у него это получается, т. к. 1-я ветвь альтернативы, [^)(]+ , замечательно матчит символ x , оставшийся в цепочке.

3. Атомарная группировка

Можно ли предотвратить эту проблему? Да, причем очень легко. Проблема в том, что «глупый» движок регексов откатывается до греческих календ, в то время как человеку одного взгляда достаточно, чтобы понять: откатываться там бесполезно. Никакое разбиение your regex (и предшествующей части цепочки) на части не поможет отыскать недостающую закрывающую скобку. Существует способ сказать движку регексов: «в этом месте не пытайся откатываться, даже если это приведет к отсутствию полного матча». (?> . ) это называется «атомарная группировка», и означает примерно «внутри части регекса, находящейся между (?> и ) , откат запрещен». Или, точнее, по-другому. Пусть (?>X) , где X — некоторый регекс, является частью большего регекса A(?>X)B (A и B — тоже какие-то регексы). Пусть на вход этого большего регекса подали цепочку ab , причем здесь a и b — не единичные символы, а некоторые цепочки символов. Пусть начальная часть A большего регекса уже нашла соответствие («отматчила») цепочку a. Движок регексов переходит к регексу (?>X), а в обрабатываемой цепочке указатель символов стоит сразу за цепочкой a (и сразу перед b). В этом случае атомарная группировка (?>X) работает так, как будто абсолютно отдельному, независимому, регексу X подали на вход цепочку b. И X «не знает» и ему всё равно, стоит ли после него какой-то ещё регекс B и получится ли у B что-то матчить. X работает, как будто кроме него никаких регексов больше нет. И если, в частности, X содержит что-то с жадным квантификатором: (?> [^)(]+ ) то атомарная группировка не позволит этой «жадной» части откатываться. Если мы сразу захватили целиком цепочку your regex , то так тому и быть, ни шагу назад! Изменив наш регекс для нахождения текста в скобках, мы решили бы проблему: / $ (?> [^)(]+ | (?R) )+ $ /x

В статье Cверхжадные квантификаторы мы рассмотрели квантификаторы ++, *+ и т. п. Оказывается, сверхжадные квантификаторы — это частный случай атомарной группировки. И мы могли бы добиться того же эффекта (избавиться от катастрофического отката), сделав квантификаторы в исходном регексе сверхжадными: / $ ( [^)(]++ | (?R) )+ $ /x или, ещё лучше, / $ ( [^)(]++ | (?R) )++ $ /x

Вот и сказке конец, а кто слушал… пусть скорбит вместе с автором, который до написания статьи и подумать не мог, что объяснения получатся столь длинными и неполными. Но если кто-то что-то понял и не повторит опыт Вани, это уже чего-то стоит.

📎📎📎📎📎📎📎📎📎📎