L'art d'analyser ou de bricoler DOM

Bonjour, Habr! Récemment, j'ai eu l'idée de créer un langage de balisage simple comme le markdown, qui serait parfait pour mes tâches, à savoir l'écriture rapide de conférences avec formatage et la possibilité d'insérer des formules mathématiques "à la volée", en utilisant un seul clavier. Pour traduire un texte écrit dans ce format sous une forme plus compréhensible, par exemple, un document LibreOffice Writer, vous avez besoin d' un analyseur , en d'autres termes, un analyseur . Depuis que je fabriquais des vélos, je suis allé sur les moteurs de recherche avec les requêtes "parser example", "html to DOM", "how to parse html", etc. par descente, ou des solutions prêtes à l'emploi telles que flex, bison, llvm et yacc ont été utilisées. Il y avait encore plus de bibliothèques destinées à analyser des langages strictement définis (gumbo, jsoup, rapidjson, outils Qt, etc.) Ni l'un ni l'autre ne faisaient partie de mes plans pour écrire mon propre analyseur de balisage en C ++ en utilisant uniquement la bibliothèque standard, donc mon au lieu de ressources électroniques, les manuels des instituts techniques sont devenus une source de connaissances sur l'art de l'analyse. Sur la façon de prendre le texte et de construire AST (arbre de syntaxe abstraite) à partir de celui-ci, sur certains des pièges que j'ai rencontrés au cours du processus, je vais vous parler des erreurs possibles aujourd'hui.

Je ferai une réservation tout de suite - si votre objectif est votre propre langage de script ou encore plus compliqué, cet article ne sera pas suffisant pour sa mise en œuvre. Idéalement, vous devez connaître parfaitement la théorie des automates et des structures discrètes. Mais pour l'instant, comme point de départ, je peux me limiter à mon expérience, que je partage généreusement sous la coupe. Ce n'est pas exactement ce que je voulais à l'origine, mais c'est idéal comme exemple. Nous analyserons HTML comme un langage simple et familier.

Tout d'abord, l'analyse, ou l'analyse, n'est pas synonyme du processus complet de transformation du texte en modèle objet. Le processus lui-même comprend deux étapes:

1. L'analyse lexicale du texte en jetons est de petits morceaux de ce texte qui ont une certaine signification syntaxique.
2. L'analyse est la construction de jetons basés sur leurs valeurs d'un arbre de syntaxe abstraite (AST - arbre de syntaxe abstraite) ou d' un modèle d'objet de document (DOM - modèle d'objet de document).

Mais mettons-le dans l'ordre. Avant d'ouvrir votre IDE préféré et d'écrire du code, vous devez développer une grammaire de la future langue. Parmi les grammaires formelles sans contexte, les plus célèbres sont la forme Backus-Naur (BNF) et la forme étendue Backus-Naur . J'ai utilisé leur symbiose, prenant le meilleur des deux formes. Toute expression peut être définie via d'autres expressions comme suit:

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

Ici, une expression est définie par trois autres qui se succèdent. À leur tour, ils doivent également être représentés par des «troisièmes» expressions, etc.

Quand arrêter?

La description de la syntaxe de n'importe quelle langue dans les grammaires formelles se compose de deux types de jetons: terminaux et non-terminaux . Les non terminaux sont des expressions qui doivent être définies:

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

Les terminaux sont autosuffisants, ils n'ont pas besoin d'être définis. Les exemples ci-dessus peuvent être écrits comme ceci:

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

où "+", "*", "/" sont les terminaux.
Vous devez sélectionner les terminaux dans la grammaire tout de suite, vous pouvez même les écrire dans une liste séparée au bas des définitions principales - ils vous seront utiles plus tard.

Une description complète de BNF est disponible sur Wikipedia ici et ici . La compilation d'une grammaire d'une langue est une étape importante dans la création d'une langue qui ne tolère pas la frivolité. Une erreur peut entraîner un code complètement inopérant, qui devra être réécrit à partir de zéro. Par conséquent, avant de passer à l'étape suivante, assurez-vous qu'il n'y a pas de problèmes controversés dans la grammaire compilée. Si vous avez deux moniteurs, il vous sera utile d'occuper un moniteur avec un document de grammaire pour le reste de votre travail afin de pouvoir rapidement y déplacer vos yeux lorsque vous codez. Croyez-moi, vous devez le faire tout le temps. Voici ma grammaire HTML5 BNF compilée:

 (* 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" 

Lorsque la grammaire est prête, vous pouvez passer à l'analyseur lexical (un autre nom pour l'analyseur lexical, car en plus de l'analyse, il identifie les erreurs lexicales dans le document). À première vue, tout est simple: absorber des caractères, écrire dans le tampon et lorsqu'un terminal clé est détecté, déterminer le jeton reçu comme un jeton avec un certain type, non? Oui, seul le type de jeton importe plus que le symbole. Je vais vous expliquer maintenant. Bien sûr, la procédure de désassemblage (ifsteam & file) doit contenir une boucle qui lit un caractère du flux d'entrée et l'envoie à la procédure process (const char & c), où ce caractère est traité. Il semble que la procédure doit contenir le commutateur ©, où chaque symbole de clé a ses propres fonctions, selon le type de jeton actuel. En fait, l'inverse est vrai: il est préférable d'utiliser le commutateur pour vérifier le type de jeton et définir les fonctions des caractères. De plus, le jeton actuel a le plus souvent un type indéfini, l'un des nombreux. Par exemple, après avoir ouvert l'équerre, vous pouvez voir: ouverture, fermeture, balises vides, ainsi qu'un commentaire de style HTML ou une balise macro (script PHP inclus dans "<? ...?>". Et pour toutes ces unions, vous avez besoin de votre propre cas. Comment est-ce à l'aide de drapeaux de bits. Soit un nombre fini de types de jetons (plus c'est mieux, car la tâche de l'analyseur lexical est de laisser le moins de travail possible à la syntaxe). Pour chaque type, un nombre unique de degré deux est donné (1, 2, 4, 8 Ensuite, au format binaire, ils ressembleront à ceci: 0001, 0010, 0 100, etc., et avec l'ajout au niveau du bit de n'importe quel nombre de tout type, un nombre unique sera obtenu.

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

Processus de procédure tronquée:

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

Nous vérifions avec le commutateur le type de jeton (ou jetons) attendu, et à l'intérieur de chaque cas, nous déterminons les procédures pour chacun des terminaux clés. Il n'y a pas tellement de fonctions, tout le monde effectue des actions simples: soit ajouter un caractère au tampon, soit vider le tampon dans le jeton suivant, soit changer le type de jeton (s) attendu (s), soit lever une exception. Il est facile de déterminer la procédure souhaitée en utilisant la grammaire écrite ci-dessus à l'aide d'un éditeur de texte interrogeable. Il suffit de rechercher toutes les inclusions du jeton attendu (jetons) dans les définitions d'autres expressions, puis l'inclusion de ces expressions dans la "troisième", etc. Voici un exemple de balise d'ouverture dans un éditeur de texte gedit:



Au début, naviguer dans la grammaire est difficile, mais avec le temps et l'expérience, cela ne devient pas plus compliqué que de diviser la colonne. Et voici la procédure de démontage:

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

Le premier jeton attendu est évidemment nécessaire pour définir le type sur TEXT, et à la fin ajouter le jeton de type END avec n'importe quel texte (ou vide, comme ici).

Par exemple, j'ai pris un de mes modèles de document HTML avec un commentaire, y ai ajouté un script pseudo-PHP, l'ai traité avec un lexer et affiché une liste de jetons au format "[" <token_text> ": <token_type>]". Voici ce qui s'est passé:



Nous sommes maintenant prêts à commencer la deuxième partie - la construction d'un arbre de syntaxe. Puisque nos balises ont des attributs, les nœuds d'arborescence, en plus de la communication avec d'autres nœuds, contiendront des tableaux de paires clé-valeur. La construction résultante peut à juste titre être appelée le modèle objet du document DOM mentionné dans le titre de l'article.

De combien de classes avez-vous besoin pour implémenter toutes les propriétés des éléments HTML?

Idéalement, il y a une classe pour chaque élément afin que les feuilles de style en cascade puissent être définies pour eux, mais nous nous limiterons à trois - une balise "Node" vide, un bloc "Block" hérité (contenu entre deux balises appariées) et hérité de lui avec la racine de l'arbre racine. Nous définissons également dans l'analyseur un tableau de balises pouvant contenir du texte, comme <p>, <li>, <strong>, etc., pour éliminer les jetons avec du texte non placé. Maintenant, c'est aux petits. Si vous avez bien travaillé sur l'analyseur lexical, la tâche de l'analyseur syntaxique consiste simplement à absorber les jetons et à effectuer l'une des trois opérations dans le nœud ouvert: ajoutez-y un nœud vide, ouvrez-en un nouveau ou fermez-le vous-même en renvoyant le pointeur au parent. Pour ce dernier, il est nécessaire que toutes les classes, en commençant par le Node de base, contiennent un tel pointeur obtenu lors de la création de l'élément. Ce processus est appelé analyse descendante .

Procédure d'analyse:

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

C'est tout! Si vous avez tout fait correctement, l'arborescence résultante peut être affichée:

 | 
 + - <ROOT>
   | 
   + - <! DOCTYPE>
   | 
   + - <html>
     | 
     + - <head>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <titre>
     |  | 
     |  + - <link>
     |  | 
     |  + - <link>
     |  | 
     |  + - <COMMENTAIRE>
     | 
     + - <body>
       | 
       + - <en-tête>
       |  | 
       |  + - <div>
       | 
       + - <nav>
       |  | 
       |  + - <ul>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  | 
       |  + - <a>
       | 
       + - <main>
       |  | 
       |  + - <MACRO>
       | 
       + - <footer>
         | 
         + - <hr>
         | 
         + - <petite>

Cependant, bien que l'arbre résultant puisse vraiment être appelé le DOM, notre analyseur est loin d'être jQuery complet, Jsoup, beautifulsoup ou Gumbo, en particulier parce qu'il ne peut pas traiter correctement le texte situé entre les balises <style> et <script> appariées, et donc la source jusqu'à ce que je l'apporte. Mais j'ajouterai certainement si les habitants de Habrovsk expriment un tel désir. Succès.

PS Codes source remplis en accès public. À mon humble avis, brut, je vais donc planifier une bibliothèque complète.

PSS La deuxième partie.