Регулярные выражения изнутри

Регулярные выражения (РВ) — это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим примеры таких систем:

  • Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
  • Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
  • РВ в языках программирования.


В данной статье мы сначала ознакомимся с конечными автоматами и их видами (ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.

Конечные автоматы


Конечный автомат (КА) — это преобразователь, который позволяет сопоставить входу соответствующий выход, причем выход этот может зависеть не только от текущего входа, но и от того, что происходило раньше, от предыстории работы конечного автомата. Даже поведение человека, а не только искусственных систем можно описать с помощью КА. Например, ваша реакция на то что ваш сосед слушает громко музыку по ночам, будет одной после первого такого случая и совершенно другой после нескольких таких случаев. Таких предысторий может быть бесконечное число, возникает вопрос: какой памятью должен обладать КА, чтобы вести себя по разному для каждой предыстроии? Понятно, что хранить бесконечное число предысторий невозможно. Поэтому автомат как бы разбивает все возможные предыстории на классы эквивалентности. Две истории являются эквивалентными, если они одинаково влияют на поведение автомата в дальнейшем. Класс эквивалентности к которому автомат отнес свою текущую предысторию, называют еще внутренним состоянием автомата.

Рассмотрим пример работы примитивного КА:



Данный КА состоит из:

  • ленты, представленной входной цепочкой.
  • считывающее устройство.
  • блок управления, который содержит список правил переходов.


Считывающее устройство может двигаться в одном направлении, как правило слева на право, тем самым считывая символы входной цепочки. За каждое такое движение оно может считать один символ. Далее, считанный символ передается блоку управлений. Блок управления изменяет состояние автомата на основе правил переходов. Если список правил переходов не содержит правила для считанного символа, то автомат «умирает».

Теперь рассмотрим, какими способами можно задать КА. Они могут задаваться в виде графов или в виде управляющих таблиц. В виде графа КА задается следующим способом:

  • вершины графа, соответствуют состояниям КА.
  • направленные ребра, соответствуют функциям переходов (возле каждого такое ребра указывается символ, по которому выполняется переход).
  • вершина с входящим в него ребром, которое не выходит не из одного состояния, соответствует начальному состоянию.
  • конечные состояния КА помечаются жирным контуром.


В виде управляющей таблицы, так:

  • состояния КА располагаются в строках таблицы.
  • символы распознаваемого языка — в столбцах.
  • на пересечении указывается состояние в которое можно попасть из данного состояния по данному символу.


Пример КА в виде графа и в виде управляющей таблицы будет представлен ниже.

ДКА и НКА



Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно. В качестве примера работы НКА можно привести идею американского физика Хью Эверетта от том, что любое событие разбивает мир на несколько миров, в каждом из которых это событие закончилось по-своему. Например, в одном мире Гитлер выиграл Вторую мировую войну, в другом – Ньютон вместо физики занялся бизнесом и открытие законов классической механики пришлось отложить лет на 50. Чтобы сделать какие-то выводы из работы автомата, следует изучить все «миры». После того как вся входная цепочка будет считана, мы полагаем, что НКА допускает данную цепочку, если он завершил работу в допускающем состоянии хотя бы в одном из множества «миров». Соответственно, автомат отвергает цепочку, если он завершил работу в недопускающем состоянии в каждом «мире». ДКА же принимает цепочку, это очевидно, если после считывания всей входной цепочки он оказывается в допускающем состоянии.

В большинстве случаев построить НКА гораздо проще чем ДКА. Но, не смотря на это использовать НКА для моделирования — не самая хорошая идея. К счастью, для каждого НКА можно построить ДКА, допускающий тот же входной язык. В данной статье мы не будем приводить алгоритм построения ДКА по НКА, а рассмотрим данный алгоритм на основе наглядного примера ниже.

Построение минимального ДКА по регулярному выражению



Для начала приведем список операций РВ используемый в данной статье, в порядке их приоритетности:

  • итерация (замыкание Клини), с помощью символа "*"
  • конкатенация задается с помощью пробела или пустой строки (например: ab)
  • объединение, с помощью символа "|"


Рассмотрим пример, дано регулярное выражение:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Нужно построить минимальный ДКА по регулярному выражению и продемонстрировать распознавание корректной и некорректной цепочки.

Для начала упростим данное РВ, используя правосторонний дистрибутивный закон конкатенации относительно объединения получаем следующее РВ:

(xy* | ab | (x | a*)) (x | y*)

Теперь строим автомат по данному РВ:



По правилу преобразования конкатенации (не будем приводить правила преобразования РВ в КА, так как они довольно очевидные), получаем следующий автомат:



По правилу преобразования объединения:



По правилу преобразования конкатенации:



И в конце применяем правило преобразования замыкания и получаем εНКА. Здесь нужно оговорится, что εНКА — это НКА, который содержит ε-переходы. В свою очередь ε-переход — это переход, при котором автомат не учитывает входную цепочку или другими словами переход по пустому символу.



Избавляемся от ε-переходов («звездочкой» обозначены конечные состояния):





В данном НКА состояния s3 и s5 эквивалентны, так как δ(s3, x) = δ(s5, x) = s1 и δ(s3, y) = δ(s5, y) = s5, s7. Переименовываем состояния s6 -> s5 и s7 -> s6:



Строим ДКА по НКА:





В данном ДКА состояния p1 и p5 эквивалентны, так как
δ(p1, x) = δ(p5, x) = p4 и δ(p1, y) = δ(p5, y) = p5. Переименовываем состояния p6 -> p5 и p7 -> p6:



Данный автомат является минимальным ДКА.

Пускай δ — функция переходов, то расширенную функцию переходов, построенную по δ, обозначим δ’, и ω — входная цепочка.

Допустим на вход подается цепочка ω = aaax, мы ожидаем, что автомат окажется в одном из допускающих состояний.

δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4

p4 — допустимое конечное состояние, таким образом цепочка aaax является корректной для данного автомата.

Теперь допустим, что ω = xyyb:

δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅

Здесь мы видим, что если подать на вход автомату символ b, когда он находится в состоянии p1, то данный автомат умрет, следовательно цепочка xyyb — некорректна.

P. S. В данной статье был рассмотрен алгоритм построение ДКА по РВ, но существуют более удобные алгоритмы, в частности для программирования, но это уже тема для другой статьи…
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 36

    +10
    Вот только на практике в реальных библиотеках регулярных выражений конечные автоматы не используются. Более того, грамматика современных расширенных регекспов теоретически себя не позволяет реализовать на КА.
      0
      Как же так? Нас же учили в университете, что регулярные грамматики и конечные автоматы эксвивалентны.
      Можете привести пример конструкции, являющейся регулярным выражением, которую нельзя реализовать на НKA?

      Желательно с комментариями.
        +9
        Потому что самые популярные так называемые Perl-compatible regular expressions на самом деле шире, чем классические регулярные выражения. Самый простой пример — ссылка назад на группу, "(a+)b+\1"
          0
          Да, понятно. Спасибо.
            0
            Спасибо, за информацию. Я только начал разбираться в этом направлении, буду «копать глубже».
              +2
              Не верьте Beholder. Обратные ссылки нормально ложатся в парадигму конечных автоматов, входят в POSIX ERE и поддерживаются всеми подряд. Для их обработки используются именно конечные автоматы. Кто не верит, может подебажить.
              perl -Mre=debug -e'"aabbaa"=~/(a+)b+\1/'
              Однако в Perl действительно есть расширение, не совместимое с конечными автоматами — это рекурсивные регулярные выражения типа
              $regex = qr/0(??{$regex})?1/;
              Для них действительно не хватит конечного числа состояний, и, следовательно, они могут зацикливаться и завешивать выполнение. Поэтому это расширение не поддерживается ничем, кроме перла. Никому ведь не хочется, чтобы, скажем, web-сервер зависал от неудачного сочетания регекспа в конфиге и урла, набранного пользователем.
                0
                Про обратные ссылки неправда, их можно реализовать исключительно при помощи бэктрекинга.
                  0
                  Ну без бектрекинга нельзя сделать даже (a|aa)*b и обратные ссылки тут не причём. А бектрекинг существует во всех порядочных NFA.

                  Другое дело, что они (обратные ссылки) приводят к очень неэффективным выражениям, но точно такие же неэффективности можно можно получить и не используя обратные ссылки :-)

                  Давайте говорить по существу. Конечный автомат или нет. А о его эффективности или фичах можно рассуждать отдельно.
                    +4
                    Ну без бектрекинга нельзя сделать даже (a|aa)*b и обратные ссылки тут не причём. А бектрекинг существует во всех порядочных NFA.

                    Еще как можно. Есть условно три типа «движков» для вычисления регекспов: ДКА (DFA), НКА (NDFA) и бектрекинг. Сравните:

                    ДКА Автомат в любой момент времени находится в определенном состоянии, для простоты считаем, что состояния перенумерованы, то есть состояние это целое число. Имеется таблица переходов, которая для текущего состояния и текущего символа строки говорит следующее состояние.

                    Вычисление происходит за в один проход по строке слева направо: прочитать очередной символ, по таблице определить следующее состояние, повторить. Количество итераций == длина строки.

                    НКА Все то же самое, только автомат находится во множестве состояний сразу. Количество итераций == длина строки.

                    Бектрекинг Каждый раз попадая в ситуацию выбора, запоминаем этот факт и исследуем первую альтернативу. Если не удалось заматчить, возвращаемся и пробуем следующую и тд. Сложность в худшем случае — экспонента от длины строки.
                      0
                      Но вы, я надеюсь, понимаете, что НКА не рассматривает сразу все альтернативы? Он запаминает каждую развилку и ходит по каждой ветке по-порядку. Именно поэтому, кстати, порядок альтернатив в скобках важен, а порядок символов в квадратных скобках не важен.

                      Так вот, вопрос. Чем, по вашему, работа НКА отличается от бектрекинга? Возможно ли одно без другого?

                      Ну а про линейность НКА вы очень сильно заблуждаетесь. Линейна только каждая ветка. Но веток-то может быть много. То есть НКА работал бы линейно, если бы чудо-машина имела столько процессорных ядер, сколько символов во входной строке. То есть, фактически, не имела бы ограничений производительности :-)
                        +1
                        Но вы, я надеюсь, понимаете, что НКА не рассматривает сразу все альтернативы?

                        В том то и дело, что рассматривает.
                        минута ликбеза
                        Позволю себе позаимствовать картинку автора топика: Легко увидеть, что это именно НКА — имеются ε переходы (переход, который не «съедает» текущий символ), а также из одного состояния могут быть переходы в разные состояния по одному и тому же символу (ex: из q0 по x можно перейти как в q2, так и q3).

                        НКА в самом деле рассматривает все альтернативы одновременно, как бы парадоксально это не звучало.

                        НКА эмулирует параллельную работу «бригады» ДКА. Если встречается «развилка» динамически добавляются новые ДКА. Если какая-то из ДКА заходит в тупик, она удаляется. Поскольку для представления всей информации о текущем состоянии ДКА достаточно одного целого числа, то состояние все «бригады» описывается списком целых чисел.

                        Легко заметить, что максимальный размер «бригады» может быть ограничен общим числом состояний НКА, а вовсе не длиной входа. В самом деле, если число эмулируемых ДКА превышает общее число состояний, значит хотя бы два ДКА находятся в одном и том же состоянии, и один из них можно безболезненно удалить.

                        Пример для наглядности (по НКА с картинки). Начальное состояние там q0, но из-за ε переходов начальный список состояний выглядит как S0=[q0, q1, q2, q6, q7]. Состояние является допускающим, то есть если строка закончится прямо сейчас, это будет ок. Кроме того, мы готовы рассматривать a или x или y в качестве следующего символа.

                        Переход из S0 по a дает S1=[q4, q6]

                        Переход из S0 по x дает S2=[q1, q2, q3, q5, q7].

                        Переход из S0 по y дает S2=[q7].

                        Ну и так далее.

                        Эквивалентный ДКА можно построить, заведя по отдельному состоянию для каждого списка состояний Sx, который возможен во время работы НКА, и соединив их переходами. Очевидно, что количество состояний в эквивалентном ДКА будет в худшем случае 2^N, где N — число состояний НКА. То есть из хиленького НКА на 32 состояния потенциально можно получить ДКА-монстра на 4 миллиарда состояний.

                        Особо отмечу, что сложность эквивалентного ДКА зависит исключительно от сложности выражения и никак не зависит от размера входа.

                        Если построение ДКА не является практичным (не вписались в лимит по памяти из-за числа состояний), используем НКА как есть. На практике часто применяется кеширование — во время матчинга при помощи НКА мы строим эквивалентный ДКА, но только для посещенных состояний. В результате вместо того, чтобы каждый раз считать новый список состояний, мы можем воспользоваться закешированным переходом (если он есть). При необходимости мы можем безболезненно удалить часть содержимого кеша.

                          0
                          Добавлю, что порядок альтернатив в скобках важен исключительно в случае применения бектрекинга.

                          В классических регулярных выражениях, как их знает computer science, порядок альтернатив не важен. К сожалению, практика в данном случае идет вразрез с теорией — в большинстве современных языковых сред регулярные выражения работают именно на бектрекинге.
                    0
                    perl -Mre=debug -e'"aaaaaa"=~/(a+)\1/'
                    

                    а это случайно не бэктрекинг?

                    В примере
                    perl -Mre=debug -e'"aabbaa"=~/(a+)b+\1/'
                    

                    помоему все же не классический конечный автомат: его вид динамически меняется в зависимости от того, какой путь ты уже прошел.
              +1
              Хм. А у Фриддла в книжке даже описан способ понять НКА или ДКА реализован в языке. С чего бы? :)
              +2
              Всё не так категорично, это зависит от задачи. Высокоэффективные реализации, типа re2 http://code.google.com/p/re2/, отказываются от некоторых фич PCRE, но при этом строят точно тот самый DFA.
                +1
                Re2 может построить DFA а может ограничиться NFA, например если превышено ограничение по памяти (состояний может быть много). Кроме того, если в выражении присутствуют capturing paranthesis, то DFA неприменим. Интересующимя крайне рекомендую к прочтению вот это.
                  0
                  Не совсем так. Захватывающие скобки используются, чтобы заматчить подвыражение. RE2 умеет это:
                  RE2 supports submatch extraction, but not backreferences.
                  А вот сослаться на подвыражение в RE2 дальше в выражении уже нельзя.
                    +1
                    Разумеется, захватывающие скобки это не то же самое что \1.

                    Я утверждаю, что re2 может использовать как DFA так и NFA, причем если есть «захватывающие» скобки применяется именно NFA. Ибо из DFA не получается добыть информацию о границах подвыражения.

                    Почитайте док по ссылке из предыдущего комента. Там в самом деле интересно, например RE2 иногда выполняет выражение задом-на-перед, зачем — не скажу :)
                    +1
                    Я не поленился и потестил: Boost.Regex, Perl RE
                    Время работы:

                    ramntry@ramntry-R418:~/studies/experiments/pcre/test_speed$ time ./pcre_test_speed
                    ok
                    
                    real	0m0.004s
                    user	0m0.000s
                    sys	0m0.000s
                    ramntry@ramntry-R418:~/studies/experiments/pcre/test_speed$ time ./pcre_test_speed.pl 
                    ok
                    
                    real	1m34.656s
                    user	1m34.562s
                    sys	0m0.008s
                    


                    Спасибо за ссылку, кстати. Там 3 статьи — не одна. И все более чем достойны внимания.
                    0
                    Спасибо за ссылку!
                    +9
                    В бауманке проходим регулярные языки на дискретной математике. Методичка, ибо может быть полезна: rghost.ru/43251770
                      0
                      Благодарю.
                        0
                        перезалил
                        https://www.dropbox.com/s/enm0ndz52ptk5e0/dm-seminars.pdf
                        0
                        Обнаруженные опечатки:

                        Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающиеих цепочки.
                        В данной статье мы сначала ознакомимся с конечными автоматами и их видами[](ДКА и НКА)
                        Например, ваша реакция, на то, что ваш сосед слушает громко музыку по ночам
                        возникает вопрос;: Ккакой памятью должен обладать КА
                        бесконечное число предысторий не вневозможно
                        с помощью пробела или пустой строки[](например
                        итерация[](замыкание Клини)
                        функция переходов, то расширеннаяую функцияию переходов, построенную по δ, обозначим
                        мы ожидаем, что автомат
                        таким образом цепочка aaax, является корректной

                        Поправьте, пожалуйста.

                        Гитлер выиграл 2-ю Мир. войну
                        Ой, а давайте имя «Вторая мировая война» писать полностью?

                        Формализм с классами эквивалентности, метафора с параллельными мирами — блестяще. И совершенно без предупреждения появляется термин «допускающее состояние». Возможно, завершив метафоры и пояснения, стоит дать (кратенько), формальное описание автомата (это пятёрка, такая, что ...). Заодно поясните точнее, что такое в контексте статьи «цепочка» и некоторые другие термины.

                        Об описании синтаксиса РВ, «используемого в данной статье». Возможно, полезно указать приоритеты вводимых операций, их арность и способ записи (инфиксная/префиксная/постфиксная). Ну и, возмножно, смысл :) Замыкание Клини, да и объединение (объединение чего? Ведь не частей регулярного выражения а ля конкатенация, а регулярных языков — это неочевидно), может потребовать более развернутого описания.

                        Пример: xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)
                        Было бы неплохо как-нибудь выделить операторы объединения верхнего уровня — а то глаз сломаешь, пока разберешься. Хотя бы так:
                        xy* (x | y*)  |  ab (x | y*)  |  (x | a*) (x | y*)

                        Ну а дальше… Не пояснили, что такое ε-переходы, не пояснили, что такое ε-замыкание (молча его используете). Если бы я не знал этот алгоритм, мне было бы трудно разобраться. Посмотрите, как этот алгоритм описан у Ахо, Сети, Ульмана и Лам ("Компиляторы. Принципы, технологии, инструменты") — практически образец ясности. Там не таких замечательных метафор и идеи с классами эквивалентности, так что эта книга не обесценивает вашу статью.

                        Статья в целом понравилась, спасибо.
                          0
                          Cпасибо, за ваши замечания, я возьму их во внимания. Данная статья является дебютной на Хабре, так что не судите строго.
                            0
                            А можно поинтересоваться, что не понравилось минусующим? Что была выполнена вычитка текста, а результаты не убраны в стол, а предоставлены автору? Или кого-то оскорбила просьба объяснить, что такое ε-замыкание в статье, которая его использует и, судя по объяснениям, что такое регулярные выражения и конечные автоматы, рассчитана на неподготовленного читателя? Или что-то еще?
                              +1
                              Список опечаток, традиционно вызывающий рекомендацию «опечатки — в ЛС!», здесь такого желания не вызвал — очень информативно.
                              +3
                              Интересующимся мог бы еще посоветовать книгу, доступную на books.ru — Регулярные выражения, Джеффри Фридл
                                +1
                                На coursera.org был/будет хороший курс Automata (FA перетекает в RE, CFG, TM, много интересных вещей)
                                  0
                                  Вспомнилось самое начало прошедшего семестра, ТРЯП — как раз с регулярных выражений и языков всё началось. Планируете ли продолжать тему классов языков: контекстно-свободные, контекстно-зависимые, общего вида?

                                  Ну и как уже писали, фактически все примеры в начале статьи некорректны: в языках программирования регулярные выражения так называются, видимо, по инерции, т.к. они практически везде охватывают гораздо более широкий класс языков, нежели регулярные. Ну и в компиляторах обычно используется нечто более близкое к КСГ, или даже шире.
                                    0
                                    Да, планирую продолжать дальше тему классов языков.
                                    На счет компиляторов, там используются LL(k), LALR(k) грамматики, вы совершенно правы, это подклассы КСГ. А в примере я имел ввиду генераторы лексических анализаторов, читайте внимательней.
                                      0
                                      … а лексические анализаторы, без сомнения, используются в компиляторах. Так что регулярные языки, регулярные выражения еще как используются в построении компиляторов.
                                    +1
                                    Полезная статья автора re2 (правда, на английском): Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)
                                      +1
                                      Вот бы эту статью 4 года назад, когда в институте была теория реализации языков программирования… Отличная статья!
                                        0
                                        опечатка: δ’(p0, aaax) = δ(δ’(p0, aaa), a) = δ(p5, a) = p4
                                        надо заменить на δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4
                                          0
                                          Исправил, спасибо.

                                        Only users with full accounts can post comments. Log in, please.