test - regexp javascript

¿Averigua qué idiomas pueden coincidir con las expresiones regulares?

Question

Hay algunas características en los motores de expresiones regulares modernas que le permiten hacer coincidir los idiomas que no podrían combinarse sin esa característica. Por ejemplo, la siguiente expresión regular que utiliza referencias atrás coincide con el lenguaje de todas las cadenas que constan de una palabra que se repite: (.+)/1 . Este lenguaje no es regular y no puede ser igualado por una expresión regular que no utiliza referencias anteriores.

¿La apariencia también afecta a qué idiomas puede coincidir una expresión regular? Es decir, ¿hay algún idioma que se pueda emparejar utilizando lookaround que de otro modo no se podría combinar? Si es así, ¿esto es cierto para todos los sabores de lookaround (lookahind o lookafter negativo o positivo) o solo para algunos de ellos?

Answer 1

Como afirman las demás respuestas, las soluciones alternativas no agregan ningún poder adicional a las expresiones regulares.

Creo que podemos mostrar esto usando lo siguiente:

One Pebble 2-NFA (vea la sección de Introducción del documento que se refiere a él).

El 1-guijarro 2NFA no trata con lookaheads anidados, pero podemos usar una variante de 2NFAs multi-guijarros (ver la sección a continuación).

Introducción

Un 2-NFA es un autómata finito no determinista que tiene la capacidad de moverse hacia la izquierda o hacia la derecha en su entrada.

Una máquina de un guijarro es donde la máquina puede colocar un guijarro en la cinta de entrada (es decir, marcar un símbolo de entrada específico con un guijarro) y hacer transiciones posiblemente diferentes en función de si hay un guijarro en la posición de entrada actual o no.

Se sabe que One Pebble 2-NFA tiene la misma potencia que un DFA regular.

Lookaheads no anidados

La idea básica es la siguiente:

El 2NFA nos permite retroceder (o ''pista delantera'') avanzando o retrocediendo en la cinta de entrada. Entonces, para una búsqueda anticipada, podemos hacer la coincidencia para la expresión regular anticipada y luego retroceder lo que hemos consumido, al unir la expresión de anticipación. ¡Para saber exactamente cuándo detener el retroceso, usamos el guijarro! Soltamos el guijarro antes de entrar en el dfa para mirar hacia adelante y marcar el punto donde el retroceso debe detenerse.

Por lo tanto, al final de ejecutar nuestra cadena a través del guijarro 2NFA, sabemos si coincidimos con la expresión anticipada o no y la entrada que queda (es decir, lo que queda por consumir) es exactamente lo que se requiere para que coincida con el resto.

Entonces, para un vistazo de la forma u (? = V) w

Tenemos los DFA para usted, v y w.

Desde el estado de aceptación (sí, podemos suponer que solo hay uno) de DFA para usted, hacemos una transición electrónica al estado de inicio de v, marcando la entrada con un guijarro.

Desde un estado de aceptación para v, realizamos e-transiciones a un estado que sigue moviendo la entrada hacia la izquierda, hasta que encuentra un guijarro, y luego transiciones al estado de inicio de w.

Desde un estado de rechazo de v, hacemos una transición electrónica a un estado que sigue moviéndose hacia la izquierda hasta que encuentra el guijarro, y las transiciones hacia el estado de aceptación de u (es decir, donde lo dejamos).

La prueba utilizada para los NFA regulares para mostrar r1 | r2, o r * etc., transfiere para estos un guijarro 2nfas. Consulte http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa para obtener más información sobre cómo se ensamblan las máquinas componentes para obtener una máquina más grande. para la expresión r *, etc.

La razón por la que las pruebas anteriores para el trabajo de r * etc. es que el retroceso asegura que el puntero de entrada esté siempre en el lugar correcto, cuando ingresemos el componente nfas para la repetición. Además, si un guijarro está en uso, una de las máquinas de componentes de anticipación lo está procesando. Dado que no hay transiciones desde la máquina de mirar hacia adelante para mirar hacia adelante de la máquina sin retroceder completamente y recuperar el guijarro, una sola máquina de guijarros es todo lo que se necesita.

Por ejemplo, considere ([^ a] | a (? = ... b)) *

y la cadena abbb.

Tenemos abbb que pasa por el peb2nfa para a (? = ... b), al final del cual estamos en el estado: (bbb, emparejado) (es decir, en la entrada bbb queda, y ha coincidido con ''a'' seguido de ''..b''). Ahora, debido a *, volvemos al principio (ver la construcción en el enlace de arriba), e ingresamos el dfa para [^ a]. Haga coincidir b, regrese al principio, ingrese [^ a] nuevamente dos veces y luego acepte.

Tratar con Lookaheads anidados

Para manejar lookaheads anidados, podemos usar una versión restringida de k-pebble 2NFA como se define aquí: Resultados de complejidad para los autómatas bidireccionales y multi-guijarros y sus lógicas (ver definición 4.1 y teorema 4.2).

En general, 2 autómatas de guijarros pueden aceptar conjuntos no regulares, pero con las siguientes restricciones, puede mostrarse que el autómata k-guijarro es regular (Teorema 4.2 en el documento anterior).

Si los guijarros son P_1, P_2, ..., P_K

• P_ {i + 1} no se puede colocar a menos que P_i ya esté en la cinta y P_ {i} no se recoja a menos que P_ {i + 1} no esté en la cinta. Básicamente, los guijarros deben usarse de manera LIFO.

• Entre el momento en que se coloca P_ {i + 1} y el momento en que se recoge P_ {i} o se coloca P_ {i + 2}, el autómata solo puede atravesar la palabra secundaria ubicada entre la ubicación actual de P_ {i} y el final de la palabra de entrada que se encuentra en la dirección de P_ {i + 1}. Además, en esta subpalabra, el autómata solo puede actuar como un autómata de 1 guijarro con Pebble P_ {i + 1}. En particular, no está permitido levantar, colocar o incluso sentir la presencia de otro guijarro.

Por lo tanto, si v es una expresión de búsqueda anticipada anidada de profundidad k, entonces (? = V) es una expresión anidada de búsqueda anticipada de profundidad k + 1. Cuando ingresamos a una máquina de inspección anticipada, sabemos exactamente cuántos guijarros se han colocado hasta el momento y, por lo tanto, podemos determinar exactamente qué guijarro colocar y cuando salimos de esa máquina, sabemos qué guijarro levantar. Todas las máquinas en la profundidad t se ingresan colocando guijarro t y salido (es decir, volvemos al procesamiento de una máquina de profundidad t-1) eliminando el guijarro t. Cualquier ejecución de la máquina completa se ve como una llamada dfs recursiva de un árbol y las dos restricciones anteriores de la máquina de guijarros múltiples pueden ser atendidas.

Ahora cuando se combinan expresiones, para rr1, dado que concat, los números de guijarro de r1 se deben incrementar por la profundidad de r. Para r * y r | r1 la numeración de guijarros sigue siendo la misma.

Por lo tanto, cualquier expresión con lookaheads se puede convertir a una máquina de multi-guijarro equivalente con las restricciones anteriores en la colocación de guijarros y, por lo tanto, es regular.

Conclusión

Esto básicamente soluciona el inconveniente de la prueba original de Francis: poder evitar que las expresiones de anticipación consuman cualquier cosa que se requiera para futuras coincidencias.

Dado que Lookbehinds son solo cadenas finitas (en realidad no expresiones regulares), podemos tratarlas primero, y luego tratar con los lookaheads.

Perdón por la redacción incompleta, pero una prueba completa implicaría dibujar muchas figuras.

Me parece correcto, pero estaré encantado de saber de cualquier error (que me parece que me gusta :-)).

Answer 2

Estoy de acuerdo con las otras publicaciones en que la apariencia es regular (lo que significa que no agrega ninguna capacidad fundamental a las expresiones regulares), pero tengo un argumento para que sea más simple que las otras que he visto.

Mostraré que la apariencia es regular al proporcionar una construcción de DFA. Un lenguaje es regular si y solo si tiene un DFA que lo reconoce. Tenga en cuenta que Perl en realidad no usa DFA internamente (consulte este documento para obtener más información: http://swtch.com/~rsc/regexp/regexp1.html ), pero construimos un DFA para los fines de la prueba.

La forma tradicional de construir un DFA para una expresión regular es construir primero un NFA usando el algoritmo de Thompson. Dado dos expresiones regulares fragmentos r1 y r2 , el algoritmo de Thompson proporciona construcciones para concatenación ( r1r2 ), alternancia ( r1|r2 ) y repetición ( r1* ) de expresiones regulares. Esto le permite construir un NFA bit a bit que reconoce la expresión regular original. Vea el documento de arriba para más detalles.

Para mostrar que las previsiones positivas y negativas son regulares, proporcionaré una construcción para la concatenación de una expresión regular u con anticipación positiva o negativa: (?=v) o (?!v) . Solo la concatenación requiere un trato especial; las construcciones de alternancia y repetición usuales funcionan bien.

La construcción es para u (? = V) y u (?! V) es:

En otras palabras, conecte cada estado final del NFA existente para u con un estado de aceptación y un NFA para v , pero se modifica de la siguiente manera. La función f(v) se define como:

• Deje que aa(v) sea ​​una función en un NFA v que cambie cada estado de aceptación en un "estado antiaceptación". Un estado antiacepta se define como un estado que hace que la coincidencia falle si cualquier ruta a través de la NFA termina en este estado para una cadena dada s , incluso si una ruta diferente a través de v para s termina en un estado de aceptación.
• Deje que loop(v) sea ​​una función en un NFA v que agregue una autotransición en cualquier estado de aceptación. En otras palabras, una vez que una ruta conduce a un estado de aceptación, esa ruta puede permanecer en el estado de aceptación para siempre, sin importar qué entrada siga.
• Para un lookahead negativo, f(v) = aa(loop(v)) .
• Para un lookahead positivo, f(v) = aa(neg(v)) .

Para proporcionar un ejemplo intuitivo de por qué funciona esto, usaré la expresión regular (b|a(?:.b))+ , que es una versión ligeramente simplificada de la expresión regular que propuse en los comentarios de la prueba de Francisco. Si utilizamos mi construcción junto con las construcciones tradicionales de Thompson, terminamos con:

Las e s son transiciones epsilon (transiciones que pueden tomarse sin consumir ninguna entrada) y los estados antiaceptos están etiquetados con una X En la mitad izquierda del gráfico, se ve la representación de (a|b)+ : cualquier a o b coloca el gráfico en un estado de aceptación, pero también permite una transición al estado de inicio para que podamos volver a hacerlo. Pero tenga en cuenta que cada vez que hacemos coincidir una a , también ingresamos la mitad derecha del gráfico, donde estamos en estados antiaceptos hasta que hagamos coincidir "cualquiera" seguido de un b .

Este no es un NFA tradicional porque los NFA tradicionales no tienen estados antiaceptos. Sin embargo, podemos usar el algoritmo tradicional NFA-> DFA para convertir esto en un DFA tradicional. El algoritmo funciona como siempre, donde simulamos múltiples ejecuciones del NFA haciendo que nuestros estados de DFA correspondan a subconjuntos de los estados de NFA en los que podríamos estar. El único giro es que aumentamos ligeramente la regla para decidir si un estado de DFA es un aceptar (final) estado o no. En el algoritmo tradicional, un estado de DFA es un estado de aceptación si alguno de los estados de NFA era un estado de aceptación. Modificamos esto para decir que un estado de DFA es un estado de aceptación si y solo si:

• = 1 estados NFA es un estado de aceptación, y

• 0 Los estados NFA son estados antiaceptos.

Este algoritmo nos dará un DFA que reconoce la expresión regular con lookahead. Ergo, lookahead es regular. Tenga en cuenta que mirar hacia atrás requiere una prueba por separado.

Answer 3

La respuesta a la pregunta que hace, que es si una clase de idiomas más grande que los idiomas regulares se puede reconocer con expresiones regulares aumentadas por lookaround, es no.

Una prueba es relativamente sencilla, pero un algoritmo para traducir una expresión regular que contiene "lookarounds" en uno sin es desordenado.

Primero: tenga en cuenta que siempre puede negar una expresión regular (sobre un alfabeto finito). Dado un autómata de estado finito que reconoce el lenguaje generado por la expresión, puede simplemente intercambiar todos los estados aceptados por estados no aceptables para obtener un FSA que reconozca exactamente la negación de ese idioma, para el cual hay una familia de expresiones regulares equivalentes .

Segundo: porque los lenguajes regulares (y por lo tanto las expresiones regulares) se cierran bajo negación también se cierran bajo intersección ya que A se cruzan con B = neg (neg (A) unión neg (B)) por las leyes de Morgan. En otras palabras, con dos expresiones regulares, puede encontrar otra expresión regular que coincida con ambas.

Esto le permite simular expresiones alternativas. Por ejemplo, u (? = V) w solo coincide con las expresiones que coincidirán con uv y uw.

Para la búsqueda anticipada negativa, necesita la expresión regular equivalente al conjunto teórico A / B, que es simplemente A interseccionar (neg B) o equivalentemente neg (neg (A) unión B). Por lo tanto, para cualquier expresión regular rys puede encontrar una expresión regular rs que coincida con aquellas expresiones que coinciden con r que no coinciden con s. En términos negativos de anticipación: u (?! V) w solo coincide con aquellas expresiones que coinciden con uw - uv.

Hay dos razones por las que la búsqueda es útil.

Primero, porque la negación de una expresión regular puede dar como resultado algo mucho menos ordenado. Por ejemplo q(?!u)=q($|[^u]) .

En segundo lugar, las expresiones regulares hacen más que emparejar expresiones, también consumen caracteres de una cadena, o al menos así es como nos gusta pensar en ellas. Por ejemplo, en python me preocupan los .start () y .end (), por lo tanto, por supuesto:

>>> re.search(''q($|[^u])'', ''Iraq!'').end()
5
>>> re.search(''q(?!u)'', ''Iraq!'').end()
4

En tercer lugar, y creo que esta es una razón bastante importante, la negación de expresiones regulares no se eleva bien sobre la concatenación. neg (a) neg (b) no es lo mismo que neg (ab), lo que significa que no puede traducir un aspecto fuera del contexto en el que lo encuentra; debe procesar toda la cadena. Supongo que eso hace que sea desagradable para las personas trabajar y romper las intuiciones de las personas sobre las expresiones regulares.

Espero haber respondido a tu pregunta teórica (es tarde por la noche, así que perdóname si no estoy seguro). Estoy de acuerdo con un comentarista que dijo que esto tiene aplicaciones prácticas. Me encontré con el mismo problema al tratar de raspar algunas páginas web muy complicadas.

EDITAR

Mis disculpas por no ser más clara: no creo que puedas dar una prueba de regularidad de las expresiones regulares + miradas por inducción estructural; mi ejemplo de u (?! V) w era solo eso, un ejemplo, y uno fácil a eso. La razón por la que una inducción estructural no funcionará es porque las miradas se comportan de una manera no compositiva, el punto que estaba tratando de hacer sobre las negaciones anteriores. Sospecho que cualquier prueba formal directa va a tener muchos detalles desordenados. Intenté pensar en una manera fácil de mostrarlo, pero no puedo pensar en una sola idea.

Para ilustrar usando el primer ejemplo de Josh de ^([^a]|(?=..b))*$ esto es equivalente a un DFSA de 7 estados con todos los estados aceptando:

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           /                  |
|          (not a)       /               (b)
|          |              /               | 
|          v                /             v
(b)        E - (a) -> F      /-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
/--------- H <-------------------(b)-----/

La expresión regular para el estado A solo se ve así:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

En otras palabras, cualquier expresión regular que vayas a obtener al eliminar las miradas en general será mucho más larga y mucho más desordenada.

Para responder al comentario de Josh, sí, creo que la forma más directa de probar la equivalencia es a través de la FSA. Lo que lo hace más desordenado es que la forma habitual de construir un FSA es a través de una máquina no determinista: es mucho más fácil expresarlo como simplemente la máquina construida a partir de máquinas para usted yv con una transición épsilon a las dos. Por supuesto, esto es equivalente a una máquina determinista, pero a riesgo de una explosión exponencial de estados. Mientras que la negación es mucho más fácil de hacer a través de una máquina determinista.

La prueba general implicará tomar el producto cartesiano de dos máquinas y seleccionar los estados que desea conservar en cada punto en el que desee insertar un vistazo. El ejemplo anterior ilustra lo que quiero decir hasta cierto punto.

Mis disculpas por no proporcionar una construcción.

NUEVA EDITACIÓN: Encontré una publicación de blog que describe un algoritmo para generar un DFA a partir de una expresión regular aumentada con lookarounds. Es claro porque el autor amplía la idea de un NFA-e con "transiciones épsilon etiquetadas" de la manera obvia, y luego explica cómo convertir dicho autómata en un DFA.

Pensé que algo así sería una forma de hacerlo, pero estoy satisfecho de que alguien lo haya escrito. Estaba más allá de mí para llegar a algo tan limpio.

Answer 4

Tengo la sensación de que hay dos preguntas distintas que se hacen aquí:

• ¿Los motores Regex que incorporan "lookaround" son más potentes que los motores Regex que no lo son?
• ¿El "lookaround" faculta a un motor Regex con la capacidad de analizar lenguajes que son más complejos que los generados a partir de un Chomsky Tipo 3 - Gramática regular ?

La respuesta a la primera pregunta en un sentido práctico es sí. Lookaround le dará a un motor Regex que usa esta característica fundamentalmente más potencia que otra que no lo hace. Esto se debe a que proporciona un conjunto más rico de "anclajes" para el proceso de correspondencia. Lookaround le permite definir una Regex completa como un posible punto de anclaje (aserción de ancho cero). regular-expressions.info/lookaround.html puede obtener una visión general bastante buena de la potencia de esta función.

La apariencia, aunque poderosa, no eleva el motor Regex más allá de los límites teóricos establecidos por una Gramática Tipo 3. Por ejemplo, nunca podrá analizar de forma fiable un lenguaje basado en una gramática de contexto libre - tipo 2 utilizando un motor Regex equipado con una apariencia. Los motores Regex están limitados a la potencia de una Automatización Estatal Finita y esto fundamentalmente restringe la expresividad de cualquier lenguaje que puedan analizar al nivel de una Gramática Tipo 3. No importa cuántos "trucos" se agreguen a su motor Regex, los idiomas generados a través de una Gramática libre de contexto siempre permanecerán más allá de sus capacidades. Análisis de contexto sin formato: la gramática de tipo 2 requiere automatización pushdown para "recordar" dónde se encuentra en un constructo de lenguaje recursivo. Todo lo que requiera una evaluación recursiva de las reglas gramaticales no se puede analizar utilizando motores Regex.

En resumen: Lookaround proporciona algunos beneficios prácticos para los motores Regex pero no "altera el juego" en un nivel teórico.

EDITAR

¿Hay alguna gramática con una complejidad en algún lugar entre Tipo 3 (Regular) y Tipo 2 (Sin contexto)?

Creo que la respuesta es no. La razón es porque no existe un límite teórico sobre el tamaño de NFA / DFA necesario para describir un idioma regular. Puede volverse arbitrariamente grande y, por lo tanto, poco práctico de usar (o especificar). Aquí es donde los esquivos como "lookaround" son útiles. Proporcionan un mecanismo abreviado para especificar lo que de otro modo conduciría a especificaciones muy grandes / complejas de NFA / DFA. No aumentan la expresividad de los idiomas regulares, solo hacen que sean más prácticos. Una vez que entiendes este punto, queda claro que hay muchas "características" que podrían agregarse a los motores Regex para hacerlos más útiles en un sentido práctico, pero nada los hará capaces de ir más allá de los límites de un lenguaje regular. .

La diferencia básica entre un lenguaje Regular y un Lenguaje Libre de Contexto es que un idioma Regular no contiene elementos recursivos. Para evaluar un lenguaje recursivo necesita una Automatización Push Down para "recordar" dónde se encuentra en la recursión. Un NFA / DFA no apila información de estado por lo que no puede manejar la recursión. Entonces, dada una definición de lenguaje no recursiva habrá algo de NFA / DFA (pero no necesariamente una expresión Regex práctica) para describirlo.