Как можно обнаружить, если два регулярных выражения накладываются в строках, они могут соответствовать?
Goto является чрезвычайно низким в моем списке вещей включать в программу только ради него. Это не означает, что это недопустимо.
Goto может быть хорошим для конечных автоматов. Оператор переключения в цикле (в порядке типичной важности): (a) не на самом деле представительный для потока управления, (b) ужасный, (c) потенциально неэффективный в зависимости от языка и компилятора. Таким образом, Вы заканчиваете тем, что писали одну функцию на состояние и сделали вещи как "возврат NEXT_STATE"; которые даже похожи на goto.
Предоставленный, трудно кодировать конечные автоматы способом, которые делают их легкими понять. Однако ничего подобного, трудность относится к использованию goto и ни одному из него, не может быть уменьшен при помощи альтернативных управляющих структур. Если Ваш язык не имеет конструкцию 'конечного автомата'. Мой не делает.
В тех редких случаях, когда Ваш алгоритм действительно является самым понятным с точки зрения пути через последовательность узлов (состояния), соединенные ограниченным набором допустимых переходов (gotos), а не больше определенным потоком управления (циклы, условные выражения, этажерка), тогда это должно быть явно в коде. И необходимо нарисовать симпатичную схему.
setjmp/longjmp может быть хорошим для реализации исключений или подобного исключению поведения. В то время как не универсально похваливший, исключения обычно считают "допустимой" управляющей структурой.
setjmp/longjmp 'более опасны', чем goto в том смысле, что их более трудно использовать правильно, не берите в голову понятно.
никогда не было, и при этом никогда не будет, никакой язык, на котором это - наименее разрядное трудное для записи плохого кода. - Donald Knuth.
Вынимающий goto из C не сделал бы немного легче записать хороший код в C. На самом деле это упустило бы суть, что C , предположил быть способным к действию как прославленный ассемблерный язык.
Следующий это будут "указатели, которые рассматривают вредными", тогда "утиный ввод, который рассматривают вредным". Тогда, кого оставят защитить Вас, когда они прибудут для убирания небезопасной конструкции программирования? А?
3 ответа
Нет простого способа.
Пока ваши регулярные выражения используют только стандартные функции (я думаю, Perl позволяет вставлять произвольный код в сопоставление), вы можете создать для каждого из них недетерминированный конечный автомат (NFA) , который компактно кодирует все строки, которым соответствует RE.
Для любой пары NFA разрешимо, является ли их пересечение пустым. Если пересечение не пусто, то некоторая строка соответствует обоим RE в паре (и наоборот).
Стандартное доказательство разрешимости состоит в том, чтобы сначала определить их в DFA , а затем построить новый DFA чьи состояния являются парами состояний двух DFA, и чьи конечные состояния - это в точности те, в которых оба состояния в паре являются конечными в своих исходных DFA. В качестве альтернативы, если вы Мы уже показали, как вычислить дополнение NFA, тогда вы можете (стиль закона ДеМоргана) получить пересечение дополнительным (объединением (дополнительным (A), дополнительным (B))) .
К сожалению. , NFA-> DFA включает потенциально экспоненциальный взрыв размера (поскольку состояния в DFA являются подмножествами состояний в NFA). Из Википедии :
Некоторые классы обычных языков могут описываться только детерминированными конечные автоматы, размер которых растет экспоненциально в размере кратчайший эквивалент обычный выражения. Стандартный пример: здесь языки L_k, состоящие из все строки в алфавите {a, b} у которого k-я последняя буква равна A.
Кстати, вам обязательно стоит использовать OpenFST . Вы можете создавать автоматы в виде текстовых файлов и экспериментировать с такими операциями, как минимизация, пересечение и т. Д., Чтобы увидеть, насколько они эффективны для вашей задачи. Уже существуют компиляторы regexp-> nfa-> dfa с открытым исходным кодом (я помню модуль Perl); измените один для вывода файлов автоматов OpenFST и поэкспериментируйте.
К счастью, можно избежать взрыва подмножества состояний и пересечь два NFA напрямую, используя ту же конструкцию, что и для DFA:
if A - > a B (в одной NFA вы можете перейти из состояния A в B, выводя букву «a»)
и X -> a Y (в другом NFA)
тогда (A, X) -> a (B, Y) на пересечении
(C, Z) является окончательным, если и только если C является окончательным в одном NFA, а Z - в другом.
Чтобы начать процесс, вы начинаете с пары начальных состояний для двух NFA, например (A , X) - это начальное состояние пересечения-NFA. Каждый раз, когда вы впервые посещаете состояние, генерируйте дугу по вышеуказанному правилу для каждой пары дуг, выходящих из двух состояний, а затем посещайте все (новые) состояния, которых достигают эти дуги. Вы бы сохранили тот факт, что вы расширили дуги состояния (например, в хеш-таблице), и в конечном итоге исследуете все состояния, достижимые с самого начала.
Если вы разрешите переходы эпсилон (которые не выводят буквы), это отлично:
если A -> эпсилон B в первом NFA, то для каждого достигнутого состояния (A, Y) добавьте дугу (A, Y ) -> эпсилон (B, Y) и аналогично для эпсилонов во второй позиции NFA.
Переходы Epsilon полезны (но не необходимы) для объединения двух NFA при преобразовании регулярного выражения в NFA; всякий раз, когда у вас есть чередование regexp1 | regexp2 | regexp3 , вы берете объединение: NFA, начальное состояние которого имеет эпсилон-переход к каждой из NFA, представляющих регулярные выражения в чередовании.
Определение пустоты для NFA легко: если вы когда-нибудь достигнете конечного состояния при выполнении поиска в глубину из начального состояния, оно не пусто.
Это пересечение NFA похоже на композицию преобразователя с конечным числом состояний (преобразователь - это NFA, который выводит пары символов, которые объединяются попарно для соответствия как входной, так и выходной строкам или для преобразования заданного входа в выход).
Переходы Epsilon полезны (но не необходимы) при объединении двух NFA при преобразовании регулярного выражения в NFA; всякий раз, когда у вас есть чередование regexp1 | regexp2 | regexp3 , вы берете объединение: NFA, начальное состояние которого имеет эпсилон-переход к каждой из NFA, представляющих регулярные выражения в чередовании.
Определение пустоты для NFA легко: если вы когда-либо достигнете конечного состояния при выполнении поиска в глубину из начального состояния, оно не пусто.
Это пересечение NFA похоже на композицию преобразователя с конечным числом состояний (преобразователь - это NFA, который выводит пары символов, которые объединяются попарно для соответствия как входной, так и выходной строкам или для преобразования заданного входа в выход).
Переходы Epsilon полезны (но не необходимы) при объединении двух NFA при преобразовании регулярного выражения в NFA; всякий раз, когда у вас есть чередование regexp1 | regexp2 | regexp3 , вы берете объединение: NFA, начальное состояние которого имеет эпсилон-переход к каждой из NFA, представляющих регулярные выражения в чередовании.
Определение пустоты для NFA легко: если вы когда-нибудь достигнете конечного состояния при выполнении поиска в глубину из начального состояния, оно не пусто.
Это пересечение NFA похоже на композицию преобразователя с конечным числом состояний (преобразователь - это NFA, который выводит пары символов, которые объединяются попарно для соответствия как входной, так и выходной строкам или для преобразования заданного входа в выход).
Этот инвертор регулярных выражений (написанный с использованием pyparsing) работает с ограниченным подмножеством синтаксиса re (например, не разрешены * или +) - вы можете преобразовать два re в два набора и затем ищите пересечение множества.
Теоретически описанная вами проблема невозможна.
На практике, если у вас есть управляемое количество регулярных выражений, которые используют ограниченное подмножество или синтаксис регулярных выражений, и / или ограниченное выбор строк, которые могут использоваться для сопоставления с контейнером регулярных выражений, вы можете решить эту проблему.
Предполагая, что вы не пытаетесь решить абстрактный общий случай, вы можете что-то сделать, чтобы решить практическое применение. Возможно, если бы вы предоставили репрезентативную выборку регулярных выражений и описали строки, с которыми вы будете сопоставлять, можно было бы создать эвристику для решения проблемы.