Dotplot Parser

Aus THM-Wiki
Wechseln zu: Navigation, Suche

Einleitung

Allgemein

Im Sommersemester 2006 fand ein Schwerpunktpraktikum bei Herrn Quibeldey-Cirkel statt. Thematik war die Dotplot Software, die über mehrere Semester von Studenten entwickelt bzw. erweitert wurde. In der Vorbesprechung zu dem Praktikum kristallisierten sich 3 Themengebiete heraus, die erweitert werden müssen.

  • Das Parser Plugin
  • Die Neugestaltung des GUI
  • Bio Java + Alignments

Unsere Wahl fiel auf das Parser Plugin.

Beschreibung des Plugins

Das Parser Plugin soll es ermöglichen die Semantik eines Codes zu vergleichen. Dazu wird der Code nach Tokens gescannt und mit den Tokens anschließend ein Baum generiert. Dies geschieht mit Hilfe von JavaCC. Ab hier beginnt die eigentliche Arbeit des Plugins: Das Filtern unötiger Knoten und das generieren für Dotplot interessante Token.

Aufgabenstellung

Zu Beginn unserer Arbeiten existierte schon eine Implementation eines Parser für die Programmiersprachen Java und PHP. Bedingt durch die Diplomarbeit von Christian Gerhardt hatte sich aber die Architektur von Dotplot grundlegend geändert, was dazu führte das der Parser nicht mehr kompatibel zu Dotplot war. So stellte sich uns die Aufgabe den vorhandenen Quellcode zu analysieren und neu zu implementieren. Eine weitere Aufgabe wurde durch eine frühe Analyse des Quellcodes sichtbar. Es bestanden viele ungenutzte Klassen und Methoden. Desweiteren war der vorhandene Quellcode auch unzureichend Dokumentiert, was eine Einarbeitung für weitere Teams sehr kompliziert machte. Diesen Notstand sollten wir beheben, in dem wir den Code übersichtlicher gestallten.

Analyse des vorhandenen Quellcodes

Ablauf des alten Parser Plugins
getNextToken() dargestellt als Flussdiagramm

Für die erste Analyse des Parsers hatte zunächst jedes Teammitglied für sich selber den Quellcode angeschaut. Danach wurden in einer kleinen Runde die Ergebnisse zusammengetragen. Um uns ein Bild über die Funktionsweise des Parsers zu machen, erstellten wir uns eine Grafik die den Ablauf kurz darstellt.

Nach einer weiteren Analyse des Quellcodes wurde schnell klar, dass die Methode getNextToken() die zentrale Arbeit verrichtet. Die Funktionsweise machten wir uns anhand eines Flussdiagrammes klar.

Als Verbesserungspunkte konnten wir folgendes ausarbeiten:

  • Die Funktionalität ist zentral in einer Methode. Dies sollte geändert werden.
  • Der Parser arbeitet mit einer alten JavaCC Version. D.h. Update erforderlich
  • Unnötige imports
  • deprecated Methoden müssen auf Java 1.5 umgeschrieben werden
  • Sourcecode ist sehr abhängig von externem Tool (JavaCC)
  • Erweiterung um neue Programmiersprache sehr aufwändig
  • Parser nicht flexibel genug, um evtl. das vergleichen von verschiedenen Programmiersprachen zu realisieren

Erste Lösungsvorschläge

Grundidee
Lösungsvorschlag 1
Lösungsvorschlag 2

Grundidee

Die erste Idee kam uns direkt nach der Analyse des vorhanden Quellcodes. Um das Problem der zentralen Methode zu umgehen, überlegten wir uns eine interne Pipes & Filters Architektur.

Dieser Vorschlag war nur eine grobe Idee, wie man etwas mehr an Flexibilität gewinnt. Auch hatten wir mit diesem Entwurf schon versucht die generierten Syntax Bäume auf einen gemeinsamen Nenner zu bringen, was einer Metasprache sehr nahe kommt. So wäre zum Beispiel ein Vergleich von verschiedenen Sprachen denkbar gewesen.

Doch war diese Idee keineswegs auf die neue Architektur von Dotplot ausgelegt, was uns nochmal dazu bewegte das Konzept zu überarbeiten. Das primäre Problem ist, dass das Service Framework nur einen bestimmten Typ im ganzen Verlauf durchreichen kann. So wäre unsere Idee unbrauchbar, da wir intern einige Typkonvertierungen geplant hatten. So mussten neue Ideen her, die mit nur einem Typ auskommen.

Lösungsvorschlag 1

Die erste Idee war, das wir den Typ, den wir von dem Sourcecode bekommen, einfach durchreichen bis zum Tokenizer. Dies ist eine der einfachsten Methoden, birgt aber wesentliche Nachteile:

  • Sollte sich der AST ändern, so müssen der Filter und der Tokenizer angepasst werden
  • Abhängigkeit zu JavaCC immer noch vorhanden
  • unterschiedliche Sprachen können nicht verglichen werden

Lösungsvorschlag 2

Als zweiten Lösungsvorschlag hatten wir uns überlegt, das man die Converterunterstützung des Frameworks nutzen könnte. Mit einem Converter ist es zum Beispiel möglich den Typ, den man von dem Sourcecode bekommt, in einen anderen Typ zu konvertieren, bevor der Tokenizer seine Arbeit aufnimmt.

So hatten wir die Idee, den Sourcecode in einem Converter zu einer Metasourcecodefile umzuwandeln. So würde der Tokenizer immer mit dem gleichen Typ arbeiten. Mit diesem Entwurf würden viele Punkte der Anforderung gelöst werden, aber es kommen dann neue Probleme hinzu:

  • Es muss ein eigener Parser für eine Metasprache entwickelt werden
  • man muss sich eine Metasprache ausdenken

Diese Punkte waren aus unserer Sicht in der vorgegebenen Zeit nicht machbar. Daher entschlossen wir uns eine Kompromisslösung zwischen den zwei vorgestellten Konzepten zu machen.

Endgültige Lösung

Die Architektur des Plugins besteht aus 4 grundsätzlichen Teilen. Dies machte die Arbeit im Team einfacher, da parallel gearbeitet werden konnte. Das Klassendiagramm zeigt das Zusammenspiel der einzelnen Komponenten, die im folgenden weiter erläutert werden.

Klassendiagramm

Converter

Ablauf des Converters

Für jede unterstützte Programmiersprache existiert eine Converterklasse. Da sich eine zentrale Funktionalität aller Converter abzeichnete, wurde diese in eine abstrakte Basisklasse ausgelagert. Von dieser Klassen erben alle spezifischen Converter.

z.B.: public class JavaParserConverter extends ParserConverter

Sollte sich in Zukunft eine andere Funktionsweise für weitere Converter ergeben, so würde der neue Converter nicht von ParserConverter erben, sondern von der darüber liegenden Schnittstelle IConverter. Diese Schnittstelle wird auch von der abstrakten Klasse ParserConverter implementiert.

public abstract class ParserConverter implements IConverter

Die Implementierung der Schnittstelle IConverter ist insofern wichtig, da das Dotplot-Framework für eine zu konvertierende Quellcodedatei, die convert() Methode des dazugehörigen Converters aufruft.

Diese Methode ist der zentrale Einstiegspunkt in den Converter. Dort wird die Sourcodedatei entgegen genommen, auf Gültigkeit geprüft, in den neuen Typ konvertiert und in einer neuen Datei gespeichert.

Zur Generierung der neuen Datei wurde eine Hilfsmethode mit dem Namen convertFile geschrieben. Diese Methode überprüft ob der Typ der reinkommende Datei stimmt und delegiert die Hauptarbeit an eine weitere Hilfsmethode namens createFile. Die Konvertierung des reinkommenden Sourcecodes wird durch die dazugehörge Mapperklasse realisiert.

Document mappedAst = this.astMapper.createMappedAst(dotplotFile);

Das private Feld astMapper wird in der speziellen Converterklasse im Konstruktor gesetzt. z.B. beim JavaParserConverter:

this.astMapper = new JavaAstMapper();  

Nach der Konvertierung durch den Mapper, wird das neue Dokument im temporären Verzeichnis gespeichert und eine Referenz auf diese Datei wird durchgereicht bis zur convert Methode. Der letzte Schritt besteht daraus, dass ein neues DotplotFile Objekt erzeugt wird und an das Dotplot Framework zurückgegeben wird.

Mapper

Wie bei den Convertern, so existiert auch beim Mapper für jede unterstützte Programmiersprache eine Mapperklasse.

Ein Mapper hat die Aufgabe die reinkommende Sourcodefile zu parsen und in ein spezielles XML Dokument umzuwandeln. Für das Parsen wird ein mit JavaCC generierter Parser benutzt, der eine Baumstruktur aufbaut. Zum Umwandeln in XML wird dieser Baum durch das Visitor Muster durchlaufen und mit der ConfigMapper Klasse auf die allgemeinen Knotennamen abgebildet.

Jeder Mapper implementiert das IAstMapper- und das jeweilige Visitor-Interface.

z.B.: public class JavaAstMapper implements IAstMapper, JavaParserVisitor

Der Einstiegspunkt in den Mapper ist die createMappedAst Methode, die den original Sourcecode rein bekommt. Hier wird ein Configmapper erzeugt,

String resourceName = "org/dotplot/parser/mapper/MapperConfig.xml";
InputStream configStream = Thread.currentThread().getContextClassLoader().getResourceAsStream(resourceName);
this.config = new NameConfigMapper(configStream);
this.config.setLanguage("Java");

der Sourcecode geparsed

JavaParser parser = new JavaParser(source.getInputStream());
ASTCompilationUnit compilationUnit;
compilationUnit = parser.CompilationUnit();

und das XML Dokument erzeugt.

initXML();
this.indent = 1;
xmlDocument.appendChild((Element) compilationUnit.jjtAccept(this, null));

Für jeden Knotentyp, des durch den Parser generierten Baumes, existiert eine visit Methode. Dort wird eine zentrale Methode mit dem Namen mainVisit aufgerufen. Ihr wird der Knotenname und der aktuelle Knoten übergeben.

z.B.: return mainVisit(node, "SimpleNode");

In der mainVisit Methode wird mit der Hilfe des ConfigMappers der Name des Knotens auf einen einheitlichen Namen abgebildet. Daraus wird dann ein XML Element erzeugt.

outputNode = config.getOutputNodeName(nodeData);
newElement = this.xmlDocument.createElement("Node");
newElement.setAttribute("Name", outputNode);
newElement.setAttribute("Indent", Integer.toString(this.indent));
newElement.setAttribute("Type", Integer.toString(config.getOutputNodeId(outputNode)));

Hat der Knoten noch Kindknoten, so wird aus jedem dieser Knoten durch einen Aufruf der accept Methode ein XML Element erzeugt und dem Vaterknoten angehängt.

if (node.jjtGetNumChildren() > 0) {
	for (int i = 0; i < node.jjtGetNumChildren(); ++i) {
		childElement = (Element) node.jjtGetChild(i).jjtAccept(this, null);
		newElement.appendChild(childElement);
	}
}

Ist der Baum komplett durchlaufen, so wird der Wurzelknoten an die createMappedAst Methode zurück gegeben, die daraus ein XML Dokument erzeugt.

Dieses Dokument wird dann an den Converter zurückgegeben.

ConfigMapper

Der ConfigMapper hat die Aufgabe die Arbeit mit der Konfigurationsdatei zu vereinfachen. So bietet er mehrere Methoden an, um an bestimmte Daten zu kommen. Die Konfigurationsdatei ist ene XML Datei und beinhaltet die Zuordnungen der durch JavaCC generierten Knotennamen zu den internen Knotennamen.

Die Basis des ConfigMappers bildet die Schnittstelle IConfigMapper. Diese wird durch die konkrete Klasse NameConfigMapper implementiert.

Um den ConfigMapper zu benutzen, muss man zuerst angeben für welche Programmiersprache die Knotennamen gewünscht sind. Dies macht man im Konstruktor

this.config = new NameConfigMapper(configStream, „Java“);

oder mit der Methode setLanguage

this.config = new NameConfigMapper(configStream);
this.config.setLanguage("Java");

Mit der Methode getOutputNodeName erhält man einen abgebildeten Knotennamen. Mit getOutputNodeId erhält man die dazugehörige interne ID.

Tokenizer

Der ParserTokenizer implementiert die durch das Framework vogegebene Schnittstelle ITokenizer.

Der Einstiegspunkt ist die setPlotSource Methode, die vom Framework als erstes aufgerufen wird, wenn Tokens generiert werden sollen.

Hier wird die Referenz auf die Quelle gespeichert,

if (this.getStreamType().getClass().isAssignableFrom( source.getType().getClass())){
	this.plotSource = source;
}
else {
	throw new UnassignablePlotSourceException("PlotSource is not of type MappedAst.");
}

und die Quelle auf Gültigkeit geprüft.

try {
	MappedAstValidator v = new MappedAstValidator();
	v.validateMappedAst(source.getInputStream());
	...
}
catch (SAXException e) {
	throw new UnassignablePlotSourceException("PlotSource is not valid for parsing: " + e.getMessage());
}

Als nächstes wird die Quelle mit der Hilfe eines SAX-Parser, der durch die Klasse MappedAstSourceReader implementiert ist, geparsed und anschließend die Tokens erzeugt. Diese werden in einer ArrayList vom Typ Token gespeichert und an den ParserTokenizer zurückgegeben.

MappedAstSourceReader reader = new MappedAstSourceReader();
...
this.tokens = reader.parseStream(source.getInputStream());

Letztendlich wird eine Referenz auf einen Iterator gespeichert, um die Tokens nacheinander durchzugehen.

this.iterator = this.tokens.iterator();

Zum Generieren von Tokens wird durch das Framework die Methode getNextToken aufgerufen. Dort wird der gespeicherte Iterator genutzt und die Tokens werden nacheinander an das Framework weitergegeben.Ist man ende des Tokenstreams angelangt, wird ein EOSToken (End Of Stream Token) zurückgegeben.

if (this.iterator == null)
	throw new TokenizerException("Could not get an iterator over the MappedAstSource.");
if (this.iterator.hasNext())
	return (Token) this.iterator.next();
else
	return new EOSToken();

Vorgehensweise um neue Programmiersprache hinzuzufügen

Converter

Der neue Converter wird von ParserConverter abgeleitet und die Methoden angepasst. Hierzu müssen lediglich ein neuer Konstruktor und getSourceType() geschrieben bzw. überschreiben werden. Im Konstruktor ist der spezifische Mapper astMapper zuzuweisen. GetSourceType muss den Typ der neuen Sprache zurückliefern. Bsp. neue Sprache C:

public ISourceType getSourceType()
{
	return Ctype.type;
}

Mapper

Als erstes sollte eine neuer JJParser hinzugefügt werden. Dazu ist die Grammatik der neuen Sprache notwendig, die man auf der JJ-Projektseite finden sollte. Nachdem diese übersetzt ist (näheres auf der Projektseite) sollte sie unter org.dotplot.parser.mapper.xxx hinzugefügt werden.

Nun muss ein Mapper geschrieben werden, der IAstMapper und das Visitor-Interface des JJParsers implementiert. Mit Hilfenahme des NameCongMapper können nun die Knotennamen auf die internen Namen gewandelt werden.

Configfile

Jetzt sollte die XML-Datei, die die Zuordnung enthält erweitert werden.

Eine neue Language-ID einführen:

<KnownLanguages>
<Language id="3"/
</KnownLanguages>

Die JJTree-Knotennamen bekannt machen:

<Language name="xxx" id="3">
<Map inputNodeName="'odeName" outputNodeId="0"/>
</Language>

Über die outputNodeId den Sprachknoten einen internen Knotennamen zuordnen.