regex - probar - Por qué no es posible usar expresiones regulares para analizar HTML/XML: una explicación formal en términos simples
probar expresiones regulares (6)
No hay día en SO que pase sin una pregunta acerca de analizar (X) HTML o XML con expresiones regulares que se le preguntan.
Si bien es relativamente fácil encontrar ejemplos que demuestren la inviabilidad de las expresiones regulares para esta tarea o con una colección de expresiones para representar el concepto, aún no pude encontrar en SO una explicación formal de por qué esto no es posible en personas no expertas. 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 error 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 los idiomas normales, 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 está, y si tiene anidamiento profundo arbitrario, necesita un autómata arbitrariamente grande, que colisiona con la noción de autómata finito.
o:
El lema de Bombeo para idiomas regulares es la razón por la que no puedes hacer eso.
[Para ser justos: la mayoría de las explicaciones anteriores vinculan a las páginas de wikipedia, pero estas no son mucho más fáciles de entender que las respuestas mismas].
Entonces mi pregunta es: ¿ podría alguien proporcionar una traducción en términos simples 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 debía aclarar: estoy buscando una "traducción" que también explique brevemente los conceptos que trata de traducir: al final de una respuesta, el lector debe tener una idea aproximada, por ejemplo - de lo que significa "lenguaje regular" y "gramática libre de contexto" ...
Concéntrese 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 está, y si tiene anidamiento profundo arbitrario, necesita un autómata arbitrariamente grande, que colisiona con la noción de autómata finito.
La definición de expresiones regulares es equivalente al hecho de que una prueba de si una cadena coincide con el patrón puede ser realizada por un autómata finito (un autómata diferente para cada patrón). Un autómata finito no tiene memoria, sin pila, sin montón, sin 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 usar eso para decidir a qué estado pasar. Como casos especiales, tiene dos estados de terminación: "sí, eso coincide" y "no, eso 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, necesitas 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" realmente permiten más que solo la definición estricta de expresiones regulares. Si pueden hacer coincidir referencias anteriores, han ido más allá de un idioma normal. Por lo tanto, la razón por la que no debe usar una biblioteca de expresiones regulares en HTML es un poco más compleja que el simple hecho de que HTML no es regular.
Porque HTML puede tener un anidamiento ilimitado de <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other> y Regex no puede lidiar con eso porque no puede rastrear un historial de lo que desciende y de lo que 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 dentro del div con el ID foo , porque no pueden distinguir la etiqueta de cierre para ese div de la etiqueta de cierre para el div del bar . Eso es porque no tienen forma de decir "está bien, ahora he descendido al segundo de dos divs, así que el siguiente cierre div que veo me devuelve uno, y el siguiente es el cierre para el primero" . Los programadores generalmente responden ideando expresiones regulares de casos especiales para la situación específica, que luego se rompen tan pronto como se introducen más etiquetas dentro de foo y tienen que ser asimiladas a un costo tremendo en tiempo y frustración. Esta es la razón por la cual la gente se enoja por todo el asunto.
Un lenguaje regular es un lenguaje que puede combinarse con una máquina de estados finitos.
(Entender las máquinas de estados finitos, las máquinas de empujar hacia abajo y las máquinas de Turing es básicamente el plan de estudios de un curso de CS de la universidad 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 contra un lenguaje normal, por lo tanto, una expresión regular.
HTML requiere que usted conozca más que solo el estado en el que 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 luego ya no es "regular". Esto se llama una máquina de empuje 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 idioma con anidamiento arbitrario de elementos de idioma, debe recordar qué tan profundo es. Es decir, debe poder contar llaves / corchetes / etiquetas.
No puedes contar con memoria finita. ¡Puede haber más niveles de refuerzo que los que tiene! Es posible que pueda analizar un subconjunto de su idioma que restrinja el número de niveles de anidación, pero sería muy tedioso.
Una gramática es una definición formal de dó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, using significa algo diferente en el using System; en 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"");
}
";
}
El hecho de que el HTML no represente un idioma normal es una pista falsa. La expresión regular y los sonidos regulares suenan de forma similar , pero no lo son, comparten el mismo origen, pero existe una distancia notable entre los "lenguajes regulares" académicos y la potencia coincidente actual de los motores. De hecho, casi todos los motores modernos de expresiones regulares admiten características no regulares; un ejemplo simple es (.*)/1 . que utiliza la referencia inversa para hacer coincidir una secuencia repetida de caracteres, por ejemplo 123123 , o 123123 . La combinación de estructuras recursivas / equilibradas las hacen aún más divertidas.
Wikipedia lo dice muy bien, en una cita de Larry Wall :
Las ''expresiones regulares'' [...] solo están relacionadas marginalmente con expresiones regulares reales. Sin embargo, el término ha crecido con las capacidades de nuestros motores de combinación de patrones, por lo que no voy a tratar de luchar contra la necesidad lingüística aquí. Sin embargo, los llamaré generalmente "regexes" (o "regexen", cuando estoy en un estado de ánimo anglosajón).
"La expresión regular solo puede coincidir con los idiomas normales", 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 el HTML con la expresión regular es que "solo porque puede no significa que deba". Si bien puede ser posible, simplemente hay mejores herramientas para el trabajo . Considerando:
- El HTML válido es más difícil / más complejo de lo que piensas.
- Hay muchos tipos de HTML "válidos": lo que es válido en HTML, por ejemplo, no es válido en XHTML.
- Gran parte del HTML de forma 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 un literal de cadena.
<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 regex que se te pueda ocurrir. Muy a menudo, XPath permite una mejor manera 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 las personas se da cuenta .
Un buen resumen del tema, y un comentario importante sobre cuándo mezclar Regex y HTML puede ser apropiado, puede encontrarse 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 proporcionarle. Aún así, en contra de la opinión popular, hay algunos casos en los que recomiendo utilizar una biblioteca de expresiones regulares y no una de analizadores:
Dadas algunas de estas condiciones:
- Cuando necesita una actualización única de sus archivos HTML, y sabe que la estructura es coherente.
- Cuando tienes 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 quiera cambiar partes del HTML, pero no todas , un analizador, que yo sepa, no puede responder a esta solicitud: analizará el documento completo y guardará un documento completo, cambiando las partes que nunca quiso cambiar.