Parsing

Ein Parser ist die Komponente, die eingehenden Text liest und daraus eine strukturierte Repräsentation aufbaut, mit der ein Programm tatsächlich arbeiten kann. Roher Text ist nur eine Folge von Zeichen ohne eigene Bedeutung für die Software; der Parser ist der Schritt, der diesen flachen Strom in etwas mit Form und Hierarchie verwandelt. Er steht an der Grenze zwischen dem von einem Menschen geschriebenen oder von einer Maschine erzeugten Text und den strukturierten Daten, die der Rest eines Programms braucht.

Zwei Schritte: tokenisieren, dann einen Baum aufbauen

Die meisten Parser arbeiten in zwei getrennten Schritten. Der erste Schritt, ein Tokenizer oder Lexer, gruppiert Zeichen zu bedeutungstragenden Einheiten – Tags, Wörter, Zahlen, Operatoren, Symbole –, sodass die Eingabe nicht mehr aus einzelnen Zeichen, sondern aus einer Folge von Tokens besteht. Der zweite Schritt, der Baumaufbau, ordnet diese Tokens nach einer Grammatik in eine Hierarchie und erzeugt einen strukturierten Baum. Diese beiden Aufgaben zu trennen, hält jede einfacher, und es ist ein Muster, das Ihnen wieder und wieder begegnen wird.

Die Tokenisierung allein löst viel Mehrdeutigkeit auf. Bedenken Sie, wie die Zeichen, die ein öffnendes Tag, einen Attributnamen und einen in Anführungszeichen gesetzten Wert bilden, als verschiedene Dinge erkannt werden müssen, bevor irgendeine Struktur aufgebaut werden kann; der Tokenizer ist es, der diese Unterscheidungen trifft. Erst wenn die Eingabe ein sauberer Strom von Tokens ist, kann der Baumaufbauschritt darüber nachdenken, wie sie ineinandergreifen und sich aufeinander beziehen.

Parser sind überall

Parser sind wahrhaftig überall, sobald man hinzusehen beginnt. Compiler analysieren Quellcode zu einem abstrakten Syntaxbaum, bevor sie Maschinenbefehle erzeugen; Browser analysieren HTML und CSS, um die Strukturen aufzubauen, die sie rendern; und gewöhnliche Anwendungen analysieren JSON, XML, YAML und Konfigurationsdateien bei jedem Start. Fast jedes Programm, das Text als Eingabe akzeptiert, hat irgendwo in seinem Inneren einen Parser, selbst wenn der Autor ihn nie unter diesem Namen denkt.

Warum die Ausgabe ein Baum ist

Die Ausgabe eines Parsers ist in der Regel ein Baum, und die Art des Baums hängt von der Domäne ab. Für eine Programmiersprache ist es ein abstrakter Syntaxbaum, der die Struktur von Ausdrücken und Anweisungen erfasst; für eine Webseite ist es das DOM, der Baum aus Elementen und Textknoten, den der Browser aus dem HTML aufbaut. In beiden Fällen ist es der Baum, nicht der ursprüngliche Text, auf dem die folgenden Schritte arbeiten.

Der Grund, warum ein Baum die natürliche Ausgabe ist, ist, dass die meisten Sprachen und Dokumentformate von Natur aus verschachtelt sind. Ein Ausdruck enthält Teilausdrücke, ein Element enthält Kindelemente, ein Konfigurationsblock enthält verschachtelte Blöcke. Eine flache Liste von Tokens kann diese Verschachtelung nicht erfassen, aber ein Baum drückt sie direkt aus, was erklärt, warum die Analyse so oft als die Umwandlung eines eindimensionalen Stroms in eine mehrstufige Struktur beschrieben wird.

Was die HTML-Analyse ungewöhnlich macht

Was die Analyse von HTML unter all diesen Beispielen ungewöhnlich macht, ist seine standardisierte Fehlerwiederherstellung. Markup aus der realen Welt steckt voller Fehler – nicht geschlossene Tags, falsch platzierte Elemente, Attribute an seltsamen Stellen – und doch müssen die Seiten dennoch angezeigt werden. Die HTML-Spezifikation begegnet dem, indem sie genau definiert, wie ein Parser jede Art fehlerhafter Eingabe behandeln muss, statt jede Implementierung raten zu lassen.

Die Folge dieser präzisen Spezifikation ist eine bemerkenswerte Interoperabilität. Weil die Fehlerwiederherstellungsregeln bis ins Detail festgelegt sind, baut jeder moderne Browser denselben DOM-Baum aus derselben kaputten Eingabe auf, statt dass jeder anders improvisiert. Deshalb wird eine fehlerhafte Seite über Browser hinweg konsistent angezeigt, und das steht im Gegensatz zu strikteren Formaten wie XML, die eine nicht wohlgeformte Eingabe schlicht zurückweisen, statt zu versuchen, sie zu reparieren.

Nachsichtig gegenüber strikt, beabsichtigt

Dieser Gegensatz beleuchtet einen bewussten Designkompromiss. Ein nachsichtiger Parser wie der von HTML stellt Widerstandsfähigkeit und das, dass der Nutzer stets etwas sieht, in den Vordergrund, um den Preis, Fehler still durchzulassen. Ein strikter Parser wie der von XML stellt Korrektheit und Vorhersehbarkeit in den Vordergrund, um den Preis, eine unvollkommene Eingabe von vornherein zurückzuweisen. Keiner ist universell besser; jeder passt zu der Aufgabe, für die er entworfen wurde, und zu erkennen, welcher Philosophie ein Format folgt, sagt Ihnen viel über sein Verhalten.

Ein mentales Modell für den gesamten Stack

Sobald man Software als eine Reihe von Parsern zu sehen beginnt, die Text in Struktur verwandeln, wird ein großer Teil des Web-Stacks leichter zu durchdenken. Der Browser, der HTML zu DOM analysiert, die Engine, die JavaScript zu einem Syntaxbaum analysiert, der Server, der einen JSON-Anfragerumpf analysiert – das ist alles dieselbe Idee, an verschiedenen Stellen angewandt. Dieses eine Prisma, von Text, der über einen Parser zu strukturierten Daten wird, ist eines der nützlichsten mentalen Modelle der gesamten Programmierung.