Есть ли библиотека, которая обеспечивает статический анализ регулярных выражений?

Question

В частности, существует ли библиотека, которая при задании 2 (или более) регулярных выражений может определить, существует ли входное значение, которое будет соответствовать обоим? Бонусные баллы, если он легко доступен через Java или .NET, но с командной строкой тоже все будет в порядке.

Лог Аскера, дополнительно:

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

Answer 1

Я нашел библиотеку Python, которая позволяет мне делать то, что мне нужно.

>>> import reCompiler
>>> fsa1 = reCompiler.compileRE('\d\d\d?\d?a')
>>> fsa2 = reCompiler.compileRE('123a')
>>> fsa3 = reCompiler.compileRE('a23a')
>>> print len(FSA.intersection(fsa1, fsa2).finalStates)
1
>>> print len(FSA.intersection(fsa1, fsa3).finalStates)
0

Библиотека называется pyFSA . Мне нужно будет выполнить некоторые подготовительные операции, чтобы превратить операторы типа \ d {2,4} в \ d \ d \ d? \ D?, Но в остальном это должно хорошо соответствовать моим потребностям. Спасибо за вклад, и если люди находят библиотеки, которые реализуют это на других языках, обязательно включайте их.

Answer 2

Если, я вас правильно понимаю, вы хотели бы знать, является ли пересечение 2 регулярных выражений пустым множеством или нет? Я считаю, что это сложно, но я не удивлюсь, если бы сложность была экспоненциальной по длине регулярного выражения (хотя некоторые регулярные выражения были бы явно проще, чем другие)

В любом случае, вот реализация на Haskell: http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

И внедрение пролога http://www.let.rug.nl/vannoord/Fsa/

Answer 3

Если бы он был, он бы не работал в течение полезного времени. Сравнение регулярных выражений - это проблема PSPACE

http://en.wikipedia.org/wiki/PSPACE-complete

Возможно, вам повезет, если вы разрешите дополнительные ограничения для своего регулярного выражения

Answer 4

Это может быть место для начала.

http://kedrigern.dcs.fmph.uniba.sk/~riso/papers/KraPhD.pdf