XML Implementierung

« | 29 Mar 2019 | »

Es ist mal wieder so weit, eine kleine XML Implementierung muss her.

Und wenn man nicht gerade Schemavalidierungen durchführen muss, dann ist so ein kleiner Parser schnell geschrieben.

---

XML basiert ja auf Tags, die untergeordnete Tags enthalten können (aber nicht müssen). Ein einfacher XML Parser kann also rekursiv aufgebaut sein, in dem eine Funktion nur einen einzigen Tag-Knoten parst (von dessen Anfang bis zu seinem Ende) und wenn darin untergeordnete Knoten enthalten sind, ruft sich die Funktion mit dem entsprechenden Sub-String selbst auf.

Wichtig ist dabei, dass die Parser-Funktion zurückliefert, wie viele Zeichen aus dem Sub-String sie für ihre Aufgabe bearbeitet hat, damit die übergeordnete Funktion diese Menge überspringen kann.

Wie geht man also vor?

1. Alles fängt mit einem Kleinerzeichen < an und dann darf man bis zum nächsten Größerzeichen > wandern.
   1. Zwischen den Tag-Begrenzern kann man zuerst den Tag-Namen bis zum ersten Whitespace (oder Ende) auslesen.
   2. Danach folgen die Attribute nachdem Schema attribut-name="wert", wobei die Attribut-Definitionen ebenso wieder durch Whitespaces getrennt sind.
2. Endet das Tag mit einem Slash /> gibt es keine Unterelemente und wir sind fertig. (return;)
3. Nun suchen wir das nächste Kleinerzeichen <.
   1. Folgt auf das Kleinerzeichen ein Slash / und danach der Tag-Name, haben wir das Ende des Tag-Blocks erreicht und sind fertig. (return;)
   2. Ist es ein neues Tag (ohne Slash ‘/’), ruft sich die Funktion mit dem Sub-String ab der Position des neuen Tags auf.
   3. Alle Zeichen zwischen dem Ende des Eltern-Tags und dem nächsten Tag sind Textdaten.
   4. Die aufgerufene Funktion übermittelt ihre bearbeiteten Zeichen im Sub-String. Diese Zeichen werden dann in der laufenden Funktion übersprungen (da schon geparst) und wir setzen wieder bei Punkt 3 fort.

Eigentlich war es das schon. Tag-Namen und Attribute werden natürlich nebenbei in den finalen XML Objektbaum eingefügt.

Ich nutze bei eigenen Implementierungen stets die Token aus dem originalen XML Dokument. Andere Bibliotheken machen es teils anders und sie führen sofort die Konvertierung von XML-Entities durch, also das Umwandeln von > in > oder von < in < usw.

Diesen Schritt mache ich immer erst, wenn auf das entsprechende Element zugegriffen wird. Denn so erreicht man, dass der Baum aus Substrings des Originals aufgebaut wird und im Falle von Reference-Counting keinen (oder nur wenig) Speicher frisst.

Wenn man sofort konvertiert, muss man die Daten in neu allokierte Strings schreiben und hat damit das XML Dokument doppelt im Speicher.

Ich gebe aber zu, dass bei häufigen Zugriffen auf das gleiche Element meine Methode zusätzliche Rechenzeit benötigt, da jedes mal aufs Neue ein temporärer Ergebnis-String erzeugt werden muss.

Alles läuft also auf die Frage “Speed vs. Size” hinaus.

---

Natürlich gibt es dann noch ein paar Sonderfälle wie ?xml, !DOCTYPE und CDATA Elemente, oder Kommentare nach dem Schema <!-- nach -->.

Doch im Grunde genommen haben wir so einen primitiven Parser in purem C bzw. C++, der wenig Speicher braucht und universell portierbar ist.

Große Bibliotheken schaffen natürlich viel mehr und gehen auf viele Zusatzdetails von XML ein, wie das dynamische Definieren von Entities, die beim Parsen durch andere Inhalte ausgetauscht werden und vieles mehr.

Doch die Mehrzahl von Projekten, die XML einsetzen nutzen diese Features nicht und schreiben ihre Daten nach fixen Vorgaben. Und dafür reicht dieser minimalistische Ansatz aus.