Генеративные регулярные выражения

Question

Обычно в нашей работе мы используем регулярные выражения в операциях capture или match .

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

У меня есть проблема, которую можно решить с помощью алгоритма генерации предложений регулярного выражения.

В псевдокоде он будет работать примерно так:

re = generate("foo(bar|baz)?", max_match = 100);  #Don't give me more than 100 results
assert re == ("foobar", "foobaz", "foo");

Какой алгоритм будет выполнять это для меня?

Answer 1

Корпорация Майкрософт имеет бесплатный инструмент «Rex» на основе SMT (лицензированный MSRL) для этого: http://research.microsoft.com/en-us/downloads/7f1d87be-f6d9-495d-a699-f12599cea030/

Из раздела «Введение» статьи «Rex: проводник символьных регулярных выражений»:

Мы переводим (расширенные) регулярные выражения или регулярные выражения [5] в символическое представление конечных автоматов, называемое SFA. В SFA ходы помечаются формулами, представляющими наборы символов, а не отдельные символы. SFA A переводится в набор (рекурсивных) аксиом, которые описывают условие принятия для строк, принятых A, и основаны на представлении строк в виде списков.

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

В более статистическом и менее формальном аспекте модуль Regexp :: Genex из CPAN также может работать: http://search.cpan.org/dist/Regexp-Genex/

Вы можете использовать его с чем-то вроде этого:

#!/usr/bin/env perl
use Regexp::Genex ':all';
my $hits = 100;
my $re = qr/[a-z](123|456)/;
local $Regexp::Genex::DEFAULT_LEN = length $re;
my %seen;
while ((time - $^T) < 2) {
    @seen{strings($re)} = ();
    $Regexp::Genex::DEFAULT_LEN++;
}
print "$_\n" for (sort %seen)[0..$hits-1];

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

Answer 2

Взгляните на Xeger (Google Code) .

В Visual Studio Team System, похоже, также есть генератор обратных выражений , но не похоже, что алгоритм имеет открытый исходный код.