检测两个正则表达式是否可能匹配相同的字符串

发布时间：2020-12-13 21:53:37 所属栏目：百科来源：网络整理

导读：参见英文答案 Regex: Determine if two regular expressions could match for the same input?5个给定两个正则表达式,是否可以检测是否存在与它们匹配的任何可能的字符串？例如,给定正则表达式A和.,我可以看到字符串“A”与它们相匹配.这是一个简单的案例.

参见英文答案 > Regex: Determine if two regular expressions could match for the same input?5个
给定两个正则表达式,是否可以检测是否存在与它们匹配的任何可能的字符串？

例如,给定正则表达式A和.,我可以看到字符串“A”与它们相匹配.这是一个简单的案例.

我的问题是针对更广泛的情况 – 给定任何两个有效的正则表达式,是否有可能明确地说是否有任何可能的字符串与两个正则表达式相匹配？假设没有要测试的输入字符串样本集.我只有正则表达式.我不一定需要生成匹配的字符串 – 我只需要确定有可能的字符串匹配两者.

将接受任何常见正则表达式规范的讨论 – .NET,Java,PERL,sed,grep等.

基本上,您想测试两个RegExps的交集是否为非空.由于交叉 – 就像补码一样 – 是一种潜在的昂贵操作(它需要确定NFA),因此在许多RegExp实现中并未实现.我所知道的一个例外是 BRICS Automaton Library,它允许启用交叉点运算符和.

要测试有问题的属性,可以像这样使用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));
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!