Расскажите как работает атомарная группировка и сверхжадный
квантификатор
Объясните как работают данные регулярные выражения
(?>#.*#)
(?:(?>#.*#)|(A))
Ответ
Чтобы понять, что такое атомарная группировка и сверхжадная кванификация- нужно хоть немного понять как устроен движок регулярных выражений внутри, а точнее, нужно иметь представление о точках возврата.
С этого и начнем.
Точка возврата
Встретив квантификацию или альтернативу (я рассматриваю простые случаи, на самом деле точки возврата создаются и в других конструкциях регулярных выражений- везде, где может потребоваться вернуться назад) движок регулярных выражений (далее просто "движок") создает точку, куда ему следует вернуться, если выражение не совпадет с текстом. Тогда вернувшись в эту точку он попробует применить альтернативу или прекратить квантификацию.
Что это означает?
Посмотрим на простое регулярное выражение .*x примененное к тексту text (точки возврата буду обозначать символом :
Движок начинает обрабатывать текст с самого начала и видит .*, так как данное выражение может совпать с "ничем", то создаем точку возврата сюда .text
Смотрим дальше - далее по тексту литерал t, захватываем его как часть .* и надо бы создать точку возврата снова в позиции 0, но это было сделано уже в пункте 1. .text
Далее по тексту литерал e, захватываем его как часть .* и создаем точку возврата перед ним .t.ext
Далее по тексту литерал x, захватываем его как часть .* и создаем точку возврата перед ним .t.e.xt
Далее по тексту литерал t, захватываем его как часть .* и создаем точку возврата перед ним .t.e.x.t
Литералы кончились, это конец строки, но выражение не совпало, потому что требуется обязательно литерал x
Возвращаемся в точку возврата перед литералом t, теперь у нас выражению .* соответствует текст tex, и пытаемся найти за ним литерал x - неудача, так как за ним литерал t
Снова пробуем вернуться назад. Для этого возвращаемся в точку возврата перед литералом x. Теперь выражению .* соответствует текст te, ищем за ним литерал x и успешно находим
Регулярное выражение закончилось, значит найдено совпадение.
Итак: Выражению .* соответствует текст te, выражению x соответствует текст x, значит полное совпадение будет с текстом tex
Если бы у нас кончились точки возврата, и совпадения так и не найдено- значит текст не соответствует регулярному выражению.
Важно проникнуться механикой создания точек возврата- с пониманием этого быстро придет понимание различных видов квантификаций и атомарной группировки.
Атомарная группировка: теория
Это группировка ВНУТРИ которой нет точек возврата.
Это означает, что как только будет найдено совпадение для выражения внутри такой группировки - это совпадение будет считаться единственным и вернуться внутрь него будет нельзя, даже, если это помешает общему совпадению.
https://regex101.com/r/cH7rO2/1
Выражение (?>#.*#)a применено к тексту aaa#aaaaaa#aaaaaaaa#a# - нет совпадений, потому что #.*# захватит самое большое совпадение #aaaaaa#aaaaaaaa#a# и внутри этого текста нет точек возврата - вернуться некуда, поэтому невозможно будет захватить литерал a, который следует за (?>#.*#)
Рассмотрим пошагово на тексте покороче b#c#a#
По тексту литерал b - не совпадает с обязательным #, переходим к следующему литералу
По тексте литерал # - совпадает с обязательным литералом #, переходим к выражению .* и запоминаем, что мы находимся внутри атомарной группировки и как только найдем совпадение для нее, то удалим все точки возврата, которые были созданы внутри нее
Захватываем литерал c, так как он соответствует , создаем точку возврата перед ним b#.c#a#
Захватываем литерал #, так как он соответствует , создаем точку возврата перед ним b#.c.#a#
Захватываем литерал a, так как он соответствует , создаем точку возврата перед ним b#.c.#.a#
Захватываем литерал #, так как он соответствует , создаем точку возврата перед ним b#.c.#.a.#
Достигли конца текста, но не нашли совпадения для литерала #. Вернемся в точку возврата перед последней решеткой. Теперь выражению .* соответствует текст c#a, выражению # - текст #
Мы достигли конца атомарной группировки, значит можно удалить все точки возврата, которые были созданы внутри нее. В итоге не останется ни одной точки возврата.
Нет точек возврата, а нужно еще совпадение с выражением a, которого нет после текста #c#a#. Результат - нет совпадений.
Подведем итог: пока ищется совпадение с атомарной группировкой - могут быть созданы точки возврата, но как только совпадение найдено - все точки возврата внутри атомарной группировки будут удалены.
Атомарная группировка: практика
На практике атомарная группировка означает очень простую вещь - текст, который захвачен этой группировкой будет рассматриваться далее как единое целое внутрь которого нельзя вернуться.
Если что-то совпало - значит оно и будет результатом для атомарной группировки, иначе никак. Поэтому она и называется атомарной, то есть неделимой на отдельные части.
На практике атомарная группировка служит обычно для оптимизации регулярных выражений, наиболее часто ее можно увидеть в рекурсивных регулярных выражениях.
Примеры оптимизаций приведу при рассказе о сверхжадной квантификации.
Сверхжадная квантификация
Это частный случай атомарной группировки, когда атомарная группировка применена в пределах одного квантификатора.
Вот и все, что следует о ней сказать.
Выражение a++ полностью равносильно выражению (?>a+).
Например выражение a++a не даст совпадения на тексте aaaa, потому что a++ захватит все литералы a, которые есть в тексте и не вернет ни одного из них, хоть это и помешает общему совпадению.
Сверхжадная квантификация может выглядеть в регулярных выражениях следующим образом:
*+
++
?+
{m,n}+
Примеры применения
Оптимизируем минимальную квантификацию .*?
Пусть есть выражение a.*?bcd и текст a-----bcd----bcd
https://regex101.com/r/cH7rO2/8
Совпадение найдено за 11 шагов.
Теперь изменим регулярное выражение на такое a(?:[^b]++|b)*?bcd
https://regex101.com/r/cH7rO2/9
Совпадение найдено за 9 шагов.
Даже на таком маленьком тексте мы получили прирост примерно 20%
Смысл оптимизации в том, что смотрим литерал, который следует за минимальной квантификацией - в данном случае это b, и разлагаем минимальную квантификацию на две альтернативы из b++ и b к которым тоже применена минимальная квантификация. Такая конструкция создает меньше точек возврата, поэтому быстрее происходит нахождение совпадения.
Оптимизируем рекурсивные регулярные выражения
Возьмем каноническую задачу по поиску сбалансированных скобок <>
Сначала напишем регулярное выражение:
<(?:[^<>]*|(?R))*>
https://regex101.com/r/cH7rO2/4
Оно даже работает и мы могли бы радоваться жизни, но попробуйте добавить в начало текста < и по одному символу a постепенно ;) Радость будет таять на глазах при виде цифры шагов - количество шагов удваивается с каждым введенным символом, а потом и вовсе видим Catastrophic backtracking
https://regex101.com/r/cH7rO2/5
А оптимизируется все очень просто - достаточно не возвращаться назад внутри выражения [^<>]* Таким способом:
<(?:[^<>]*+|(?R))*>
https://regex101.com/r/cH7rO2/6
Или таким:
<(?:(?>[^<>]*)|(?R))*>
https://regex101.com/r/cH7rO2/7
Комментариев нет:
Отправить комментарий