Comments 23
Полезное напоминание, спасибо. Как раз недавно «нырял» в регулярки, после праздников опять :)
Вот очень классная статья по регекспам. Рассматривается, в частности, и описанная проблема, а также имплементация регекспов с помощью конечного автомата: swtch.com/~rsc/regexp/regexp1.html
И вот заодно дико классная классическая книжка по регекспам и не только. Помимо прочего, рассказывают, почему нельзя парсить Html с помощью regex: en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation
Почему нельзя парсить html регулярками — это сюда stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 :)
Можете ли вы в двух словах сказать почему?
Если строго, то html по классификации Хомского принадлежыт к типу 2 (контекстно-свободные), в тоже время регулярки — 3 тип. То есть html нельзя описать (а значит и пропарсить) с помощью regexp.
Я так понимаю, здесь потерялась частица не?
Любая контекстно-свободная грамматика может быть легко преобразована в вид, в котором правила состоят только из лево-регулярных или право-регулярных (для контекстно-свободных грамматик допустимо наличие тех и других одновременно). Следовательно, такие грамматики могут выразить все контекстно-свободные языки. Регулярные грамматики могут содержать либо лево-регулярные правила, либо право-регулярные, но не оба вида одновременно. Поэтому они могут описать лишь подмножество языков, называемых регулярными языками.
Любая контекстно-свободная грамматика может быть легко преобразована в вид, в котором правила состоят только из лево-регулярных или право-регулярных (для контекстно-свободных грамматик допустимо наличие тех и других одновременно). Следовательно, такие грамматики могут выразить все контекстно-свободные языки. Регулярные грамматики могут содержать либо лево-регулярные правила, либо право-регулярные, но не оба вида одновременно. Поэтому они могут описать лишь подмножество языков, называемых регулярными языками.
Я думаю что regexp применяют к html в случае когда нужно выкусить кусок текста, а не пропарсить весь документ. В таком применении он бывает удобнее чем html/xml парсеры.
другой инструмент.
Было на Хабре с подробными объяснения, что плохо и как надо.
Атомарная группировка, или Ни шагу назад!
Вот несколько цитат оттуда, чтобы показать, что речь о том же.
А далее объясняется, как на самом деле работает это регулярное выражение (постоянно отступая назад), и повествуется о пользе атомарных группировок.
Атомарная группировка, или Ни шагу назад!
Вот несколько цитат оттуда, чтобы показать, что речь о том же.
На собеседовании Ивану дали такую задачу. Написать регекс, который матчит выражение в круглых скобках (...), причем внутри скобок может быть множество выражений в других круглых скобках, вероятно, вложенных.
Однако, регекс не должен матчить такую часть цепочки, в которой скобки не сбалансированы (открытые скобки не закрываются или, наоборот, закрываются скобки, которые вовсе не были открыты).Далее выписываются рассуждения гипотетического Ивана и составленное им регулярное выражение.
Иван проверяет регекс на нескольких примерах цепочек (благо, на интервью разрешено прогонять тестовые программы, нельзя лишь заходить в Интернет и читать документацию)
и регекс с ними со всеми справляется как положено. Довольный, Иван показывает решение интервьюеру. Happy end, занавес? Но почему статья названа так, как она названа??
Интервьюер спрашивает, что должен (если должен) найти регекс в следующей цепочке:
(you're gonna fail sonny unless you correct it (your regex)
Прочитав и побледнев, Ванюша, тем не менее, не моргнув глазом отвечает, что, раз 1-я скобка нигде не закрывается, регекс должен найти 2-ю пару скобок: (your regex). Его просят проверить. Иван вбивает эту цепочку в свой проверочный скрипт
Проверив синтаксис, Иван запускает скрипт и… и ничего не происходит, скрипт как будто «зависает». Не говорит ни «да», ни «нет». Иван и интервьюер молча смотрят на это секунд 10. За это время Иван из бледного становится ярко-розовым: он уже явно чувствует подвох. Но чтО он сделал не так?? В этот момент лэптоп, на котором был запущен (и до сих пор почему-то не завершился) скрипт, начинает отчетливо гудеть, хотя до тех пор работал бесшумно.
А далее объясняется, как на самом деле работает это регулярное выражение (постоянно отступая назад), и повествуется о пользе атомарных группировок.
Some people, when confronted with a problem, think «I know, I'll use regular expressions.» Now they have two problems.
© Jamie Zawinski
Хотя иногда, конечно, без регулярных выражений не обойтись.
© Jamie Zawinski
Хотя иногда, конечно, без регулярных выражений не обойтись.
А если взять какой-нибудь BusyBeaver в 6 состояний и конвертнуть в регэкспу? :) Надо будет посчитать на досуге.
Мне кажется, это не сразу получится: busy beaver--это пример машины тьюринга; а регекспы описываются конечными автоматами, и уступают в мощности машинам тьюринга. Вот тут про это есть.
Сначала, хотел написать WTF? Запустил на Java проверил различные варианты и мда… действительно не работает.
Вопрос как же так? Обычная регулярка. Простой Недетерминированный автомат => Детерминированный.
Причем тут бэктрекинг??? В автоматах.
Вопрос как же так? Обычная регулярка. Простой Недетерминированный автомат => Детерминированный.
Причем тут бэктрекинг??? В автоматах.
Как видим, время исполнения растет экспоненциально.
только если нет оптимизации для такого случая)
$ time perl -E 'my $s = "a" x 1_000_000; say $s =~ /(a+)*b/'
perl -E 'my $s = "a" x 1_000_000; say $s =~ /(a+)*b/' 0.01s user 0.01s system 85% cpu 0.016 total
UFO just landed and posted this here
Only those users with full accounts are able to leave comments. Log in, please.
Catastrophic backtracking в регулярных выражениях