Тестирование регекспов на совместимость

Сомневаюсь :) imho это тема для диссертации. Погугли на предмет regular expressions intersection

> такая задача -- есть два регекспа, для начала basic regexps. Нужно уметь проверять совместны ли они, то есть существует ли строка которая удовлетворяет им обоим.

Какая прелесть! Можно мне спереть задачу для своего клуба? Супер! Откуда задачка?

> Можно мне спереть задачу для своего клуба?

школьников мучать?

> Откуда задачка?

из индустрии:)

Есть база правил вида условие->действие.

Условие это булевская комбинация из примарных условий. Примарное условие это тест значения некого параметра, например тест на то матчится ли оно регулярным выражением.

На этапе компиляции эта база преобразуется в перловый код, который должен выполнить все действия для которых условие истинно.

Неоптимизированная форма просто проходит список всех условий, вычисляет их и если условие верно, то выполняет действие.

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

Поэтому можно генерировать древовидный код.

А сабжевая задача нужна вот для чего -- если мы знаем например что регекспы несовместны, то истинность одного выражения влечет ложность другого и код оптимизируется.

> школьников мучать?

Нет, профи-хакеров мучить :)

А так интересно. Но вот тоже в голову сходу ничего не приходит. Хочется чего-то элегантного для решения.

> Один из подходов -- это заметить что многие встречающиеся примарные
> условия связаны, т,е, знание результата одного условия влечет знание
> результата некоторых других.
Регексп это же программа, конечный автомат. Как можно посчитать результат программы, не выполняя программу? Разве что строить автомат и анализировать полученные графы на предмет похожести. Или тупо перебирать все входы.

> Нужно уметь проверять совместны ли они, то есть существует ли строка
> которая удовлетворяет им обоим. Есть какие-то стандартные алгоритмы?
DFS? Если для упрощения принять что регексп проверяет что-нибудь вроде ^..$, то DFS очевиден. Наверное все алгоритмы будут вариациями DFS. Хотя интересно может конкретно для этой узкоспециализированной задачи существует динамический алгоритм?

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

> По регэкспу несложно строится конечный автомат; для двух автоматов
> несложно построить их произведение.
Как, если не секрет, построить?

Сначала строишь недетерминированный автомат (из каждого состояния могут быть несколько переходов по одному и тому же входу; кроме того, могут быть переходы БЕЗ входа). Строится напрямую по регэкспу: ну, например, так:

1) обычный символ -> автомат с двумя состояниями, первое - начальное, второе - конечное; единственный переход по входу, совпадающему с данным символом, из первого состояния во второе. 2) альтернатива (R1|R2) - строишь автоматы по R1 и R2; затем добавляешь новое начальное состояние, откуда делаешь переходы без входа в начальные состояния R1 и R2; аналогично добавляешь новое конечное состояние. 3) Повторение R+ (заметь: повторение хотя бы один раз) - строишь автомат по R, затем добавляешь переход без входа из конечного состояния в начальное.

Остальное собирается из этих кирпичей; кое-где можно пооптимизировать.

Далее, можно из НКА сделать ДКА (детерминированный), а можно работать и с НКА: по регэкспам R1 и R2 делаешь автоматы A1 и A2, затем собираешь автомат A, состояния которого - пары (s1,s2), s1 - состояние A1, s2 - состояние A2; переход из (s1,s2) в (s1',s2') по входу 'c' имеется тогда и только тогда, когда есть переход из s1 в s1' и переход из s2 в s2' по этому же входу; аналогично - переходы без входа. Начальное и конечное состояния A сам сообразишь.

Ну и, далее, надо посмотреть, какие состояния вообще в принципе достижимы из начального. Если конечное среди них есть - ура, регэкспы совместимы; если нет - увы.

> по регэкспам R1 и R2 делаешь автоматы A1 и A2, затем собираешь автомат
> A, состояния которого - пары (s1,s2), s1 - состояние A1, s2 -
> состояние A2; переход из (s1,s2) в (s1',s2') по входу 'c' имеется
> тогда и только тогда, когда есть переход из s1 в s1' и переход из s2 в
> s2' по этому же входу; аналогично - переходы без входа.
А.. Объединяешь состояния.. То есть для двух автоматов каждый с N состояниями, в результате выйдет автомат с 2^N состяниями или что-то вроде того?

N*N то есть..

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

Угу.

> Может, я не совсем понял задачу, но ведь любой регексп можно разложить
> на элементарные подмножества символов, после чего, натравить на
> получившуюся строку второй регексп. Если прошло - значит такая строка > существует.
А на что ты хочешь натравить второй регексп если первый это например [a-z]*?