php - 两个正则表达式的交集

Question

我正在寻找函数(PHP 将是最好的)，它返回 true 是否存在字符串匹配 regexpA 和 regexpB。

示例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. 将正则表达式转换为有限自动机(例如，可以在here(第 9 章)中找到该算法)。
2. 构建自动机的交集(两个自动机状态的笛卡尔积中的每个状态都有一个状态。然后，根据原始自动机的转换规则在状态之间进行转换。例如，如果您处于状态x1y2，您得到输入 a，第一个自动机对于输入 x 有一个转换 x1->x4，第二个自动机有 y2->y3，您转换到状态 x4y3)。
3. 检查新自动机中是否存在从开始状态到结束状态的路径。如果存在，则两个正则表达式相交，否则不相交。