"Обычные" из computer science, для которых строится конечный автомат, и после его создания - они обрабатывают каждый символ за O(1). К сожалению, построеный автомат может занимать экспонциально много места (или если лениво - то расти как 30байт*размер входа).
И есть PCRE, с backreferences. Они не требуют памяти, но зато могут работать эспоненциально долго, из-за перебора вариантов.
Вопрос, называть ли PCRE "регулярными выражением" - культурно-терминологический, как кофе мужского рода. В университете за это поставят двойку на экзамене. А в реальной работе - неважно как оно называется, важно умещается ли оно в память и быстро ли работает. Но иногда можно нарваться на собеседовании на университетского зануду.
По технической стороне все так. Беспокоит меня человеческая, когда рабочий программист задает такой вопрос, при этом зная, что регекспы не только в учебниках бывают - и потом, бывает, на основании ответов Выводы делает, вплоть до "сдайте ваш диплом обратно". Но эта проблема общая, конечно.
Ну можно так и ответить, благо собеседование - это не тест с вариантами ответов: Если регулярные выражения сделаны на конечных автоматов - тогда нельзя. Если это PCRE с рекурсивными backreferences - то можно.
Даже короткие выражения могут вызывать у метода детерминированных конечных автоматов сбой по нехватке памяти, а у недетерминированных - по времени работы. (Какие-то другие алгоритмы могут быть компромиссными и практичными, но они будут компромиссными и по достоинствам [скорость и простота реализации].)
На этом, казалось бы, можно было бы забыть о применимости "регулярных выражений" на практике и называть это как-нибудь по-другому.
Но в реальности словосочетание оставили, недостатки оставили, зато добавили примочек, которые разрывают связь с теорией.
Практика все-таки разная бывает, для простых вещей они имхо вполне подходят. Если, конечно, помнить о возможности организовать экспоненциальное время работы (ну или экспоненциальную же память).
Самое смешное, что рекурсивный ужос из поста - a(?R)?b(?R)? - похоже отрабатывает за линейное время. Т.к. каждый очередной символ однозначно задает дальнейший ход матчинга, и развесистых деревьев - причины тормозов/перебора по памяти - просто не будет.
Они подходят во многом потому, что есть готовые движки.
Сейчас трудно представить себе написание таких движков на типичной работе, того, кто начнёт писать, скорее всего "не поймут". Ну и с квалификацией могут быть проблемы (а того, кто не сможет написать, скорее всего не выгонят).
Другое дело, что как раз написать руками проверку скобок - может быть более разумным, чем использование "регулярных выражений", каким бы ни был движок.
Ну движки - "чёрные ящики" фактически. Я догадываюсь, что в PCRE-движках скобки скорее всего проверяли в связи с рекуррентными выражениями (это у них основной пример, зачем они нужны, как я понял), но общее соображение, что что-то легко можно сделать линейным, может и не сработать. Ну или окажется, что на "<миллиард открывающих скобок><миллиард закрывающих скобок>" движок вылетит. Надо будет проверить, когда под рукой будет работающий Перл
Проверил, но не на Перле самом, а на утилите для тестирования PCRE с http://www.rexegg.com/pcregrep-pcretest.html : всё было хорошо (выражение было почти из документации: "^(? \(([^()]++|(?&pn))*\))$" [начало и конец строки добавлены, чтобы он не искал долго подходящую подстроку, а только проверял текст целиком]), но на тысяче открывающих и тысяче закрывающих скобок вышло переполнение стека (в виде исключения c00000fd).
Вроде бы есть версия библиотеки и без рекурсии, но подходящей иллюстрацией являются и условия по умолчанию. Ведь версией без рекурсии не надо пользоваться: "If you want to build a version of PCRE2 that works this way, add --disable-stack-for-recursion to the configure command. By default, the system functions malloc() and free() are called to manage the heap memory that is required, but custom memory management functions can be called instead. PCRE2 runs noticeably more slowly when built in this way."
Comments 7
"Обычные" из computer science, для которых строится конечный автомат, и после его создания - они обрабатывают каждый символ за O(1). К сожалению, построеный автомат может занимать экспонциально много места (или если лениво - то расти как 30байт*размер входа).
И есть PCRE, с backreferences. Они не требуют памяти, но зато могут работать эспоненциально долго, из-за перебора вариантов.
Вопрос, называть ли PCRE "регулярными выражением" - культурно-терминологический, как кофе мужского рода. В университете за это поставят двойку на экзамене. А в реальной работе - неважно как оно называется, важно умещается ли оно в память и быстро ли работает. Но иногда можно нарваться на собеседовании на университетского зануду.
Reply
Беспокоит меня человеческая, когда рабочий программист задает такой вопрос, при этом зная, что регекспы не только в учебниках бывают - и потом, бывает, на основании ответов Выводы делает, вплоть до "сдайте ваш диплом обратно".
Но эта проблема общая, конечно.
Reply
Если регулярные выражения сделаны на конечных автоматов - тогда нельзя.
Если это PCRE с рекурсивными backreferences - то можно.
Reply
Даже короткие выражения могут вызывать у метода детерминированных конечных автоматов сбой по нехватке памяти, а у недетерминированных - по времени работы. (Какие-то другие алгоритмы могут быть компромиссными и практичными, но они будут компромиссными и по достоинствам [скорость и простота реализации].)
На этом, казалось бы, можно было бы забыть о применимости "регулярных выражений" на практике и называть это как-нибудь по-другому.
Но в реальности словосочетание оставили, недостатки оставили, зато добавили примочек, которые разрывают связь с теорией.
Reply
Самое смешное, что рекурсивный ужос из поста - a(?R)?b(?R)? - похоже отрабатывает за линейное время. Т.к. каждый очередной символ однозначно задает дальнейший ход матчинга, и развесистых деревьев - причины тормозов/перебора по памяти - просто не будет.
Reply
Сейчас трудно представить себе написание таких движков на типичной работе, того, кто начнёт писать, скорее всего "не поймут". Ну и с квалификацией могут быть проблемы (а того, кто не сможет написать, скорее всего не выгонят).
Другое дело, что как раз написать руками проверку скобок - может быть более разумным, чем использование "регулярных выражений", каким бы ни был движок.
Ну движки - "чёрные ящики" фактически. Я догадываюсь, что в PCRE-движках скобки скорее всего проверяли в связи с рекуррентными выражениями (это у них основной пример, зачем они нужны, как я понял), но общее соображение, что что-то легко можно сделать линейным, может и не сработать. Ну или окажется, что на "<миллиард открывающих скобок><миллиард закрывающих скобок>" движок вылетит. Надо будет проверить, когда под рукой будет работающий Перл
Reply
\(([^()]++|(?&pn))*\))$" [начало и конец строки добавлены, чтобы он не искал долго подходящую подстроку, а только проверял текст целиком]), но на тысяче открывающих и тысяче закрывающих скобок вышло переполнение стека (в виде исключения c00000fd).
Вроде бы есть версия библиотеки и без рекурсии, но подходящей иллюстрацией являются и условия по умолчанию. Ведь версией без рекурсии не надо пользоваться: "If you want to build a version of PCRE2 that works this way, add
--disable-stack-for-recursion
to the configure command. By default, the system functions malloc() and free() are called to manage the heap memory that is required, but custom memory management functions can be called instead. PCRE2 runs noticeably more slowly when built in this way."
Reply
Leave a comment