#php #регулярные_выражения
Расскажите как работает атомарная группировка и сверхжадный
квантификатор
Объясните как работают данные регулярные выражения
(?>#.*#)
(?:(?>#.*#)|(A))
Ответы
Ответ 1
Чтобы понять, что такое атомарная группировка и сверхжадная кванификация- нужно хоть немного понять как устроен движок регулярных выражений внутри, а точнее, нужно иметь представление о точках возврата. С этого и начнем. Точка возврата Встретив квантификацию или альтернативу (я рассматриваю простые случаи, на самом деле точки возврата создаются и в других конструкциях регулярных выражений- везде, где может потребоваться вернуться назад) движок регулярных выражений (далее просто "движок") создает точку, куда ему следует вернуться, если выражение не совпадет с текстом. Тогда вернувшись в эту точку он попробует применить альтернативу или прекратить квантификацию. Что это означает? Посмотрим на простое регулярное выражение .*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
Комментариев нет:
Отправить комментарий