definicion - title html css

¿HTML es un lenguaje sin contexto? (4)

NO

Ver Editar a continuación

~~Depende.~~

~~Si está hablando del subconjunto que consiste solo en HTML teórico, entonces sí .~~

Si también incluye la vida real, el código HTML de trabajo al que millones de personas acceden y utilizan con éxito todos los días en muchos de los principales sitios de Internet, entonces NO .

Eso es lo que le da flexibilidad HTML. El motor de análisis agrega etiquetas, cierra etiquetas y se ocupa de cosas que un CFG teórico no puede hacer. Si tomó autómatas, puede recordar que una regla de producción en una gramática formal no puede estar vacía (también conocida como epsilon / lambda) en lhs (lado izquierdo). Dado que el motor de análisis utiliza básicamente el conocimiento que una gramática formal y un autómata no podrían tener, no está restringido por eso y la ''gramática'' tendría un resultado epsilon/lambda -> result donde se elige la regla épsilon / lambda específica basada en información no disponible en la gramática.

Como no creo que las gramáticas formales estén permitidas en ninguna gramáticas formales, HTML no puede definirse mediante una gramática formal y no es un lenguaje formal en absoluto.

Claro, HTML5 podría tratar de avanzar hacia una descripción del lenguaje "más formal", pero la probabilidad de que se convierta en un lenguaje libre de contexto en la realidad (es decir, cadenas rechazadas por la gramática) es sobre la probabilidad de que XHTML 2.0 tome al mundo por sorpresa y reemplaza el HTML por completo (XHTML es el intento que hicieron de convertir HTML en un lenguaje formal ... fue rechazado en masa debido a su fragilidad).

¡Vale la pena mencionar que HTML 5 es el PRIMER estándar HTML que se debe definir antes de implementarse! Así es, HTML 1-4 consiste en ideas aleatorias que alguien acaba de implementar en un navegador, y se recopilaron en estándares después del hecho en función de qué características se usaron popularmente y se implementaron ampliamente. Luego probaron XHTML, que no se adoptó por completo. Incluso ''xhtml'' en la web se analiza automáticamente como HTML en casi cualquier circunstancia para evitar que las cosas acaben de romper con un error de sintaxis críptico. Ahora puede ver cómo llegamos aquí y por qué es poco probable que se formalice en el corto plazo.

Lección: "En teoría, no hay diferencia entre la teoría y la práctica. En la práctica, sí existe". - Yogi Berra

EDITAR:

De hecho, después de leer los documentos, resulta que HTML, incluso de acuerdo con la especificación HTML 4.01, en realidad no se ajusta a SGML. Para verlo usted mismo, vea la definición del tipo de documento HTML estricto HTML 4.01 (doctype) en http://www.w3.org/TR/html4/strict.dtd y tenga en cuenta las siguientes líneas:

La especificación HTML 4.01 incluye restricciones sintácticas adicionales que no se pueden expresar dentro de las DTD.

Entonces, diría que probablemente no sea una CFL debido a esas características (aunque técnicamente no refuta la hipótesis de que hay algún PDA posible que acepte HTML 4.01, sí evita el argumento de que SGML es una CFL, por lo tanto, HTML es un CFL).

Flip-flops HTML5, abandonando cualquier conformidad implícita con SGML , pero es presumiblemente descriptible por un CFG. Sin embargo, aún proporcionará un análisis del mejor esfuerzo no basado en un cfg, por lo que IMO la situación actual (es decir, la especificación del lenguaje se define formalmente, con cadenas inválidas aún aceptadas, analizadas y representadas de la mejor manera posible) a este respecto es poco probable que cambiar drásticamente por un largo, largo, largo tiempo.

Leer some questions related me hizo pensar en la naturaleza teórica de HTML.

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

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

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

¿Qué hay de HTML5?

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

El HTML válido no es un lenguaje sin contexto.

En primer lugar, HTML es una aplicación de SGML que 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 observar el algoritmo de análisis HTML realmente definido. Funciona en dos niveles: tokenización y construcción de árboles. Lo que HTML llama a la tokenización es una operación de mayor nivel que lo que habitualmente se llama tokenización cuando se habla de analizadores. En el caso de HTML, la tokenización divide una secuencia de caracteres en unidades como etiquetas de inicio, etiquetas de finalización, comentarios y texto. El tokenizer expande las referencias de caracteres. Por lo general, cuando se habla de analizadores sintácticos, probablemente trataría cosas como el signo menor que "tokens" y consideraría que las referencias de caracteres consisten en tokens en lugar de ser resueltos por el tokenizer.

Si considera el proceso de dividir el flujo de entrada en tokens, ese nivel del lenguaje HTML es regular (a excepción de los comentarios del generador de árbol).

Sin embargo, hay tres complicaciones: la primera es que dividir el flujo de entrada en tokens es solo el primero y luego está el lado del generador de árbol que realmente se preocupa por los identificadores en los tokens. El segundo es que el generador de árboles retroalimenta el tokenizador de modo que algunas transiciones de estado hechas por el tokenizer dependen del estado del generador de árbol. 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 creación de árbol y esas reglas son lo suficientemente complejas como para que no puedan definirse completamente usando autómatas de árbol (como lo demuestra RELAX NG no ser expresivo suficiente para describir todas las restricciones de validez).

Esta no es una prueba real, pero probablemente pueda desarrollar pruebas reales al trabajar con las complicaciones n. ° 2 y n. ° 3.

Tenga en cuenta que el caso de los documentos no válidos no es particularmente interesante como una cuestión de si el lenguaje está 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 tenga una interpretación inteligible en términos del árbol que genera un analizador HTML. El analizador HTML consumirá con éxito todas las cadenas posibles, por lo que en ese sentido, todas las cadenas posibles se encuentran en el lenguaje "HTML no válido".

Editar: preguntas interesantes dejadas como ejercicio para el lector:

¿El HTML no contiene errores de parseo pero ignora la validez de un lenguaje sin contexto?

¿El HTML sin errores de análisis e ignorando la validez general, pero con solo los nombres de elementos válidos, permite un lenguaje sin contexto?

(La complicación n. ° 2 se aplica en ambos casos).

HTML5 es diferente de las versiones HTML anteriores en que define estrictamente el comportamiento del código que no es completamente correcto. Los analizadores pre-HTML5 varían y cada uno hace su mejor esfuerzo para ''adivinar'' la intención del autor del código.

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

X→δ

Esa restricción simple permite que X sea sustituido por el lado derecho de las reglas en el que aparece a la izquierda sin tener en cuenta lo que sucedió antes o después. Por 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→δ

Estos requerirían saber qué se podría derivar alrededor de X para determinar si se aplica una regla, y eso conduce a la no determinación (lo que está cerca de X también le gustaría saber a qué se deriva), que es un no-no en el análisis, y en En cualquier caso, queremos que un idioma esté bien definido.

La única forma de probar que un idioma no tiene contexto es demostrando que hay una gramática libre de contexto para él, lo cual no es una tarea fácil. La mayoría de los lenguajes de programación de los que se habla ya están descritos por los CFG, por lo que el trabajo está hecho. Pero hay otros idiomas, incluidos los lenguajes de programación, que se describen usando lógica o 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 el HTML definido encima también es una CFL. Analizadores y gramáticas para ambos idiomas abundan en la Web. En cualquier caso, la existencia de gramáticas LL (k) para HTML válido es prueba suficiente de que el lenguaje está libre de contexto, porque LL es un subconjunto comprobado de CF.

Pero la forma en que HTML evolucionó a lo largo de la vida de la Web forzó a los navegadores a considerarla como algo no tan bien definido. Los navegadores web modernos harán todo lo posible para tratar de hacer algo sensato con casi cualquier cosa que encuentren. Las gramáticas que utilizan no son CFG, y los analizadores son mucho más complejos que los necesarios para SGML / HTML.

HTML se define en varios niveles.

En el nivel léxico, existen las reglas para caracteres válidos, identificadores, cadenas, etc.
En el siguiente nivel está XML, que consiste en las <tags> apertura y cierre que definen una estructura de documento jerárquica. Puede usar XML o algo parecido a XML para cualquier propósito, como 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, tiene las reglas semánticas sobre lo que significa un documento HTML dado.

La parte sintáctica se define lo suficientemente bien como para poder verified . 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 modelo de objetos del documento (DOM), y cómo un modelo debe representarse en la pantalla.

En el final:

El análisis correcto de HTML es extremadamente sencillo (no tiene contexto y es 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 difícil.