通常在我们的工作中我们会使用正则表达式capture or match运营。
但是,可以使用正则表达式(至少手动)来生成与正则表达式匹配的合法句子。当然,有些正则表达式可以匹配无限长的句子,例如表达式.+
.
我有一个问题可以通过使用正则表达式句子生成算法来解决。
在伪代码中,它的操作如下:
re = generate("foo(bar|baz)?", max_match = 100); #Don't give me more than 100 results
assert re == ("foobar", "foobaz", "foo");
什么算法可以为我执行此操作?
Microsoft 为此提供了基于 SMT 的免费(MSRL 许可)“Rex”工具:http://research.microsoft.com/en-us/downloads/7f1d87be-f6d9-495d-a699-f12599cea030/
来自“Rex:符号正则表达式浏览器”论文的简介部分:
我们将(扩展)正则表达式或正则表达式 [5] 转换为称为 SFA 的有限自动机的符号表示。在 SFA 中,移动由表示字符集而不是单个字符的公式来标记。 SFA A 被转换为一组(递归)公理,描述 A 接受的字符串的接受条件,并建立在字符串表示为列表的基础上。
由于 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];
根据需要调整时间和样本量。希望这可以帮助!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)