JavaCC, JJTree und das Visitor-Pattern
Das Visitor-Pattern ist ein wichtiges Entwurfsmuster beim Aufbau von Parsern. Dieser Artikel zeigt die Verwendung des Patterns unter Verwendung von JavaCC und JJTree.
Der Parser benötigt zusätzlich die Jar-Datei des JPGD-Projektes (http://www.alexander-merz.com/graphviz/)
Syntaxbäume
Aufgabe eines Parser ist üblicherweise ein Dokument einzulesen und den Dokumenten-Inhalt in eine Datenstruktur zu überführen. Zwei Varianten sind dabei denkbar: die Ziel-Datenstruktur wird während des Parse-Vorganges sofort erzeugt und befüllt, oder es wird zuerst ein Syntaxbaum erzeugt und aus diesem Syntaxbaum die endgültige Datenstruktur gebildet. In vielen Situationen ist der Aufbau eines Syntaxbaum unumgänglich, gerade wenn eine Struktur mehrmals durchlaufen werden muss.
Die meisten Parser-Generatoren unterstützen die automatisierte Erzeugung von Syntaxbäumen. JavaCC unterstützt sie über JJTree. JJTree arbeitet als Präprozessor für den eigentlichen JavaCC-Prozessor.
In einer jjt-Datei wird dazu die Grammatik mit den erforderlichen Produktion wie üblich definiert, z.B.:
...
void node_attribute() : {}
{
node() attrib_list()
}
void node() : {}
{
<ID>
}
void attrib_list() : {}
{
<LBRACKET>
(attribute())*
<RBRACKET>
}
void attribute() : {}
{
...
}
...
com/alexmerz/simpleviz/parser/simpleviz.jjt
Die jjt-Datei wird dem JJT-Präprozessor übergeben, der daraus eine
gleichnamige jj-Datei erzeugt. Vom JJT-Präprozessor wird der
erforderliche Code eingefügt, um die Baumstruktur aufzubauen. Dadurch ist
die Art des Baumaufbaus sehr transparent. Einziges Problem ist, das der
Präprozessor selbst keine Grammatik-Analyse vornimmt, sondern dies
JavaCC bei der jj-Datei überlässt.
Damit beziehen sich Zeilenangaben in Fehlermeldungen natürlich auf die
jj-Datei und nicht auf die jjt-Datei.
Für jedes erkannte Nicht-Terminalsymbol wird dabei automatisch ein Knoten im Baum
erzeugt. JJTree verwendet für Knoten standardmäßig Objekte der Klasse
SimpleNode. Der resultierende Syntaxbaum würde so aussehen:
- node_attribute
- node
- attrib_list
- attribute
- attribute
Eigene Knotenobjekte
Wir benötigen eigene Knotenobjekte, welche Methoden und Objekt-Variablen
enthalten, die entsprechende Daten aufnehmen. Diese Klassen
generiert und benutzt JJTree automatisch, wenn wir die Definition der
Produktionen entsprechend ergänzen. Dazu muss im options-Block
der jjt-Datei die Option MULTI auf true gesetzt
und die Klassennamen hinzugefügt werden.
...
void node_attribute() #NodeAttribute : {}
...
void node() #Node : {}
...
void attrib_list() : {}
...
void attribute() #Attribute : {}
...
com/alexmerz/simpleviz/parser/simpleviz.jjt
Als Folge daraus werden drei Klasse erzeugt: ASTNodeAttribute, ASTNode und ASTAttribute, alle sind direkt von SimpleNode abgeleitet. Diese Klassen können wir nun bearbeiten, sie werden von JJTree nicht mehr angefasst – nur neu generiert, wenn sie gelöscht wurden. Der Prefix AST in den Klassenname kann durch eine entsprechende Option geändert werden.
Es fällt auf, dass attrib_list() keine Klasse zugewiesen wird, das
ist für die Anwendung auch gar nicht notwendig. Schließlich wissen wir, dass
wenn ein node_attribute auftritt, der nachfolgende Knoten ein
node() sein muss, dem beliebige viele attribute() folgen.
Ein Knoten für attrib_list() wäre hier also redundant. Wir setzen
deshalb Option NODE_DEFAULT_VOID auf true,
dann wird für diese Produktion kein Knoten im Syntaxbaum erzeugt.
Der resultierende Syntaxbaum ist damit:
- NodeAttribute
- Node
- Attribute
- Attribute
- ...
Die entsprechenden Klassen ergänzen wir um den erforderlichen Code. Für
ASTNode kann das z.B. so aussehen:
public class ASTNode extends SimpleNode {
private String id="";
public void setId(String id) {
this.id = id;
}
public String getId() {
return id;
}
...
}
com/alexmerz/simpleviz/ASTNode.java
Die node()-Prduktion ändern wir entsprechend, damit der Wert in der Klasse gespeichert wird:
void node() #Node : {Token t;}
{
t = <ID> {jjtThis.setId(t.image);}
}
Die Variable jjtThis enthält das aktuelle Knoten-Objekt, hier also
ein ASTNode-Objekt.
Syntaxbaum als Datenstruktur?
Nun könnte man auf die Idee kommen diesen Mechanismus zu nutzen und die
Knoten-Objekte direkt für die Ziel-Datenstruktur nutzen.
Es gibt allerdings einige Gründe, die dagegen sprechen:
- Es ist meist sehr aufwendig, die Grammatik entsprechend so zu formulieren, dass sie möglichst nah an die Ziel-Datenstruktur herankommt.
- Änderungen an der Ziel-Datenstruktur beeinflussen die Formulierung der Grammatik und umgekehrt.
- Der Syntaxbaum sollte möglichst leichtgewichtig sein, um den Parse-Vorgang so schnell und speichersparend wie möglich zu halten.
Üblicherweise ist das Parsen eines Dokumentes kein Selbstzweck, die Ziel-Datenstruktur soll für irgendetwas benutzt werden. Bei einer Programmiersprache müssen die entsprechenden Low-Level-Befehle generiert bzw. ausgeführt werden. Bei Grafikformaten, wie z.B. SVG muss der Inhalt gerendert werden. Der Parse-Vorgang sollte keinesfalls länger dauern als die eigentliche Aktion. Oder strikter: die Dauer des Parse-Vorganges sollte gegenüber der eigentlichen Aktion überhaupt nicht ins Gewicht fallen.
Nehmen wir ein Beispiel: Das Graphviz-Format beschreibt Graphen, deren Knoten und Kanten. Ein entsprechendes Werkzeug erzeugt aus einer Graphviz-Datei ein entsprechendes Bild. Das Objekt für eine Kante enthält somit neben der Angabe, welche Knoten miteinander verbunden sind, auch Daten, wie z.B. die Darstellungsfarbe der Linie, die Dicke der Linie, das Linien-Muster usw. Dazu kommen vielleicht noch Daten, die erst noch berechnet werden müssen, wenn das Objekt erstellt wird, wie die Pixel-Länge der Linie. Die Erzeugung eines entsprechenden Objektes ist damit relativ teuer. Noch problematischer wird es, wenn sich die Eigenschaften eines Objektes aufgrund von späteren Anweisungen im Dokument noch ändern können.
Es ist richtig, dass dieser Aufwand irgendwann getrieben werden muss, aber idealerweise sollte das erst geschehen, wenn wir sicher sind, dass unser Dokument überhaupt das richtige Format hat. Es ist frustrierend, wenn ein großes Dokument fünf Minuten lang "geladen" wird, um dann in der letzten Zeile ein vergessenes Komma festzustellen und einen große Syntaxbaum wegzuwerfen.
Deshalb sollte der Baum auch nur die Daten enthalten, die unbedingt notwendig sind, Redundanzen und jegliche Berechnungen vermieden werden.
Visitor-Pattern
Aus Sicht der Objektorientierung sind "dumme" Datenstrukturen natürlich ungünstig, aber wie gezeigt, sinnvoll. Allerdings entsteht dadurch ein anderes Problem: Wie bauen wir nun die Ziel-Datenstruktur zusammen?
Ergänzen wir entsprechende Methoden in den Knotenobjekten, landen wir wieder bei schwergewichtigen Objekten. Platzieren wir entsprechende Methoden in den Objekten der Zielstruktur selbst, heben wir die gewünschte Trennung zwischen Zielstruktur und Syntaxbaum auf.
Komplizierter wird es auch noch durch die verschiedenen Klassen im Syntaxbaum. Z.B. besitzt die Node-Klasse einen Identifier plus entsprechende Zugriffsmethoden, eine Klasse für eine Kanten-Anweisung besitzt diese nicht, dafür eine Variable für die Art der Kante (gerichtet/ungerichtete Kante). Eine einfache Methode der Art: Durchlaufe alle Objekte und rufe dessen getId()-Methode auf, wird also fehlschlagen. Nun gut, wir können Fallunterscheidungen integrieren: Wenn Klasse ASTNode, dann ..., wenn ASTEdge, dann... Je mehr unterschiedliche Klasse aber existieren, um so unübersichtlich wird es. Und das Ausführungsverhalten aufgrund von Klassenarten zu steuern, gilt aus verschiedenen Gründen als schlechter Stil.
Eine Lösung des Dilemmas bietet das Visitor-Pattern. Im Grundprinzip ist dieses Pattern von der obigen Idee nicht weit entfernt.
Wir benötigen auf jeden Fall in jeder Klasse im Syntaxbaum eine einheitliche Methode accept(). Dieser Methode wird ein Objekt einer Visitor-Klasse übergeben. Diese Visitor-Klasse wiederum besitzt eine festgelegte Methode: visit(). Dieser Methode übergibt sich das Objekt selbst als Parameter.
Was zunächst sehr seltsam wirkt, wird in einem konkreten Beispiel klarer. JJTree unterstützt das Visitor-Pattern. Dazu muss im options-Block die Option VISITOR auf true gesetzt werden. Der JJTree-Präprozessor ergänzt darauf die SimpleNode-Klasse um die Methode jjtAccept(). Und es erzeugt ein Interface <Name des Parsers>Visitor (im SimpleViz-Beispiel: JJTParserVisitor).
In diesem Visitor-Interface wurde für jede Knotenklasse eine
visit()-Methode deklariert:
public interface JJTParserVisitor
{
public Object visit(SimpleNode node, Object data);
public Object visit(ASTStart node, Object data);
...
public Object visit(ASTNodeAttribute node, Object data);
public Object visit(ASTAttribute node, Object data);
public Object visit(ASTNode node, Object data);
...
}
com/alexmerz/simpleviz/JJTParserVisitor.java
In unserem Beispiel ist es sinnvoll, eine abstrakte Klasse zu
definieren, welche dieses Interface implementiert. Warum wird weiter
unten deutlich.
public abstract class AbstractVisitor implements JJTParserVisitor {
...
public Object visit(ASTStart node, Object data) {
return null;
}
...
public Object visit(ASTNodeAttribute node, Object data) {
return null;
}
public Object visit(ASTAttribute node, Object data) {
return null;
}
public Object visit(ASTNode node, Object data) {
return null;
}
}
com/alexmerz/simpleviz/visitor/AbstractVisitor.java
Visitor-Klasse
Jetzt können wir eine echte Visitor-Klasse implementieren. Ein typisches Problem beim Parsen von Programmiersprachen ist die Prüfung von Variablen und ihrem korrekten Einsatz z.B. hinsichtlich Typsicherheit. Dazu wird eine Variablen-Tabelle geführt. Wird eine Variable definiert, wird sie darin aufgenommen. Wird sie irgendwo verwendet, z. B. in einem Funktionsaufruf, dann wird an Hand der Tabelle geprüft, ob diese Variable auch für den Aufruf verwendet werden darf.
Ein ähnliche Situationen findet sich auch im SimpleViz-Beispiel. Knoten
müssen nicht explizit definiert werden, sie gelten als definiert,
wenn sie zum ersten Mal auftreten. Gleichzeitig müssen wir aufpassen,
dass die Zuweisung von Eigenschaften zu bestimmten Knoten auch korrekt
erfolgen. Die folgenden Beispiele sind z. B. äquivalent, beide müssen
zu identischen Datenstrukturen führen, obwohl der Syntaxbaum sich unterscheidet:
graph TestGraph {
node1 [label="hallo"]; // Attributzuweisung
node1 –- node2; // Kantendefinition
node1 [color=blue];
}
graph TestGraph {
node1 –- node2;
node1 [color=blue];
node1 [label="hallo"];
}
Es darf nur ein Node-Objekt für node1 in der Ziel-Struktur erzeugt werden, egal ob er nun zuerst in einer Attribut-Zuweisung auftritt oder einer Kantendefinition. Und die weiteren Operationen müssen sich auf diesen Knoten beziehen. Es gibt noch eine dritte Variante, in der ein Node-Objekt erzeugt werden muss: Ein Subgraph erhält auch eine Node-Repräsentation in der Ziel-Struktur.
Für die Verwaltung der Node-Objekte innerhalb der SimpleViz-Bibliothek kommt die Klasse NodeList zu Einsatz. Sie kümmert sich darum, das keine Node-Objekte mehrfach definiert werden.
Unsere Visitor-Klasse soll nun für uns eine Tabelle mit Node-Objekten
aufbauen und für die korrekten Zuweisungen sorgen. Die Klasse erhält
den Namen NodeListVisitor und erbt von AbstractVisitor.
Der Konstruktor erwartet ein Objekt der Klasse NodeList.
Sie repräsentiert die aufzubauende Tabelle mit den Node-Objekten.
public class NodeListVisitor extends AbstractVisitor {
private NodeList nl = null;
public NodeListVisitor(NodeList nl) {
this.nl = nl;
}
}
com/alexmerz/simpleviz/visitor/NodeListVisitor.java
Wie oben angesprochen, sind für uns drei Knoten-Objekte im Syntaxbaum
interessant: ASTNode, ASTNodeAttribute und ASTSubgraph. Für diese drei
Objekte implementieren wir die entsprechenden visit()-Methoden von
AbstractVisitor.
public Object visit(ASTNode node, Object data) {
Node n = nl.addUnique(node.getId());
return null;
}
public Object visit(ASTSubgraph node, Object data) {
Node n = nl.addUnique(node.getId());
n.representsSubgraph(true);
return null;
}
public Object visit(ASTNodeAttribute nodeAttr, Object data) {
...
// umfrangreich, siehe Orginalcode
}
com/alexmerz/simpleviz/visitor/NodeListVisitor.java
Als nächstes benötigen wir noch eine Methode, um sämtlich Knoten zu
durchlaufen. Im Beispiel befindet sich diese in der SimpleViz-Klasse:
public class SimpleViz {
...
public static void main(String[] args) throws ParseException,
FileNotFoundException {
...
NodeList sysnl = new NodeList();
NodeListVisitor nlv = new NodeListVisitor(sysnl);
...
traverseNodes(node, nlv);
...
}
private static void traverseNodes(SimpleNode node,
AbstractVisitor visitor) {
for(int i=0;i<node.jjtGetNumChildren();i++) {
SimpleNode sn = (SimpleNode)node.jjtGetChild(i);
sn.jjtAccept(visitor, null);
traverseNodes(sn, visitor);
}
}
}
Es wird eine NodeList erzeugt, die unsere Node-Objekte aufnimmt und ein Objekt der NodeVisitor-Klasse. Die traverseNodes()-Methode durchläuft absteigend den Syntaxbaum.
Was passiert?
Interessant an der traverseNodes()-Methode ist die vollständige Abwesenheit von Fallunterscheidungen bezüglich der Klasse. Denn die übernimmt die Java-VM für uns!
Machen wir uns klar, war passiert: Der SimpleViz-Parser liefert als Wurzel-Knoten im Syntaxbaum ein Objekt der Klasse ASTStart zurück. Dieser Start-Knoten wird an traverseNodes() übergeben. Die Methode durchläuft dessen Kind-Knoten (ASTGraph-Objekte) und ruft zuerst deren jjtAccept()-Methode auf mit der Visitor-Klasse als Parameter, hier unserem NodeListVisitor-Objekt. Diese Methode ruft nun die visit()-Methode der NodeListVisitor-Klasse auf. Relevant ist dabei mit welcher Methodensignatur die visit()-Methode aufgerufen wird – es wird nach einer Methode gesucht, die als Parameter ein Objekt der Klasse ASTGraph erwartet. In der NodeListVisitor-Klasse existiert aber solch eine Methode nicht! Also wird die entsprechende Methode in AbstractVisitor aufgerufen, die aber nichts tut.
Mit dem Kind-Knoten wird nun erneut traverseNodes() aufgerufen, und damit die Kinder des ASTGraph-Knotens. Nehmen wir an, ein Kind-Knoten ist ein Objekt der Klasse ASTSubgraph. In der jjtAccept()-Methode wird nun die visit()-Methode mit dem ASTSubgraph-Objekt übergeben. Eine Methode mit diesem Parameter wird von unserer NodeListVisitor-Klasse implementiert. Demzufolge werden die entsprechenden Operationen auf der NodeList ausgeführt.
Fazit
Bemerkenswert an diesem Ansatz sind folgende Dinge:
- Vollständige Trennung von Syntaxbaum und Ziel-Datenstruktur. Es existiert nur ein Berührungspunkt: die Visitor-Klasse. Wie mächtig dieses Konzept ist, zeigt sich darin, dass die Ziel-Datenstruktur einfach von einem existierenden Projekt (JPGD) übernommen wurde, statt sie neu zu entwerfen.
-
Aufgabenorientiertes Vorgehen bei der Analyse des Syntaxbaumes. Alle
Operationen, welche die Node-Tabelle betreffen, sind in einer Klasse
zusammengefasst. Weitere Operationen, die z.B. eine Liste von Kanten oder
Subgraphen verwalten, werden in einer eigenen Klasse platziert und
analog eingebunden, z.B:
EdgeList sysel = new EdgeList(); EdgeListVisitor elv = new EdgeListVisitor(sysel); traverseNodes(node, elv);