Comments 38
Вот только на практике в реальных библиотеках регулярных выражений конечные автоматы не используются. Более того, грамматика современных расширенных регекспов теоретически себя не позволяет реализовать на КА.
Как же так? Нас же учили в университете, что регулярные грамматики и конечные автоматы эксвивалентны.
Можете привести пример конструкции, являющейся регулярным выражением, которую нельзя реализовать на НKA?
Желательно с комментариями.
Можете привести пример конструкции, являющейся регулярным выражением, которую нельзя реализовать на НKA?
Желательно с комментариями.
Потому что самые популярные так называемые Perl-compatible regular expressions на самом деле шире, чем классические регулярные выражения. Самый простой пример — ссылка назад на группу,
"(a+)b+\1"Да, понятно. Спасибо.
Спасибо, за информацию. Я только начал разбираться в этом направлении, буду «копать глубже».
Не верьте Beholder. Обратные ссылки нормально ложатся в парадигму конечных автоматов, входят в POSIX ERE и поддерживаются всеми подряд. Для их обработки используются именно конечные автоматы. Кто не верит, может подебажить.
perl -Mre=debug -e'"aabbaa"=~/(a+)b+\1/'$regex = qr/0(??{$regex})?1/;
Про обратные ссылки неправда, их можно реализовать исключительно при помощи бэктрекинга.
Ну без бектрекинга нельзя сделать даже
Другое дело, что они (обратные ссылки) приводят к очень неэффективным выражениям, но точно такие же неэффективности можно можно получить и не используя обратные ссылки :-)
Давайте говорить по существу. Конечный автомат или нет. А о его эффективности или фичах можно рассуждать отдельно.
(a|aa)*b и обратные ссылки тут не причём. А бектрекинг существует во всех порядочных NFA.Другое дело, что они (обратные ссылки) приводят к очень неэффективным выражениям, но точно такие же неэффективности можно можно получить и не используя обратные ссылки :-)
Давайте говорить по существу. Конечный автомат или нет. А о его эффективности или фичах можно рассуждать отдельно.
Ну без бектрекинга нельзя сделать даже (a|aa)*b и обратные ссылки тут не причём. А бектрекинг существует во всех порядочных NFA.
Еще как можно. Есть условно три типа «движков» для вычисления регекспов: ДКА (DFA), НКА (NDFA) и бектрекинг. Сравните:
ДКА Автомат в любой момент времени находится в определенном состоянии, для простоты считаем, что состояния перенумерованы, то есть состояние это целое число. Имеется таблица переходов, которая для текущего состояния и текущего символа строки говорит следующее состояние.
Вычисление происходит за в один проход по строке слева направо: прочитать очередной символ, по таблице определить следующее состояние, повторить. Количество итераций == длина строки.
НКА Все то же самое, только автомат находится во множестве состояний сразу. Количество итераций == длина строки.
Бектрекинг Каждый раз попадая в ситуацию выбора, запоминаем этот факт и исследуем первую альтернативу. Если не удалось заматчить, возвращаемся и пробуем следующую и тд. Сложность в худшем случае — экспонента от длины строки.
Но вы, я надеюсь, понимаете, что НКА не рассматривает сразу все альтернативы? Он запаминает каждую развилку и ходит по каждой ветке по-порядку. Именно поэтому, кстати, порядок альтернатив в скобках важен, а порядок символов в квадратных скобках не важен.
Так вот, вопрос. Чем, по вашему, работа НКА отличается от бектрекинга? Возможно ли одно без другого?
Ну а про линейность НКА вы очень сильно заблуждаетесь. Линейна только каждая ветка. Но веток-то может быть много. То есть НКА работал бы линейно, если бы чудо-машина имела столько процессорных ядер, сколько символов во входной строке. То есть, фактически, не имела бы ограничений производительности :-)
Так вот, вопрос. Чем, по вашему, работа НКА отличается от бектрекинга? Возможно ли одно без другого?
Ну а про линейность НКА вы очень сильно заблуждаетесь. Линейна только каждая ветка. Но веток-то может быть много. То есть НКА работал бы линейно, если бы чудо-машина имела столько процессорных ядер, сколько символов во входной строке. То есть, фактически, не имела бы ограничений производительности :-)
Но вы, я надеюсь, понимаете, что НКА не рассматривает сразу все альтернативы?
В том то и дело, что рассматривает.
минута ликбеза
Позволю себе позаимствовать картинку автора топика: 
Легко увидеть, что это именно НКА — имеются ε переходы (переход, который не «съедает» текущий символ), а также из одного состояния могут быть переходы в разные состояния по одному и тому же символу (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 миллиарда состояний.
Особо отмечу, что сложность эквивалентного ДКА зависит исключительно от сложности выражения и никак не зависит от размера входа.
Если построение ДКА не является практичным (не вписались в лимит по памяти из-за числа состояний), используем НКА как есть. На практике часто применяется кеширование — во время матчинга при помощи НКА мы строим эквивалентный ДКА, но только для посещенных состояний. В результате вместо того, чтобы каждый раз считать новый список состояний, мы можем воспользоваться закешированным переходом (если он есть). При необходимости мы можем безболезненно удалить часть содержимого кеша.
НКА в самом деле рассматривает все альтернативы одновременно, как бы парадоксально это не звучало.
НКА эмулирует параллельную работу «бригады» ДКА. Если встречается «развилка» динамически добавляются новые ДКА. Если какая-то из ДКА заходит в тупик, она удаляется. Поскольку для представления всей информации о текущем состоянии ДКА достаточно одного целого числа, то состояние все «бригады» описывается списком целых чисел.
Легко заметить, что максимальный размер «бригады» может быть ограничен общим числом состояний НКА, а вовсе не длиной входа. В самом деле, если число эмулируемых ДКА превышает общее число состояний, значит хотя бы два ДКА находятся в одном и том же состоянии, и один из них можно безболезненно удалить.
Пример для наглядности (по НКА с картинки). Начальное состояние там 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 миллиарда состояний.
Особо отмечу, что сложность эквивалентного ДКА зависит исключительно от сложности выражения и никак не зависит от размера входа.
Если построение ДКА не является практичным (не вписались в лимит по памяти из-за числа состояний), используем НКА как есть. На практике часто применяется кеширование — во время матчинга при помощи НКА мы строим эквивалентный ДКА, но только для посещенных состояний. В результате вместо того, чтобы каждый раз считать новый список состояний, мы можем воспользоваться закешированным переходом (если он есть). При необходимости мы можем безболезненно удалить часть содержимого кеша.
Добавлю, что порядок альтернатив в скобках важен исключительно в случае применения бектрекинга.
В классических регулярных выражениях, как их знает computer science, порядок альтернатив не важен. К сожалению, практика в данном случае идет вразрез с теорией — в большинстве современных языковых сред регулярные выражения работают именно на бектрекинге.
В классических регулярных выражениях, как их знает computer science, порядок альтернатив не важен. К сожалению, практика в данном случае идет вразрез с теорией — в большинстве современных языковых сред регулярные выражения работают именно на бектрекинге.
perl -Mre=debug -e'"aaaaaa"=~/(a+)\1/'
а это случайно не бэктрекинг?
В примере
perl -Mre=debug -e'"aabbaa"=~/(a+)b+\1/'
помоему все же не классический конечный автомат: его вид динамически меняется в зависимости от того, какой путь ты уже прошел.
Хм. А у Фриддла в книжке даже описан способ понять НКА или ДКА реализован в языке. С чего бы? :)
Всё не так категорично, это зависит от задачи. Высокоэффективные реализации, типа re2 http://code.google.com/p/re2/, отказываются от некоторых фич PCRE, но при этом строят точно тот самый DFA.
Re2 может построить DFA а может ограничиться NFA, например если превышено ограничение по памяти (состояний может быть много). Кроме того, если в выражении присутствуют capturing paranthesis, то DFA неприменим. Интересующимя крайне рекомендую к прочтению вот это.
Не совсем так. Захватывающие скобки используются, чтобы заматчить подвыражение. RE2 умеет это:
RE2 supports submatch extraction, but not backreferences.А вот сослаться на подвыражение в RE2 дальше в выражении уже нельзя.
Разумеется, захватывающие скобки это не то же самое что \1.
Я утверждаю, что re2 может использовать как DFA так и NFA, причем если есть «захватывающие» скобки применяется именно NFA. Ибо из DFA не получается добыть информацию о границах подвыражения.
Почитайте док по ссылке из предыдущего комента. Там в самом деле интересно, например RE2 иногда выполняет выражение задом-на-перед, зачем — не скажу :)
Я утверждаю, что re2 может использовать как DFA так и NFA, причем если есть «захватывающие» скобки применяется именно NFA. Ибо из DFA не получается добыть информацию о границах подвыражения.
Почитайте док по ссылке из предыдущего комента. Там в самом деле интересно, например RE2 иногда выполняет выражение задом-на-перед, зачем — не скажу :)
Я не поленился и потестил: Boost.Regex, Perl RE
Время работы:
Спасибо за ссылку, кстати. Там 3 статьи — не одна. И все более чем достойны внимания.
Время работы:
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 статьи — не одна. И все более чем достойны внимания.
Спасибо за ссылку!
В бауманке проходим регулярные языки на дискретной математике. Методичка, ибо может быть полезна: rghost.ru/43251770
Обнаруженные опечатки:
Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающиеих цепочки.
В данной статье мы сначала ознакомимся с конечными автоматами и их видами[](ДКА и НКА)
Например, ваша реакция, на то, что ваш сосед слушает громко музыку по ночам
возникает вопрос;: Ккакой памятью должен обладать КА
бесконечное число предысторийне вневозможно
с помощью пробела или пустой строки[](например
итерация[](замыкание Клини)
функция переходов, то расширеннаяую функцияию переходов, построенную по δ, обозначим
мы ожидаем, что автомат
таким образом цепочка aaax, является корректной
Поправьте, пожалуйста.
Формализм с классами эквивалентности, метафора с параллельными мирами — блестяще. И совершенно без предупреждения появляется термин «допускающее состояние». Возможно, завершив метафоры и пояснения, стоит дать (кратенько), формальное описание автомата (это пятёрка, такая, что ...). Заодно поясните точнее, что такое в контексте статьи «цепочка» и некоторые другие термины.
Об описании синтаксиса РВ, «используемого в данной статье». Возможно, полезно указать приоритеты вводимых операций, их арность и способ записи (инфиксная/префиксная/постфиксная). Ну и, возмножно, смысл :) Замыкание Клини, да и объединение (объединение чего? Ведь не частей регулярного выражения а ля конкатенация, а регулярных языков — это неочевидно), может потребовать более развернутого описания.
Пример: xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)
Было бы неплохо как-нибудь выделить операторы объединения верхнего уровня — а то глаз сломаешь, пока разберешься. Хотя бы так:
xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)
Ну а дальше… Не пояснили, что такое ε-переходы, не пояснили, что такое ε-замыкание (молча его используете). Если бы я не знал этот алгоритм, мне было бы трудно разобраться. Посмотрите, как этот алгоритм описан у Ахо, Сети, Ульмана и Лам ("Компиляторы. Принципы, технологии, инструменты") — практически образец ясности. Там не таких замечательных метафор и идеи с классами эквивалентности, так что эта книга не обесценивает вашу статью.
Статья в целом понравилась, спасибо.
Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающ
В данной статье мы сначала ознакомимся с конечными автоматами и их видами[](ДКА и НКА)
Например, ваша реакция
возникает вопрос
бесконечное число предысторий
с помощью пробела или пустой строки[](например
итерация[](замыкание Клини)
функция переходов, то расширенн
мы ожидаем, что автомат
таким образом цепочка aaax
Поправьте, пожалуйста.
Гитлер выиграл 2-ю Мир. войнуОй, а давайте имя «Вторая мировая война» писать полностью?
Формализм с классами эквивалентности, метафора с параллельными мирами — блестяще. И совершенно без предупреждения появляется термин «допускающее состояние». Возможно, завершив метафоры и пояснения, стоит дать (кратенько), формальное описание автомата (это пятёрка, такая, что ...). Заодно поясните точнее, что такое в контексте статьи «цепочка» и некоторые другие термины.
Об описании синтаксиса РВ, «используемого в данной статье». Возможно, полезно указать приоритеты вводимых операций, их арность и способ записи (инфиксная/префиксная/постфиксная). Ну и, возмножно, смысл :) Замыкание Клини, да и объединение (объединение чего? Ведь не частей регулярного выражения а ля конкатенация, а регулярных языков — это неочевидно), может потребовать более развернутого описания.
Пример: xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)
Было бы неплохо как-нибудь выделить операторы объединения верхнего уровня — а то глаз сломаешь, пока разберешься. Хотя бы так:
xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)
Ну а дальше… Не пояснили, что такое ε-переходы, не пояснили, что такое ε-замыкание (молча его используете). Если бы я не знал этот алгоритм, мне было бы трудно разобраться. Посмотрите, как этот алгоритм описан у Ахо, Сети, Ульмана и Лам ("Компиляторы. Принципы, технологии, инструменты") — практически образец ясности. Там не таких замечательных метафор и идеи с классами эквивалентности, так что эта книга не обесценивает вашу статью.
Статья в целом понравилась, спасибо.
Cпасибо, за ваши замечания, я возьму их во внимания. Данная статья является дебютной на Хабре, так что не судите строго.
А можно поинтересоваться, что не понравилось минусующим? Что была выполнена вычитка текста, а результаты не убраны в стол, а предоставлены автору? Или кого-то оскорбила просьба объяснить, что такое ε-замыкание в статье, которая его использует и, судя по объяснениям, что такое регулярные выражения и конечные автоматы, рассчитана на неподготовленного читателя? Или что-то еще?
Список опечаток, традиционно вызывающий рекомендацию «опечатки — в ЛС!», здесь такого желания не вызвал — очень информативно.
Интересующимся мог бы еще посоветовать книгу, доступную на books.ru — Регулярные выражения, Джеффри Фридл
На coursera.org был/будет хороший курс Automata (FA перетекает в RE, CFG, TM, много интересных вещей)
Вспомнилось самое начало прошедшего семестра, ТРЯП — как раз с регулярных выражений и языков всё началось. Планируете ли продолжать тему классов языков: контекстно-свободные, контекстно-зависимые, общего вида?
Ну и как уже писали, фактически все примеры в начале статьи некорректны: в языках программирования регулярные выражения так называются, видимо, по инерции, т.к. они практически везде охватывают гораздо более широкий класс языков, нежели регулярные. Ну и в компиляторах обычно используется нечто более близкое к КСГ, или даже шире.
Ну и как уже писали, фактически все примеры в начале статьи некорректны: в языках программирования регулярные выражения так называются, видимо, по инерции, т.к. они практически везде охватывают гораздо более широкий класс языков, нежели регулярные. Ну и в компиляторах обычно используется нечто более близкое к КСГ, или даже шире.
Полезная статья автора re2 (правда, на английском): Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)
Вот бы эту статью 4 года назад, когда в институте была теория реализации языков программирования… Отличная статья!
опечатка: δ’(p0, aaax) = δ(δ’(p0, aaa), a) = δ(p5, a) = p4
надо заменить на δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4
надо заменить на δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4
UFO just landed and posted this here
не будем приводить правила преобразования РВ в КА, так как они довольно очевидные
Ну здрасьте. Вообще-то именно в этом и должна была быть заявленная цель статьи. Человек, который только что познакомился с конечными автоматами, хочет знать, как они применяются, и начинать надо с примеров вида ab.*cd - без этого дальнейшие показанные графы просто темный лес. Тем более, что рисовать на ребре не один символ, а сразу целое выражение - тоже нифига не очевидно для того, кто регэкспы уже видел, а конечные автоматы еще нет. Ну про эпсилон уже сказали.
Sign up to leave a comment.
Регулярные выражения изнутри