Обнаружение конфликтов регулярных выражений
Предположим, что два регулярных выражения e1 и e2 столкнитесь, если существует какая-либо строка s, такая, что оба e1 и e2 совпадают s.
Существует ли какой-либо простой (эффективный) способ проверить, сталкиваются ли два регулярных выражения без перебора набора всех возможных строк в нашем словаре?
Примечание 1: Я не знаю, называется ли это как-то по-другому в литературе. Может быть, мне просто не хватает подходящего имени для поиска это.
Примечание 2: Идеальным ответом для меня является написанный PHP-код, но я принимаю любое предложение, не обязательно PHP.
1 answers
Итак, после дальнейших исследований, похоже, что в литературе это называется пересечением регулярных выражений .
Это возможно, и, по-видимому, это несложно реализовать, но, похоже, официальной поддержки PHP нет.
Ключ к реализации простого алгоритма основан на переводе регулярных выражений в конечный автомат. Прочитайте прикрепленные ссылки, чтобы лучше понять решение.
Связанный с переполнением стека вопросы:
Пересечение двух регулярных выражений
Вычислите, не пересекаются ли два бесконечных набора решений регулярных выражений
Неофициальная библиотека для PHP:
Https://github.com/KendallHopkins/FormalTheory
Редактировать: Добавление фрагмента кода для проверки пересечений с использованием библиотеки Кендалла Хопкинса:
function doRegexIntersection($regex_string_1, $regex_string_2) {
$lexer = new FormalTheory_RegularExpression_Lexer();
$nfa1 = $lexer->lex( $regex_string_1 )->getNFA();
$nfa2 = $lexer->lex( $regex_string_2 )->getNFA();
return FormalTheory_FiniteAutomata::intersection( $nfa1, $nfa2 )->validSolutionExists();
}