Как вы можете определить, совпадают ли два регулярных выражения в строках, которые они могут сопоставить?

Ответ 1

Нет простого способа.

Пока ваши регулярные выражения используют только стандартные функции (Perl позволяет вам встраивать произвольный код в соответствие, я думаю), вы можете создавать из каждого недетерминированный конечный автомат (NFA), который компактно кодирует все строки, совпадающие с RE.

Учитывая любую пару NFA, она разрешима, является ли их пересечение пустым. Если пересечение не пустое, то некоторая строка соответствует обеим RE в паре (и наоборот).

Стандартное доказательство разрешимости состоит в том, чтобы сначала определить их в DFA, а затем построить новый DFA, состояния которого являются парами двух состояний DFAs, и конечными состояниями которых являются те, в которых оба состояния в паре являются окончательными в их исходном DFA. В качестве альтернативы, если вы уже указали, как вычислить дополнение NFA, вы можете (стиль закона DeMorgan) получить пересечение на complement(union(complement(A),complement(B))).

К сожалению, NFA- > DFA включает потенциальный взрыв экспоненциального размера (поскольку состояния в DFA являются подмножествами состояний в NFA). Из Wikipedia:

Некоторые классы регулярных языков могут только описываются детерминированными конечные автоматы, размер которых растет экспоненциально в размере кратчайший эквивалентный регулярный выражения. Стандартный пример здесь языки 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. Каждый раз, когда вы впервые посещаете состояние, генерируете дугу по приведенному выше правилу для каждой пары дуг, оставляющих два состояния, а затем посещайте все (новые) состояния, которые достигают эти дуги. Вы сохранили бы факт, что вы расширили дуги состояния (например, в хеш-таблице) и в конечном итоге исследуете все состояния, доступные с самого начала.

Если вы разрешаете переходы epsilon (которые не выводят букву), это прекрасно:

если A ->epsilon B в первом NFA, то для каждого состояния (A,Y) вы достигаете, добавьте дугу (A,Y) ->epsilon (B,Y) и аналогично для эпсилонов во второй позиции NFA.

Переходы Эпсилона полезны (но не обязательно) при объединении двух NFA при переводе регулярного выражения в NFA; всякий раз, когда у вас есть чередование regexp1|regexp2|regexp3, вы принимаете объединение: NFA, состояние начала которого имеет переход epsilon к каждому из NFA, представляющих регулярные выражения в чередовании.

Решение о пустоте для NFA легко: если вы когда-либо достигли конечного состояния при выполнении поиска по глубине из состояния начала, оно не пустое.

Это пересечение NFA аналогично составу преобразователя конечного состояния (преобразователь представляет собой NFA, который выводит пары символов, которые конкатенируются попарно, чтобы соответствовать как входной, так и выходной строкам, или преобразовывать заданный вход в выходной сигнал).

Ответ 2

Этот постоянный преобразователь (написанный с использованием pyparsing) работает с ограниченным подмножеством синтаксиса re (например, без * или +) - вы можете инвертировать два re в два набора, а затем искать множество пересечений.

Ответ 3

В теории проблема, которую вы описываете, невозможна.

На практике, если у вас есть управляемое количество регулярных выражений, которые используют ограниченное подмножество или синтаксис regexp и/или ограниченный выбор строк, которые могут использоваться для сопоставления с контейнером регулярных выражений, вы можете быть в состоянии для его решения.

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