RegEx, удовлетворяющий другому RegEx [duplicate]

Задачу можно переформулировать так: «если языки, описанные двумя или более регулярными выражениями, имеют непустое пересечение»?

Если вы зададите вопрос pure регулярные выражения (без обратных ссылок, lookahead, lookbehind или других функций, которые позволяют распознавать контекстно-свободные или более сложные языки), вопрос, по меньшей мере, разрешимый. Регулярные языки закрыты под пересечением, и существует алгоритм, который принимает два регулярных выражения в качестве входных данных и в течение конечного времени создает DFA, который распознает пересечение.

Каждое регулярное выражение может быть преобразовано в недетерминированное конечный автомат, а затем - детерминированный конечный автомат. Пара DFA может быть преобразована в DFA, который распознает пересечение. Если есть путь от состояния начала до любого принимающего состояния этого окончательного DFA, пересечение непустое («конфликт», используя вашу терминологию).

К сожалению, существует, возможно, экспоненциальная раздутие при преобразовании исходной NFA в DFA, поэтому проблема на практике становится практически невозможной, поскольку размер входных выражений возрастает.

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

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

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

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

Другой подход заключается в том, чтобы вместо этого использовать Perl Regexp :: Optimizer [GG] Дэн Когай.

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

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

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