Die Kunst des Parsens oder Do-it-yourself-DOM

Hallo Habr! Vor kurzem kam mir die Idee, eine einfache Markup-Sprache wie Markdown zu erstellen, die sich perfekt für meine Aufgaben eignet, nämlich das schnelle Schreiben von Vorlesungen mit Formatierung und die Möglichkeit, mathematische Formeln "on the fly" mit nur einer Tastatur einzufügen. Um in diesem Format geschriebenen Text in eine verständlichere Form zu übersetzen, z. B. ein LibreOffice Writer-Dokument, benötigen Sie einen Parser , dh einen Parser . Da ich früher Fahrräder hergestellt habe, ging ich zu Suchmaschinen mit den Abfragen "Parser-Beispiel", "HTML zu DOM", "Wie man HTML analysiert" usw. Zu meiner Enttäuschung über alle gefundenen Ressourcen, entweder elementare Beispiele wie Straustrup-Rechner mit rekursiv durch Abstieg oder fertige Lösungen wie Flex, Bison, llvm und Yacc wurden verwendet. Es gab noch mehr Bibliotheken, die zum Parsen streng definierter Sprachen (Gumbo, Jsoup, RapidJson, Qt-Tools usw.) bestimmt waren. Weder die eine noch die andere waren Teil meiner Pläne, meinen eigenen Markup-Parser in C ++ nur mit der Standardbibliothek zu schreiben Anstelle elektronischer Ressourcen wurden Handbücher technischer Institute zu einer Wissensquelle über die Kunst des Parsens. Wie man den Text nimmt und daraus AST (abstrakter Syntaxbaum) erstellt, über einige der Fallstricke, auf die ich dabei gestoßen bin, werde ich Ihnen heute über mögliche Fehler berichten.

Ich werde sofort eine Reservierung vornehmen. Wenn Ihr Ziel Ihre eigene Skriptsprache ist oder noch komplizierter, reicht dieser Artikel für die Implementierung nicht aus. Idealerweise müssen Sie die Theorie der Automaten und diskreten Strukturen genau kennen. Aber als Ausgangspunkt kann ich mich vorerst auf meine Erfahrung beschränken, die ich großzügig unter dem Schnitt teile. Dies ist nicht genau das, was ich ursprünglich beabsichtigt hatte, aber es ist ideal als Beispiel. Wir werden HTML als einfache und vertraute Sprache analysieren.

Erstens ist Parsen oder Parsen kein Synonym für den vollständigen Prozess, Text in ein Objektmodell umzuwandeln. Der Prozess selbst besteht aus zwei Phasen:

1. Die lexikalische Analyse von Text in Token besteht aus kleinen Teilen dieses Textes, die eine bestimmte syntaktische Bedeutung haben.
2. Das Parsen ist die Konstruktion von Token basierend auf ihren Werten eines abstrakten Syntaxbaums (AST - abstrakter Syntaxbaum) oder eines Dokumentobjektmodells (DOM - Dokumentobjektmodell).

Aber lasst es uns in Ordnung bringen. Bevor Sie Ihre Lieblings-IDE öffnen und Code schreiben, müssen Sie eine Grammatik der zukünftigen Sprache entwickeln. Von den formalen kontextfreien Grammatiken sind die Backus-Naur (BNF) -Form und die erweiterte Backus-Naur-Form die bekanntesten . Ich benutzte ihre Symbiose und nahm das Beste aus beiden Formen. Jeder Ausdruck kann durch andere Ausdrücke wie folgt definiert werden:

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

Hier wird ein Ausdruck durch drei weitere definiert, die nacheinander folgen. Sie müssen wiederum auch durch „dritte“ Ausdrücke usw. dargestellt werden.

Wann aufhören?

Die Beschreibung der Syntax einer Sprache in formalen Grammatiken besteht aus zwei Arten von Token: Terminals und Nicht-Terminals . Nichtterminale sind Ausdrücke, die definiert werden müssen:

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

Terminals sind autark, sie müssen nicht definiert werden. Die obigen Beispiele können folgendermaßen geschrieben werden:

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

Dabei sind "+", "*", "/" die Terminals.
Sie müssen Terminals sofort aus der Grammatik auswählen. Sie können sie sogar in eine separate Liste am Ende der Hauptdefinitionen schreiben - sie werden später nützlich sein.

Eine vollständige Beschreibung von BNF finden Sie hier und hier auf Wikipedia. Das Zusammenstellen einer Grammatik einer Sprache ist eine wichtige Phase bei der Erstellung einer Sprache, die keine Frivolität toleriert. Ein Fehler kann zu einem völlig funktionsunfähigen Code führen, der von Grund auf neu geschrieben werden muss. Stellen Sie daher vor dem nächsten Schritt sicher, dass die kompilierte Grammatik keine kontroversen Themen enthält. Wenn Sie über zwei Monitore verfügen, können Sie für den Rest Ihrer Arbeit bequem einen Monitor mit einem Grammatikdokument belegen, damit Sie beim Codieren schnell Ihre Augen darauf richten können. Glauben Sie mir, Sie müssen dies die ganze Zeit tun. Hier ist meine kompilierte HTML5 BNF-Grammatik:

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

Wenn die Grammatik fertig ist, können Sie den lexikalischen Analysator starten (ein anderer Name für den lexikalischen Parser, da er neben dem Parsen auch lexikalische Fehler im Dokument identifiziert). Auf den ersten Blick ist alles einfach: Zeichen aufnehmen, in den Puffer schreiben und, wenn ein Schlüsselterminal erkannt wird, das empfangene Token als Token mit einem bestimmten Typ bestimmen, oder? Ja, nur die Art des Tokens ist hier wichtiger als das Symbol. Ich werde es jetzt erklären. Natürlich sollte die Disassemble-Prozedur (ifsteam & file) eine Schleife enthalten, die ein Zeichen aus dem Eingabestream liest und an die Prozessprozedur (const char & c) sendet, in der dieses Zeichen verarbeitet wird. Es scheint, dass die Prozessprozedur switch © enthalten muss, wobei jedes Schlüsselsymbol abhängig vom aktuellen Token-Typ seine eigenen Funktionen hat. In der Tat ist das Gegenteil der Fall: Es ist besser, den Schalter zu verwenden, um den Token-Typ zu überprüfen und Funktionen für Zeichen zu definieren. Darüber hinaus hat das aktuelle Token meistens einen unbestimmten Typ, einen von vielen. Nach dem Öffnen der spitzen Klammer können Sie beispielsweise Folgendes sehen: Öffnen, Schließen, leere Tags sowie einen Kommentar oder ein Makrotag im HTML-Stil (PHP-Skript in "<? ...?>". Und für alle derartigen Gewerkschaften benötigen Sie Ihren eigenen Fall. Wie ist das? Verwenden von Bit-Flags. Es sei eine endliche Anzahl von Token-Typen angegeben (je mehr desto besser, da die Aufgabe des lexikalischen Analysators darin besteht, der Syntax so wenig Arbeit wie möglich zu überlassen). Für jeden Typ wird eine eindeutige Anzahl von Grad zwei angegeben (1, 2, 4, 8) usw.). Dann sehen sie im Binärformat folgendermaßen aus: 0001, 0010, 0 100 usw. und mit der bitweisen Addition einer beliebigen Anzahl von Typen wird eine eindeutige Nummer erhalten. Wenn die Textbeschreibung schwer zu verstehen ist, gebe ich den Code. Hier ist die Definition der Typen:

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

Prozess der abgeschnittenen Prozedur:

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

Wir überprüfen mit dem Schalter den Typ des erwarteten Tokens (oder der Token) und bestimmen in jedem Fall die Prozeduren für jedes der Schlüsselterminals. Es gibt nicht so viele Funktionen, jeder führt einfache Aktionen aus: entweder Hinzufügen eines Zeichens zum Puffer oder Speichern des Puffers im nächsten Token oder Ändern des erwarteten Token-Typs oder Auslösen einer Ausnahme. Es ist einfach, die gewünschte Prozedur unter Verwendung der oben beschriebenen Grammatik unter Verwendung eines durchsuchbaren Texteditors zu bestimmen. Suchen Sie einfach nach allen Einschlüssen des erwarteten Tokens (Token) in den Definitionen anderer Ausdrücke, dann nach dem Einschluss dieser Ausdrücke in den "dritten" usw. Hier ist ein Beispiel für ein Eröffnungs-Tag in einem gedit-Texteditor:



Das Navigieren in der Grammatik ist zunächst schwierig, aber mit der Zeit und Erfahrung wird es nicht komplizierter als das Teilen der Spalte. Und hier ist das Demontageverfahren:

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

Das erste erwartete Token ist offensichtlich erforderlich, um den Typ auf TEXT zu setzen und am Ende das Token vom Typ END mit einem beliebigen Text (oder leer, wie hier) hinzuzufügen.

Zum Beispiel habe ich eine meiner HTML-Dokumentvorlagen mit einem Kommentar versehen, ein Pseudo-PHP-Skript hinzugefügt, mit einem Lexer verarbeitet und eine Liste von Token im Format "[" <Token_text> ": <Token_Typ>]" angezeigt. Folgendes ist passiert:



Jetzt können wir mit dem zweiten Teil beginnen - der Erstellung eines Syntaxbaums. Da unsere Tags Attribute haben, enthalten die Baumknoten zusätzlich zur Kommunikation mit anderen Knoten Arrays von Schlüssel-Wert-Paaren. Die resultierende Konstruktion kann zu Recht als Objektmodell des im Titel des Artikels genannten DOM-Dokuments bezeichnet werden.

Wie viele Klassen benötigen Sie, um alle Eigenschaften von HTML-Elementen zu implementieren?

Idealerweise eine Klasse für jedes Element, damit kaskadierende Stylesheets für sie definiert werden können, aber wir beschränken uns auf drei - ein leeres "Node" -Tag, einen geerbten "Block" -Block (Inhalt zwischen zwei Paar-Tags eingeschlossen) und von geerbt ihn mit der Wurzel des Wurzelbaums. Wir definieren im Parser auch ein Array von Tags, die Text enthalten können, wie z. B. <p>, <li>, <strong> usw., um Token mit nicht platziertem Text auszusondern. Jetzt liegt es an den Kleinen. Wenn Sie mit dem lexikalischen Analysator gut gearbeitet haben, besteht die Aufgabe des syntaktischen Analysators einfach darin, Token zu absorbieren und eine von drei Operationen im geöffneten Knoten auszuführen: Fügen Sie einen leeren Knoten hinzu, öffnen Sie einen neuen oder schließen Sie ihn selbst, indem Sie den Zeiger auf den übergeordneten Knoten zurückgeben. Für letzteres ist es erforderlich, dass alle Klassen, beginnend mit dem Basisknoten, einen solchen Zeiger enthalten, der beim Erstellen des Elements erhalten wird. Dieser Vorgang wird als Top-Down-Analyse bezeichnet .

Analyseverfahren:

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

Das ist alles! Wenn Sie alles richtig gemacht haben, kann der resultierende Baum angezeigt werden:

 | 
 + - <ROOT>
   | 
   + - <! DOCTYPE>
   | 
   + - <html>
     | 
     + - <head>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <Titel>
     |  | 
     |  + - <link>
     |  | 
     |  + - <link>
     |  | 
     |  + - <KOMMENTAR>
     | 
     + - <body>
       | 
       + - <header>
       |  | 
       |  + - <div>
       | 
       + - <nav>
       |  | 
       |  + - <ul>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  | 
       |  + - <a>
       | 
       + - <main>
       |  | 
       |  + - <MACRO>
       | 
       + - <Fußzeile>
         | 
         + - <hr>
         | 
         + - <klein>

Obwohl der resultierende Baum wirklich als DOM bezeichnet werden kann, ist unser Parser weit von vollständigem jQuery, Jsoup, beautifulsoup oder Gumbo entfernt, insbesondere weil er Text zwischen den gepaarten <style> - und <script> -Tags und damit der Quelle nicht korrekt verarbeiten kann bis ich es bringe. Aber ich werde auf jeden Fall hinzufügen, wenn die Bewohner von Habrovsk einen solchen Wunsch äußern. Erfolge.

PS Gefüllte Quellcodes im öffentlichen Zugriff. IMHO, roh, also werde ich eine vollständige Bibliothek planen.

PSS Der zweite Teil.