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

Question

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

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

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

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

Answer 1

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

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

• http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

И еще есть RAGEL

• http://www.complang.org/ragel/

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

ОБНОВЛЕНИЕ: Я только что опробовал Ragel с регулярным выражением OP.Ragel может генерировать «точечный» файл для graphviz из конечного автомата, который является потрясающим.Пересечение регулярного выражения OP выглядит следующим образом в синтаксисе Ragel:

('xy1' digit any*) & (any* ^digit digit '2') 

и имеет следующий конечный автомат:

В то время как пустое пересечение:

('xy1' digit any*) & ('q' any* ^digit digit '2')

выглядит так:

Так что если все остальное терпит неудачу тогда вы все равно можете заставить Ragel вычислить пересечение и проверить, выводит ли он пустой конечный автомат, сравнивая сгенерированный файл "точка".

Answer 2

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

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

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

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

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

Answer 3

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

Пусть [R] будет набором строк, сгенерированных регулярным выражением R. Затем, учитывая регулярные выражения R и T, мы можем попытаться сопоставить T с [R]. То есть [R] соответствует T, если в [R] есть строка, соответствующая T.

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

Answer 4

Если вы ищете библиотеку в 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));
    }

Оригинальный ответ:

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

Answer 5

Другой подход - использовать Perl Regexp :: Optimizer Дэна Когая.

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

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

Может быть, Regexp :: Assemble Рона Сэвиджа может быть даже более полезным. Это позволяет собирать произвольное количество регулярных выражений в одно регулярное выражение, которое соответствует всем, что совпадают отдельные RE. * Или комбинация обоих.

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