Stream orientierter XML-Parser?



  • Guten Tag,

    ich benötige für mein Projekt im Bereich der Embedded Programmierung einen XML-Parser. Problem: Das Teil müsste Stream-orientiert sein, faktisch basieren aber alle Parser bis auf Expat (http://expat.sourceforge.net/) darauf, dass die gesamte Datei vollständig zur Verfügung steht, also ein sehr langer String geparst werden kann.
    Leider funktioniert das so auf einem Mikrocontroller nicht, denn ich kann ja nicht eine 1.27MB Große Datei mal eben einlesen und dann schön alles in einer XML-Struktur speichern. Daher streambasiert.

    Expat wiederum ist zwar streambasiert, aber so wie ich das sehe, vom Programmcode zu umfangreich. Es ist die Hölle 😞 .

    Frage 1: Gibt es vlt. noch eine Alternative, die euch auf anhieb einfällt? Ob in C oder C++ ist egal.

    Frage 2: Ich analysiere zwar noch Expat, spiele aber mit dem Gedanken, mir einen rudimentären XML-Parser selbst zu schreiben. Je mehr ich darüber nachdenke, desto komplizierter erscheint mir das jedoch. Da sind ja zig Sonderfälle enthalten, Beispiel:

    char buff[50] = {"   <doc id=\"1\">  <!-- comment--> <!-"};
    p.parse(buff);
    

    Das könnte eine aktuelle Zeile sein, die der Parser parsen müsste. Problematisch finde ich besonders, dass der Parser "merken" muss, wenn wie hier am Ende ein möglicher Kommentar (Oder Element,...) geöffnet wird und er auf den nächsten Datensatz warten muss, um zu überprüfen, ob das wirklich ein Kommentar oder ein Syntaxfehler ist. Gefühlt gibt es so viele Sonderfälle 😕

    Wie würdet ihr das angehen? Wirklich eine Zustandsmaschine die Zeichen für Zeichen ihren Zustand ändert? Oder irgendwas mit strtok? Ich fühle mich gerade überfordert



  • Ratsuchender123 schrieb:

    Wie würdet ihr das angehen? Wirklich eine Zustandsmaschine die Zeichen für Zeichen ihren Zustand ändert? Oder irgendwas mit strtok? Ich fühle mich gerade überfordert

    Lexer und Parser entwerfen wie es in Lehrbüchern beschrieben ist. Das geht sehr systematisch und man muss sich nicht mit Sonderfällen rumärgern. Außerdem reicht es dem Lexer dann aus, Zeichen für Zeichen einzulesen.



  • qweqweasdyxc schrieb:

    Ratsuchender123 schrieb:

    Wie würdet ihr das angehen? Wirklich eine Zustandsmaschine die Zeichen für Zeichen ihren Zustand ändert? Oder irgendwas mit strtok? Ich fühle mich gerade überfordert

    Lexer und Parser entwerfen wie es in Lehrbüchern beschrieben ist. Das geht sehr systematisch und man muss sich nicht mit Sonderfällen rumärgern. Außerdem reicht es dem Lexer dann aus, Zeichen für Zeichen einzulesen.

    Ich hab sowas noch nie gemacht. Wird soetwas sehr umfangreich von der Programmgröße? Sonst könnte ich vlt. doch gleich Expat nutzen?



  • Nein das Programm hätte sehr überschaubaren Umfang. XML ist nicht sehr komplex. Aber: Das Einlesen in die Theorie dürfte Dich etwas Zeit kosten.



  • http://rapidxml.sourceforge.net/

    It is an in-situ parser written in modern C++, with parsing speed approaching that of strlen function executed on the same data.

    http://www.wilmott.ca/conferences/insituanswer.txt schrieb:

    "In-Situ" XML parsing leaves the XML data in the original location or device from where it was provided to the XML parser, rather than copying it into the XML parser. An In-Situ parser passes data to its client by referring to the original data rather than by prividing the client with the parser's copy.



  • pyhax schrieb:

    http://rapidxml.sourceforge.net/

    It is an in-situ parser written in modern C++, with parsing speed approaching that of strlen function executed on the same data.

    http://www.wilmott.ca/conferences/insituanswer.txt schrieb:

    "In-Situ" XML parsing leaves the XML data in the original location or device from where it was provided to the XML parser, rather than copying it into the XML parser. An In-Situ parser passes data to its client by referring to the original data rather than by prividing the client with the parser's copy.

    RapidXML hatte ich auch gefunden. Es klingt aber für mich so, als ob RapidXML letztendlich intern eine Art Verweise auf die externen Daten beim parsen erzeugt. Ich kann die Daten aber wie geschrieben nicht als ganzes vorliegen haben, die werden immer Häppchenweise von einer SD-Karte gelesen. Oder hab ich das falsch verstanden?

    Soweit ich das bei Expat richtig verstanden habe, fütterst du den Parser mit diesen Häppchen und wenn der Parser ein vollständiges Element entdeckt, ruft er deine Callbackfunktion auf, mit der du dann direkt die Daten verarbeiten kannst.



  • Soweit ich weiß, ist das Stichwort nach dem du suchen solltest "SAX Parser"

    Gruß



  • Ratsuchender123 schrieb:

    Expat wiederum ist zwar streambasiert, aber so wie ich das sehe, vom Programmcode zu umfangreich. Es ist die Hölle 😞 .

    Nimm Expat !!! Damit sollte man eigentlich schon als Anfänger klar kommen.
    Zwei Callbacks definieren, fertig ist der Parser.

    Wenn du das umfangreich nennst, hast du noch nie mit boost oder xerces gearbeitet.



  • @nurf
    Ich schätze er meint den Expat-Code selbst, nicht den Client-Code den er schreiben müsste.
    Schliesslich muss der XML-Parser auch irgendwo im RAM/ROM vorliegen, und Speicher ist auf Embedded Systems halt manchmal etwas knapp.

    @Ratsuchender123

    Ratsuchender123 schrieb:

    Das könnte eine aktuelle Zeile sein, die der Parser parsen müsste. Problematisch finde ich besonders, dass der Parser "merken" muss, wenn wie hier am Ende ein möglicher Kommentar (Oder Element,...) geöffnet wird und er auf den nächsten Datensatz warten muss, um zu überprüfen, ob das wirklich ein Kommentar oder ein Syntaxfehler ist. Gefühlt gibt es so viele Sonderfälle

    Wenn du es richtig angehst gibt es gar keine Sonderfälle.
    Im Prinzip musst du nur den Zustand den du bei einem Recursive-Descent-Parser hättest explizit als State-Machine abspeichern.

    Und du musst ja nicht wirklich Zeichen für Zeichen verarbeiten. Wenn du z.B. ein "<" bekommst, kannst du das ja erstmal puffern und warten was als nächstes kommt.
    Wenn als nächstes ein "-" kommt hast du ein "<-". Das lässt du immer noch stehen. Wenn dann noch ein "-" kommt hast du ein "<--" und damit den Anfang eines Kommentars.
    Dann modifizierst du den State und löscht den Input-Puffer.

    Und du wirst, zumindest wenn du Fehler wie "<a>blub</b>" erkennen willst, natürlich schon bestimmte Strukturen im Speicher halten müssen. Nämich einen Stack von gerade "offenen" Elementen. Der max. Speicherverbrauch ist dann allerdings nur mehr von der Schachtelungstiefe der Elemente abhängig, und nicht davon wie gross das File ist.
    (Und natürlich von der max. Länge eines Element-/Attribut-Namen, und ggf. - wenn du Attribut-Werte bzw. Inner-Text nicht auch zum Client "streamen" willst - noch die max. Länge der Attribut-Werte bzw. Element-Inhalte.)

    "Die Hölle", wie du schreibst, wird es erst, wenn du "vollständigen Feature Support" brauchst. Also Support für diverse Encodings, DTD Entities, Namespaces etc.


Log in to reply