varias ternario operadores operador logicos condiciones comparacion asignacion anidado javascript regex regex-greedy

ternario - operadores de comparacion javascript



¿La codicia se comporta de manera diferente en JavaScript? (3)

Hubo una pregunta que me hizo darme cuenta de que la codicia de los cuantificadores no es siempre la misma en ciertos motores de expresiones regulares. Tomando la expresión regular de esa pregunta y modificándola un poco:

!/[(.*?)*/]

(Sé que * es redundante aquí, pero encontré que lo que sigue es un comportamiento bastante interesante).

Y si intentamos emparejar contra:

![][][]

Esperaba que el primer grupo de captura estuviera vacío, porque (.*?) Es perezoso y se detendrá en el primer momento en que se encuentre. Esto es precisamente lo que sucede en:

Miré a mi alrededor con otros idiomas, por ejemplo, ruby , java , C# pero todos se comportan como los esperaba (es decir, devuelven grupos de captura vacíos).

(El sabor Golang de golang aparentemente también obtiene grupos de captura no vacíos)

Parece que el motor de expresiones regulares de JavaScript está interpretando el segundo * para convertir .*? De perezosos a codiciosos. Tenga en cuenta que convertir el segundo * a *? parece hacer que las expresiones regulares funcionen como esperaba (al igual que quitar el cuantificador por completo, porque sé que está siendo redundante en esta situación, pero ese no es el punto).

* se usó en la expresión regular, pero este comportamiento es similar con + ? o {m,n} y convertirlos a su versión perezosa da los mismos resultados que con *? .

¿Alguien sabe lo que realmente está pasando?

Respuesta corta

El comportamiento se define en las especificaciones ECMA-262 en la sección 15.10.2 Semántica de patrones , especialmente en 15.10.2.5 donde se analiza la semántica de la producción Term :: Atom Quantifier .

Como una ligera generalización: Sea E un patrón que puede coincidir con una cadena vacía . Si existe una cadena de entrada S, donde la cadena vacía es la primera opción coincidente en E, los patrones que contienen una repetición codiciosa del patrón E se ven afectados. Por ejemplo:

(a*?)* against aaaa !/[(.*?)*/] against ![][][] (.*?){1,4} against asdf (|a)* against aaaa (a|()|b){0,4} against aaabbb

Firefox y otros navegadores basados ​​en Webkit parecen seguir de cerca las especificaciones, mientras que IE no cumple con las especificaciones en el caso cuando no hay una secuela del patrón afectado.

Respuesta larga

La parte relevante de las especificaciones se cita a continuación. Algunas partes de las especificaciones se omiten ([...]) para mantener la discusión relevante. Lo explicaré mediante la condensación de la información de las especificaciones a la vez que la mantengo simple.

Vocabulario

  • Un estado es un par ordenado ( endIndex , capturas ) donde endIndex es un número entero y captures es una matriz interna de los valores de NcapturingParens . Los estados se utilizan para representar estados de coincidencia parcial en los algoritmos de coincidencia de expresiones regulares. EndIndex es uno más el índice del último carácter de entrada que coincide hasta ahora con el patrón, mientras que las capturas contienen los resultados de la captura de paréntesis. [...]. Debido al retroceso, muchos estados pueden estar en uso en cualquier momento durante el proceso de comparación.
  • Un MatchResult es un estado o una falla especial del token que indica que la coincidencia falló.

No debe haber confusión aquí. State realiza un seguimiento de la posición que se ha procesado hasta ahora (y también de las capturas, que no nos interesan por el momento). MatchResult , bueno, es el resultado del partido (duh!).

  • Un procedimiento de continuación es un cierre interno (es decir, un procedimiento interno con algunos argumentos ya vinculados a valores) que toma un argumento de estado y devuelve un resultado de MatchResult . Si un cierre interno hace referencia a las variables vinculadas a la función que crea el cierre, el cierre utiliza los valores que tenían estas variables en el momento en que se creó el cierre. La Continuación intenta hacer coincidir la parte restante (especificada por los argumentos ya vinculados del cierre) del patrón con la Cadena de entrada, comenzando en el estado intermedio dado por su argumento Estado . Si el partido tiene éxito, la Continuación devuelve el estado final que alcanzó; Si la coincidencia falla, la Continuación devuelve falla .
  • Un procedimiento de Matcher es un cierre interno que toma dos argumentos, un Estado y una Continuación , y devuelve un resultado de MatchResult . Un Matcher intenta hacer coincidir un subpatrón medio (especificado por los argumentos ya enlazados del cierre) del patrón con la Cadena de entrada, comenzando en el estado intermedio dado por su argumento State . El argumento de continuación debe ser un cierre que coincida con el resto del patrón. Después de hacer coincidir el subpatrón de un patrón para obtener un nuevo estado , el Matcher luego llama Continuación en ese nuevo estado para probar si el resto del patrón también puede coincidir. Si puede, el Matcher devuelve el Estado devuelto por Continuación ; si no, el Matcher puede probar diferentes opciones en sus puntos de elección, llamando repetidamente a Continuación hasta que tenga éxito o se hayan agotado todas las posibilidades.

Un Matcher contiene un código para coincidir con un subpatrón que representa, y llamará Continuación para continuar la coincidencia. Y Continuación contiene código para continuar la partida desde donde Matcher se detuvo. Ambos aceptan el Estado como un argumento para saber dónde comenzar a hacer coincidir.

Plazo de producción :: Atom Quantifier

La producción Term :: Atom Quantifier se evalúa de la siguiente manera:

  1. Evaluar Atom para obtener un Matcher m .
  2. Evalúe el cuantificador para obtener los tres resultados: un entero min , un entero (o) max y boolean greedy .
  3. Si max es finito y menor que min , lanza una excepción SyntaxError .
  4. Deje que parenIndex sea ​​el número de paréntesis de captura a la izquierda en la expresión regular completa que aparece a la izquierda del Término de esta expansión de producción. [...]
  5. Sea parenCount el número de paréntesis de captura a la izquierda en la expansión del Atom de esta producción. [...]
  6. Devuelve un cierre interno del Matcher que toma dos argumentos, un Estado x y una Continuación c , y realiza lo siguiente:
    1. Llame a RepeatMatcher ( m, min, max, greedy, x, c, parenIndex, parenCount ) y devuelva su resultado.

Tenga en cuenta que m es el Matcher para el átomo que se está repitiendo, y la Continuación c se transmite desde el código generado a partir de reglas de producción de nivel superior.

La operación abstracta RepeatMatcher toma ocho parámetros, un Matcher m , un entero min , un entero (o) max , un booleano codicioso , un Estado x , una Continuación c , un entero parenIndex y un entero parenCount , y realiza lo siguiente:

  1. Si max es cero, llame a c (x) y devuelva su resultado.
  2. Cree un cierre de Continuación interno d que tome un argumento de Estado y realice lo siguiente:
    1. Si min es cero y el índice de final de y es igual al índice de final de x , entonces devuelva el error .
    2. Si min es cero entonces deja que min2 sea ​​cero; De lo contrario, deje que min2 sea min - 1.
    3. Si max es ∞, entonces max2 sea ​​∞; de lo contrario, sea max2 sea max - 1.
    4. Llame a RepeatMatcher ( m, min2, max2, codicioso, y, c, parenIndex, parenCount ) y devuelva su resultado.
  3. Permita que cap sea ​​una copia nueva de la matriz interna de capturas de x .
  4. Para cada entero k que satisface parenIndex < k y k ? parenIndex + parenCount , establece el límite [ k ] a indefinido .
  5. Dejemos que sea x el índice final .
  6. Sea xr el Estado ( e, cap ).
  7. Si min no es cero, llame a m (xr, d) y devuelva su resultado.
  8. Si la codicia es falsa , entonces
    1. Llame a c (x) y sea z el resultado.
    2. Si z no falla , devuelve z .
    3. Llame a m (xr, d) y devuelva su resultado.
  9. Llame a m (xr, d) y sea z el resultado.
  10. Si z no falla , devuelve z .
  11. Llame a c (x) y devuelva su resultado.

El Paso 2 define una Continuación d donde intentamos hacer coincidir otra instancia del Átomo repetido, que se llama más adelante en el paso 7 (caso min > 0), el paso 8.3 (caso perezoso) y el paso 9 (caso codicioso) a través del Matcher m .

Los pasos 5 y 6 crean una copia del estado actual, con el fin de realizar un seguimiento y para detectar una coincidencia de cadena vacía en el paso 2.

Los pasos a partir de aquí describen 3 casos separados:

  • El paso 7 cubre el caso donde el cuantificador tiene un valor mínimo distinto de cero. A pesar de la codicia, debemos hacer coincidir al menos las instancias mínimas de Atom antes de poder llamar a la Continuación c .

  • Debido a la condición en el paso 7, el minuto es 0 a partir de este punto. El paso 8 trata el caso en el que el cuantificador es perezoso. El paso 9, 10, 11 trata el caso en el que el cuantificador es codicioso. Tenga en cuenta el orden inverso de la llamada.

Llamar a m (xr, d) significa hacer coincidir una instancia del átomo, luego llamar a Continuación d para continuar la repetición.

La continuación de la llamada c (x) significa salir de la repetición y hacer coincidir lo que viene después. Observe cómo se pasa la Continuación c al RepeatMatcher dentro de la Continuación d , de modo que esté disponible para toda la iteración posterior de la repetición.

Explicación de la peculiaridad en JavaScript RegExp

El paso 2.1 es el culpable que causa la discrepancia en el resultado entre PCRE y JavaScript.

  1. Si min es cero y el índice de final de y es igual al índice de final de x , entonces devuelva el error .

La condición min = 0 se alcanza cuando el cuantificador originalmente tiene 0 como min ( * o {0,n} ) o mediante el paso 7, que debe llamarse siempre que min > 0 (el cuantificador original sea + o {n,} o {n,m} ).

Cuando min = 0 y el cuantificador son codiciosos, se llamará al Matcher m (en el paso 9), que intenta hacer coincidir una instancia de Atom y llamar a Continuación d que se configura en el paso 2. La continuación d llamará repetidamente a RepeatMatcher, que en turno llamará nuevamente al Matcher m (paso 9).

Sin el paso 2.1, si el Matcher m tiene una cadena vacía como la primera opción posible para avanzar en la entrada, la iteración continuará (teóricamente) para siempre sin avanzar. Dadas las funciones limitadas que admite RegExp de JavaScript (no hay referencias atrasadas declaradas hacia adelante u otras funciones sofisticadas), no hay necesidad de continuar con otra iteración cuando la iteración actual coincida con una cadena vacía; de todos modos, una cadena vacía será igual. . El paso 2.1 es el método de JavaScript para lidiar con la repetición de una cadena vacía.

Como se estableció en el paso 2.1, cuando min = 0, el motor de expresiones regulares de JavaScript se podará cuando el Matcher m coincida con una cadena vacía ( error de retorno). Esto rechaza efectivamente "la cadena vacía repetida finitadamente muchas veces es una cadena vacía" .

Otro efecto secundario del paso 2.1 es que, desde el punto en que min = 0, siempre que haya una instancia en la que el Matcher m coincida con la cadena no vacía, se garantiza que la última repetición de Atom no será vacía.

Por el contrario, parece que PCRE (y otros motores) aceptan que "la cadena vacía repetida muchas veces es una cadena vacía", y continúa con el resto del patrón. Esto explica el comportamiento de PCRE en los casos mencionados anteriormente. En cuanto al algoritmo, PCRE detiene la repetición después de hacer coincidir la cadena vacía dos veces seguidas.

Esto no está respondiendo por qué Grediness se está comportando de manera diferente en Javascript, pero muestra que esto no es un error y se probó para que se comporte así. Tomaré como ejemplo el motor v8 de google. Encontré un ejemplo similar en sus pruebas.

/test/mjsunit/third_party/regexp-pcre.js:

line 1085: res[1006] = /([a]*?)*/; line 4822: assertToStringEquals("aaaa,a", res[1006].exec("aaaa "), 3176);

https://code.google.com/p/v8/source/browse/trunk/test/mjsunit/third_party/regexp-pcre.js#1085

Este código funciona bien para Javascript http://regex101.com/r/nD0uG8 pero no tiene la misma salida para PCRE php y python.

ACTUALIZACIÓN: Sobre tu pregunta:

Parece que el motor de expresiones regulares de JavaScript está interpretando el segundo * para convertir. *? de perezoso a codicioso

https://code.google.com/p/v8/source/browse/trunk/src/parser.cc#5157

RegExpQuantifier::QuantifierType quantifier_type = RegExpQuantifier::GREEDY; if (current() == ''?'') { quantifier_type = RegExpQuantifier::NON_GREEDY; Advance(); } else if (FLAG_regexp_possessive_quantifier && current() == ''+'') { // FLAG_regexp_possessive_quantifier is a debug-only flag. quantifier_type = RegExpQuantifier::POSSESSIVE; Advance(); }

Hice algunas pruebas y descubrí que en Firefox y Chrome, si un grupo tiene un cuantificador codicioso y directa o indirectamente contiene uno o más cuantificadores perezosos con cero como el número mínimo de iteraciones, entonces para las iteraciones del cuantificador codicioso donde el número mínimo Ya se han cumplido las iteraciones, el cuantificador perezoso más a la izquierda que puede coincidir con una o más iteraciones coincidirá con una iteración si el grupo encontraría una coincidencia de longitud cero si el cuantificador perezoso coincidiera con las iteraciones cero.

Por ejemplo, (.{0,2}?){5,8} coincide con "abc" en "abcdefghijklmnopqrstuvwxyz" porque .{0,2}? coincide con una iteración para las iteraciones 6, 7 y 8 de {5,8} .

Si hay tokens después del grupo con el cuantificador codicioso que no puede ser igualado, entonces el cuantificador perezoso expande su número de iteraciones. La permutación con cero iteraciones nunca se intenta. Pero el cuantificador codicioso todavía puede retroceder a su mínimo número de iteraciones.

En la misma cadena de asunto, (.{0,3}?){5,6}[ad] coincide con "abcd" mientras que (.{0,3}?){5,6}a coincide con "a".

Si hay algo más dentro del grupo que encuentra una coincidencia, los cuantificadores perezosos se comportan como lo hacen en otros motores de expresiones regulares.

Lo mismo ocurre en Internet Explorer si y solo si hay tokens que no son opcionales después del grupo con el cuantificador codicioso. Si no hay tokens después del grupo o todos son opcionales, IE se comporta como la mayoría de los otros motores de expresiones regulares.

La explicación del comportamiento en Firefox y Chrome parece ser la combinación de dos pasos en la sección 15.10.2.5 en el estándar de JavaScript. El paso 2.1 para RepeatMatcher hace que el motor de expresiones regulares falle las iteraciones de longitud cero de los cuantificadores que ya han coincidido con el número mínimo de iteraciones requeridas, en lugar de simplemente detener la iteración continua. El Paso 9 evalúa lo que viene después de un cuantificador perezoso antes de evaluar el cuantificador perezoso en sí. En estos ejemplos se incluye la repetición continua del cuantificador codicioso. Cuando este cuantificador codicioso falla en el paso 2.1, el cuantificador perezoso se ve obligado a repetir al menos una vez.

Entonces, para responder si se trata de un error, diría que es un error en la especificación de JavaScript. Este comportamiento no tiene ningún beneficio y hace que las expresiones regulares de JavaScript sean innecesariamente diferentes de todos los otros motores de expresiones regulares de retroceso (populares). Sin embargo, no espero que las futuras especificaciones de JavaScript cambien esto.

La ópera se comporta de manera diferente. (.{0,2}?){5,8} coincide con "abcd" mientras que (.{0,2}?){6,8} coincide con "abcde". Opera parece forzar al cuantificador perezoso a que coincida con al menos una iteración para todos menos la primera iteración del cuantificador codicioso, y luego deja de iterar cuando el cuantificador codicioso ha encontrado el número mínimo requerido de iteraciones.

Recomiendo no usar grupos o alternativas en las que todo sea opcional. Asegúrese de que cada alternativa y cada grupo coincida con algo. Si el grupo necesita ser opcional, use ? para hacer que todo el grupo sea opcional, en lugar de hacer que todo dentro del grupo sea opcional. Esto reducirá el número de permutaciones que debe probar el motor de expresiones regulares.