给定两个正则表达式,是否可以检测是否存在与它们都匹配的可能字符串?
例如,给定正则表达式A
and .
,我可以看到那个字符串"A"
匹配他们两个。这是一个简单的案例。
我的问题是针对更广泛的情况 - 给定任何两个有效的正则表达式,是否可以明确地说是否有任何可能的字符串与这两个正则表达式匹配?假设没有要测试的输入字符串样本集。我所拥有的只是正则表达式。我不一定需要生成匹配的字符串——我只需要确定是否存在可能与两者匹配的字符串。
将接受任何常见正则表达式规范的讨论——.NET、Java、PERL、sed、grep 等。
基本上,您想测试是否路口两个正则表达式的非空。由于交集(就像补码一样)是一种潜在昂贵的操作(它需要 NFA 的确定),因此在许多 RegExp 实现中并未实现它。我知道的一个例外是金砖国家自动机图书馆 http://www.brics.dk/automaton,它允许启用交集运算符&
.
要测试相关属性,您可以使用 BRICS (Java) 库,如下所示:
RegExp re = new RegExp("(.) & (a)", RegExp.INTERSECTION); // Parse RegExp
Automaton a = re.toAutomaton(); // convert RegExp to automaton
if(a.isEmpty()) { // Test if intersection is empty
System.out.println("Intersection is empty!");
}
else {
// Print the shortest accepted string
System.out.println("Intersection is non-empty, example: " + a.getShortestExample(true));
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)