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 that you have read and understand our privacy policy and code of conduct.

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