php – 正则表达式碰撞检测

发布时间：2020-12-13 22:53:55 所属栏目：PHP教程来源：网络整理

导读：假设存在任何字符串s,则两个正则表达式e1和e2碰撞,使得e1和e2都匹配s. 是否有任何简单(有效)的方法来检查两个正则表达式是否发生碰撞而不迭代我们字典中所有可能字符串的集合？注1：我不知道是否在文献中以其他方式调用了这个.也许我只是缺少正确的名称来搜

假设存在任何字符串s,则两个正则表达式e1和e2碰撞,使得e1和e2都匹配s.

是否有任何简单(有效)的方法来检查两个正则表达式是否发生碰撞而不迭代我们字典中所有可能字符串的集合？

注1：我不知道是否在文献中以其他方式调用了这个.也许我只是缺少正确的名称来搜索它.

注2：对我来说理想的答案是编写PHP代码,但我接受任何建议,不一定是PHP.

解决方法

因此,经过进一步研究,看起来这在文献中被称为正则表达式交集.

这是可能的,显然它并不难实现,但似乎没有正式的PHP支持.

实现easy算法的关键在于将正则表达式转换为有限自动机.阅读附加链接以更好地理解解决方案.

Stackoverflow相关问题：

Intersection of two regular expressions

Calculate if two infinite regex solution sets don’t intersect

PHP的非官方库：

https://github.com/KendallHopkins/FormalTheory

编辑：添加代码片段以使用Kendall Hopkins库检查交叉点：

function doRegexIntersection($regex_string_1,$regex_string_2) {
    $lexer = new FormalTheory_RegularExpression_Lexer();
    $nfa1 = $lexer->lex( $regex_string_1 )->getNFA();
    $nfa2 = $lexer->lex( $regex_string_2 )->getNFA();
    return FormalTheory_FiniteAutomata::intersection( $nfa1,$nfa2 )->validSolutionExists();
}

（编辑：李大同）

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