Studienarbeit am Institut für Informationssysteme



Generierung validierender LL(1)-Parser für XML-Dokumente


Beschreibung

Gegenstand der Studienarbeit ist die Entwicklung eines Generators für optimierte XML-Parser, die die analysierten Dokumente gleichzeitig auf Gültigkeit überprüfen. Für die Problemstellung soll, aufbauend auf einem aus der Literatur bekannten Algorithmus zur Umsetzung von regulären Ausdrücken in deterministische endliche Automaten, eine Lösung entworfen werden. Diese Lösung, die einen LL(1)-Parser-Generator realisiert, kann sich entweder in eine bereits bestehenden Implementierung einfügen oder neu umgesetzt werden.

Im einzelnen sind folgende Teilaufgaben zu erfüllen:

  1. Zunächst ist eine Einarbeitung in die Definition von Auszeichnungssprachen mittels XML-Dokumenttyp-Definitionen (DTDs) notwendig. Danach wird durch eine große DTD (evtl. aus dem Bereich des Open-Financial-Exchange (OFX)) und dazu gültigen kleinen Dokumenten ein Testszenario definiert, für welches die Leistungsfähigkeiten der gängigen validierenden XML-Parser überprüft werden.
  2. Die Arbeitsweise des Algorithmus' zur Umsetzung von regulären Ausdrücken in deterministische endliche Automaten nach Ullman ist ebenfalls zu erarbeiten und anschließend zu implementieren. Diese Implementierung soll einen Parser erzeugen, der die Gültigkeit eines Dokuments schon während der syntaktischen Analyse ermittelt, wobei das Inhaltsmodell der zugrundeliegenden DTD ausgenutzt wird. Dabei ist es freigestellt, ob ein bestehender XML-Parser um diese Funktionalität erweitert und ergänzt wird, oder ob eine eigenständige Entwicklung vorgenommen wird.
  3. Zuletzt ist das oben definierte Testszenario auf die eigene Implementierung anzuwenden und mit den schon ermittelten Ergebnissen zu vergleichen.

Vorkenntnisse:
Vorlesung Datenbanksysteme
Grundlagen in XML und JAVA

Bearbeiter:
Tobias Mende

Ergebnis:
Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden.

Betreuung:
Martin Kempa
Institut für Informationssysteme
Osterweide 8
23562 Lübeck
Telefon: 0451/502530

15.10.2001 webmaster