4
  1. Расскажите как работает атомарная группировка и сверхжадный квантификатор
  2. Объясните как работают данные регулярные выражения
    1. (?>#.*#)
    2. (?:(?>#.*#)|(A))
8
  • 1
    Опять вопрос с кучей подвопросов с непонятной сутью :)
    – ReinRaus
    21 мая 2016 в 11:26
  • @ReinRaus а что непонятно то? если бы где-то это четко объяснялось я бы и не спрашивал, хочу разобраться всего лишь то!
    – MaximPro
    21 мая 2016 в 11:28
  • Группировка "без обратной связи" не вписывается в остальной список. Это просто группировка без сохранения результата в ней. То же самое, что и обычная группировка, но без сохранения. Вот атомарная группировка и сверхжадная квантификация - относятся к одной теоритической теме. Их можно объединить в один вопрос.
    – ReinRaus
    21 мая 2016 в 11:29
  • Вопрос сформулирован так, что он является набором непонятно чего. Ведь можно сформулировать очень просто "Что такое атомарная группировка и сверхжадная квантификация". "Что выведет онлайн парсер" - это к чему вообще? Вы хотите узнать что выведет парсер или что делают эти виды группировок ?
    – ReinRaus
    21 мая 2016 в 11:30
  • Мне интересно объяснение этих примеров, я вот допустим не понимаю почему так выбирает или не выбирает
    – MaximPro
    21 мая 2016 в 11:31

1 ответ 1

6

Чтобы понять, что такое атомарная группировка и сверхжадная кванификация- нужно хоть немного понять как устроен движок регулярных выражений внутри, а точнее, нужно иметь представление о точках возврата.
С этого и начнем.


Точка возврата

Встретив квантификацию или альтернативу (я рассматриваю простые случаи, на самом деле точки возврата создаются и в других конструкциях регулярных выражений- везде, где может потребоваться вернуться назад) движок регулярных выражений (далее просто "движок") создает точку, куда ему следует вернуться, если выражение не совпадет с текстом. Тогда вернувшись в эту точку он попробует применить альтернативу или прекратить квантификацию.
Что это означает?
Посмотрим на простое регулярное выражение .*x примененное к тексту text (точки возврата буду обозначать символом . :

  1. Движок начинает обрабатывать текст с самого начала и видит .*, так как данное выражение может совпать с "ничем", то создаем точку возврата сюда .text
  2. Смотрим дальше - далее по тексту литерал t, захватываем его как часть .* и надо бы создать точку возврата снова в позиции 0, но это было сделано уже в пункте 1. .text
  3. Далее по тексту литерал e, захватываем его как часть .* и создаем точку возврата перед ним .t.ext
  4. Далее по тексту литерал x, захватываем его как часть .* и создаем точку возврата перед ним .t.e.xt
  5. Далее по тексту литерал t, захватываем его как часть .* и создаем точку возврата перед ним .t.e.x.t
  6. Литералы кончились, это конец строки, но выражение не совпало, потому что требуется обязательно литерал x
  7. Возвращаемся в точку возврата перед литералом t, теперь у нас выражению .* соответствует текст tex, и пытаемся найти за ним литерал x - неудача, так как за ним литерал t
  8. Снова пробуем вернуться назад. Для этого возвращаемся в точку возврата перед литералом x. Теперь выражению .* соответствует текст te, ищем за ним литерал x и успешно находим
  9. Регулярное выражение закончилось, значит найдено совпадение.
  10. Итак: Выражению .* соответствует текст te, выражению x соответствует текст x, значит полное совпадение будет с текстом tex

Если бы у нас кончились точки возврата, и совпадения так и не найдено- значит текст не соответствует регулярному выражению.
Важно проникнуться механикой создания точек возврата- с пониманием этого быстро придет понимание различных видов квантификаций и атомарной группировки.


Атомарная группировка: теория

Это группировка ВНУТРИ которой нет точек возврата.
Это означает, что как только будет найдено совпадение для выражения внутри такой группировки - это совпадение будет считаться единственным и вернуться внутрь него будет нельзя, даже, если это помешает общему совпадению.
https://regex101.com/r/cH7rO2/1

Выражение (?>#.*#)a применено к тексту aaa#aaaaaa#aaaaaaaa#a# - нет совпадений, потому что #.*# захватит самое большое совпадение #aaaaaa#aaaaaaaa#a# и внутри этого текста нет точек возврата - вернуться некуда, поэтому невозможно будет захватить литерал a, который следует за (?>#.*#)

Рассмотрим пошагово на тексте покороче b#c#a#

  1. По тексту литерал b - не совпадает с обязательным #, переходим к следующему литералу
  2. По тексте литерал # - совпадает с обязательным литералом #, переходим к выражению .* и запоминаем, что мы находимся внутри атомарной группировки и как только найдем совпадение для нее, то удалим все точки возврата, которые были созданы внутри нее
  3. Захватываем литерал c, так как он соответствует ., создаем точку возврата перед ним b#.c#a#
  4. Захватываем литерал #, так как он соответствует ., создаем точку возврата перед ним b#.c.#a#
  5. Захватываем литерал a, так как он соответствует ., создаем точку возврата перед ним b#.c.#.a#
  6. Захватываем литерал #, так как он соответствует ., создаем точку возврата перед ним b#.c.#.a.#
  7. Достигли конца текста, но не нашли совпадения для литерала #. Вернемся в точку возврата перед последней решеткой. Теперь выражению .* соответствует текст c#a, выражению # - текст #
  8. Мы достигли конца атомарной группировки, значит можно удалить все точки возврата, которые были созданы внутри нее. В итоге не останется ни одной точки возврата.
  9. Нет точек возврата, а нужно еще совпадение с выражением 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

8
  • Если что не ясно - пишите в чате, попробую объяснить, заодно может ответ поправлю в сторону более лучшего изложения мысли.
    – ReinRaus
    21 мая 2016 в 16:23
  • 1. Ни разу не пользовался чатом и не знаю где он 2. a(?:[^b]++|b)*?b - почему именно так, а не так: a(?:[^b]++)*?b, зачем было ставить литерал альтернативы на символ b после сверхжадной квантификации?
    – MaximPro
    22 мая 2016 в 3:53
  • Да, верное замечание для неочевидной вещи. Оптимизация идет по первому литералу, который следует за минимальной квантификацией. Литералов же может быть множество, но оптимизируем по первому.
    – ReinRaus
    22 мая 2016 в 4:21
  • Не хочу оффтопить, но я так и не понял момент где используется рекурсия
    – MaximPro
    22 мая 2016 в 4:35
  • Рекурсивные шаблоны - отдельная тема, ее тоже можно долго раскрывать, в рамках данного вопроса я лишь показал как правильно составить рекурсию, чтобы не получить Catastrophic backtracking - ситуация, когда движок превышает ограничение на максимальное количество точек возврата.
    – ReinRaus
    22 мая 2016 в 4:39

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.