Я хочу выяснить, могут ли быть конфликты между двумя известными регулярными выражениями, чтобы позволить пользователю создавать список взаимоисключающих регулярных выражений.
Например, мы знаем, что приведенные ниже регулярные выражения совершенно разные, но оба они соответствуют xy50:
'^xy1\d'
'[^\d]\d2$'
Можно ли определить, используя компьютерный алгоритм, если два регулярных выражения могут иметь такой конфликт? Как?
Здесь нет проблем с остановкой. Все, что вам нужно, это вычислить, если пересечение ^xy1\d и [^\d]\d2$ не пусто.
Я не могу дать вам алгоритм здесь, но вот два обсуждения метода для генерации пересечения, не прибегая к построению DFA:
И тогда есть RAGEL
который может вычислить пересечение регулярных выражений тоже.
ОБНОВЛЕНИЕ: я только что опробовал Ragel с OP regexp. Ragel может генерировать "точечный" файл для graphviz из конечного автомата, который является потрясающим. Пересечение регулярного выражения OP выглядит следующим образом в синтаксисе Ragel:
('xy1' digit any*) & (any* ^digit digit '2')
и имеет следующий конечный автомат:
Пока пустое пересечение:
('xy1' digit any*) & ('q' any* ^digit digit '2')
выглядит так:
Так что, если все остальное терпит неудачу, тогда вы все равно можете заставить Ragel вычислить пересечение и проверить, выводит ли он пустой конечный автомат, сравнивая сгенерированный файл "точка".
Задачу можно переформулировать так: "делать языки, описанные двумя или более регулярными выражения имеют непустое пересечение "?
Если вы ограничиваете вопрос чисто регулярными выражениями (без обратных ссылок, lookahead, lookbehind или другие функции, которые позволяют распознавать контекстно-свободный или более сложный языки), вопрос, по крайней мере, разрешимый. Регулярные языки закрыты под пересечение, и существует алгоритм, который принимает два регулярных выражения как входы и производит за конечное время DFA, который распознает пересечение.
Каждое регулярное выражение может быть преобразовано в недетерминированный конечный автомат, а затем к детерминированному конечному автомату. Пара DFA может быть преобразована к DFA, который распознает пересечение. Если есть путь от начать состояние в любое принимающее состояние этого окончательного DFA, пересечение не пустое ( "конфликт", используя вашу терминологию).
К сожалению, возможно, экспоненциальное раздутие при преобразовании исходного NFA к DFA, поэтому проблема на практике становится практически невозможной, поскольку размер входные выражения растут.
И если разрешены расширения для обычных регулярных выражений, все ставки отключены - такие языки больше не закрываются при пересечении, поэтому эта конструкция не будет работа.
Я использовал этот пакет в python: http://qntm.org/greenery
Да, я думаю, что это разрешимо: вместо того, чтобы думать о регулярных выражениях как подходящих строках, вы также можете думать о них как о генерации строк. То есть все строки, которые они будут соответствовать.
Пусть [R] - множество строк, порожденных регулярным выражением R. Тогда для регулярных выражений R и T мы можем попытаться сопоставить T с [R]. Это [R] соответствует T, если в [R] есть строка, которая соответствует T.
Должно быть возможно разработать это в алгоритм, где [R] лениво построена по мере необходимости: где нормальное соответствие регулярных выражений будет пытаться сопоставить следующий символ с входной строкой и затем перейти к следующему символу в строке, модифицированный алгоритм будет проверять, может ли FSM, соответствующий входному регулярному выражению, генерировать соответствующий символ в его текущем состоянии, а затем переходит к "всем следующим состояниям" одновременно.
Другой подход - использовать Dan Kogai Perl Regexp :: Optimizer.
use Regexp::Optimizer;
my $o = Regexp::Optimizer->new->optimize(qr/foobar|fooxar|foozap/);
# $re is now qr/foo(?:[bx]ar|zap)/
... сначала оптимизируйте, а затем отбросьте все избыточные шаблоны.
Может быть, Ron Savage Regexp :: Assemble может быть еще более полезным. Это позволяет собирать произвольное количество регулярных выражений в одно регулярное выражение, которое соответствует всем, что совпадают отдельные RE. * Или комбинация обоих.
* Однако вы должны знать о некоторых различиях между Perl и Java или другими PCRE-разновидностями.
Если вы ищете библиотеку в Java, вы можете использовать Automaton, используя оператор '&':
RegExp re = new RegExp("(ABC_123.*56.txt)&(ABC_12.*456.*\\.txt)", RegExp.INTERSECTION); // Parse RegExp
Automaton a = re.toAutomaton(); // convert RegExp to automaton
if(a.isEmpty()) { // Test if intersection is empty
System.out.println("Intersection is empty!");
}
else {
// Print the shortest accepted string
System.out.println("Intersection is non-empty, example: " + a.getShortestExample(true));
}
Оригинальный ответ:
Обнаружение, могут ли два регулярных выражения соответствовать одной и той же строке