expressions - expresiones regulares regex

¿Por qué los motores de expresiones regulares permiten/intentan automáticamente hacer coincidencias al final de la cadena de entrada? (6)

^Nota: ^{* Python se utiliza para ilustrar comportamientos, pero esta pregunta es agnóstica del lenguaje.} ^{* Para el propósito de esta discusión, supongamos que solo una entrada de una línea , porque la presencia de nuevas líneas (entrada de varias líneas) introduce variaciones en el comportamiento de $ y .} ^{que son incidentales a las preguntas en cuestión.}

La mayoría de los motores regex:

acepte una expresión regular que intente hacer coincidir explícitamente una expresión después del final de la cadena de entrada ^[1] .
$ python -c "import re; print(re.findall(''$.*'', ''a''))" [''''] # !! Matched the hypothetical empty string after the end of ''a''
al buscar / reemplazar globalmente , es decir, al buscar todas las coincidencias no superpuestas de una expresión regular dada y haber llegado al final de la cadena , intente coincidir nuevamente de nuevo ^[2] , como se explica en esta respuesta a una pregunta relacionada :
$ python -c "import re; print(re.findall(''.*$'', ''a''))" [''a'', ''''] # !! Matched both the full input AND the hypothetical empty string

Tal vez no sea necesario decirlo, tales intentos de coincidencia solo tienen éxito si la expresión regular en cuestión coincide con la cadena vacía (y la expresión regular de forma predeterminada / está configurada para informar coincidencias de longitud cero).

Estos comportamientos son, al menos a primera vista, contraintuitivos , y me pregunto si alguien puede proporcionarles una justificación de diseño , entre otras cosas porque:

No es obvio cuál es el beneficio de este comportamiento.
por el contrario, en el contexto de encontrar / reemplazar globalmente con patrones como .* y .*$ , el comportamiento es francamente sorprendente. ^[3]
- Para formular la pregunta de manera más precisa: ¿por qué la funcionalidad diseñada para encontrar múltiples coincidencias no superpuestas de una expresión regular (es decir, una coincidencia global ) decide incluso intentar otra coincidencia si sabe que ya se ha consumido toda la entrada , independientemente de cuál sea el resultado? la expresión regular es (aunque nunca verá el síntoma con una expresión regular que al menos no coincide con la cadena vacía)
- Los siguientes lenguajes / motores muestran un comportamiento sorprendente: .NET, Python (tanto 2.x como 3.x) ^[2] , Perl (tanto 5.x como 6.x), Ruby, Node.js (JavaScript)

Tenga en cuenta que los motores de expresiones regulares varían en el comportamiento con respecto a dónde continuar la coincidencia después de una coincidencia de longitud cero (cadena vacía).

Cualquiera de las dos opciones (comenzar en la misma posición del personaje frente a comenzar en la siguiente) es defendible: consulte el capítulo sobre coincidencias de longitud cero en www.regular-expressions.info .

Por el contrario, el caso .*$ Que se analiza aquí es diferente en que, con cualquier entrada no vacía, la primera coincidencia para .*$ No es una coincidencia de longitud cero, por lo que la diferencia de comportamiento no se aplica; en cambio, la posición del carácter Debería avanzar incondicionalmente después del primer partido, lo cual, por supuesto, es imposible si ya está al final.
Una vez más, mi sorpresa es el hecho de que se intenta otro emparejamiento, sin embargo, a pesar de que no queda nada por definición.

^{[1] Aquí estoy usando $ como marcador de final de entrada, aunque en algunos motores, como .NET, puede marcar el final del final de la entrada, opcionalmente seguido de una nueva línea final .} ^{Sin embargo, el comportamiento se aplica igualmente cuando se usa el marcador incondicional de fin de entrada, /z .}

^{[2] Python 2.xy 3.x hasta 3.6.x comportamiento de reemplazo aparentemente especial en este contexto: python -c "import re; print(re.sub(''.*$'', ''[/g<0>]'', ''a''))" utiliza para obtener solo [a] , es decir, solo se encontró y reemplazó una coincidencia.} ^{Desde Python 3.7, el comportamiento ahora es como en la mayoría de los otros motores de expresiones regulares, donde se realizan dos reemplazos, dando como resultado [a][] .}

^{[3] Puede evitar el problema ya sea (a) eligiendo un método de reemplazo diseñado para encontrar una coincidencia como máximo o (b) use ^.* Para evitar que se encuentren múltiples coincidencias a través del anclaje de inicio de entrada.} ^{(a) no puede ser una opción, según la forma en que un lenguaje determinado aparezca en la funcionalidad;} ^{por ejemplo, el operador de PowerShell reemplaza invariablemente todas las ocurrencias;} ^{Considere el siguiente intento de incluir todos los elementos de la matriz en "..." :} ^{''a'', ''b'' -replace ''.*'', ''"$&"'' .} ^{Debido al emparejamiento dos veces , esto produce los elementos "a""" y "b""" ;} ^{la opción (b), ''a'', ''b'' -replace ''^.*'', ''"$&"'' , soluciona el problema.}

"Vacío al final de la cadena" es una posición separada para los motores de expresiones regulares porque un motor de expresiones regulares se ocupa de las posiciones entre los caracteres de entrada:

|a|b|c| <- input line ^ ^ ^ ^ positions at which a regex engine can "currently be"

Todas las demás posiciones pueden describirse como "antes del carácter Nth" pero para el final, no hay ningún carácter al que referirse.

Según las coincidencias de expresiones regulares de longitud cero - Regular-expressions.info , también es necesario para las coincidencias de longitud cero (que no son compatibles con todas las versiones de expresiones regulares):

Por ejemplo, una expresión regular /d* sobre la cadena abc coincidiría 4 veces: antes de cada letra y al final.

Se permite $ en cualquier parte de la expresión regular por uniformidad: se trata igual que cualquier otra ficha y coincide en esa posición mágica de "final de cadena". Hacer que "finalice" el trabajo de expresión regular daría lugar a una inconsistencia innecesaria en el trabajo del motor y evitaría otras cosas útiles que pueden coincidir allí, como por ejemplo mirar detrás de /b (básicamente, cualquier cosa que pueda ser una coincidencia de longitud cero), es decir, Ser tanto una complicación de diseño como una limitación funcional sin beneficio alguno.

Finalmente, para responder por qué un motor de expresiones regulares puede o no intentar coincidir "de nuevo" en la misma posición, veamos Avance después de una coincidencia de expresiones regulares de longitud cero - Partidas de expresiones regulares de longitud cero - Regular-expressions.info :

Digamos que tenemos la expresión regular /d*|x , la cadena de asunto x1

La primera coincidencia es una coincidencia en blanco al comienzo de la cadena. Ahora, ¿cómo le damos una oportunidad a otros tokens mientras no nos atascamos en un bucle infinito?

La solución más simple, que es utilizada por la mayoría de los motores de expresiones regulares, es comenzar el siguiente intento de coincidencia con un carácter después del final de la coincidencia anterior

Esto puede dar resultados contraintuitivos, por ejemplo, la expresión regular anterior coincidirá con '''' al comienzo, 1 y '''' al final, pero no con x .

La otra solución, que utiliza Perl, es comenzar siempre el siguiente intento de coincidencia al final de la coincidencia anterior, independientemente de si fue de longitud cero o no. Si era de longitud cero, el motor toma nota de eso, ya que no debe permitir una coincidencia de longitud cero en la misma posición.

Que "salta" coincide menos a costa de una complejidad adicional. Por ejemplo, la expresión regular anterior producirá '''' , x , 1 y '''' al final.

El artículo continúa demostrando que no hay mejores prácticas establecidas aquí y varios motores de expresiones regulares están probando activamente nuevos enfoques para tratar de producir resultados más "naturales":

Una excepción es el motor JGsoft. El motor JGsoft avanza un carácter después de una coincidencia de longitud cero, como la mayoría de los motores. Pero tiene una regla adicional para omitir coincidencias de longitud cero en la posición donde terminó la coincidencia anterior, por lo que nunca puede tener una coincidencia de longitud cero inmediatamente adyacente a una coincidencia de longitud no cero. En nuestro ejemplo, el motor JGsoft solo encuentra dos coincidencias: la coincidencia de longitud cero al comienzo de la cadena, y 1.
Python 3.6 y avance previo después de coincidencias de longitud cero. La función gsub () para buscar y reemplazar salta coincidencias de longitud cero en la posición donde terminó la coincidencia de longitud no cero anterior, pero la función finditer () devuelve esas coincidencias. Por lo tanto, una búsqueda y reemplazo en Python da los mismos resultados que las aplicaciones de Just Great Software, pero al enumerar todas las coincidencias se agrega la coincidencia de longitud cero al final de la cadena.
Python 3.7 cambió todo esto. Maneja coincidencias de longitud cero como Perl. gsub () ahora reemplaza las coincidencias de longitud cero que son adyacentes a otra coincidencia. Esto significa que las expresiones regulares que pueden encontrar coincidencias de longitud cero no son compatibles entre Python 3.7 y versiones anteriores de Python.
PCRE 8.00 y posteriores y PCRE2 manejan coincidencias de longitud cero como Perl por retroceso. Ya no avanzan un carácter después de una comparación de longitud cero como solía hacer PCRE 7.9.
Las funciones de expresión regular en R y PHP se basan en PCRE, por lo que evitan quedarse atascadas en una coincidencia de longitud cero al realizar un seguimiento al igual que PCRE. Pero la función gsub () para buscar y reemplazar en R también omite coincidencias de longitud cero en la posición donde terminó la coincidencia de longitud no cero anterior, como hace gsub () en Python 3.6 y anterior. Las otras funciones de expresión regular en R y todas las funciones en PHP permiten coincidencias de longitud cero inmediatamente adyacentes a coincidencias de longitud no cero, al igual que PCRE.

¿Cuál es la razón detrás de usar .* Con el modificador global activado? Debido a que alguien de alguna manera espera que se devuelva una cadena vacía como una coincidencia o no sabe qué es el cuantificador * , de lo contrario no se debería establecer un modificador global. .* sin g no devuelve dos partidos.

No es obvio cuál es el beneficio de este comportamiento.

No debería haber un beneficio. En realidad estás cuestionando la existencia de coincidencias de longitud cero. Usted está preguntando por qué existe una cadena de longitud cero?

Tenemos tres lugares válidos donde existe una cadena de longitud cero:

Comienzo de la cadena de asunto
Entre dos personajes
Fin de la cadena de asunto

Debemos buscar la razón en lugar del beneficio de esa segunda salida de coincidencia de longitud cero utilizando .* Con el modificador g (o una función que busca todas las ocurrencias). Esa posición de longitud cero después de una cadena de entrada tiene algunos usos lógicos. El diagrama de estado inferior se toma de debuggex contra .* Pero agregué épsilon en la transición directa del estado de inicio al estado de aceptación para demostrar una definición:

Esa es una coincidencia de longitud cero (lea más sobre la transición de épsilon ).

Todo esto se relaciona con la codicia y la no codicia. Sin posiciones de longitud cero, una expresión regular como .?? no tendría un significado No intenta el punto primero, lo salta. Coincide con una cadena de longitud cero para este propósito para transitar el estado actual a un estado aceptable temporal.

Sin una posición de longitud cero .?? nunca se pudo omitir un carácter en la cadena de entrada y eso da como resultado un sabor completamente nuevo.

La definición de codicia / pereza conduce a coincidencias de longitud cero.

Estoy dando esta respuesta solo para demostrar por qué una expresión regular querría permitir que aparezca cualquier código después del último ancla de $ en el patrón. Supongamos que necesitamos crear una expresión regular para hacer coincidir una cadena con las siguientes reglas:

comienza con tres números
seguido de una o más letras, números, guiones o guiones bajos
Termina solo con letras y números.

Podríamos escribir el siguiente patrón:

^/d{3}[A-Za-z0-9/-_]*[A-Za-z0-9]$

Pero esto es un poco voluminoso, porque tenemos que usar dos clases de caracteres similares adyacentes entre sí. En su lugar, podríamos escribir el patrón como:

^/d{3}[A-Za-z0-9/-_]+$(?<!_|-)

^/d{3}[A-Za-z0-9/-_]+(?<!_|-)$

Aquí, eliminamos una de las clases de caracteres, y en su lugar usamos un aspecto negativo detrás del $ anchor para afirmar que el carácter final no era un guión bajo ni un guión.

Aparte de mirar por detrás, no tiene sentido para mí por qué un motor de expresiones regulares permitiría que algo apareciera después del ancla de $ . Mi punto aquí es que un motor de expresiones regulares puede permitir que aparezca un aspecto detrás del $ , y hay casos en los que lógicamente tiene sentido hacerlo.

No sé de dónde viene la confusión.
Los motores Regex son básicamente estúpidos .
Son como Mikey, van a comer cualquier cosa.

$ python -c "import re; print(re.findall(''$.*'', ''a''))" [''''] # !! Matched the hypothetical empty string after the end of ''a''

Podría poner mil expresiones opcionales después de $ y aún coincidirá con el
EOS. Los motores son estúpidos.

$ python -c "import re; print(re.findall(''.*$'', ''a''))" [''a'', ''''] # !! Matched both the full input AND the hypothetical empty string

Piénsalo de esta manera, aquí hay dos expresiones independientes.
.* | $ . La razón es que la primera expresión es opcional.
Simplemente sucede a tope contra la aserción de EOS.
De este modo, obtienes 2 coincidencias en una cadena no vacía.

¿Por qué la funcionalidad diseñada para encontrar múltiples coincidencias no superpuestas de una expresión regular (es decir, una coincidencia global) decide incluso intentar otra coincidencia si sabe que ya se ha consumido toda la entrada,

La clase de cosas llamadas aserciones no existe en las posiciones de los personajes.
Solo existen entre las posiciones de los personajes.
Si existen en la expresión regular, no se sabe si se ha consumido toda la entrada.
Si se pueden satisfacer como un paso independiente, pero solo una vez, coincidirán
independientemente.

Recuerde, regex es una propuesta de left-to-right .
También recuerde, los motores son estúpidos .
Esto es por diseño.
Cada construcción es un estado en el motor, es como una tubería.
Agregar complejidad seguramente lo condenará al fracaso.

Como nota al margen, ¿comienza realmente .*a desde el principio y comprueba cada carácter?
No. .* comienza inmediatamente al final de la cadena (o línea, dependiendo) y comienza
retrocediendo

Otra cosa divertida. Veo a muchos novatos usando .*? al final de su
expresiones regulares, pensando que obtendrá todos los kruft restantes de la cadena.
Es inútil, nunca coincidirá con nada.
Incluso un independiente .*? Las expresiones regulares siempre serán iguales para tantos caracteres.
hay en la cadena

¡Buena suerte! No te preocupes, los motores de expresiones regulares son ... bueno, estúpido .

Recordemos varias cosas:

^ y $ son aserciones de ancho cero : coinciden justo después del inicio lógico de la cadena (o después de que cada línea termina en modo multilínea con el indicador m en la mayoría de las implementaciones de expresiones regulares) o en el final lógico de la cadena (o final de la línea ANTES de Carácter de fin de línea o caracteres en modo multilínea.)
.* es potencialmente una coincidencia de longitud cero de ninguna coincidencia en absoluto. La única versión de longitud cero sería $(?:end of line){0} DEMO (lo cual es útil como comentario, supongo ...)
. no coincide con /n (a menos que tenga la bandera s ) pero sí con /r en los finales de línea CRLF de Windows. Entonces, $.{1} solo coincide con los finales de línea de Windows (pero no haga eso. Use el literal /r/n lugar).

No hay ningún beneficio en particular que no sean los casos simples de efectos secundarios.

La expresión regular $ es útil;
.* es útil.
El regex ^(?a lookahead) y (?a lookbehind)$ son comunes y útiles.
Las (?a lookaround)^ regulares (?a lookaround)^ o $(?a lookaround) son potencialmente útiles.
El regex $.* No es útil y lo suficientemente raro como para no justificar la implementación de una optimización para que el motor deje de buscar en ese caso de vanguardia. La mayoría de los motores de expresiones regulares hacen un trabajo decente de análisis de sintaxis; un apoyo faltante o paréntesis, por ejemplo. Para que el motor analice $.* Como no útil, sería necesario analizar el significado de esa expresión regular como diferente de $(something else)
Lo que obtenga dependerá en gran medida del sabor de las expresiones regulares y del estado de las banderas s y m .

Para ejemplos de reemplazos, considere la siguiente salida de script Bash de algunos de los principales sabores de expresiones regulares:

#!/bin/bash echo "perl" printf "123/r/n" | perl -lnE ''say if s/$.*/X/mg'' | od -c echo "sed" printf "123/r/n" | sed -E ''s/$.*/X/g'' | od -c echo "python" printf "123/r/n" | python -c "import re, sys; print re.sub(r''$.*'', ''X'', sys.stdin.read(),flags=re.M) " | od -c echo "awk" printf "123/r/n" | awk ''{gsub(/$.*/,"X")};1'' | od -c echo "ruby" printf "123/r/n" | ruby -lne ''s=$_.gsub(/$.*/,"X"); print s'' | od -c

Huellas dactilares:

perl 0000000 X X 2 X 3 X /r X /n 0000011 sed 0000000 1 2 3 /r X /n 0000006 python 0000000 1 2 3 /r X /n X /n 0000010 awk 0000000 1 2 3 /r X /n 0000006 ruby 0000000 1 2 3 X /n 0000005

^Nota: ^{* Mi publicación de preguntas contiene dos preguntas relacionadas, pero distintas , para las que debería haber creado publicaciones separadas, como ahora me doy cuenta.} ^{* Las otras respuestas aquí se enfocan en una de las preguntas de cada una, así que en parte esta respuesta proporciona un mapa de ruta para determinar qué respuestas responden a cada pregunta .}

En cuanto a por qué patrones como $<expr> están permitidos / cuando tienen sentido:

La respuesta de dawg sostiene que las combinaciones sin sentido como $.+ probablemente no se eviten por razones pragmáticas ; descartarlos puede que no valga la pena el esfuerzo.
La respuesta de Tim muestra cómo ciertas expresiones pueden tener sentido después de $ , es decir, con una mirada negativa detrás de las afirmaciones .
La segunda mitad de la respuesta de ivan_pozdeev sintetiza convincentemente las respuestas de dawg y de Tim.

En cuanto a por qué la coincidencia global encuentra dos coincidencias para patrones como .* Y. .*$ :

La respuesta de revo contiene una gran información de fondo sobre el emparejamiento de longitud cero (cadena vacía), que es a lo que finalmente se reduce el problema.

Permítame complementar su respuesta relacionándola más directamente con cómo el comportamiento contradice mis expectativas en el contexto de la comparación global :

Desde una perspectiva puramente de sentido común , es lógico pensar que una vez que la entrada se ha consumido completamente durante la comparación, no queda nada por definición, por lo que no hay razón para buscar más coincidencias.
En contraste, la mayoría de los motores de expresiones regulares consideran la posición del carácter después del último carácter de la cadena de entrada , la posición conocida como final de la cadena del sujeto en algunos motores, una posición de inicio válida para una coincidencia y, por lo tanto, intenta otra .
- Si la expresión regular en cuestión coincide con la cadena vacía (produce una coincidencia de longitud cero; por ejemplo, expresiones regulares como .* , O a? ), Coincide con esa posición y devuelve una coincidencia de cadena vacía.
- A la inversa, no verá una coincidencia adicional si la expresión regular no (también) coincide con la cadena vacía, mientras que la coincidencia adicional todavía se intenta en todos los casos, no se encontrarán coincidencias en este caso, dado que la cadena vacía es la única coincidencia posible en la posición de final de la cadena de sujeto.

Si bien esto proporciona una explicación técnica del comportamiento, todavía no nos dice por qué coincidir después de que se implementó el último carácter.

Lo más cercano que tenemos es una suposición educada por parte de Wiktor Stribiżew en un comentario (énfasis agregado), que nuevamente sugiere una razón pragmática para el comportamiento:

... como cuando se obtiene una coincidencia de cadena vacía, aún puede coincidir con el siguiente carácter que todavía se encuentra en el mismo índice en la cadena. Si un motor de expresiones regulares no lo admite, se omitirán estas coincidencias. Hacer una excepción para el final de la cadena probablemente no fue tan crítico para los autores de motores de expresiones regulares .

La primera mitad de la respuesta de ivan_pozdeev explica el comportamiento con más detalles técnicos al decirnos que el vacío al final de la cadena [entrada] es una posición válida para la coincidencia, al igual que cualquier otra posición de límite de caracteres .
Sin embargo, aunque tratar todas estas posiciones, el mismo es sin duda internamente consistente y presumiblemente simplifica la implementación , el comportamiento aún desafía el sentido común y no tiene beneficios obvios para el usuario .

Otras observaciones son la concordancia de cadenas vacías:

^{Nota: En todos los fragmentos de código a continuación, se realiza el reemplazo de cadena global para resaltar las coincidencias resultantes: cada coincidencia se incluye en [...] , mientras que las partes no coincidentes de la entrada se pasan como están.}

Sin embargo, tenga en cuenta que la coincidencia en la posición de final de la cadena de asunto no se limita a aquellos motores donde la coincidencia continúa en la misma posición de carácter después de una coincidencia vacía .

Por ejemplo, el motor de expresiones regulares .NET no lo hace (ejemplo de PowerShell):

PS> ''a1'' -replace ''/d*|a'', ''[$&]'' []a[1][]

Es decir:

/d* coincide con la cadena vacía antes de
a sí mismo no coincidió, lo que implica que la posición del carácter avanzó después de la coincidencia vacía.
1 fue emparejado por /d*
La posición de final de la cadena de asunto fue nuevamente igualada por /d* , lo que resultó en otra coincidencia de cadena vacía.

Perl 5 es un ejemplo de un motor que reanuda la coincidencia en la misma posición de carácter:

$ "a1" | perl -ple "s//d*|a/[$&]/g" [][a][1][]

Tenga en cuenta cómo se emparejó una también.

Curiosamente, Perl 6 no solo se comporta de manera diferente, sino que exhibe otra variante de comportamiento:

$ "a1" | perl6 -pe "s:g//d*|a/[$/]/" [a][1][]

Aparentemente, si una alternancia encuentra una coincidencia vacía y no vacía, solo se informa la no vacía; consulte el comentario de revo a continuación.