两个正则表达式的交集

Question

我正在寻找功能(PHP将是最好的),无论是否存在字符串匹配regexpA和regexpB,它都返回true.

例1:

$regexpA = '[0-9]+';
$regexpB = '[0-9]{2,3}';

hasRegularsIntersection($regexpA,$regexpB)返回TRUE因为'12'匹配两个正则表达式

例2:

$regexpA = '[0-9]+';
$regexpB = '[a-z]+';

hasRegularsIntersection($regexpA,$regexpB) 返回FALSE,因为数字永远不会与文字匹配.

感谢您提出如何解决此问题的任何建议.

亨利

Answer 1

对于实际上是常规的正则表达式(即不使用后向引用等不规则的功能),您可以执行以下操作:

1. 将regexen转换为有限自动机(例如,可以在此处找到算法(第9章)).
2. 构建自动机的交集(你在两个自动机状态的笛卡尔积中得到每个状态的状态.然后根据原始自动机的转换规则在状态之间转换.例如,如果你处于状态x1y2,你得到输入a,第一个自动机对输入x有一个转换x1-> x4,第二个自动机有y2-> y3,你转换到状态x4y3).
3. 检查新自动机中是否存在从开始状态到结束状态的路径.如果存在,则两个正则相交,否则它们不相交.

Answer 2

有可能的。我在学习语义网络技术时使用 Pellet OWL Reasoner 遇到过一次。

下面是一个示例，展示了如何将正则表达式解析为树结构。然后，您可以（理论上）将两个正则表达式解析为树，并查看一棵树是否是另一棵树的子集，即。如果可以在其他树的节点中找到一棵树。

如果找到，则另一个正则表达式将匹配（不仅是）第一个正则表达式将匹配的子集。

这不是一个解决方案，但也许会对您有所帮助。