Regex: Определите, могут ли два регулярных выражения совпадать для одного входа?

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

Например, мы знаем, что регулярные выражения ниже отличаются друг от друга, но оба они соответствуют xy50 :

 '^xy1\d' '[^\d]\d2$' 

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

Здесь нет проблемы с остановкой. Все, что вам нужно, это вычислить, если пересечение ^xy1\d и [^\d]\d2$ в непустое.

Я не могу дать вам алгоритм здесь, но вот два обсуждения метода для создания пересечения, не прибегая к построению DFA:

А потом есть RAGEL

который также может вычислять пересечение регулярных выражений.

UPDATE: Я просто попробовал Ragel с регулярным выражением OP. Ragel может генерировать «dot» файл для 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, поэтому проблема на практике становится практически невозможной, поскольку размер входных выражений возрастает.

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

Да, я думаю, что это разрешимо: вместо того, чтобы думать о регулярных выражениях как подходящих строках, вы также можете думать о них как о генерации строк. То есть все строки, которые они будут соответствовать.

Пусть [R] – множество строк, порожденных регулярным выражением R. Тогда для регулярных выражений R и T мы можем попытаться сопоставить T с [R]. Это [R] соответствует T, если в [R] есть строка, которая соответствует T.

Должно быть возможно разработать это в алгоритм, где [R] лениво строится по мере необходимости: где нормальное соответствие регулярных выражений будет пытаться сопоставить следующий символ с входной строкой, а затем перейти к следующему символу в строке, модифицированный алгоритм будет проверять, может ли FSM, соответствующий входному регулярному выражению, генерировать соответствующий символ в его текущем состоянии, а затем переходит к «всем следующим состояниям» одновременно.

Другим подходом было бы использовать инструмент Perl Regexp :: Optimizer от Dan Kogai .

  use Regexp::Optimizer; my $o = Regexp::Optimizer->new->optimize(qr/foobar|fooxar|foozap/); # $re is now qr/foo(?:[bx]ar|zap)/ 

.. сначала оптимизируйте, а затем отбросьте все избыточные шаблоны.

Возможно, Regexp :: Assemble Ron Savage может быть еще более полезным. Это позволяет собирать произвольное количество регулярных выражений в одно регулярное выражение, которое соответствует всем, что соответствует отдельным RE. * Или комбинация обоих.

* Тем не менее, вам нужно знать некоторые различия между Perl и Java или другими вариантами PCRE.

  • Заменить первое вхождение строки в Python
  • Найдите «слово», а не «@»
  • Извлечение чисел из векторов строк
  • Регулярное выражение: числовой диапазон
  • Регулярное выражение для соответствия формату времени HH: MM
  • Как я могу распознать злое регулярное выражение?
  • Регулярное выражение для остановки при первом совпадении
  • Регулярное выражение для чисел с плавающей запятой
  • Regex найти повторяющиеся числа
  • Может ли расширенная реализация регулярных выражений анализировать HTML?
  • Изучение регулярных выражений
  • Давайте будем гением компьютера.