¿Es HTML un lenguaje libre de contexto?

Question

¿Es HTML un lenguaje libre de contexto?

Leyendo algunos relacionados las preguntas me hicieron pensar en la naturaleza teórica del HTML.

No estoy hablando de código similar a XHTML aquí. Estoy hablando de cosas como esta loca pieza de marcado, que es perfectamente válido HTML (!)

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html<head>
<title//
<p ltr<span id=p></span</p>
</>

Así que dada la enorme complejidad que SGML inyecta aquí, ¿es HTML un lenguaje libre de contexto? Es un lenguaje formal de todos modos? Con una gramática?

¿Qué pasa con HTML5?

_{Soy nuevo en el concepto de idiomas formales, así que por favor tengan paciencia conmigo. Y sí, he leído el artículo de wikipedia ;)}

39

html grammar language-theory sgml

Author: Community, 0000-00-00

Source

2 answers

HTML válido no es un lenguaje libre de contexto.

En primer lugar, HTML siendo una aplicación de SGML es ficción para todos los propósitos prácticos, por lo que analizar SGML para responder a la pregunta es inútil. (Sin embargo, la ficción SGML probablemente tampoco está libre de contexto.)

Es más útil mirar el algoritmo de análisis HTML realmente definido. Funciona en dos niveles: tokenización y construcción de árboles. Lo que HTML llama tokenización es una operación de mayor nivel que lo que normalmente se llama tokenización cuando se habla de analizadores. En el caso de HTML, la tokenización divide un flujo de caracteres en unidades como etiquetas de inicio, etiquetas de fin, comentarios y texto. El tokenizador expande las referencias de caracteres. Por lo general, cuando se habla de analizadores, probablemente trataría cosas como el signo menos que como "tokens" y consideraría que las referencias de caracteres consisten en tokens en lugar de ser resueltas por el tokenizador.

Si considera el proceso de dividir el flujo de entrada en tokens, eso el nivel del lenguaje HTML es regular ( excepto para la retroalimentación del creador de árboles).

Sin embargo, hay tres complicaciones: La primera es que dividir el flujo de entrada en tokens es solo la primera y luego está el lado del constructor de árboles que realmente se preocupa por los identificadores en los tokens. La segunda es que el constructor de árboles se retroalimenta en el tokenizador para que algunas transiciones de estado hechas por el tokenizador dependan del estado del constructor de árboles. El tercero es que los documentos válidos en el lenguaje están definidos por reglas que se aplican a la salida de la etapa de constructor de árboles y esas reglas son lo suficientemente complejas como para que no se puedan definir completamente usando autómatas de árboles (como lo demuestra que RELAX NG no es lo suficientemente expresivo como para describir todas las restricciones de validez).

Esto no es una prueba real, pero probablemente puede desarrollar pruebas reales trabajando a partir de las complicaciones #2 y #3.

Tenga en cuenta que el caso de documentos no válidos no es particularmente interesante como una cuestión de si el lenguaje es libre de contexto en el sentido de que hay una gramática libre de contexto que genera todas las cadenas posibles sin tener en cuenta que el árbol de análisis tiene alguna interpretación inteligible en términos del árbol que genera un analizador HTML. El analizador de HTML consumirá con éxito todas las cadenas posibles, por lo que en ese sentido, todas las cadenas posibles están en el lenguaje "HTML no válido".

Editar: Preguntas interesantes dejadas como exerci

14

Author: ,
Warning: date() expects parameter 2 to be long, string given in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61

score 49 · Accepted Answer

Context Free es un concepto de la teoría del lenguaje que tiene implicaciones importantes en la implementación del analizador sintáctico. Un Lenguaje Libre de Contexto se puede describir mediante una Gramática Libre de Contexto, que es una en la que todas las reglas tienen un solo símbolo no terminal a la izquierda de la flecha:

X→δ

Esa simple restricción permite que X se sustituya por el lado derecho de las reglas en el que aparece a la izquierda sin tener en cuenta lo que vino antes o después. Para ejemplo, si al derivar o analizar uno llega a:

αXλ

Uno está seguro de que

αδλ

También Es válido. Ejemplos de reglas sin contexto serían:

XY→δ
Xa→δ
aX→δ

Esos requerirían saber qué se podría derivar alrededor X para determinar si una regla se aplica, y eso conduce al no-determinismo (lo que está alrededor X también quisiera saber a qué se deriva), que es un no-no en el análisis, y en cualquier caso queremos que un lenguaje esté bien definido.

La única manera de demostrar que un lenguaje es libre de contexto es demostrando que hay una gramática libre de contexto para él, que no es una tarea fácil. La mayoría de los lenguajes de programación que se producen ya están descritos por CFGs, por lo que el trabajo está hecho. Pero hay otros lenguajes, incluyendo lenguajes de programación, que se describen usando la lógica o el inglés simple, por lo que se requiere trabajo para encontrar si están libres de contexto.

Para HTML, la respuesta sobre su libertad de contexto es sí. SGML es un Lenguaje libre de Contexto bien definido, y HTML definido en la parte superior es también una CFL. Los analizadores y gramáticas para ambos idiomas abundan en la Web. En cualquier caso, que existan gramáticas LL(k) para HTML válido es suficiente prueba de que el lenguaje es libre de contexto, porque LL es un subconjunto probado de CF.

Pero la forma en que HTML evolucionó a lo largo de la vida de la Web obligó a los navegadores a tratarlo como si no estuviera tan bien definido. Los navegadores web modernos harán todo lo posible para tratar de hacer algo sensible de casi cualquier cosa encuentran. Las gramáticas que utilizan no son CFGs, y los analizadores son mucho más complejos que los requeridos para SGML/HTML.

HTML se define en varios niveles.

A nivel léxico están las reglas para caracteres válidos, identificadores, cadenas, etc.
En el siguiente nivel está XML, que consiste en la apertura y el cierre <tags> que definen una estructura jerárquica del documento. Puede usar XML o algo similar a XML para cualquier propósito, como lo hace Apache Ant para construir scripts.
En el siguiente nivel están las etiquetas que son válidas en HTML, y las reglas sobre qué etiquetas pueden anidarse dentro de qué etiquetas.
En el siguiente nivel están las reglas sobre qué atributos son válidos para qué etiquetas, idiomas que se pueden incrustar en HTML como CSS y JavaScript.
Finalmente, tenemos las reglas semánticas sobre lo que significa un documento HTML dado.

La parte sintáctica está lo suficientemente bien definida como para que pueda ser verificada. El la parte semántica es mucho más grande que la sintáctica, y se define en términos de acciones del navegador con respecto a HTTP, y el Document Object Model (DOM), y cómo se debe representar un modelo en la pantalla.

Al final:

Analizar HTML correctamente es extremadamente fácil (es libre de contexto y LL/LR).
Analizar el HTML que realmente existe en la Web es difícil.
Implementar la semántica (un navegador) sobre HTML / CSS / DOM es extremadamente complicado.