Faça você mesmo analisando arte ou DOM

Olá Habr! Recentemente, tive a ideia de criar uma linguagem de marcação simples, como markdown, que seria perfeita para minhas tarefas, a saber: escrita rápida de palestras com formatação e a capacidade de inserir fórmulas matemáticas "on the fly", usando apenas um teclado. Para converter o texto escrito neste formato em um formato mais compreensível, por exemplo, um documento do LibreOffice Writer, você precisa de um analisador , ou seja, de um analisador . Como eu costumava fazer bicicletas, fui aos mecanismos de pesquisa com as consultas "exemplo de analisador", "html para DOM", "como analisar html" etc. etc. Para minha decepção, em todos os recursos encontrados, alguns exemplos elementares, como a calculadora Straustrup com por descida, ou soluções prontas como flex, bison, llvm e yacc foram usadas. Havia ainda mais bibliotecas destinadas a analisar linguagens estritamente definidas (ferramentas gumbo, jsoup, quickjson, Qt etc.). Nem uma nem a outra fazia parte dos meus planos de escrever meu próprio analisador de marcação em C ++ usando apenas a biblioteca padrão. em vez de recursos eletrônicos, os manuais de institutos técnicos se tornaram uma fonte de conhecimento sobre a arte de analisar. Sobre como pegar o texto e criar a partir dele AST (árvore de sintaxe abstrata), sobre algumas das armadilhas que encontrei no processo, falarei sobre possíveis erros hoje.

Farei uma reserva imediatamente. Se seu objetivo for sua própria linguagem de script ou ainda mais complicada, este artigo não será suficiente para sua implementação. Idealmente, você precisa conhecer perfeitamente a teoria dos autômatos e estruturas discretas. Mas, por enquanto, como ponto de partida, posso me limitar à minha experiência, que compartilho generosamente sob o corte. Não é exatamente isso que eu pretendia originalmente, mas é ideal como exemplo. Analisaremos o HTML como uma linguagem simples e familiar.

Antes de tudo, analisar ou analisar não é sinônimo do processo completo de transformar texto em um modelo de objeto. O processo em si consiste em duas etapas:

1. A análise lexical do texto em tokens é pequenos pedaços deste texto que têm um certo significado sintático.
2. A análise é a construção de tokens com base nos valores de uma árvore de sintaxe abstrata (AST - árvore de sintaxe abstrata) ou de um modelo de objeto de documento (DOM - modelo de objeto de documento).

Mas vamos colocá-lo em ordem. Antes de abrir seu IDE favorito e escrever código, você precisa desenvolver uma gramática do idioma futuro. Das gramáticas formais, livres de contexto, as mais famosas são a forma Backus-Naur (BNF) e a forma estendida de Backus-Naur . Usei a simbiose deles, aproveitando o melhor das duas formas. Qualquer expressão pode ser definida através de outras expressões, como a seguir:

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

Aqui uma expressão é definida através de outras três, uma após a outra. Eles, por sua vez, também devem ser representados através de expressões de "terceiros", etc.

Quando parar?

A descrição da sintaxe de qualquer idioma nas gramáticas formais consiste em dois tipos de tokens: terminais e não terminais . Não terminais são expressões que precisam ser definidas:

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

Os terminais são auto-suficientes, não precisam ser definidos. Os exemplos acima podem ser escritos assim:

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

onde "+", "*", "/" são os terminais.
Você precisa selecionar os terminais da gramática imediatamente, pode até escrevê-los em uma lista separada na parte inferior das principais definições - elas serão úteis mais tarde.

Uma descrição completa do BNF está disponível na Wikipedia aqui e aqui . Compilar uma gramática de um idioma é um estágio importante na criação de um idioma que não tolera frivolidade. Um erro nele pode levar a um código completamente inoperante, que precisará ser reescrito do zero. Portanto, antes de dar o próximo passo, verifique se não há problemas controversos na gramática compilada. Se você tiver dois monitores, será conveniente ocupar um monitor com um documento gramatical pelo resto do seu trabalho, para que você possa rapidamente passar os olhos para ele ao codificar. Acredite, você tem que fazer isso o tempo todo. Aqui está minha 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" 

Quando a gramática estiver pronta, você poderá prosseguir para o analisador lexical (outro nome para o analisador lexical, pois além de analisar, ele identifica erros lexicais no documento). À primeira vista, tudo é simples: absorva caracteres, grave no buffer e, quando um terminal principal for detectado, determine o token recebido como um token com um determinado tipo, certo? Sim, apenas o tipo de token aqui é mais importante que o símbolo. Eu vou explicar agora Obviamente, o procedimento de desmontagem (ifsteam & file) deve conter um loop que lê um caractere do fluxo de entrada e o envia para o processo (const char & c), onde esse caractere é processado. Parece que o procedimento do processo precisa conter a chave ©, onde cada símbolo de tecla tem suas próprias funções, dependendo do tipo atual de token. De fato, o oposto é verdadeiro: é melhor usar a opção para verificar o tipo de token e definir funções para caracteres. Além disso, o token atual geralmente possui um tipo indefinido, um dentre muitos. Por exemplo, depois de abrir o colchete angular, você pode ver: abertura, fechamento, tags vazias, além de um comentário em estilo HTML ou macro (script PHP incluído em "<? ...?>". E para todas essas uniões, você precisa do seu próprio caso. Como é isso? implementar? Usando sinalizadores de bit. Permita que seja fornecido um número finito de tipos de token (quanto mais, melhor, pois a tarefa do analisador lexical é deixar o mínimo possível de trabalho para a sintaxe). Para cada tipo, é fornecido um número exclusivo de grau dois (1, 2, 4, 8 etc.) Em seguida, no formato binário, eles ficarão assim: 0001, 0010, 0 100, etc., e com a adição bit a bit de qualquer número de qualquer tipo, um número único será obtido.Se a descrição do texto for difícil de entender, darei o código.Aqui está a definição dos 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 }; 

Processo de procedimento 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 com o comutador o tipo de token (ou tokens) esperado e, em cada caso, determinamos os procedimentos para cada um dos terminais principais. Não há muitas funções, todos executam ações simples: adicionando um caractere ao buffer ou despejando-o no próximo token, ou alterando o tipo esperado de token ou lançando uma exceção. É fácil determinar o procedimento desejado usando a gramática escrita acima usando um editor de texto pesquisável. Basta procurar por todas as inclusões do token esperado (tokens) nas definições de outras expressões e, em seguida, a inclusão dessas expressões no "terceiro", etc. Aqui está um exemplo para uma tag de abertura em um editor de texto gedit:



A princípio, navegar pela gramática é difícil, mas com o tempo e a experiência, não se torna mais complicado do que dividir a coluna. E aqui está o procedimento de desmontagem:

 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); } } 

O primeiro token esperado é obviamente necessário para definir o tipo como TEXT e, no final, adicione o token do tipo END com qualquer texto (ou vazio, como aqui).

Por exemplo, peguei um dos meus modelos de documento HTML com um comentário, adicionei um script pseudo-PHP, processei-o com um lexer e exibi uma lista de tokens no formato "[" <token_text> ": <token_type>]". Aqui está o que aconteceu:



Agora estamos prontos para começar a segunda parte - a construção de uma árvore de sintaxe. Como nossas tags têm atributos, os nós da árvore, além da comunicação com outros nós, conterão matrizes de pares de valores-chave. A construção resultante pode ser chamada de modelo de objeto do documento DOM mencionado no título do artigo.

Quantas classes você precisa para implementar todas as propriedades dos elementos HTML?

Idealmente, uma classe para cada elemento, para que as folhas de estilo em cascata possam ser definidas para eles, mas nos limitaremos a três - uma tag "Node" vazia, um bloco "Block" herdado (conteúdo entre duas tags de par) e herdado de ele com a raiz da árvore Raiz. Também definimos no analisador uma matriz de tags que podem conter texto, como <p>, <li>, <strong>, etc., para eliminar tokens com texto não inserido. Agora cabe aos pequenos. Se você trabalhou bem no analisador lexical, a tarefa do sintático é simplesmente absorver tokens e executar uma das três operações no nó aberto: adicione um nó vazio a ele, abra um novo ou feche você mesmo retornando o ponteiro ao pai. Para o último, é necessário que todas as classes, começando com o Nó base, contenham um ponteiro obtido ao criar o elemento. Esse processo é chamado de análise de cima para baixo .

Procedimento de análise:

 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); } } 

Isso é tudo! Se você fez tudo corretamente, a árvore resultante pode ser exibida:

 | 
 + - <ROOT>
   | 
   + - <! DOCTYPE>
   | 
   + - <html>
     | 
     + - <head>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <título>
     |  | 
     |  + - <link>
     |  | 
     |  + - <link>
     |  | 
     |  + - <COMMENT>
     | 
     + - <body>
       | 
       + - <cabeçalho>
       |  | 
       |  + - <div>
       | 
       + - <nav>
       |  | 
       |  + - <ul>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  | 
       |  + - <a>
       | 
       + - <main>
       |  | 
       |  + - <MACRO>
       | 
       + - <pé>
         | 
         + - <hr>
         | 
         + - <small>

No entanto, embora a árvore resultante possa realmente ser chamada de DOM, nosso analisador está longe de jQuery, Jsoup, beautifulsoup ou Gumbo, principalmente porque não pode processar corretamente o texto localizado entre as marcas <style> e <script> e, portanto, a origem até eu trazer. Mas acrescentarei definitivamente se os residentes de Habrovsk expressam esse desejo. Sucessos.

PS Códigos-fonte preenchidos em acesso público. IMHO, cru, então vou planejar uma biblioteca completa.

PSS A segunda parte.