Strukturiertes und effizientes XML-Parsing mit den APIs SAX2

Kistenwelt

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 Abpictureung 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. Abpictureung 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

Abb. 2: Syntaxdiagramme für die Typdeklarationen der Beispiellemente pile und box. (Die angebrachten Zahlen sind nur für SAX2-Parsing interessant.)
Abpictureung 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
element typausdruck>
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 ");
    }
    attr = nextStartTag.getAttributes();
    read();
    return attr;
}
protected void readEndTag(String expectedTagName)
throws IOException
{
    if (nextType != Xml.END_TAG ||
        !nextTag.getName().equals(expectedTagName))
    {
        complain("Expecting " + expectedTagName 
  + ">");
    }
    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 Abpictureung
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 Abpictureung
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 Abpictureung 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 Abpictureungsspezifikation
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
Geschrieben von
Sönke Kannapinn
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.