两个正则表达式的交点

本文介绍了两个正则表达式的交点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

Im looking for function (PHP will be the best), which returns true whether exists string matches both regexpA and regexpB.

示例1:

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

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

hasRegularsIntersection($regexpA,$regexpB) returns TRUE because '12' matches both regexps

示例2:

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

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

hasRegularsIntersection($regexpA,$regexpB) returns FALSE because numbers never matches literals.

感谢您提供解决此问题的建议.

Thanks for any suggestions how to solve this.

亨利

推荐答案

对于实际上是正则表达式的正则表达式(即，不要使用反向引用之类的不规则功能)，您可以执行以下操作:

For regular expressions that are actually regular (i.e. don't use irregular features like back references) you can do the following:

将regexen转换为有限自动机(可以在此处找到该算法(例如第9章).

构建自动机的交集(在两个自动机的状态的笛卡尔积中，每个状态都有一个状态.然后根据原始自动机的转换规则在状态之间进行转换.例如，如果处于状态x1y2，得到输入a，第一个自动机对输入x具有过渡x1-> x4，第二个自动机具有y2-> y3，过渡到状态x4y3).

检查新自动机中是否存在从开始状态到结束状态的路径.如果存在，则两个regexen相交，否则不相交.

Transform the regexen into finite automata (the algorithm for that can be found here(chapter 9) for example).

Build the intersection of the automata (You have a state for each state in the cartesian product of the states of the two automata. You then transition between the states according to the original automata's transition rules. E.g. if you're in state x1y2, you get the input a, the first automaton has a transition x1->x4 for input x and the second automaton has y2->y3, you transition into the state x4y3).

Check whether there's a path from the start state to the end state in the new automaton. If there is, the two regexen intersect, otherwise they don't.