Por qué no es posible usar expresiones regulares para analizar HTML / XML: una explicación formal en términos simples

No hay día en SO que pase sin una pregunta sobre el análisis de (X) HTML o XML con expresiones regulares.

Si bien es relativamente fácil encontrar ejemplos que demuestren la no viabilidad de las expresiones regulares para esta tarea o con una colección de expresiones para representar el concepto, todavía no pude encontrar en SO una explicación formal de por qué esto no es posible hecho en laicos condiciones.

Las únicas explicaciones formales que pude encontrar hasta ahora en este sitio son probablemente extremadamente precisas, pero también bastante crípticas para el programador autodidacta:

el defecto aquí es que HTML es una gramática Chomsky Tipo 2 (gramática libre de contexto) y RegEx es una gramática Chomsky Tipo 3 (expresión regular)

o:

Las expresiones regulares solo pueden coincidir con lenguajes regulares, pero HTML es un lenguaje sin contexto.

o:

Un autómata finito (que es la estructura de datos que subyace a una expresión regular) no tiene memoria aparte del estado en el que se encuentra, y si tiene una anidación arbitrariamente profunda, necesita un autómata arbitrariamente grande, que choca con la noción de un autómata finito.

o:

El lema de Bombeo para idiomas regulares es la razón por la que no puede hacer eso.

[Para ser justos: la mayoría de las explicaciones anteriores enlazan con páginas de wikipedia, pero estas no son mucho más fáciles de entender que las propias respuestas].

Entonces, mi pregunta es: ¿ podría alguien proporcionar una traducción en términos sencillos de las explicaciones formales dadas anteriormente de por qué no es posible usar expresiones regulares para analizar (X) HTML / XML?

EDITAR: Después de leer la primera respuesta, pensé que debería aclarar: estoy buscando una "traducción" que también explique brevemente los conceptos que intenta traducir: al final de una respuesta, el lector debe tener una idea aproximada, por ejemplo - de lo que significan "lenguaje regular" y "gramática libre de contexto" ...

Concéntrate en este:

Un autómata finito (que es la estructura de datos que subyace a una expresión regular) no tiene memoria aparte del estado en el que se encuentra, y si tiene una anidación arbitrariamente profunda, necesita un autómata arbitrariamente grande, que choca con la noción de un autómata finito.

La definición de expresiones regulares es equivalente al hecho de que un autómata finito (un autómata diferente para cada patrón) puede realizar una prueba de si una cadena coincide con el patrón. Un autómata finito no tiene memoria, no hay pila, no hay montón, no hay cinta infinita para garabatear. Todo lo que tiene es un número finito de estados internos, cada uno de los cuales puede leer una unidad de entrada de la cadena que se está probando y usarla para decidir a qué estado pasar al siguiente. Como casos especiales, tiene dos estados de terminación: "sí, que coincide" y "no, que no coincide".

HTML, por otro lado, tiene estructuras que pueden anidar arbitrariamente en profundidad. Para determinar si un archivo es HTML válido o no, debe verificar que todas las etiquetas de cierre coincidan con una etiqueta de apertura anterior. Para entenderlo, necesita saber qué elemento se está cerrando. Sin ningún medio para "recordar" qué etiquetas de apertura has visto, no hay posibilidad.

Sin embargo, tenga en cuenta que la mayoría de las bibliotecas "regex" permiten algo más que la definición estricta de expresiones regulares. Si pueden hacer coincidir las referencias anteriores, entonces han ido más allá de un lenguaje normal. Entonces, la razón por la que no debería usar una biblioteca de expresiones regulares en HTML es un poco más compleja que el simple hecho de que HTML no es regular.

El hecho de que HTML no represente un lenguaje regular es una pista falsa. Las expresiones regulares y los lenguajes regulares suenan algo similar , pero no lo son; comparten el mismo origen, pero hay una distancia notable entre los "lenguajes regulares" académicos y la potencia de coincidencia actual de los motores. De hecho, casi todos los motores de expresiones regulares modernos admiten características no regulares; un ejemplo simple es (.*)\1. que utiliza referencias inversas para hacer coincidir una secuencia repetida de caracteres, por ejemplo 123123, o bonbon. La combinación de estructuras recursivas / equilibradas las hace aún más divertidas.

Wikipedia dice esto muy bien, en una cita de Larry Wall :

Las 'expresiones regulares' [...] sólo están relacionadas marginalmente con expresiones regulares reales. Sin embargo, el término ha crecido con las capacidades de nuestros motores de coincidencia de patrones, por lo que no voy a intentar luchar contra la necesidad lingüística aquí. Sin embargo, generalmente los llamaré "regexes" (o "regexen", cuando estoy de humor anglosajón).

"La expresión regular sólo puede coincidir con lenguajes regulares", como puede ver, no es más que una falacia comúnmente declarada.

Entonces, ¿por qué no entonces?

Una buena razón para no hacer coincidir HTML con expresiones regulares es que "solo porque puedas no significa que debas". Si bien puede ser posible, simplemente existen mejores herramientas para el trabajo . Considerando:

• HTML válido es más difícil / más complejo de lo que piensas.
• Hay muchos tipos de HTML "válido"; lo que es válido en HTML, por ejemplo, no es válido en XHTML.
• Gran parte del HTML de formato libre que se encuentra en Internet no es válido de todos modos . Las bibliotecas HTML también hacen un buen trabajo al tratar con estos y se probaron para muchos de estos casos comunes.

• Muy a menudo, es imposible hacer coincidir una parte de los datos sin analizarlos como un todo. Por ejemplo, es posible que esté buscando todos los títulos y termine haciendo coincidir dentro de un comentario o una cadena literal. <h1>.*?</h1>puede ser un intento audaz de encontrar el título principal, pero podría encontrar:

  <!-- <h1>not the title!</h1> -->

  O incluso:

  <script>
  var s = "Certainly <h1>not the title!</h1>";
  </script>

El último punto es el más importante:

• Usar un analizador HTML dedicado es mejor que cualquier expresión regular que se le ocurra. Muy a menudo, XPath permite una forma más expresiva de encontrar los datos que necesita, y usar un analizador HTML es mucho más fácil de lo que la mayoría de la gente cree .

Se puede encontrar un buen resumen del tema y un comentario importante sobre cuándo mezclar Regex y HTML puede ser apropiado en el blog de Jeff Atwood: Parsing Html The Cthulhu Way .

¿Cuándo es mejor usar una expresión regular para analizar HTML?

En la mayoría de los casos, es mejor usar XPath en la estructura DOM que una biblioteca puede ofrecerle. Aún así, en contra de la opinión popular, hay algunos casos en los que recomendaría encarecidamente usar una expresión regular y no una biblioteca de analizador:

Dadas algunas de estas condiciones:

• Cuando necesite una actualización única de sus archivos HTML y sepa que la estructura es coherente.
• Cuando tiene un fragmento muy pequeño de HTML.
• Cuando no se trata de un archivo HTML, sino de un motor de plantillas similar (puede ser muy difícil encontrar un analizador en ese caso).
• Cuando desee cambiar partes del HTML, pero no todo , un analizador, que yo sepa, no puede responder a esta solicitud: analizará todo el documento y guardará un documento completo, cambiando partes que nunca quiso cambiar.

Porque HTML puede tener un anidamiento ilimitado <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>y regex realmente no puede hacer frente a eso porque no puede rastrear un historial de lo que desciende y sale.

Una construcción simple que ilustra la dificultad:

<body><div id="foo">Hi there!  <div id="bar">Bye!</div></div></body>

El 99,9% de las rutinas de extracción basadas en expresiones regulares generalizadas no podrán darme correctamente todo lo que hay dentro de la divID foo, porque no pueden distinguir la etiqueta de cierre para ese div de la etiqueta de cierre para el bardiv. Esto se debe a que no tienen forma de decir "está bien, ahora he descendido al segundo de dos divs, por lo que el siguiente cierre de div que veo me devuelve uno, y el siguiente es la etiqueta de cierre del primero". . Los programadores normalmente responden ideando expresiones regulares en casos especiales para la situación específica, que luego se rompen tan pronto como se introducen más etiquetas en el interior fooy tienen que desenredarse a un costo tremendo en tiempo y frustración. Es por eso que la gente se enoja por todo esto.

Un lenguaje regular es un lenguaje que puede ser igualado por una máquina de estados finitos.

(Comprender las máquinas de estado finito, las máquinas de empuje hacia abajo y las máquinas de Turing es básicamente el plan de estudios de un curso de informática universitaria de cuarto año).

Considere la siguiente máquina, que reconoce la cadena "hola".

(Start) --Read h-->(A)--Read i-->(Succeed)
  \                  \
   \                  -- read any other value-->(Fail) 
    -- read any other value-->(Fail)

Esta es una máquina simple para reconocer un lenguaje regular; Cada expresión entre paréntesis es un estado y cada flecha es una transición. Construir una máquina como esta le permitirá probar cualquier cadena de entrada con un lenguaje regular, por lo tanto, una expresión regular.

HTML requiere que sepa más que solo en qué estado se encuentra: requiere un historial de lo que ha visto antes, para que coincida con el anidamiento de etiquetas. Puede lograr esto si agrega una pila a la máquina, pero entonces ya no es "normal". A esto se le llama máquina Push-down y reconoce una gramática.

Una expresión regular es una máquina con un número finito (y típicamente bastante pequeño) de estados discretos.

Para analizar XML, C o cualquier otro lenguaje con anidamiento arbitrario de elementos del lenguaje, debe recordar qué tan profundo es. Es decir, debe poder contar llaves / corchetes / etiquetas.

No se puede contar con memoria finita. ¡Puede haber más niveles de aparatos ortopédicos que estados! Es posible que pueda analizar un subconjunto de su idioma que restrinja el número de niveles de anidamiento, pero sería muy tedioso.

Una gramática es una definición formal de adónde pueden ir las palabras. Por ejemplo, los adjetivos preceden a los sustantivos in English grammar, pero siguen a los sustantivos en la gramática española. Libre de contexto significa que la gramática es universal en todos los contextos. Sensible al contexto significa que hay reglas adicionales en ciertos contextos.

En C #, por ejemplo, usingsignifica algo diferente en using System;la parte superior de los archivos que using (var sw = new StringWriter (...)). Un ejemplo más relevante es el siguiente código dentro del código:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

Hay otra razón práctica para no usar expresiones regulares para analizar XML y HTML que no tiene nada que ver con la teoría de la informática: su expresión regular será horriblemente complicada o estará mal.

Por ejemplo, está muy bien escribir una expresión regular para que coincida

<price>10.65</price>

Pero si su código debe ser correcto, entonces:

• Debe permitir espacios en blanco después del nombre del elemento tanto en la etiqueta inicial como en la final.

• Si el documento está en un espacio de nombres, entonces debe permitir que se use cualquier prefijo de espacio de nombres

• Probablemente debería permitir e ignorar cualquier atributo desconocido que aparezca en la etiqueta de inicio (dependiendo de la semántica del vocabulario particular)

• Es posible que deba permitir espacios en blanco antes y después del valor decimal (nuevamente, dependiendo de las reglas detalladas del vocabulario XML en particular).

• No debe coincidir con algo que parezca un elemento, pero que en realidad esté en un comentario o en una sección CDATA (esto se vuelve especialmente importante si existe la posibilidad de que datos maliciosos intenten engañar a su analizador).

• Es posible que deba proporcionar diagnósticos si la entrada no es válida.

Por supuesto, algo de esto depende de los estándares de calidad que esté aplicando. Vemos muchos problemas en StackOverflow con personas que tienen que generar XML de una manera particular (por ejemplo, sin espacios en blanco en las etiquetas) porque lo está leyendo una aplicación que requiere que se escriba de una manera particular. Si su código tiene algún tipo de longevidad, entonces es importante que pueda procesar XML entrante escrito de cualquier manera que permita el estándar XML, y no solo el documento de entrada de muestra en el que está probando su código.

En un sentido puramente teórico, es imposible que las expresiones regulares analicen XML. Se definen de una manera que no les permite la memoria de ningún estado anterior, lo que evita la coincidencia correcta de una etiqueta arbitraria, y no pueden penetrar a una profundidad arbitraria de anidación, ya que la anidación debería incorporarse a la expresión regular.

Los analizadores de expresiones regulares modernos, sin embargo, están diseñados para su utilidad para el desarrollador, en lugar de su adherencia a una definición precisa. Como tal, tenemos cosas como referencias inversas y recursividad que hacen uso del conocimiento de estados anteriores. Con estos, es muy sencillo crear una expresión regular que pueda explorar, validar o analizar XML.

Considere, por ejemplo,

(?:
    <!\-\-[\S\s]*?\-\->
    |
    <([\w\-\.]+)[^>]*?
    (?:
        \/>
        |
        >
        (?:
            [^<]
            |
            (?R)
        )*
        <\/\1>
    )
)

Esto encontrará la siguiente etiqueta XML o comentario correctamente formado, y solo lo encontrará si todo su contenido está correctamente formado. (Esta expresión ha sido probada usando Notepad ++, que usa la biblioteca de expresiones regulares de Boost C ++, que se aproxima mucho a PCRE).

Así es como funciona:

1. El primer fragmento coincide con un comentario. Es necesario que esto sea lo primero para que se ocupe de cualquier código comentado que, de lo contrario, podría causar bloqueos.
2. Si eso no coincide, buscará el comienzo de una etiqueta. Tenga en cuenta que utiliza paréntesis para capturar el nombre.
3. Esta etiqueta terminará en a />, completando así la etiqueta, o terminará con a >, en cuyo caso continuará examinando el contenido de la etiqueta.
4. Continuará analizando hasta que llegue a <, en cuyo punto volverá al principio de la expresión, lo que le permitirá tratar con un comentario o una nueva etiqueta.
5. Continuará a través del bucle hasta que llegue al final del texto o en un punto <que no pueda analizar. No hacer coincidir, por supuesto, hará que el proceso comience de nuevo. De lo contrario, <es presumiblemente el comienzo de la etiqueta de cierre para esta iteración. Usando la referencia inversa dentro de una etiqueta de cierre <\/\1>, coincidirá con la etiqueta de apertura para la iteración actual (profundidad). Solo hay un grupo de captura, por lo que esta coincidencia es un asunto simple. Esto lo hace independiente de los nombres de las etiquetas utilizadas, aunque puede modificar el grupo de captura para capturar solo etiquetas específicas, si es necesario.
6. En este punto, saldrá de la recursividad actual, pasará al siguiente nivel o terminará con una coincidencia.

Este ejemplo resuelve problemas relacionados con los espacios en blanco o la identificación de contenido relevante mediante el uso de grupos de caracteres que simplemente niegan <o >, en el caso de los comentarios, mediante el uso [\S\s], que coincidirá con cualquier cosa, incluidos los retornos de carro y las nuevas líneas, incluso en una sola línea. modo, continuando hasta que llegue a -->. Por lo tanto, simplemente trata todo como válido hasta que llega a algo significativo.

Para la mayoría de los propósitos, una expresión regular como esta no es particularmente útil. Validará que XML está formado correctamente, pero eso es todo lo que realmente hará, y no tiene en cuenta las propiedades (aunque esto sería una adición fácil). Es así de simple porque omite problemas del mundo real como este, así como las definiciones de los nombres de las etiquetas. Ajustarlo para un uso real lo convertiría en una bestia. En general, un verdadero analizador XML sería muy superior. Este es probablemente el más adecuado para enseñar cómo funciona la recursividad.

En pocas palabras: use un analizador XML para el trabajo real y utilícelo si quiere jugar con las expresiones regulares.

No analice XML / HTML con expresiones regulares, utilice un analizador XML / HTML adecuado y un potente xpath consulta.

teoría:

De acuerdo con la teoría de la compilación, XML / HTML no se puede analizar usando expresiones regulares basadas en una máquina de estado finito . Debido a la construcción jerárquica de XML / HTML, necesita utilizar un autómata pushdown y manipular la gramática LALR utilizando una herramienta como YACC .

realLife © ® ™ herramienta diaria en un cáscara :

Puede utilizar uno de los siguientes:

xmllint a menudo se instala de forma predeterminada con libxml2, xpath1 (verifique mi contenedor para tener una salida delimitada por nuevas líneas

xmlstarlet puede editar, seleccionar, transformar ... No está instalado por defecto, xpath1

xpath instalado a través del módulo XML de perl :: XPath, xpath1

xidel xpath3

saxon-lint mi propio proyecto, envoltorio sobre la biblioteca de Java Saxon-HE de @Michael Kay, xpath3

o puede usar lenguajes de alto nivel y bibliotecas adecuadas, pienso en:

pitón's lxml( from lxml import etree)

perl's XML::LibXML, XML::XPath, XML::Twig::XPath,HTML::TreeBuilder::XPath

rubí nokogiri, mira este ejemplo

php DOMXpath, mira este ejemplo

Verificación: uso de expresiones regulares con etiquetas HTML