生成正则表达式
通常在我们的工作中,我们使用正则表达式捕获或匹配操作。
但是,可以使用正则表达式(至少手动)来生成与正则表达式匹配的法律句子。 当然,一些正则表达式可以匹配无限长的句子,例如表达式.+
。
我有一个问题可以通过使用正则表达式句子生成算法来解决。
在伪代码中,它会像这样操作:
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];
根据需要调整时间和样本大小。 希望这可以帮助!
看看Xeger(谷歌代码)。
Visual Studio Team System似乎也有一个逆向正则表达式生成器,但它看起来并不像算法是开源的。
链接地址: http://www.djcxy.com/p/3647.html上一篇: Generative regular expressions
下一篇: How to determine whether a web application is currently running