regex - 生成正则表达式

Question

通常在我们的工作中，我们在捕获或匹配操作中使用正则表达式。

但是，可以使用正则表达式(至少手动)来生成与正则表达式匹配的合法句子。当然，有些正则表达式可以匹配无限长的句子，例如表达式 .+ .

我有一个问题可以通过使用正则表达式句子生成算法来解决。

在伪代码中，它会像这样运行:

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

什么算法会为我执行此操作？

Answer 1

微软为此提供了一个基于 SMT 的免费(MSRL 许可)“Rex”工具:http://research.microsoft.com/en-us/downloads/7f1d87be-f6d9-495d-a699-f12599cea030/

从“Rex:符号正则表达式资源管理器”论文的介绍部分:

We translate (extended) regular expressions or regexes [5] into a symbolic representation of finite automata called SFAs. In an SFA, moves are labeled by formulas representing sets of characters rather than individual characters. An SFA A is translated into a set of (recursive) axioms that describe the acceptance condition for the strings accepted by A and build on the representation of strings as lists.

由于 SMT 求解器可以在一定大小范围内输出所有可能的解决方案，因此这可能与您正在寻找的结果相近。

在更统计和不太正式的方面，CPAN 的 Regexp::Genex 模块也可以工作: 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];

根据需要调整时间和样本大小。希望这可以帮助!