Inconsistencia entre las expresiones regulares de sed y python

Question

Me disculpo si esto se publica en alguna parte, pero mi búsqueda superficial no encontró nada.

Mientras que hace un poco de programación Python me di cuenta de que el siguiente comando:

re.sub("a*((ab)*)b", r"\1", "aabb") 

devuelve la cadena vacía. Pero un comando equivalente en sed:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/" 

devuelve ab.

Tiene sentido para mí que la directiva "a *" al comienzo de la expresión regular de python coincida con a, haciendo que "(ab) *" coincida cero veces, pero no tengo idea de cómo viene sed con ab. ¿Alguien sabe cuál es la diferencia entre los dos motores de expresiones regulares que causa esto? Creo que ambos combinan las estrellas codiciosamente de forma predeterminada, pero se me ocurrió que sed podría coincidir desde la derecha en lugar de la izquierda. Cualquier idea sería muy apreciada.

Answer 1

Rompecabezas interesante que has construido. Según lo que he leído, los motores de expresiones regulares de python y sed están basados ​​en la biblioteca de expresiones regulares de Henry Spencer (como la de perl), que se basa en el rastreo.(Desafortunadamente no puedo encontrar el artículo en el que estoy basando esto).

De todos modos, esto es no algo que se supone que es un detalle de implementación: el comportamiento de Python va en contra del estándar POSIX, lo que requiere RE para (a) coinciden en el punto más temprana posible, y (b) que coincida con la mayor longitud posible cadena que comienza en ese punto. (Consulte man 7 regex (en Linux) para esto y mucho más.)

Para encontrar la coincidencia más larga, un motor de expresiones retrospectivas ("NFA-type") debe seguir examinando alternativas después de encontrar una coincidencia. Entonces, no es sorprendente que los implementadores reduzcan las esquinas. Obviamente, el comportamiento de Python no es conforme, ya que no puede encontrar la coincidencia más larga. De acuerdo con la página de manual de sed, sed no siempre se ajusta, "por razones de rendimiento". Pero, obviamente, este caso es correcto.

Por cierto, los comandos no son totalmente equivalentes: re.sub llevará a cabo un cambio tantas veces como sea posible, mientras sed de s/a/b/ sólo se llevará a cabo la versión que once.The sed debería haber sido:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/g" 

Esto explica por qué obtenemos la cadena vacía en python: la RE coincide con aab la primera vez y la b restante la segunda vez, eliminando cada parte (ya que todo coincide con a* y la final de la expresión regular). Esto se puede ver por la siguiente variante:

>>> re.sub("a*((ab)*)b", r"X\1Y", "aabb") 
'XYXY' 

Answer 2

Python y sed son codiciosos por defecto, pero ... Python regex intenta evaluar de izquierda a derecha en todas las circunstancias, a pesar de que debe hacer una traza inversa al estado anterior si la rama que se intenta no puede continuar haciendo coincidir Sed regex, por el contrario, se optimizan antes de la evaluación con el fin de evitar una traza inversa innecesaria, mediante la reescritura de la expresión regular a una forma más determinista. Por lo tanto, el patrón opcional combinado "aab" probablemente se pruebe antes que la "a" simple porque se intenta primero la cadena más específica posible.

patrón Python coincide con el "aabb" cadena dos veces como "aab" "b" + (marcada entre "< >")

>>> re.sub("a*((ab)*)b", r"<\1>", "aabb") 
'<><>' 

mientras sed partidos todo el "aabb" por una sustitución:

$ echo "aabb" | sed "s/a*\(\(ab\)*\)b/<\1>/" 
<ab> 

El algoritmo de retroceso de Pyge regex se explica bien en regex howto - Repeating Things en dos párrafos introducidos por las palabras "Un ejemplo paso a paso ...". Hace IMO exactamente lo que se describe regex docs: "A medida que se explora la cadena objetivo, las RE se separan por '|' se intentan de izquierda a derecha. "

Demostración

El orden de "(| a | bis)" por cierto. "(AA | a |)" es respetado por Python

>>> re.sub("(?:|a|aa)((ab)*)b", r"<\1>", "aabb") 
'<ab>' 
>>> re.sub("(?:aa|a|)((ab)*)b", r"<\1>", "aabb") 
'<><>' 

pero esta orden es ignorado por sed dado que sed optimiza expresiones regulares. La coincidencia de "aab" + "b" se puede reproducir eliminando la opción "a" del patrón.

$ echo "aabb" | sed "s/\(\|a\|aa\)\(\(ab\)*\)b/<\2>/g" 
<ab> 
$ echo "aabb" | sed "s/\(aa\|a\|\)\(\(ab\)*\)b/<\2>/g" 
<ab> 
$ echo "aabb" | sed "s/\(aa\|\)\(\(ab\)*\)b/<\2>/g" 
<><> 

---

Editar: Me eliminado todo sobre DFA/NFA porque no puedo demostrarlo a partir de textos actuales.