regulares - ¿Qué tipo de lenguajes formales pueden analizar los motores regex modernos?

probar expresiones regulares

Question

Aquí, así, la gente a veces dice algo como "no se puede analizar X con expresiones regulares, porque X no es un lenguaje regular". Sin embargo, a mi entender, los modernos motores de expresiones regulares pueden igualar más que los lenguajes regulares en el sentido de Chomsky . Mis preguntas:

dado un motor de expresión regular que soporta

• referencias inversas
• Afirmaciones de ancho ilimitado.
• recursion, como (?R)

¿Qué tipo de idiomas puede analizar? ¿Puede analizar cualquier lenguaje libre de contexto, y si no, cuál sería el contraejemplo?

(Para ser precisos, con "analizar" me refiero a "construir una expresión regular única que acepte todas las cadenas generadas por la gramática X y rechace todas las demás cadenas").

Add .: Me interesa particularmente ver un ejemplo de un lenguaje libre de contexto que los motores de expresiones regulares modernas (Perl, Net, módulo de expresiones regulares de python) no podrían analizar.

Answer 1

Los motores de expresiones regulares modernas pueden analizar un conjunto de idiomas más grande que el de los lenguajes regulares. Dicho esto, ninguno de los cuatro conjuntos clásicos de Chomsky son reconocidos exactamente por expresiones regulares. Todos los idiomas regulares son claramente reconocidos por expresiones regulares. Existen algunos lenguajes clásicos libres de contexto que no se pueden reconocer por expresiones regulares, como el lenguaje de paréntesis equilibrado a^nb^n , a menos que estén disponibles las referencias inversas con conteo. Sin embargo, una expresión regular puede analizar el lenguaje ww que es sensible al contexto.

En realidad, las expresiones regulares en la teoría del lenguaje formal están ligeramente relacionadas con las expresiones regulares. La combinación de expresiones regulares con referencia inversa ilimitada es NP-Completa en el caso más general, por lo que todos los algoritmos de coincidencia de patrones para expresiones regulares lo suficientemente poderosas son exponenciales, al menos en el caso general. Sin embargo la mayoría de las veces para la mayoría de las entradas son bastante rápidas. Se sabe que la coincidencia de idiomas libres de contexto es, a lo sumo, algo más rápido que n^3 , por lo que hay algunos idiomas en expresiones regulares que no son libres de contexto (como ww ), pero no todas las lenguas libres de contexto se pueden analizar mediante expresiones regulares. Los idiomas de tipo 0 no son decidibles en general, las expresiones regulares no llegan allí.

Entonces, como conclusión no muy concluyente, las expresiones regulares pueden analizar un amplio conjunto de idiomas que incluyen todos los lenguajes regulares, y algunos libres de contexto y sensibles al contexto, pero no es exactamente igual a ninguno de esos conjuntos. Existen otras categorías de idiomas y otras taxonomías, donde podría encontrar una respuesta más precisa, pero ninguna taxonomía que incluya idiomas libres de contexto como un subconjunto adecuado en una jerarquía de idiomas puede proporcionar un solo idioma exactamente reconocido por regexes, porque regexes solo se interseca en alguna parte con lenguajes libres de contexto, y ninguno de ellos es un subconjunto adecuado del otro.

Answer 2

Puede leer sobre expresiones regulares en Introducción a la lengua y la lingüística por Ralph W. Fasold, Jeff Connor-Linton P.477

Jerarquía de Chomsky :

Type0> = Type1> = Type2> = Type3

La lingüística computacional incluye principalmente gramáticas de tipo 2 y 3

• Tipo 3 gramáticas :

–Incluye expresiones regulares y autómatas de estados finitos (también conocido como máquinas de estados finitos)

–El punto focal del resto de esta charla.

• Tipo 2 gramáticas :

–Comúnmente usado para analizadores de lenguaje natural.

–Utilizado para modelar la estructura sintáctica en muchas teorías lingüísticas (a menudo complementadas por otros mecanismos)

–Haremos una tirada clave en la próxima charla sobre el análisis.

la mayoría de los XML, como Microsoft DGML (Directed Graph Markup Language) que tiene enlaces inter-relacionales, son ejemplos de que Regex no sirve para nada.

y estas tres respuestas pueden ser útiles:

1 - does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions

2 - regular-expressions-arent

3 - where-do-most-regex-implementations-fall-on-the-complexity-scale

Answer 3

Recientemente escribí un artículo bastante largo sobre este tema: El verdadero poder de las expresiones regulares .

Para resumir:

• Las expresiones regulares que admiten referencias de subpattern recursivos pueden coincidir con todos los lenguajes libres de contexto (por ejemplo, a^nb^n ).
• Las expresiones regulares con aserciones de lookaround y referencias de subpattern pueden coincidir al menos con algunos lenguajes sensibles al contexto (por ejemplo, ww y a^nb^nc^n ).
• Si las aserciones tienen un ancho ilimitado (como usted dice), entonces todas las gramáticas sensibles al contexto pueden coincidir. No conozco ningún tipo de expresión regular, aunque no tiene restricciones de ancho fijo en la apariencia (y al mismo tiempo admite referencias de subpatrón).
• Las expresiones regulares con referencias inversas están completas en NP, por lo que cualquier otro problema de NP se puede resolver utilizando expresiones regulares (después de aplicar una transformación de tiempo polinómico).

Algunos ejemplos:

• Coincidencia con el lenguaje libre de contexto {a^nb^n, n>0} :

  /^(a(?1)?b)$/
  # or
  /^ (?: a (?= a* (/1?+ b) ) )+ /1 $/x

• Coincidencia con el lenguaje sensible al contexto {a^nb^nc^n, n>0} :

  /^
  (?=(a(?-1)?b)c)
  a+(b(?-1)?c)
  $/x
  # or
  /^ (?: a (?= a* (/1?+ b) b* (/2?+ c) ) )+ /1 /2 $/x