¿Cómo saber si una expresión regular coincide con un subconjunto de otra expresión regular?

Solo me pregunto si es posible usar una expresión regular para que coincida con otra, es una especie de:

['a-z'].match(['b-x']) True ['m-n'].match(['0-9']) False 

¿Es este tipo de cosas posibles con expresiones regulares en absoluto? Estoy trabajando en Python, por lo que cualquier consejo específico para la implementación del módulo re ayudaría, pero tomaré cualquier cosa que pueda obtener respecto a la expresión regular.

Edit: Ok, algunas aclaraciones obviamente están en orden! Definitivamente sé que la syntax de concordancia normal se vería así:

 expr = re.compile(r'[az]*') string = "some words" expr.match(string)  

pero me pregunto si las expresiones regulares tienen la capacidad de coincidir con otras expresiones menos específicas en la versión no sintácticamente correcta que intenté explicar anteriormente, cualquier letra de bx siempre será un subconjunto (coincidencia) de cualquier letra de az. Sé que solo por intentar esto no es algo que pueda hacer simplemente llamando a la concordancia de una expresión comstackda en otra expresión comstackda, pero la pregunta sigue siendo: ¿es esto posible?

Déjame saber si esto todavía no está claro.

Creo que, en teoría, para determinar si regexp A coincide con un subconjunto de lo que regexp B coincide, un algoritmo podría:

  1. Calcule la Automatización Finita Determinista mínima de B y también de la “unión” A|B
  2. Compruebe si los dos DFA son idénticos. Esto es cierto si y solo si A coincide con un subconjunto de lo que B coincide.

Sin embargo, es probable que sea un proyecto importante para hacer esto en la práctica. Hay explicaciones como Construir un DFA de estado mínimo a partir de una expresión regular, pero solo tienden a considerar expresiones regulares matemáticamente puras. También deberías manejar las extensiones que Python agrega para mayor comodidad. Además, si alguna de las extensiones hace que el lenguaje no sea regular (no estoy seguro de que sea así), es posible que no pueda manejarlas.

Pero, ¿qué estás tratando de hacer? Tal vez hay un enfoque más fácil …?

Además de la respuesta de antinome :

Muchas de las construcciones que no forman parte de la definición básica de expresiones regulares son aún regulares y se pueden convertir después de analizar la expresión regular (con un analizador real, porque el lenguaje de expresiones regulares no es el mismo): (x?) (x|) , (x+) a (xx*) , clases de caracteres como [ad] a su unión correspondiente (a|b|c|d) etc. Así que uno puede usar estas construcciones y aún probar si una expresión regular coincide con un subconjunto de la otra expresiones regulares utilizando la comparación DFA mencionada por antinome.

Algunas construcciones, como las referencias anteriores, no son regulares y no pueden representarse por NFA o DFA.

Incluso el problema aparentemente simple de probar si una expresión regular con referencias anteriores coincide con una cadena en particular es NP-complete ( http://perl.plover.com/NPC/NPC-3COL.html ).

Verificación de la publicación por “antinome” usando dos regex: 55 * y 5 *:

REGEX_A: 55 * [Esto coincide con “5”, “55”, “555” etc. y NO coincide con “4”, “54” etc.]

REGEX_B: 5 * [Esto coincide con “”, “5” “55”, “555” etc. y NO coincide con “4”, “54” etc.]

[Aquí hemos asumido que 55 * no es implícitamente. 55. * Y 5 * no lo es. 5. * – Esta es la razón por la que 5 * no coincide con 4]

REGEX_A puede tener una NFA de la siguiente manera:

  {A}--5-->{B}--epsilon-->{C}--5-->{D}--epsilon-->{E} {B} -----------------epsilon --------> {E} {C} <--- epsilon ------ {E} 

REGEX_B puede tener una NFA de la siguiente manera:

  {A}--epsilon-->{B}--5-->{C}--epsilon-->{D} {A} --------------epsilon -----------> {D} {B} <--- epsilon ------ {D} 

Ahora podemos derivar NFA * DFA de (REGEX_A | REGEX_B) de la siguiente manera:

  NFA: {state A} ---epsilon --> {state B} ---5--> {state C} ---5--> {state D} {state C} ---epsilon --> {state D} {state C} <---epsilon -- {state D} {state A} ---epsilon --> {state E} ---5--> {state F} {state E} ---epsilon --> {state F} {state E} <---epsilon -- {state F} NFA -> DFA: | 5 | epsilon* ----+--------------+-------- A | B,C,E,F,G | A,C,E,F B | C,D,E,F | B,C,E,F c | C,D,E,F | C D | C,D,E,F,G | C,D,E,F E | C,D,E,F,G | C,E,F F | C,E,F,G | F G | C,D,E,G | C,E,F,G 5(epsilon*) -------------+--------------------- A | B,C,E,F,GB,C,E,F,G | C,D,E,F,GC,D,E,F,G | C,D,E,F,G Finally the DFA for (REGEX_A|REGEX_B) is: {A}--5--->{B,C,E,F,G}--5--->{C,D,E,F,G} {C,D,E,F,G}---5--> {C,D,E,F,G} Note: {A} is start state and {C,D,E,F,G} is accepting state. 

De manera similar, DFA para REGEX_A (55 *) es:

  | 5 | epsilon* ----+--------+-------- A | B,C,E | A B | C,D,E | B,C,E C | C,D,E | C D | C,D,E | C,D,E E | C,D,E | C,E 5(epsilon*) -------+--------------------- A | B,C,EB,C,E | C,D,E C,D,E | C,D,E {A} ---- 5 -----> {B,C,E}--5--->{C,D,E} {C,D,E}--5--->{C,D,E} Note: {A} is start state and {C,D,E} is accepting state 

De manera similar, DFA para REGEX_B (5 *) es:

  | 5 | epsilon* ----+--------+-------- A | B,C,D | A,B,D B | B,C,D | B C | B,C,D | B,C,D D | B,C,D | B,D 5(epsilon*) -------+--------------------- A | B,C,DB,C,D | B,C,D {A} ---- 5 -----> {B,C,D} {B,C,D} --- 5 ---> {B,C,D} Note: {A} is start state and {B,C,D} is accepting state 

Conclusiones:

 DFA of REGX_A|REGX_B identical to DFA of REGX_A -- implies REGEX_A is subset of REGEX_B DFA of REGX_A|REGX_B is NOT identical to DFA of REGX_B -- cannot infer about either gerexes. 

Deberías hacer algo en este sentido:

 re.match("\[[bx]-[bx]\]", "[az]") 

La expresión regular tiene que definir cómo debe ser la cadena. Si desea hacer coincidir un corchete de apertura seguido de una letra de b a x, luego un guión, luego otra letra de b a x y finalmente un corchete de cierre, la solución anterior debería funcionar.

Si pretende validar que una expresión regular es correcta, debería considerar probar si se comstack en su lugar.

Es posible con la representación de cadena de una expresión regular, ya que cualquier cadena puede coincidir con expresiones regulares, pero no con la versión comstackda devuelta por re.compile . Sin embargo, no veo qué uso sería. Además, toma una syntax diferente.

Edición : parece que estás buscando la capacidad de detectar si el lenguaje definido por una RE es un subconjunto de otras RE. Sí, creo que es posible, pero no, el módulo de re de Python no lo hace.

 pip3 install https://github.com/leafstorm/lexington/archive/master.zip python3 >>> from lexington.regex import Regex as R >>> from lexington.regex import Null >>> from functools import reduce >>> from string import ascii_lowercase, digits >>> a_z = reduce(lambda a, b: a | R(b), ascii_lowercase, Null) >>> b_x = reduce(lambda a, b: a | R(b), ascii_lowercase[1:-2], Null) >>> a_z | b_x == a_z True >>> m_n = R("m") | R("n") >>> zero_nine = reduce(lambda a, b: a | R(b), digits, Null) >>> m_n | zero_nine == m_n False 

También se probó con éxito con Python 2. Vea también cómo hacerlo con una biblioteca diferente .

Alternativamente, pip3 install https://github.com/ferno/greenery/archive/master.zip y:

 from greenery.lego import parse as p a_z = p("[az]") b_x = p("[bx]") assert a_z | b_x == a_z m_n = p("m|n") zero_nine = p("[0-9]") assert not m_n | zero_nine == m_n 

Se requiere alguna aclaración, creo:

.

 rA = re.compile('(? 

'(? es un patrón

rA es una instancia de la clase RegexObject cuyo tipo es < * type '_sre.SRE_Pattern'> * .

Personalmente, uso el término regex exclusivamente para este tipo de objetos, no para el patrón.

Tenga en cuenta que rB = re.compile(rA) también es posible, produce el mismo objeto (id (rA) == id (rB) es igual a True)


 ch = 'lshdgbfcs luyt52uir bqisuytfqr454' x = rA.match(ch) # or y = rA.search(ch) 

x e y son instancias de la clase MatchObject cuyo tipo es * *


.

Dicho esto, desea saber si hay una manera de determinar si un regex rA puede coincidir con todas las cadenas coincidentes con otro regex rB, mientras que rB coincide solo con una subsesta de todas las cadenas coincidentes con rA.

No creo que exista tal manera, sea lo que sea teóricamente o prácticamente.