Donnerstag, 4. Dezember 2008





April 2006
aus Java Magazin Ausgabe: 03.2002
Kistenwelt
Strukturiertes und effizientes XML-Parsing mit den APIs SAX2
von Sönke Kannapinn

Mit einem DOM- oder JDOM-Parser lassen sich bekanntlich XML-Dokumente sehr bequem einlesen, jedoch zu einem gewissen Preis: Die Bequemlichkeit ist mit Behäbigkeit und Heap-Belastung zu bezahlen. Grund ist die gelieferte Baumstruktur, die oft nur genutzt wird, um an die darin enthaltenen Informationen zu kommen. Abhilfe verspricht, die Applikation direkt auf ein API von niedrigem Abstraktionsniveau (SAX2, kXML, ...) aufzusetzen. Allerdings lässt sich eine gute Lösung ohne einige systematische Kenntnisse nicht während einer Tasse Kaffee in die Tasten klopfen. Hier will ich etwas Nachhilfe bieten: Ich zeige an einem Beispiel, wie man sowohl für das SAX2-API wie auch für das kXML-API geradlinig zu gut strukturiertem Code für das XML-Parsing gelangt, der sich zudem leicht um Code zur Verarbeitung der gelesenen Informationen anreichern lässt.


XML ist populär - zu Recht. Die verschiedensten Informationen lassen sich mit XML prägnant und portabel modellieren und vielen Lesern dürfte das Problem nicht neu sein, dass in einer Applikation ein XML-Dokument eingelesen und sein Inhalt "verstanden" werden muss - z.B. zum Zweck der Konfiguration, aber auch in vielen anderen Kontexten. Gerade in Server-Anwendungen kann die Forderung hinzukommen, dass dieser Analyse-Vorgang laufzeit- und ressourceneffizient erfolgen muss. Naheliegende Vorgehensweise hierfür ist, die Applikation direkt auf dem bekannten SAX2-API aufzusetzen [SAX2]. Schließlich ist SAX2 der De-facto-Standard für eventbasiertes XML-Parsing, auch weil so namhafte Firmen wie Sun, IBM und Oracle für dieses API Implementierungen bereitgestellt haben. Es arbeitet nach der so genannten Push-Strategie, indem es die gelesene XML-Struktur in eine Folge von Callbacks (ContentHandler-Methoden startElement, characters, endElement) umsetzt, die jeweils Code der Applikation abrufen. Wieso sich allerdings diese Key-Player der Software-Industrie für gerade dieses API einsetzen, ist mir nicht ganz klar. Denn ein solches API sollte vor allem auch leicht zu benutzen sein, und wer - erst recht ohne Compilerbau-Kenntnisse - einmal versucht hat, ein etwas komplexer strukturiertes XML-Dokument effizient und systematisch mit SAX2 zu parsen, weiß, dass dies schwierig ist! Und das SAX2-API (genauer: die Push-Strategie) hat an dieser Schwierigkeit wesentlich Mitschuld.
Meine Kritik wäre unseriös, wenn ich sie nicht belegen könnte. Und der beste Beleg, der mir einfällt, ist, erstens, das SAX2-API nach bestem Wissen und Gewissen so geschickt wie möglich für eine strukturierte und effiziente Lösung eines repräsentativen, beispielhaften Problems einzusetzen. Zweitens, im Vergleich dazu das gleiche Problem mit dem weniger bekannten kXML-API anzugehen [kXML], was zu einer merklich einfacheren und prägnanteren Lösung führen wird. Dieses API arbeitet nach der Pull-Strategie, d.h. es wird beim XML-Parsing wiederholt von der Applikation aufgerufen und liefert bei jedem Aufruf ein weiteres ParseEvent-Objekt, das die Situation an der aktuellen Einleseposition charakterisiert. Für beide Lösungen greife ich auf gängige Compilerbau-Techniken zurück - keine Bange, nichts wirklich Schwieriges. Aus didaktischen Gründen werden wir in diesem Beitrag so vorgehen, dass wir zunächst das Anwendungsbeispiel vorstellen und dann zuerst die kXML- und schließlich die SAX2-basierte Lösung herleiten und diskutieren. Außerdem steht auch der Beleg zu meiner Behauptung aus, dass XML-Parsing mit einem DOM- oder JDOM-Parser tatsächlich "behäbiger" gerät als das Parsing direkt auf Low-level-APIs wie SAX2 oder kXML. Die Zahlen einer kleinen Messreihe hierzu finden sich am Ende des Beitrags.
Beispiel: Kisten, Kästen, Pyramiden
Mein kleines Beispiel-Szenario, das alle wesentlichen Klippen enthält, ist spielerisch gewählt: Stellen wir uns eine Spielzeug-Kistenwelt () vor, in der es Würfel () und Pyramiden () gibt, aus denen auch Türmchen () gebaut werden können. Natürlich verdienen nur mindestens zwei gestapelte Bausteine die Bezeichnung "Turm" und Pyramiden können in Türmen höchstens als Dach verbaut werden. Ferner haben wir (um Rekursion ins Spiel zu bringen) auch noch Kisten (), die leer sein können, in denen sich aber auch beliebig viele Würfel, Pyramiden, Türme daraus und weitere Kisten befinden können. Eine komplette Szenariobeschreibung per XML darf noch einen Kommentar (<comment>) tragen. Folgende DTD charakterisiert unsere Spielzeugwelt-Szenarien:








Abb. 1: Ein Beispielszenario aus unserer Spielzeug-Kistenwelt

Zum Beispiel wird das Szenario aus Abbildung 1 durch folgendes XML-Dokument (ohne DTD) beschrieben:



  
    Ein Wuerfel und eine Kiste mit einer Pyramide, 
    noch einer Kiste und zwei Tuermen.
    Die innere Kiste ist leer.
  
  <cube/>
  
    <pyramid/>
    <box/>
    <cube/><pyramid/>
    <cube/><cube/>
  

Wir nehmen uns vor, solche XML-Dokumente effizient einzulesen und ihre Korrektheit bezüglich der Tag-Strukturen und Textplatzierungen rigoros zu überprüfen. Die Behandlung von Attributen klammern wir aus, sie ist aber nicht schwierig. Die eingelesenen Informationen wollen wir umsetzen in Objekte passenden Typs (Klassen BoxWorld, Box, Cube, Pile und Pyramid - siehe Datei listing_1.zip auf der CD) mit Beziehungen untereinander, die genau die hierarchische Anordnung der Elemente in der eingelesenen XML-Szenariobeschreibung wiedergeben sollen. Unser Beispiel-BoxWorld-Objekt soll, abschließend per toString() ausgegeben, so in der Ausgabe erscheinen:

box world:
"
    Ein Wuerfel und eine Kiste mit einer Pyramide, 
    noch einer Kiste und zwei Tuermen.
    Die innere Kiste ist leer.
  "
[cube, box:[pyramid, box:[], pile:[cube, pyramid], 
pile:[cube, cube]]]
Was nützt eine DTD?
Bekannt sind den meisten Lesern sicherlich die Begriffe des wohlgeformten und des gültigen XML-Dokuments: Wohlgeformt ist ein XML-Dokument im Wesentlichen, wenn die vorkommenden Start- und Ende-Tags ordentlich hierarchisch ineinander geschachtelt sind; eine DTD spielt hierfür keine Rolle, sie muss nicht einmal vorhanden sein. Gültig ist es im Wesentlichen, wenn es nicht nur wohlgeformt ist, sondern die Verschachtelungsstruktur der vorkommenden Start- und Ende-Tags zudem noch konform geht mit den Vorschriften der DTD. (Auch zu Attributen kann die DTD Vorschriften enthalten, worauf wir aber hier nicht eingehen.) Nun mag man hoffen, ein XML-Dokument verarbeite sich quasi im Handumdrehen, wenn denn eine DTD vorhanden ist und ein validierender Parser verwendet wird. Das ist ein Irrtum!
Zwar kann eine DTD beschreiben, welche vorkommenden Tags (und Attribute) in welcher hierarchischen Anordnung von einer verarbeitenden Applikation verstanden werden. Sie ermöglicht insofern, ein XML-Dokument auf Verarbeitbarkeit hin automatisch mit Hilfe eines validierenden XML-Browsers zu plausibilisieren. Aber selbst wenn eine Applikation XML-Dokumente über einen validierenden Parser internalisiert und verarbeitet, wird eine Änderung der DTD doch oft nicht ohne eine entsprechende Änderung von Programmcode für die Verarbeitung der XML-Dokumente einhergehen. Dann aber kann die Applikation auch auf die Eigenschaft "validierend" eines benutzten XML-Parser-APIs verzichten, wenn sie stattdessen das Validieren parallel zum Einlesen der XML-Dokumente selbst vornimmt. Wir werden sehen, wie dies effizient und strukturiert vonstatten geht.
Fehlertolerante oder exakte Parser
Zwei prinzipielle Herangehensweisen fallen mir ein, was das Analysieren eines XML-Dokuments angeht. Ich will sie hier als "exaktes Parsen" und "fehlertolerantes Parsen" bezeichnen. In diesem Artikel werde ich mich auf ersteres beschränken: Ich werde eine Vorgehensweise erklären, wie XML-Dokumente exakt syntaktisch analysiert werden. "Spezifikation" hierfür ist eine vorhandene DTD - und auch nur sie. Sonstige Bedingungen (die womöglich nicht mit den Mitteln einer DTD zu formulieren sind) sind zwar je nach Anwendungskontext verschieden denkbar, sich zu überlegen, wie ihre Implementierung in den Code noch integriert werden kann, überlasse ich aber den Lesern. Auch wie vorgegangen werden kann, wenn die korrekte Syntax durch eine Schema-Datei statt eine DTD beschrieben wird, werde ich nicht mehr thematisieren, da ich hoffe, dass dies allen Lesern dann selbst klar sein wird.
Es kann ferner sinnvoll sein, einen fehlertoleranten Parser zu implementieren, also einen, der seine DTD sozusagen "nur ungefähr" implementiert. Beispielsweise kann die Reihenfolge hintereinandergereihter XML-Elemente laxer gehandhabt werden, als die DTD vorschreibt, sofern immer noch alle geforderten Elemente auftauchen. Oder es kann tolerant auf fehlende oder unbekannte XML-Elemente reagiert werden, um so mit einem maßvollen Auseinanderlaufen von Applikation und XML-Dokumentenstruktur sinnvoll umgehen zu können. Fehlertolerantes XML-Parsing ist eine Variation von exaktem XML-Parsing und ich werde zu diesen Variationsmöglichkeiten nicht ins Detail gehen. Stattdessen geht es mir um die prinzipielle Technik, ohne Variation.
Wir sehen uns zunächst das kXML-API an, da die systematische Vorgehensweise hier übersichtlicher und sozusagen klassisch ist.
kXML-Parsing durch rekursiven Abstieg
Das Verfahren des rekursiven Abstiegs mit einer Symbolvorausschau von einem Symbol ist ein bekanntes und gerne verwendetes Standardverfahren zur syntaktischen Analyse von Sprachen im Allgemeinen. Es eignet sich vor allem dafür, die Syntaxanalysekomponente von Hand zu implementieren (anstatt sie von einem Parsergenerator generieren zu lassen). Voraussetzung für seine erfolgreiche Anwendung ist, dass sich die zu analysierende Sprache für das Verfahren eignet. Für jede XML-Sprache, die einer konkreten, korrekten DTD genügt, ist dies der Fall. Grund hierfür ist im Kern die Forderung aus der XML-Spezifikation [XML, Abschnitt E], dass "content models in element type declarations be deterministic". Was bedeutet hierin "deterministisch"?
Eine DTD ähnelt einer Programmiersprachengrammatik, auch wenn sie formal keine eigentliche Grammatik für entsprechende XML-Dokumente ist. Aber DTD-Regeln können in Grammatikregeln, wie man sie von Programmiersprachenbeschreibungen kennt, umgesetzt werden. Dies ist der Weg, den wir jetzt verfolgen werden, und zwar indem wir zu jeder Element-Typdeklaration einer DTD eine entsprechende Syntaxdiagramm-Regel (bekannt z.B. von Pascal) erzeugen.
Jeder typausdruck ist dabei entweder das Wort EMPTY oder aber ein regulärer Ausdruck, bestehend aus Operatoren, Klammern, Elementnamen und den Wörtern #PCDATA und #ANY, wobei wir im Folgenden zur Vereinfachung auf Vorkommen von #ANY verzichten werden. Wie wir einfach und systematisch durch wiederholte Anwendung von Erzeugungsvorschriften (man sagt: "induktiv") zu einem beliebigen typausdruck schrittweise ein zugehöriges Syntaxdiagramm erzeugen, im Kasten "Umsetzung von DTD-Elementtypdeklarationen in Syntaxdiagramme" beschrieben. Abbildung 2 zeigt, welche Diagramme sich im Fall unseres Beispiels für die Elemente pile und box ergeben, die interessante Elementtypdeklarationen aufweisen.


Abb. 2: Syntaxdiagramme für die Typdeklarationen der Beispiellemente pile und box. (Die angebrachten Zahlen sind nur für SAX2-Parsing interessant.)

Umsetzung von DTD-Elementtypdeklarationen in Syntaxdiagramme
Für den Entwurf eines XML-Parsers erhalten wir ein grafisches Modell in Form von Syntaxdiagrammen durch Anwendung verschiedener zusammenspielender Erzeugungsregeln für Syntaxdiagramme. Diese Regeln beschreiben für jede DTD-Elementtypdeklaration je nach den angewendeten regulären Operatoren im typausdruck in- und aneinanderzusetzende Syntaxdiagramm-Fragmente, die insgesamt ein vollständiges Syntaxdiagramm ergeben.
Eine der folgenden beiden Regeln formt die "äußere Hülle" des entstehenden Diagramms.


Fall typausdruck = EMPTY


Fall typausdruck = RA, RA ist ein regulärer Ausdruck


Die restlichen Regeln beschreiben einzeln je nach induktiver Zusammensetzung des regulären Typausdrucks RA innere Syntaxdiagrammfragmente.


Basisfall #PCDATA


Basisfall Elementvorkommen


Fall Optionsoperator '?'


Fall Konkatenationsoperator ','


Fall Alternativenoperator '|'


Fall '*'-Iterationsoperator


Fall '+'-Iterationsoperator:

Abbildung 2 dieses Abschnitts zeigt zwei Endergebnisse, anhand derer der Erzeugungsprozess nachvollzogen werden kann.
Wir können allgemein jedes Syntaxdiagramm als ein Schienennetz entlang zwei Sorten von Stationen mit einem Eingang (links) und einem Ausgang (rechts) ansehen. Oval gezeichnete Stationen geben an, wie ein "Satzanfang" um ein nächstes "Wort" direkt korrekt fortgesetzt wird. "Wort" meint in diesem Zusammenhang eine zusammenhängende Zeichenkette, wie sie das verwendete API, hier kXML, im Rumpf des analysierten XML-Dokuments erkennen und an die Applikation liefern kann, also die angetroffenen Starttags, Endetags und normalen Textabschnitte. Ausnahme sind Kommentare, die wir komplett herausfiltern, weswegen wir sie in den Syntaxdiagrammen nicht berücksichtigen müssen.
Eckig gezeichnete Stationen in den Syntaxdiagrammen sagen aus, dass vor der Fortsetzung an Ort und Stelle zunächst einen "Ausflug" (möglicherweise echt rekursiv) in das Schienennetz des angegebenen Elements erfolgt. Insgesamt erzeugt eine beliebige komplette Fahrt durch das Diagramm des Startelements inklusive aller möglicherweise durchzuführenden Ausflüge den vollständigen Inhalt eines gültigen XML-Dokuments zu der DTD. Das Analysieren eines XML-Dokuments zu unserer DTD bedeutet demnach, einen solchen Weg durch die Schienennetze zu finden, der das Dokument beschreibt. Und wir können nun sagen, dass die Syntaxdiagramme "deterministisch" sind, wenn beim Durchfahren des Diagramms an jeder möglichen Weggabelung die Entscheidung, welche Wegalternative weiterzuverfolgen ist, mit dem nächsten zu erkennenden Wort aus der Eingabe stets klar ist. Das Weiterlesen in der Eingabe und das Weiterverfolgen des zur Eingabestruktur passenden Weges durch die Diagramme ist gerade deshalb einfach, weil es aufgrund des geforderten Determinismus nur einen Lösungsweg geben kann, der sackgassenfrei parallel zum Lesen der Eingabe von links nach rechts gefunden werden kann. Und da dieser Prozess sackgassenfrei ist, kann das Verarbeiten der entlang des Weges eingelesenen XML-Dokumentfragmente unmittelbar in den Code zum Parsing eingearbeitet werden. Am Ergebniscode für unser Beispiel wird klar werden, was ich damit meine.

Im Anwendungsfeld XML bedeutet die Methode des rekursiven Abstiegs prinzipiell, für jede in der DTD vorkommende Elementtypdeklaration von der Form das Parsing eines entsprechenden Eingabeabschnitts ... mittels einer passenden Methode parseElement() zu behandeln, deren Rumpf die Struktur des typausdrucks genau reflektiert und nur noch ergänzt wird um Code zur Verarbeitung bzw. "Übersetzung" der gelesenen Informationen, die gegebenenfalls. als Returnwert an den Aufrufer propagiert wird. Um ferner die Benutzung des kXML-APIs erheblich zu vereinfachen, formulieren wir eine Methode void read(), die direkt auf dem kXML-API operiert und die aus Compilern bekannte typische Rolle einer Komponente zur lexikalischen Analyse spielt, nämlich die Erkennung von Zeichenketteneinheiten im Eingabezeichenstrom zu leisten. Sie beschafft den nächsten relevanten ParseEvent, hinterlegt ihn in der globalen Variablen nextParseEvent und überliest sogleich Kommentare und unbedeutenden Leerraum. Die von ihr ebenfalls gefüllten Klassenvariablen nextType, nextTag und nextStartTag geben dem Parsing-Code sehr einfach zusätzliche Auskunft über den nextParseEvent. Ebenfalls gezeigt sind zwei Spezialisierungen von read(), die helfen, den Parsing-Code noch übersichtlicher zu gestalten (siehe Listing 1).

Listing 1
protected void read() throws IOException
{
    // Read next ParseEvent into nextParseEvent/nextType
    // and nextTag, nextStartTag (if applicable)
    // skipping comment & whitespace.
    nextParseEvent = parser.read();
    nextType = nextParseEvent.getType();
    nextTag = nextStartTag = null;
    while (nextType == Xml.COMMENT || nextType == Xml.WHITESPACE)
    {
        nextParseEvent = parser.read();
        nextType = nextParseEvent.getType();
    }
    if (nextType == Xml.END_TAG)
        nextTag = (Tag) nextParseEvent;
    else if (nextType == Xml.START_TAG)
        nextTag = nextStartTag = (StartTag) nextParseEvent;
}
protected Vector readStartTag(String expectedTagName)
throws IOException
{
    Vector attr;
    if (nextType != Xml.START_TAG ||
        !nextStartTag.getName().equals(expectedTagName))
    {
        complain("Expecting <" + expectedTagName 
  + ">");
    }
    attr = nextStartTag.getAttributes();
    read();
    return attr;
}
protected void readEndTag(String expectedTagName)
throws IOException
{
    if (nextType != Xml.END_TAG ||
        !nextTag.getName().equals(expectedTagName))
    {
        complain("Expecting ");
    }
    read();
}
 
Unter Nutzung von read() liest nun eine parseElement()-Methode in der Eingabe voran und verfolgt dabei die gelesenen ParseEvents im Syntaxdiagramm zu element weiter, bis das Ende des Diagramms erreicht ist: An ovalen Stationen werden direkte Vergleiche durchgeführt, ob der aktuelle ParseEvent der erwartete ist. Eckige Stationen werden durch einen rekursiven Aufruf einer weiteren parseElement()-Methode abgewickelt. Die Aufrufe von read() werden ferner so platziert, dass grundsätzlich ein ParseEvent vorausgeschaut wird, insbesondere auch über die Grenze eines parseElement()-Aufrufs hinweg. Am Code für die Elemente pile und box unseres Beispiels ist gut zu erkennen, wie die in verschiedenen Teilausdrücken im jeweiligen typausdruck vorkommenden regulären Operatoren ?, * und + in entsprechende if-, while- und do-while-Anweisungen umgesetzt werden, die genau gemäß der Verschachtelungsstruktur des typausdrucks angeordnet werden. In den Bedingungen dazu wird auf das Vorliegen eines den Teilausdruck einleitenden ParseEvents geprüft. Code zur Verarbeitung gelesener Informationen ist zur Verdeutlichung blau eingefärbt (siehe Listing 2).

Die Gesamtstruktur der kXML-Lösung ist in Listing 3 gezeigt. Dies ist zwar noch nicht alles Wissenswerte zur kXML-Lösung unseres Beispielproblems. Für den letzten Rest verweise ich jedoch auf ein Selbststudium der vollständigen Java-Lösung auf der Heft-CD. Wer noch weitere Hilfe zum Verfahren des rekursiven Abstiegs benötigt, findet sie in Niklaus Wirths preiswertem Buch [Wirth96] über Compilerbau.

Listing 2
// DTD: 
protected Box parseBox() throws IOException
{
    ArrayList objects = new ArrayList();
    readStartTag("box");
    while (true)
    {
        if (nextType == Xml.START_TAG)
        {
            if (nextStartTag.getName().equals("box"))
                objects.add(parseBox());
            else if (nextStartTag.getName().equals("cube"))
                objects.add(parseCube());
            else if (nextStartTag.getName().equals("pile"))
                objects.add(parsePile());
            else if (nextStartTag.getName().equals("pyramid"))
                objects.add(parsePyramid());
            else
                complain("Expecting , , 
  , or ");
        }
        else
            break;
    }
    readEndTag("box");
    return new Box(objects);
}
// DTD: 
protected Pile parsePile() throws IOException
{
    ArrayList objects = new ArrayList();
    readStartTag("pile");
    objects.add(parseCube());
    if (nextType == Xml.START_TAG &&
 nextStartTag.getName().equals("pyramid"))
        objects.add(parsePyramid());
    else if (nextType == Xml.START_TAG &&
 nextStartTag.getName().equals("cube"))
    {
        objects.add(parseCube());
        while (nextType == Xml.START_TAG &&
 nextStartTag.getName().equals("cube"))
            objects.add(parseCube());
        if (nextType == Xml.START_TAG && 
nextStartTag.getName().equals("pyramid"))
            objects.add(parsePyramid());
    }
    else
        complain("Expecting  or ");
    readEndTag("pile");
    return new Pile(objects);
}
 

Listing 3
...
/**
 * kXML-based recursive descent parser for "box world 
  scenarios" described
 * as XML documents. Reconstructs the scenario by creating 
  corresponding
 * objects.
 *
 * @author Soenke Kannapinn, Wincor-Nixdorf GmbH & Co. 
  KG
 */
public class BoxWorldParser
{
    protected BoxWorldParser(XmlParser parser) {...}
    protected void complain(String text)
       throws ParseException {...}
    protected void read()
       throws IOException {...}
    protected String readText()
       throws IOException {...}
    protected Vector readStartTag(String expectedTagName)
       throws IOException {...}
    protected void readEndTag(String expectedTagName)
       throws IOException {...}
    // DTD: 
    protected BoxWorld parseBoxWorld()
       throws IOException {...}
    // DTD: 
    protected Box parseBox()
       throws IOException {...}
    // DTD: 
    protected String parseComment()
       throws IOException {...}
    // DTD: 
    protected Cube parseCube()
       throws IOException {...}
    // DTD: 
    protected Pile parsePile()
       throws IOException {...}
    // DTD: 
    protected Pyramid parsePyramid()
       throws IOException {...}
    protected BoxWorld parseDocument()
       throws IOException {...}
    /**
     * Parse and translate an XML "box world scenario".
     *
     * @param parser The kXML parser instance to be used.
     * @return The BoxWorld meaning 
  of the XML input.
     * @exception IOException in case of IO or parse errors.
     */
    public static BoxWorld parseAndTranslate(XmlParser parser)
       throws IOException {...}
    {
        return new BoxWorldParser(parser).parseDocument();
    }
}
 
SAX2-Parsing durch CallableContentHandler
Die gezeigten Codefragmente und Grafiken und darüber hinaus der Quellcode auf der Heft-CD haben hoffentlich das Verfahren des rekursiven Abstiegs prinzipiell klar machen können. Seine Stärken sind Effizienz, Strukturiertheit und die Tatsache, dass Code zur Verarbeitung der eingelesenen XML-Fragmente leicht direkt dem Parsing-Code überlagert werden kann und so jedwede Form von Zwischen-Datenstrukturen gänzlich vermieden wird. Das kXML-API eignet sich grundsätzlich dazu, dieses Verfahren problemlos anzuwenden - aus einem entscheidenden Grund: der Pull-Strategie, die es verfolgt. Die Kontrolle während des Parsings hat die Applikation und sie kann deswegen ihren Zustand bezüglich des Parsings in Codeposition und Laufzeitkeller ausdrücken. Dasselbe ist für die Applikation im Falle des SAX2-APIs mit seiner Push-Strategie nicht möglich. Wir wollen nun die Vorteile des Verfahrens des rekursiven Abstiegs auch im Kontext von SAX2 nutzen.
Es ist nicht schwer einzusehen und kann z.B. auch an Abbildung 2 beobachtet werden, dass die verschiedenen Stationen unserer Syntaxdiagramme mit den Callback-Methoden eines ContentHandlers korrespondieren, die ein SAX2-API abruft. Um stets im Bilde darüber zu sein, wie die bereits gelesene Eingabe korrekt fortgesetzt werden könnte, muss sich die Applikation anschaulich über die verschiedenen Callback-Aufrufe hinweg die aktuelle Position im aktuellen Syntaxdiagramm in einer Zustandsvariablen merken. Und die Applikation muss sich allgemein sogar zu beliebig vielen begonnenen Diagrammen in Kellermanier Fortsetzungspunkte merken, um exakt zu parsen. Schon für die Zustandsverwaltung beim Durchqueren eines einzigen Syntaxdiagramms ist es der Lesbarkeit des Codes abträglich, dass die einzelnen Aktivitäten zur Zustandsverwaltung über mehrere Methoden des ContentHandlers verteilt sind. Die Unübersichtlichkeit würde sich beträchtlich verschärfen, wenn die Applikation einen einzigen monolithischen ContentHandler für alle Syntaxdiagramme zusammen verwenden würde.
Glücklicherweise kann hier Abhilfe geschaffen werden: Wir werden die Idee konsequent umsetzen, je Syntaxdiagramm einen eigenen dedizierten ContentHandler zu implementieren und systematisch zwischen verschiedenen ContentHandlern umzuschalten, indem wir je nach Situation den gerade am SAX2-Parser registrierten ContentHandler ummelden. Wir verwenden dazu eine selbst geschriebene abstrakte Basisklasse CallableContentHandler, deren verschiedene Konkretisierungen sich sozusagen gegenseitig "aufrufen" und wieder zu ihrem "Aufrufer" zurückkehren. Eine Art Aufrufkette von CallableContentHandlern entsteht, indem jeder aufgerufene Handler eine Referenz auf den bei "Aufruf" noch installierten Handler hält. Bei "Rückkehr" zum beim "Aufruf" installierten Handler kann ein "Returnwert" übermittelt werden. Die Art und Weise, wie wir damit systematisch und strukturiert XML-Parsing auf Grundlage des SAX2-APIs betreiben, ist, abgesehen von der expliziten Zustandsverwaltung, dem am Beispiel des kXML-APIs vorgeführten Verfahren des rekursiven Abstiegs bestmöglich nachempfunden. Die abstrakte Klasse CallableContentHandler finden Sie in listing_2.zip auf der CD. Ihre Methode void characters(char [] text, int start, int length) ist vorformuliert für die Standardbehandlung von Leerraum, kann aber überladen werden, falls anderes Verhalten nötig ist.
Allgemein schreiben wir systematisch für das Parsing von Eingabefragmenten der Form ... gemäß einer DTD-Regel eine aus CallableContentHandler abgeleitete Klasse ElementCH, deren Konstruktor die Instanz des aufrufenden CallableContentHandlers mitgeteilt wird. Ein "Aufruf" eines frischen solchen YElementCH-Handlers von einem XElementCH-Handler aus geschieht durch new YElementCH(this).enter(). Die "Rückkehr" aus dem YElementCH-Handler an seinen "aufrufenden" Handler inklusive dem "Liefern" eines yResultObject geschieht durch Aufruf von void leaveYielding(yResultObject). Für die Übergabe des Return-Objekts stellt der aufrufende Handler eine Methode void receiveResult(Object result) zur Verfügung, die im Zuge der "Rückkehr" vom "aufgerufenen" Handler aktiviert wird. Für unser Kistenwelt-Beispiel finden Sie die ausprogrammierten (inneren) Klassen BoxCH und PileCH in listing_3.zip auf der Heft-CD; die vergebenen Werte für die jeweilige Zustandsvariable sind genau die in den entsprechenden Syntaxdiagrammen in Abbildung 2 eingezeichneten Zahlen. Aus diesen beispielhaften Fragmenten der Lösung geht hervor, wie ein Syntaxdiagramm systematisch in den Methoden eines CallableContentHandlers ausprogrammiert wird. Interessant ist, wie teilweise auf einen Callback-Aufruf sozusagen vorausgeschaut wird, um diesen dann an einen erst noch "aufzurufenden" anderen ContentHandler weiterzudelegieren.
Nachzudenken ist lediglich an der einen oder anderen Stelle noch darüber, wie Zustände an einem zu implementierenden Syntaxdiagramm korrekt vergeben werden müssen. Hierzu sind folgende Regeln zu befolgen, für deren Verdeutlichung ich einen erneuten Blick auf Abbildung 2 empfehle:
  • Außer für sehr einfache Diagramme muss stets ein Startzustand vergeben werden.
  • Für jeden "Aufruf" eines eingelagerten ContentHandlers (eckige Station) wird ein neuer Zustand vergeben, um den dabei berechneten "Returnwert" geordnet erwarten zu können.
  • Jeweils sozusagen an der Ausfahrt aus einer durchlaufenen Station (außer der Endstation des Diagramms, die nur noch das Endetag abarbeitet) wird ein Zustand platziert, der sich von dort aus entlang aller wegführenden Wege erstreckt. Es darf durchaus an verschiedenen Stationsausfahrten derselbe Zustand vergeben werden, aber nur dann, wenn von beiden Stationsausfahrten genau dieselben nächsten Stationen erreicht werden, da ansonsten anschaulich Sprünge im Diagramm möglich wären und damit die Fehlerhaftigkeit einiger XML-Eingaben nicht bemerkt würde.
Hinweisen möchte ich noch auf eine beliebte, aber unzulässige Vereinfachung im Zusammenhang mit dem Einsatz der Callback-Methode void characters(char [] text, int start, int length): Hier wird gerne der Hinweis in der SAX2-API-Dokumentation übersehen, dass längere Zeichenfolgen aus Effizienzgründen in mehreren Hintereinander-Aufrufen dieser Methode gestückelt abgeliefert werden können. Die einzelnen Textabschnitte müssen also in einem StringBuffer zunächst gesammelt werden, um erst verzögert in einen String umgesetzt zu werden.

Einen Überblick über die Gesamtstruktur der SAX2-Lösung gibt Listing 4.

Listing 4
package my.box.world;
import org.xml.sax.SAXException;
import org.xml.sax.SAXParseException;
import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.XMLReaderFactory;
import java.io.IOException;
import java.util.ArrayList;
/**
 * SAX2-based parser for "box world scenarios" 
  described as XML documents.
 * Reconstructs the scenario by creating corresponding objects.
 *
 * @author Soenke Kannapinn, Wincor-Nixdorf GmbH & Co. 
  KG
 */
public class BoxWorldParser
{
    static private class MainCH extends CallableContentHandler
    {
        // DTD: 
        public MainCH(XMLReader parser) {...}
        public void startElement(String namespaceURI, String 
  localName,
               String qName, Attributes atts) throws SAXException 
  {...}
        public void endElement(String namespaceURI, String 
  localName,
               String qName) throws SAXException {...}
        public void receiveResult(Object result) {...}
        public BoxWorld parse(InputSource is)
               throws IOException, SAXException {...}
    }
    static private class CommentCH extends CallableContentHandler
    {
        // DTD: 
        public CommentCH(CallableContentHandler caller) {...}
        public void startElement(String namespaceURI, String 
  localName,
               String qName, Attributes atts) throws SAXException 
  {...}
        public void characters(char[] text, int start, int 
  length)
               throws SAXException {...}
        public void endElement(String namespaceURI, String 
  localName,
               String qName) throws SAXException {...}
    }
    static private class BoxCH extends CallableContentHandler
    {
        // DTD: 
        public BoxCH(CallableContentHandler caller) {...}
        public void startElement(String namespaceURI, String 
  localName,
               String qName, Attributes atts) throws SAXException 
  {...}
        public void endElement(String namespaceURI, String 
  localName,
               String qName) throws SAXException {...}
        public void receiveResult(Object result) {...}
    }
    static private class CubeCH extends CallableContentHandler
    {
        // DTD: 
        public CubeCH(CallableContentHandler caller) {...}
        public void startElement(String namespaceURI, String 
  localName,
               String qName, Attributes atts) throws SAXException 
  {...}
        public void endElement(String namespaceURI, String 
  localName,
               String qName) throws SAXException {...}
    }
    static private class PyramidCH extends CallableContentHandler
    {
        // DTD: 
        public PyramidCH(CallableContentHandler caller) {...}
        public void startElement(String namespaceURI, String 
  localName,
               String qName, Attributes atts) throws SAXException 
  {...}
        public void endElement(String namespaceURI, String 
  localName,
               String qName) throws SAXException
    }
    static private class PileCH extends CallableContentHandler
    {
        // DTD: 
        public PileCH(CallableContentHandler caller) {...}
        public void startElement(String namespaceURI, String 
  localName,
               String qName, Attributes atts) throws SAXException 
  {...}
        public void endElement(String namespaceURI, String 
  localName,
               String qName) throws SAXException {...}
        public void receiveResult(Object result) {...}
    }
    private BoxWorldParser() throws SAXException {}
    /**
     * Parse and translate an XML "box world scenario".
     *
     * @param parser The SAX2 parser instance to be used.
     * @param inputSource Where to get the XML input document 
  from.
     * @return The BoxWorld meaning 
  of the XML input.
     * @exception IOException in case of IO or parse errors.
     */
    public static BoxWorld parseAndTranslate(XMLReader parser,
           InputSource inputSource)
       throws IOException, SAXException, SAXParseException
    {
        return new MainCH(parser).parse(inputSource);
    }
}
 
Ein paar Zahlen

Um einmal direkt gleichwertige Lösungen desselben Problems mit den verschiedenen Strategien zum XML-Parsing einander gegenüberstellen zu können, habe ich zusätzlich zu den vorgestellten Beispielapplikationen auf Basis von SAX2 und kXML auch noch äquivalente Applikationen erstellt, die das XML-Parsing über das DOM-API [DOM] und das JDOM-API [JDOM] abwickeln. Mit allen Lösungen wurden verschieden große XML-Dateien eingelesen und wie gezeigt in einen entsprechenden Objektbaum umgesetzt. Die dafür benötigten Laufzeiten auf meinem Scenic Mobile 360 (366 MHz Pentium II, Windows 98, JBuilder 5 mit JDK 1.3.0_02) sind in Tabelle 1 zusammengestellt. Die benötigte Laufzeit ist erfahrungsgemäß auch ein gutes Indiz für die schwierig präzise zu bestimmende Heap-Belastung. Die Zahlen sollten nicht überinterpretiert werden, da ich mir keine Mühe gemacht habe, z.B. Zeiten zum Laden von Klassen und JIT-Kompilationen herauszurechnen. Sie machen hauptsächlich relativ zueinander Sinn und bestätigen grundsätzlich meine Behauptung, dass die Bequemlichkeit von *DOM-basiertem XML-Parsing ihren Preis hat. Als Implementierung von SAX2 und DOM kam Xerces [Xerces] zum Einsatz.

Tabelle 1
XML-Eingabegröße
1 K
10 K
100 K
1000 K
Applikation auf Basis
Laufzeit
kXML 1.20
110 ms
170 ms
490 ms
1090 ms
SAX2 (Xerces 1.2.2)
1150 ms
1370 ms
1760 ms
3570 ms
DOM (Xerces 1.2.2)
1650 ms
1760 ms
2750 ms
6920 ms
JDOM Beta 7
1430 ms
1650 ms
2690 ms
7360 ms

Ein kurzes Fazit

kXML-basiertes XML-Parsing führt zu kompaktem und schnellem Code. Das Anlaufen des Parsers ist auffällig schnell. Aus Applikationssicht geschieht die Zustandsverwaltung beim Parsing geschickt über Codeposition und Aufrufstack. Der Ressourcenverbrauch ist schlank. Aber auch das kXML-API ist nicht perfekt in Sachen Sparsamkeit: Es werden zu viele ParseEvent-Objekte erzeugt, die von der Applikation dann gar nicht verarbeitet werden (Whitespace, Comment, Processing Instructions).
SAX2-basiertes XML-Parsing ist aus Sicht der Applikation in mehreren Belangen problematisch: Erstens drängt die Push-Strategie der Applikation eine komplizierte Zustandsverwaltung auf. Übersichtlichkeit schafft hier erst unsere selbst geschriebene CallableContentHandler-Klasse. Das Anlaufen zumindest der Xerces-Parser-Implementierung ist erheblich langsamer als das des kXML-Parsers.
JDOM- und DOM-basierte Lösungen sind aufgrund ihres Ansatzes in Laufzeit und sicher auch Heap-Belastung merklich teurer. Falls Performance im Projekt eine wesentliche Rolle spielt, sollten APIs auf niedrigerem Abstraktionsniveau, wie es SAX2 oder kXML sind, vorgezogen werden, wobei SAX2-basiertes XML-Parsing kniffliger gut zu lösen ist. Ich fürchte, einen guten SAX2-basierten Parser zu implementieren, dürfte Otto, den Normal-Programmierer, oftmals überfordern. Wie dies vonstatten gehen kann, habe ich hoffentlich verdeutlichen können.
Von Suns JAXB-Data-Binding-Ansatz ist mittlerweile eine Early-Access-Implementierung erhältlich [JAXB], die für das Transformieren von Objekten nach und von XML (Marshalling und Unmarshalling) wertvolle Automatisierungsunterstützung darstellen dürfte: Unter anderem wird aus einer DTD und einer Abbildungsspezifikation effizienter Code zum speziellen XML-Parsing generiert, sodass sich Anwender mit dieser Problematik demnächst vielleicht nur noch in spezielleren Fällen werden befassen müssen.
Literatur und Links


    Hat Ihnen dieser Artikel gefallen? Dann abonnieren Sie das Entwickler Magazin direkt über unser Online-Formular.

zur vorherigen Seite
zurück
an den Anfang der Seite
nach oben
Diesen Artikel drucken
drucken
Diesen Artikel weiterempfehlen
empfehlen




Software & Support Verlag GmbH