Hágalo usted mismo analizando arte o DOM

Hola Habr! Recientemente, se me ocurrió la idea de crear un lenguaje de marcado simple como Markdown, que sería perfecto para mis tareas, a saber, la escritura rápida de conferencias con formato y la capacidad de insertar fórmulas matemáticas "sobre la marcha", usando solo un teclado. Para traducir el texto escrito en este formato a una forma más comprensible, por ejemplo, un documento de LibreOffice Writer, necesita un analizador , en otras palabras, un analizador . Como solía hacer bicicletas, fui a los motores de búsqueda con las consultas "ejemplo de analizador", "html a DOM", "cómo analizar html", etc. Para mi decepción, en todos los recursos encontrados, ejemplos elementales como la calculadora Straustrup con recursivo por descenso, o se utilizaron soluciones ya preparadas como flex, bison, llvm y yacc. Incluso había más bibliotecas destinadas a analizar lenguajes estrictamente definidos (gumbo, jsoup, rapidjson, herramientas Qt, etc.) Ni una ni la otra formaban parte de mis planes para escribir mi propio analizador de marcado en C ++ usando solo la biblioteca estándar, por lo que mi En lugar de recursos electrónicos, los manuales de los institutos técnicos se convirtieron en una fuente de conocimiento sobre el arte del análisis. Sobre cómo tomar el texto y construir AST (árbol de sintaxis abstracta) a partir de él, sobre algunos de los escollos que encontré en el proceso, hoy les contaré sobre posibles errores.

Haré una reserva de inmediato: si su objetivo es su propio lenguaje de secuencias de comandos o incluso más complicado, este artículo no será suficiente para su implementación. Idealmente, debe conocer perfectamente la teoría de los autómatas y las estructuras discretas. Pero por ahora, como punto de partida, puedo limitarme a mi experiencia, que generosamente comparto bajo el corte. Esto no es exactamente lo que pretendía originalmente, pero es ideal como ejemplo. Analizaremos HTML como un lenguaje simple y familiar.

En primer lugar, analizar o analizar no es sinónimo del proceso completo de convertir texto en un modelo de objeto. El proceso en sí consta de dos etapas:

1. El análisis léxico del texto en tokens son pequeñas piezas de este texto que tienen un cierto significado sintáctico.
2. El análisis es la construcción de tokens en función de sus valores de un árbol de sintaxis abstracta (AST - árbol de sintaxis abstracta), o un modelo de objeto de documento (DOM - modelo de objeto de documento).

Pero pongámoslo en orden. Antes de abrir su IDE favorito y escribir código, debe desarrollar una gramática del lenguaje futuro. De las gramáticas formales libres de contexto, las más famosas son la forma Backus-Naur (BNF) y la forma extendida Backus-Naur . Usé su simbiosis, tomando lo mejor de ambas formas. Cualquier expresión se puede definir a través de otras expresiones de la siguiente manera:

<> = <_1> <_> <_2> 

Aquí una expresión se define a través de otras tres que siguen una tras otra. Ellos, a su vez, también deben representarse a través de "terceras" expresiones, etc.

¿Cuándo parar?

La descripción de la sintaxis de cualquier lenguaje en gramáticas formales consta de dos tipos de tokens: terminales y no terminales . Los no terminales son expresiones que deben definirse:

 <_1> = <> (<_> | <_>) <> 

Los terminales son autosuficientes, no necesitan ser definidos. Los ejemplos anteriores se pueden escribir así:

 <> = <_1> "+" <_2> <_1> = <> ("*" | "/") <> 

donde "+", "*", "/" son los terminales.
Debe seleccionar los terminales de la gramática de inmediato, incluso puede escribirlos en una lista separada en la parte inferior de las definiciones principales; serán útiles más adelante.

Una descripción completa de BNF está disponible en Wikipedia aquí y aquí . Compilar una gramática de un idioma es una etapa importante en la creación de un lenguaje que no tolera la frivolidad. Un error en él puede conducir a un código completamente inoperativo, que deberá reescribirse desde cero. Por lo tanto, antes de dar el siguiente paso, asegúrese de que no haya problemas controvertidos en la gramática compilada. Si tiene dos monitores, será conveniente que ocupe un monitor con un documento de gramática para el resto de su trabajo, de modo que pueda mover rápidamente los ojos cuando codifique. Créeme, tienes que hacer esto todo el tiempo. Aquí está mi gramática HTML5 BNF compilada:

 (* document *) <document> = {<document_part>} <END> <document_part> = <block> | <empty_tag> | <comment> | <macro_tag> | <text> <block> = <opening_tag> {<document_part>} <closing_tag> (* tags *) <opening_tag> = "<" {<ws>} <block_tag_name> [<attributes_list>] {<ws>} ">" <closing_tag> = "<" "/" {<ws>} <block_tag_name> {<ws>} ">" <empty_tag> = "<" "!" {<ws>} <empty_tag_name> [<attributes_list] {<ws>} ["/"] ">" <comment> = "<" "!" "--" <comment_text> "--" ">" <macro_tag> = "<" "?" <macro_text> "?" ">" <block_tag_name> = "a" | "abbr" | "address" | "article" | "aside" | "audio" | "b" | "bdo" | "blockquote" | "body" | "button" | "canvas" | "caption" | "cite" | "code" | "colgroup" | "data" | "datalist" | "dd" | "del" | "details" | "dfn" | "dialog" | "div" | "dl" | "dt" | "em" | "fieldset" | "figcaption" | "figure" | "footer" | "form" | "h1" | "h2" | "h3" | "h4" | "h5" | "h6" | "head" | "header" | "html" | "i" | "iframe" | "ins" | "kbd" | "label" | "legend" | "li" | "main" | "map" | "mark" | "meter" | "nav" | "noscript" | "object" | "ol" | "optgroup" | "option" | "output" | "p" | "picture" | "pre" | "progress" | "q" | "ruby" | "rb" | "rt" | "rtc" | "rp" | "s" | "samp" | "script" | "section" | "select" | "small" | "span" | "strong" | "style" | "sub" | "summary" | "sup" | "table" | "tbody" | "td" | "template" | "textarea" | "tfoot" | "th" | "thead" | "time" | "title" | "tr" | "track" | "u" | "ul" | "var" | "video" <empty_tag_name> = "area" | "base" | "br" | "col" | "embed" | "hr" | "img" | "input" | "link" | "menuitem" | "meta" | "param" | "source" | "track" | "wbr" (* attributes *) <attributes_list> = <ws> {<ws>} <attribute> {<ws> {<ws>} <attribute>} <attribute> = <empty_attribute> | <unquoted_attribute> | <single_quoted_attribute> | <double_quoted_attribute> <empty_attribute> = <attribute_name> <unquoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} <unquoted_attribute_value> <single_quoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} "'" <single_quoted_attribute_value> "'" <double_quoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} "\"" <double_quoted_attribute_value> "\"" <attribute_name> = (<letter> | <digit>) {<letter> | <digit>} {* attribute values *) <unquoted_attribute_value> = /^[\s"'=<>/]/ {/^[\s"'=<>/]/} <single_quoted_attribute_value> = /^[']/ {/^[']/} <double_quoted_attribute_value> = /^["]/ {/^["]/} (* nonterminals *) <text> = {/^[<>]/} <comment_text> = ... <macro_text> = ... <letter> = /[a-zA-Z]/ <digit> = /[0-9]/ <ws> = " " | "\t" | "\n" (* terminals *) "<", ">", "/", "!", "?", " ", "\t", "\n" 

Cuando la gramática está lista, puede pasar al analizador léxico (otro nombre para el analizador léxico, porque además del análisis, identifica errores léxicos en el documento). A primera vista, todo es simple: absorber caracteres, escribir en el búfer y, cuando se detecta un terminal clave, determinar el token recibido como un token con cierto tipo, ¿verdad? Sí, solo el tipo de token aquí importa más que el símbolo. Te lo explicaré ahora. Por supuesto, el procedimiento de desmontaje (ifsteam y archivo) debe contener un bucle que lee un carácter de la secuencia de entrada y lo envía al procedimiento de proceso (const char & c), donde se procesa este carácter. Parece que el procedimiento del proceso debe contener el interruptor ©, donde cada símbolo de tecla tiene sus propias funciones, según el tipo de token actual. De hecho, lo contrario es cierto: es mejor usar el interruptor para verificar el tipo de token y definir funciones para los caracteres. Además, el token actual suele tener un tipo indefinido, uno de muchos. Por ejemplo, después de abrir el paréntesis angular, puede ver: apertura, cierre, etiquetas vacías, así como un comentario de estilo HTML o una etiqueta macro (script PHP encerrado en "<? ...?>". Y para todas estas uniones necesita su propio caso. ¿Cómo es esto? implementar? Usando banderas de bits. Deje que se dé un número finito de tipos de token (cuanto más mejor, ya que la tarea del analizador léxico es dejar el menor trabajo posible para la sintaxis). Para cada tipo, se da un número único de grado dos (1, 2, 4, 8 etc.) Luego en formato binario se verán así: 0001, 0010, 0 100, etc., y con la adición de cualquier número de cualquier tipo, se obtendrá un número único. Si la descripción del texto es difícil de entender, le daré el código. Aquí está la definición de los tipos:

 enum Token_type { END = 1, TEXT = 2, OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO_TAG = 64, ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBLE_QUOTED_ATTRIBUTE_VALUE = 1024 }; 

Proceso de procedimiento truncado:

 void Lexer::process (const char &c) { switch (curr_token_type) { case END: { throw string("unexpected ending!"); break; } case TEXT: { if (c == '>') throw string("unexpected symbol: \">\"!"); else if (c == '<') { if (!buffer.empty()) { add(buffer, TEXT); buffer.clear(); } curr_token_type = OPENING_BLOCK_TAG_NAME | CLOSING_BLOCK_TAG_NAME | EMPTY_TAG_NAME | COMMENT | MACRO_TAG; } else buffer.push_back(c); break; } case OPENING_BLOCK_TAG_NAME: { throw string("error!"); break; } case CLOSING_BLOCK_TAG_NAME: { if (c == '<') throw string("unexpected symbol: \"<\"!"); else if (c == '/') throw string("unexpected symbol: \"<\"!"); else if (c == '!') throw string("unexpected symbol: \"!\"!"); else if (c == '?') throw string("unexpected symbol: \"?\"!"); else if (c == ' ') throw string("unexpected symbol: \" \"!"); else if (c == '\t') throw string("unexpected symbol: \"\\t\"!"); else if (c == '\n') throw string("unexpected symbol: \"\\n\"!"); else if (c == '>') { for (unsigned int i(0); i < BLOCK_TAGS_COUNT; i++) if (buffer == block_tags[i]) { add(buffer, CLOSING_BLOCK_TAG_NAME); buffer.clear(); curr_token_type = TEXT; break; } } else buffer.push_back(c); break; } case EMPTY_TAG_NAME: { throw string("error!"); break; } case COMMENT: { ... break; } case MACRO_TAG: { ... break; } case OPENING_BLOCK_TAG_NAME | CLOSING_BLOCK_TAG_NAME | EMPTY_TAG_NAME | COMMENT | MACRO_TAG: { ... break; } case EMPTY_TAG_NAME | COMMENT: { ... break; } case ATTRIBUTE_NAME: { ... break; } case ATTRIBUTE_NAME | UNQUOTED_ATTRIBUTE_VALUE | SINGLE_QUOTED_ATTRIBUTE_VALUE | DOUBLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } case UNQUOTED_ATTRIBUTE_VALUE | SINGLE_QUOTED_ATTRIBUTE_VALUE | DOUBLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } case UNQUOTED_ATTRIBUTE_VALUE: { ... break; } case SINGLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } case DOUBLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } } } 

Verificamos con el interruptor el tipo de token esperado (o tokens), y dentro de cada caso determinamos los procedimientos para cada uno de los terminales clave. No hay tantas funciones, todos realizan acciones simples: ya sea agregando un carácter al búfer, o volcando el búfer en el siguiente token, o cambiando el tipo esperado de token (s), o lanzando una excepción. Es fácil determinar el procedimiento deseado usando la gramática escrita arriba usando un editor de texto de búsqueda. Simplemente busque todas las inclusiones del token esperado (tokens) en las definiciones de otras expresiones, luego la inclusión de estas expresiones en el "tercero", etc. Aquí hay un ejemplo para una etiqueta de apertura en un editor de texto gedit:



Al principio, navegar la gramática es difícil, pero con el tiempo y la experiencia, no se vuelve más complicado que dividir la columna. Y aquí está el procedimiento de desmontaje:

 void Lexer::disassemble (ifstream &file) { tokens_count = 0; curr_token_type = 0; unsigned long line(1), pos(1); try { char c; curr_token_type = TEXT; while ((c = file.get()) != EOF) { if (c == '\n') { pos = 1; line++; } else pos++; process(c); } if (buffer.size() != 0) { if (!(curr_token_type | TEXT)) throw string("text was expected!"); add(buffer, TEXT); buffer.clear(); } add("", END); } catch (const string &error) { throw string("lexer: " + to_string(line) + "," + to_string(pos) + ": " + error); } } 

El primer token esperado es obviamente necesario para establecer el tipo en TEXT, y al final agregar el token de tipo END con cualquier texto (o vacío, como aquí).

Por ejemplo, tomé una de mis plantillas de documentos HTML con un comentario, le agregué un script pseudo-PHP, la procesé con un lexer y mostré una lista de tokens en el formato "[" <token_text> ": <token_type>]". Esto es lo que sucedió:



Ahora estamos listos para comenzar la segunda parte: la construcción de un árbol de sintaxis. Como nuestras etiquetas tienen atributos, los nodos del árbol, además de la comunicación con otros nodos, contendrán conjuntos de pares clave-valor. La construcción resultante puede llamarse legítimamente el modelo de objeto del documento DOM mencionado en el título del artículo.

¿Cuántas clases necesitas para implementar todas las propiedades de los elementos HTML?

Idealmente, hay una clase para cada elemento para que las hojas de estilo en cascada se puedan definir para ellos, pero nos limitaremos a tres: una etiqueta "Nodo" vacía, un bloque "Bloque" heredado (contenido encerrado entre dos etiquetas emparejadas) y heredado de él con la raíz del árbol raíz. También definimos en el analizador un conjunto de etiquetas que pueden contener texto, como <p>, <li>, <strong>, etc., para eliminar tokens con texto no colocado. Ahora depende de los pequeños. Si ha trabajado bien en el analizador léxico, la tarea del sintáctico es simplemente absorber tokens y realizar una de tres operaciones en el nodo abierto: agregue un nodo vacío, abra uno nuevo o ciérrelo usted mismo devolviendo el puntero al padre. Para este último, se requiere que todas las clases, comenzando con el Nodo base, contengan dicho puntero obtenido al crear el elemento. Este proceso se llama análisis de arriba hacia abajo .

Procedimiento de análisis:

 void Parser::parse (const Lexer &lexer) { Block * open_block = (Block*) tree; Node * last_node = (Node*) tree; try { unsigned long long size = lexer.count(); for (unsigned long long i(0); i < size-2; i++) { switch (lexer[i].type) { case Lexer::TEXT: { for (unsigned int j(0); j < TEXT_TAGS_COUNT; j++) if (open_block->get_name() == text_tags[j]) last_node = open_block->add("TEXT", lexer[i].lexeme); break; } case Lexer::OPENING_BLOCK_TAG_NAME: { last_node = open_block = open_block->open(lexer[i].lexeme); break; } case Lexer::CLOSING_BLOCK_TAG_NAME: { if (lexer[i].lexeme != open_block->get_name()) throw string("unexpected closing tag: </" + lexer[i].lexeme + ">"); open_block = open_block->close(); break; } case Lexer::EMPTY_TAG_NAME: { last_node = open_block->add(lexer[i].lexeme); break; } case Lexer::COMMENT: { last_node = open_block->add("COMMENT", lexer[i].lexeme); break; } case Lexer::MACRO_TAG: { last_node = open_block->add("MACRO", lexer[i].lexeme); break; } case Lexer::ATTRIBUTE_NAME: { last_node->add_attr(lexer[i].lexeme, lexer[i].lexeme); break; } case Lexer::UNQUOTED_ATTRIBUTE_VALUE: { last_node->set_last_attr(lexer[i].lexeme); break; } case Lexer::SINGLE_QUOTED_ATTRIBUTE_VALUE: { last_node->set_last_attr(lexer[i].lexeme); break; } case Lexer::DOUBLE_QUOTED_ATTRIBUTE_VALUE: { last_node->set_last_attr(lexer[i].lexeme); break; } case Lexer::END: { if (open_block->get_type() != Node::ROOT) throw string("unexpected ending!"); open_block->close(); } } } } catch (const string &error) { throw string("parser: " + error); } } 

Eso es todo! Si hizo todo correctamente, se puede mostrar el árbol resultante:

 El | 
 + - <ROOT>
   El | 
   + - <! DOCTYPE>
   El | 
   + - <html>
     El | 
     + - <head>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <meta>
     El |  El | 
     El |  + - <título>
     El |  El | 
     El |  + - <enlace>
     El |  El | 
     El |  + - <enlace>
     El |  El | 
     El |  + - <COMENTARIO>
     El | 
     + - <cuerpo>
       El | 
       + - <encabezado>
       El |  El | 
       El |  + - <div>
       El | 
       + - <nav>
       El |  El | 
       El |  + - <ul>
       El |  El | 
       El |  + - <li>
       El |  El |  El | 
       El |  El |  + - <a>
       El |  El | 
       El |  + - <li>
       El |  El |  El | 
       El |  El |  + - <a>
       El |  El | 
       El |  + - <li>
       El |  El | 
       El |  + - <a>
       El | 
       + - <principal>
       El |  El | 
       El |  + - <MACRO>
       El | 
       + - <footer>
         El | 
         + - <hr>
         El | 
         + - <pequeño>

Sin embargo, aunque el árbol resultante puede llamarse DOM, nuestro analizador está lejos de ser jQuery, Jsoup, beautifulsoup o Gumbo, en particular porque no puede procesar correctamente el texto ubicado entre las etiquetas emparejadas <style> y <script>, y por lo tanto la fuente hasta que lo traiga. Pero definitivamente agregaré si los residentes de Habrovsk expresan tal deseo. Éxitos

PS Códigos fuente llenos en acceso público. En mi humilde opinión, en bruto, así que voy a planear una biblioteca completa.

PSS La segunda parte.