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

Question

В частности, существует ли библиотека, которая при наличии двух (или более) регулярных выражений может определить, существует ли ввод, которому оба будут соответствовать?Бонусные баллы, если к нему легко получить доступ через 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

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

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

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

Answer 3

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

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

И реализация прологаhttp://www.let.rug.nl/vannoord/Fsa/

Answer 4

Это может быть отправной точкой.

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