php - 正则表达式碰撞检测

Question

假设两个正则表达式 e1 和 e2 碰撞 如果存在任何字符串 s，这样e1 和 e2 都匹配 s。

有没有简单(有效)的方法来检查两个正则表达式是否冲突，而无需遍历字典中所有可能字符串的集合？

注1:我不知道在文献中是否以其他方式调用它。也许我只是缺少合适的名称来搜索它。

注意 2: 对我来说理想的答案是编写 PHP 代码，但我接受任何建议，不一定是 PHP。

Answer 1

所以，经过进一步研究，这似乎是文献中称为正则表达式交集。

这是可能的，显然也不难实现，但似乎没有正式的 PHP 支持。

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

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();
}