Bernd Kühl (bkuehl@web.de)
Axel-Tobias Schreiner (axel@uos.de)
Fachbereich Mathematik/Informatik
Universität Osnabrück
yacc bzw. bison sind die wohl bekanntesten Compiler-Generatoren in der C-Branche. Viele Programmierer haben sich an diese Tools und deren Handhabung gewöhnt. jay ist eine weitgehend originalgetreue Umsetzung von yacc. Damit kann man in gewohnter Technik Sprachen auch mit Java implementieren. Entwickler müssen nicht mühsam neue Tools für diese Aufgabe erlernen. Der vorliegende Artikel zeigt Schritt für Schritt auch für yacc-Unkundige, wie man mit jay und Java programmiert; mit Design und Erweiterungsmöglichkeiten von jay beschäftigt sich [1].
Viele Projekte haben als Teilprojekte die Erkennung von Sprachen. Dabei muß es sich gar nicht um so komplexe Aufgaben wie die Parsierung eines Programms einer Programmiersprache handeln. Bereits die Erkennung von HTML und URLs in Web-Projekten oder gar nur die Bewertung von einfachen arithmetischen Ausdrücken ist ohne die Verwendung von Entwicklungswerkzeugen nur mühsam zu implementieren. Von Hand codierte Parser sind fehleranfällig und später eher schwer erweiterbar.
Normalerweise implementiert man Parser heute in C oder Dialekten wie C++ oder besser Objective C mit Hilfe des Compiler-Generators yacc. yacc akzeptiert und prüft eine in BNF spezifizierte Grammatik und generiert im Zuge der Analyse einen Parser für die Sprache. Während eine Eingabe erkannt wird, führt der Parser vom Entwickler angegebene Aktionen aus. Der generierte Parser wird mit den Aktionen von yacc in einer C-Datei abgelegt, welche mit einem C-Compiler übersetzt wird.
Mit dieser Technik werden seit zwei Jahrzehnten Parser und weiter auch Compiler für die verschiedensten Sprachen konstruiert. Fast alle Entwickler in dieser Branche arbeiten routinemäßig mit yacc. Aber auch viele andere Programmierer sind mit dem Tool vertraut oder haben es zumindest im Studium schon einmal verwendet.
Seit kurzer Zeit beginnt sich die Sprache Java zu verbreiten. Viele neue Projekte setzen auf Java. Daher entsteht relativ schnell der Wunsch nach einem Compiler-Generator \(`a la yacc für Java. jay ist eine originalgetreue Umsetzung von yacc nach Java. jay bietet neben der eleganten Syntax von yacc und einer flexiblen Einbettung in Java einen sehr hohen Wiedererkennungswert für alle, die mit yacc vertraut sind. Somit können Entwickler sehr schnell auch mit jay und Java produktiv werden. Die Quellen von jay bauen auf BSD-yacc auf und sind unter dem BSD-Copyright frei verfügbar [2].
Im folgenden geht es wieder einmal um arithmetische Ausdrücke. Ziel ist es, Zeilen wie (2+3)*4 zu erkennen und später entweder direkt zu bewerten oder die parsierte Information als Baum von Objekten für eine weitere Bearbeitung zu hinterlegen. An diesem Beispiel wird der Umgang mit jay Schritt für Schritt erklärt; yacc-Kenner werden vieles wiedererkennen. Alle Quellen sind im Web zu beziehen [2].
Eine Grammatik für arithmetische Ausdrücke ist schnell aufgeschrieben:
%token Number
%left '+' '-'
%left '*' '/'
%right UNARY
%start prog
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '+' expr %prec UNARY
| '-' expr %prec UNARY
| '(' expr ')'
| Number
prog : /* null */
| prog expr '\n'
| prog '\n'
%%
Noch sieht man keinen Unterschied zwischen Eingaben für yacc und jay. Quellen bestehen aus drei Teilen, die durch %%-Zeilen getrennt sind. Der mittlere Teil beinhaltet die eigentliche in BNF spezifizierte Grammatik. Regeln kann man optional mit einem Semikolon terminieren. jay erlaubt Kommentare mit // und mit /*...*/. Einzelne Eingabezeichen können direkt zitiert werden. Eingabesymbole werden im ersten Teil durch die %token-Anweisung erklärt. Das Eingabesymbol Number steht hier für eine Zahl ohne Vorzeichen. Wird nicht durch eine %start-Anweisung etwas anderes festgelegt, so beginnt die Parsierung immer bei dem ersten Grammatikbegriff. Mit %left, %right, %nonassoc und %prec kann man Vorrang und Assoziativität für Operatoren festlegen. Dadurch werden Mehrdeutigkeiten in der Formulierung einer Grammatik entschieden, und man kommt zu kompakteren Sprachbeschreibungen.(2+3)*4 ist eine legale Symbolfolge der Sprache, eben ein arithmetischer Ausdruck.
Der Vorteil von yacc und jay liegt in dieser Phase darin, daß eine Grammatik nur mit der Definition von Eingabesymbolen als Vorspann sofort auf Verwendbarkeit geprüft werden kann. Bei einem Tool wie JavaCC [3] muß man die Grammatik viel mehr syntaktisch verkleiden, bevor man sie auch nur prüfen kann.
Die Prüfung erfolgt mit der Anweisung
$ jay -v Arith.jay </dev/null
Ist die Grammatik mehrdeutig,
untersucht man die Datei
y.output.
In dieser Datei werden von
yacc
und
jay
alle erkannten Zustände des späteren Parser-Automaten
inklusive der eventuellen Konflikte aufgeschrieben.
Hat die Grammatik die Prüfung überstanden, kann man zum Beispiel Aktionen hinzufügen, um arithmetische Ausdrücke sofort zu bewerten. Der folgende Quelltext zeigt einen Teil der jay-Eingabedatei. jay gibt den Java-Code des zu erzeugenden Parsers als Standardausgabe aus. Wie von yacc gewohnt, wird der Text, der im ersten Teil der Quelle durch %{- und %}-Zeilen eingeschlossen wird, einfach kopiert. Hier muß die Klasse des Parsers angegeben werden. In diesem Block kann man auch Pakete definieren und importieren. Auch der dritte Teil der Quelle wird einfach kopiert. Hier steht dann auch die schließende geschweifte Klammer, die die Klasse abschließt. jay generiert aus dem mittleren Teil und den %-Anweisungen des ersten Teils nun als Code des eigentlichen Parsers die Methode yyparse() und die zugehörigen Tabellen. Dieser Java-Text ist aber von dem durchkopierten Text umgeben und hier dann in der Klasse Arith eingebettet.
%{
package arith_simple;
import java.io.*;
import java.util.*;
public class Arith {
%}
%token <Double> Number 99
%type <Double> expr
%left '+' '-'
%left '*' '/'
%right UNARY
%start prog
%% // public Object yyparse(yyInput yyLex) throws IOException, yyException
expr : expr '+' expr { $$ = new Double($1.doubleValue()+$3.doubleValue()); }
| expr '-' expr { $$ = new Double($1.doubleValue()-$3.doubleValue()); }
| expr '*' expr { $$ = new Double($1.doubleValue()* $3.doubleValue()); }
| expr '/' expr { $$ = new Double($1.doubleValue()/$3.doubleValue()); }
| '+' expr %prec UNARY { $$ = $<>2; } // can suppress class
| '-' expr %prec UNARY { $$ = new Double(-$2.doubleValue()); }
| '(' expr ')' { $$ = $2; }
| Number // $$ = yyDefault($1);
prog : /* null */
| prog expr '\n' { System.out.println("\t"+$2); }
| prog '\n'
%%
..... siehe unten
}
Der generierte Parser arbeitet mit zwei Stacks: einen für die Syntax-Erkennung und parallel dazu einen zweiten zur Ablage von benutzerdefinierten Werten, die zu erkannten Symbolen gehören.
Eine Aktion steht am Schluß einer Phrase der Grammatik in geschweiften Klammern und wird ausgeführt, wenn die Phrase erkannt wurde. Mit einer Angabe wie $1 kann sie auf den Wert zugreifen, der zum ersten Symbol in ihrer Phrase gehört. $$ist der Wert des Symbols dieser Phrase für die obergeordnete Phrase.
Bei einem jay-Parser enthält der Wert-Stack immer Object-Elemente. Der Nachteil dieser Technik ist, daß primitive Datentypen immer in Objekten gekapselt werden müssen. Dies sieht man schön in den Aktionen des Beispiels. Wird ein Teil des arithmetischen Ausdrucks erkannt, so wird dieser sofort bewertet. Das Ergebnis wird aber immer als Objekt der Klasse Double auf den Wert-Stack gelegt. Ist ein arithmetischer Ausdruck komplett erkannt, wird bei der Aktion zu prog sofort der Wert in der Aktion ausgegeben.
In dem von jay erzeugten Code befinden sich auch die Zeilen
protected Object yyDefault (Object first) {
return first;
}
Wird hinter einer Alternative eines Grammatikbegriffs keine Aktion angegeben, so wird als Default
$$ = yyDefault($1);
ausgeführt.
Damit wird wie in
yacc
der Wert des ersten Begriffs der Alternative zum Wert des Grammatikbegriffs.
Ist der Grammatikbegriff eine leere Alternative,
so kommt ein Nullverweis auf den Stack.
Durch Ableiten der Parser-Klasse und Überdefinieren der Methode
yyDefault()
kann der Entwickler das
Standardverhalten aber auch ändern.
So möchte man vielleicht keine Objektverweise durchkopieren,
sondern erst eine tiefe Kopie des Objekts machen.
jay generiert eine Methode yyparse(), die man zur Ausführung der Erkennung aufrufen muß. Dabei übergibt man, anders als bei yacc, einen oder zwei Parameter: Der erste Parameter ist ein yyInput-Objekt, der zweite Parameter dient zu Debug-Zwecken. jay generiert yyInput als inneres Interface der Parser-Klasse. Die Methoden dienen zur lexikalischen Analyse. Mit welchen Techniken man nun diese Methoden implementiert, ist jay und dem erzeugten Parser egal. Lediglich das Interface ist einzuhalten.
public interface yyInput {
boolean advance () throws java.io.IOException;
int token ();
Object value ();
}
advance() rückt ein Symbol in der Eingabe vor und liefert false, wenn man sich am Ende der Symbole befindet. token() liefert als Integer-Zahl das gerade erkannte Symbol, und mit value() holt sich yyparse() zu einem akzeptierten Eingabesymbol das assoziierte Objekt für den Wert-Stack. jay nutzt intern wie yacc kleine Integer-Zahlen für die zu erkennenden Symbole. Man kann wie gewohnt bei der %token-Anweisung die Zahl auf Wunsch auch konkret angeben.
Als Scanner (lexikalische Analyse) kann bei sehr einfachen Problemen ein Objekt einer Unterklasse der Klasse StreamTokenizer dienen. Die folgende selbständige Klasse Scanner implementiert das yyInput-Interface mit dieser Technik und sucht nach Zahlen ohne Vorzeichen. Diese Klasse kann auch im dritten Teil der jay-Quelle als innere Klasse der Parser-Klasse stehen.
class Scanner extends StreamTokenizer implements Arith.yyInput {
public Scanner (Reader r) {
super (r);
eolIsSignificant(true); // need '\n'
ordinaryChar('/'); // gotcha: would start comment
ordinaryChar('-'); // gotcha: would start Number
commentChar('#'); // comments from # to end-of-line
}
public boolean advance () throws IOException {
return ttype != TT_EOF && super.nextToken() != TT_EOF;
}
public int token () {
value = null;
switch (ttype) {
case TT_EOF: return 0; // should not happen
case TT_EOL: return '\n';
case TT_NUMBER: value = new Double(nval);
return Arith.Number;
case TT_WORD: return Arith.yyErrorCode;
default: return ttype;
}
}
protected Object value;
public Object value () {
return value;
}
}
Dieser Scanner eignet sich nicht gut für interaktiven Betrieb,
da
StreamTokenizer
grundsätzlich ein Zeichen vorausliest.
Die Klassenvariable Arith.Number wurde von jay als int-Konstante für die %token-Anweisung im Vorspann der Grammatik generiert.
Für kompliziertere Scanner reicht diese Technik allerdings nicht mehr. Eine bessere Technik, die man ebenfalls aus dem Umfeld von yacc kennt, stellen wir später kurz vor.
...
%%
...
%%
public static void main (String args []) {
Scanner scanner = new Scanner(new InputStreamReader(System.in));
try {
new Arith().yyparse(scanner);
} catch (IOException ie) { ie.printStackTrace(); }
catch (yyException ye) { System.err.println(ye); }
}
}
Im Hauptprogramm wird ein Scanner-Objekt erzeugt und die yyparse()-Methode mit diesem Objekt als Argument aufgerufen. yyparse() erzeugt eine Arith.yyException-Exception, wenn beim Parsieren ein nicht abgefangener Fehler auftritt. Die Exception enthält eine Beschreibung des Fehlers als Information. Die Klasse yyException ist wieder als innere Klasse der Parser-Klasse definiert. yyparse ruft advance() beim Scanner-Objekt auf. Daher müssen auch mögliche IOExceptions abgefangen werden.
Von der jay-Quelle zum Java-Text des Parsers kommt es nun mit dem folgenden Aufruf:
$ jay <skeleton Arith.jay > Arith.java
jay bekommt als Argument den Namen der jay-Quelldatei und gibt den generierten Parser auf der Standardausgabe aus. Wie yacc generiert auch jay eigentlich nur Tabellen und setzt einen vordefinierten Interpreter für die Tabellen mit den leicht modifizierten Aktionen zusammen. All dies wird durch eine Datei skeleton gesteuert, die jay als Standardeingabe verwendet. skeleton ist Teil von jay und kann prinzipiell auch verändert werden [1]. Nun ist auch klar, warum beim Testen der Grammatik zum Anfang des Artikels die Standardeingabe geschlossen worden ist. Damit ist die Standardeingabe leer, und jay gibt keinen Parser-Code aus. Die Grammatik wird nur getestet.
Da skeleton keine weiteren Klassen voraussetzt, ist die Übersetzung des Java-Codes des Parsers relativ einfach. Die arithmetischen Ausdrücke werden korrekt berechnet:
$ CLASSPATH=.. javac Arith.java
$ { echo 36/5; echo '5 * (3+4)'; } | CLASSPATH=.. java arith_simple.Arith
7.2
35.0
Als nächster Schritt sollen nun die arithmetischen Ausdrücke nicht sofort bewertet, sondern in einem Baum von Objekten gespeichert und später ausgeführt werden. Dazu dienen Klassen, die von java.lang.Number abstammen und ebenfalls java.io.Serializable implementieren. Als Blätter in dem Baum befinden sich dann echte Number-Objekte wie java.lang.Double oder java.lang.Long. Die Klassen für die Baum-Knoten müssen die verschiedenen Operationen von Number implementieren. Sie sind nicht aufwendig, aber relativ langatmig; dafür können sie wiederverwendet werden. Ein Ausschnitt:
import java.io.Serializable;
public abstract class Node extends Number implements Serializable {
protected abstract static class Binary extends Node {
protected Number left;
protected Number right;
protected Binary (Number left, Number right) {
this.left = left; this.right = right;
}
}
public static class Add extends Binary {
public Add (Number left, Number right) {
super(left, right);
}
...
public double doubleValue () {
return left.doubleValue() + right.doubleValue();
}
}
...
}
Da Number und damit Node und folglich alle Baumknoten Serializable implementieren, kann man einen derartigen Baum mit einem java.io.ObjectOutputStream speichern und später laden und ausführen. Fügt man einen Eingabeknoten zur Sprache hinzu, resultiert schon ein ganz praktisches Werkzeug, zum Beispiel zum Umgang mit Euro-Beträgen oder für andere wiederkehrende Berechnungen.
Der folgende Ausschnitt aus einer jay-Eingabedatei zeigt, wie der Baum der Node-Objekte in den Aktionen gebaut wird. Hier wird mit einer anderen Grammatik die Erkennung der arithmetischen Ausdrücke gesteuert. Der Vorrang ist durch die Grammatik selbst geregelt.
%{
...
%}
%token <Number> Constant
%type <Number> sum, product, term
%type <Vector> line
%%
line : sum '\n' { $$ = new Vector(); $<Vector>$.addElement($1); }
| line sum '\n' { $1.addElement($2); }
sum : product // $$ = $1
| sum '+' product { $$ = new Node.Add($1, $3); }
| sum '-' product { $$ = new Node.Sub($1, $3); }
product : term // $$ = $1
| product '*' term { $$ = new Node.Mul($1, $3); }
| product '/' term { $$ = new Node.Div($1, $3); }
| product '%' term { $$ = new Node.Mod($1, $3); }
term : '+' term { $$ = $2; }
| '-' term { $$ = new Node.Minus($2); }
| '(' sum ')' { $$ = $2; }
| Constant // $$ = $1
%%
}
Der Grammatikbegriff line erkennt Folgen von Newline-terminierten arithmetischen Ausdrücken (sum). In den Aktionen zu line werden die Ausdruck-Bäume als Elemente in einem Vector gespeichert. Für line wird mit %type deshalb Vector als Klasse eingestellt. Alle anderen Wert-Stack-Elemente sind Number -- entweder Baum-Knoten, die in Aktionen konstruiert werden, oder zum Beispiel Double-Objekte, die der Scanner erzeugt hat. yyparse() liefert als Resultat das Objekt auf dem Wert-Stack für den obersten Grammatikbegriff, hier also den Vektor der Bäume.
Aus einer Aktion in der jay-Datei wie
$$ = new Node.Add($1, $3);
wird in dem erzeugten Java-Text die Zeile
yyVal = new Node.Add(((Number)yyVals[-2+yyTop]), ((Number)yyVals[0+yyTop])); }
Angaben wie $1 und $3 werden also heftig umgewandelt. Dies kann man steuern: $<>i verhindert die Umwandlung und $<Klasse>i wandelt explizit um. Für $$ generiert jay nur yyVal, denn sonst könnte man nicht zuweisen. Andrerseits sieht man bei der ersten Aktion zu line, daß eine Umwandlung mit $<Klasse>$ manchmal nötig ist.
Das Beispiel ruft wieder im Hauptprogramm yyparse() auf und merkt sich als Resultat den Vektor mit den Bäumen der Ausdrücke. Wird das Programm mit der Flagge -c aufgerufen, wird der komplette Vektor serialisiert auf der Standardausgabe ausgegeben. Ohne die Flagge werden alle Einträge im Vektor bewertet. Zu bemerken ist, daß hier das Hauptprogramm nun im Gegensatz zum vorherigen Beispiel im ersten Teil der jay-Quelle hinterlegt ist.
%{
...
public class Arith {
public static void main (String args []) {
boolean cflag = args.length > 0 && args[0].equals("-c");
Scanner scanner = new Scanner(new InputStreamReader(System.in));
Arith parser = new Arith();
try {
Vector vec = (Vector)parser.yyparse(scanner);
if (vec != null)
if (cflag) {
ObjectOutputStream out = new ObjectOutputStream(System.out);
out.writeObject(vec);
out.close();
} else
for (Enumeration e = vec.elements() ; e.hasMoreElements() ;) {
System.out.println(((Number) e.nextElement()).floatValue());
}
} catch (yyException ye) { System.err.println(scanner+": "+ye); }
catch (IOException ioe) { System.err.println(ioe); }
}
%}
Wie verarbeitet man später den serialisierten Vektor? Das kleine Hilfsprogramm Go zeigt dies. Es liest den Vektor ein und gibt die Ausdrücke als long- und double-Werte aus.
import java.io.ObjectInputStream;
import java.util.Vector;
public class Go {
public static void main (String args []) {
try {
ObjectInputStream in = new ObjectInputStream(System.in);
Vector lines = (Vector)in.readObject();
System.out.println("long\tdouble");
for (int i = 0; i < lines.size(); ++ i) {
Number n = (Number)lines.elementAt(i);
System.out.println(n.longValue()+"\t"+n.doubleValue());
}
} catch (Exception e) { System.err.println(e); }
}
}
Der Strom der serialisierten Objekte kann über eine Pipe, eine Netzverbindung oder eine Datei an Go geliefert werden. Hier wird eine Pipe verwendet.
$ make test
{ echo 2+3; echo '32768 * 3.2 + 128'; \
} | CLASSPATH=.. java arith_tree.Arith
5.0
104985.6
{ echo 2+3; echo '32768 * 3.2 + 128'; \
} | CLASSPATH=.. java arith_tree.Arith -c \
| CLASSPATH=.. java arith_tree.Go
long double
5 5.0
98432 104985.6
Liefert die lexikalische Analyse ein unpassendes Eingabesymbol, wird von yyparse() die Methode yyerror(String) bzw. yyerror(String, String[]) aufgerufen. Der erste Parameter beschreibt den Fehler und der zweite Parameter die erwarteten Eingabesymbole [4]. jay implementiert beide Methoden in der Parser-Klasse, aber man kann natürlich ableiten und ersetzen.
Paßt die Eingabe nicht, endet yyparse() mit einer yyException. Dies kann man umgehen, indem man in der Grammatik Regeln einfügt, die sich mit einem fiktiven Eingabesymbol error beschäftigen. yacc und jay reagieren identisch in der Verarbeitung von error. Wie man error sinnvoll für typische Konstrukte wie optionale Folgen, Folgen und Listen verwendet, ist an anderer Stelle erklärt [4]. Die bei yacc übliche Aktion yyerrok muß bei jay als Zuweisung yyErrorFlag = 0 formuliert werden.
jay bietet eine Schnittstelle zur Ablaufverfolgung [5]. Die Idee ist, dem Parser bei der Arbeit zuzusehen, das heißt, die Entwicklung des Zustands- und Wert-Stacks zu verfolgen. Wird jay mit der Option -t aufgerufen, werden im generierten Parser einige Zeilen entkommentiert. Diese Zeilen implementieren die Ablaufverfolgung. Aktiviert wird die Ablaufverfolgung, indem yyparse() als zweiten Parameter ein yyDebug-Objekt erhält. yyDebug ist ein Interface, das in einem Paket jay.yydebug definiert ist und Methoden definiert, die von yyparse() beim yyDebug-Objekt aufgerufen werden und mit denen man zum Beispiel ein Protokoll oder eine grafische Ablaufverfolgung implementieren kann. Adapter-Klassen für beides sind schon im Paket: yyDebugAdapter liefert zum Beispiel folgendes Protokoll für die Eingabe 2+3
$ echo 2+3 | CLASSPATH=.. java arith_debug.Arith trace push state 0 value null lex state 0 reading Constant value 2 shift from state 0 to 2 push state 2 value 2 reduce state 2 uncover 0 rule (15) term : Constant goto from state 0 to 9 push state 9 value 2 reduce state 9 uncover 0 rule (8) product : term goto from state 0 to 8 push state 8 value 2 lex state 8 reading '+' value null reduce state 8 uncover 0 rule (5) sum : product goto from state 0 to 7 ... reduce state 15 uncover 0 rule (1) line : sum '\n' goto from state 0 to 6 lex state 6 reading end-of-file value null accept value [arith_debug.Node$Add@80cd04e] 5.0
Schöner, aber genauso trivial zu verwenden, ist yyAnim. Übergibt man eine Instanz an yyparse(), sieht man folgendes Fenster:
In der Oberfläche werden die von der lexikalischen Analyse erkannten Eingabesymbole mit ihrem Wert für den Wert-Stack dargestellt. Mit einer Checkbox kann auf Wunsch die Ablaufverfolgung bei Eintreffen eines neuen Eingabesymbols angehalten werden. Der Zustands- und Wert-Stack werden angezeigt, und auch hier kann bei jeder Veränderung die Ablaufverfolgung gestoppt werden. Weiterhin werden alle anderen Informationen, die von yyparse() über die Methoden des yyDebug-Interfaces geliefert werden, in einem Kommentar-Fenster ausgegeben. Da in Java Terminal-Eingaben und Grafik nicht unbedingt zusammen funktionieren, kann man bei der Erzeugung des yyAnim-Objekts entscheiden, ob und wie im unteren Bereich ein Terminal simuliert werden soll. Auch die Kommentare und das simulierte Terminal sind mit einer Checkbox zur möglichen Unterbrechung der Ablaufverfolgung bei einer Änderung versehen. Der continue-Knopf setzt eine gestoppte Ablaufverfolgung fort.
Im Rahmen einer Vorlesung über Compilerbau [6] haben wir entsprechende Werkzeuge für Java getestet. Zur Generierung von Scannern kennen wir vier Werkzeuge:
jlex [7] ist ein brauchbarer Nachbau von lex in Java, der aus einer Tabelle von egrep-artigen Mustern und Java-Anweisungen als Aktionen zu erkannten Mustern eine Klasse erzeugt, auf deren Methoden sich zum Beispiel das für jay geforderte Interface yyInput leicht aufsetzen läßt. Den Quellen zu diesem Artikel liegt ein mit jlex entwickelter Scanner für die arithmetischen Ausdrücke bei. Mit jlex kommt man leicht zu Scannern, die die Fähigkeiten von StreamTokenizer weit übertreffen.
jf [8] ist in Java implementiert und übersetzt Scanner, die mit flex erzeugt wurden, von C in Java. jlex ist direkt in Java zu verwenden und verlangt einen gewöhnungsbedürftigen Vorspann. jf bedingt dagegen eine zweistufige Übersetzung.
JavaCC [3] und antlr [9] sind weitere Parser-Generatoren, die auch Vorkehrungen zur Konstruktion ihrer Scanner enthalten. Abgesehen von barocken syntaktischen Feinheiten beruhen sie ebenfalls auf regulären Ausdrücken.
Auch zur Generierung von Parsern gibt es Alternativen zu jay, die direkt in Java implementiert sind. JavaCC ist im Web bei Sun zu beziehen und automatisiert wie antlr die Generierung von Parsern auf der Basis der Methode des rekursiven Abstiegs. JavaCC wurde in [10] ausführlich vorgestellt. Die Syntax ist teilweise nur rudimentär dokumentiert. JavaCC erzeugt viele Klassen und Interfaces. Wenigstens einige davon sollten unseres Erachtens innere Klassen sein. Durch die Vermischung von EBNF und Java-Code in Form von Funktionsköpfen, -aufrufen, Zuweisungen und try-Blöcken ensteht eine sehr unübersichtliche Repräsentation der Grammatik. Erst JJDoc, das Dokumentations-Tools zu JavaCC, fördert die eigentliche Grammatik wieder zutage, wenigstens soweit sie außerhalb der Aktionen sichtbar ist. Speziell bei der Fehlerbehandlung muß man viele Interna kennen. Wir halten diese Aspekte für so unangenehm, daß sie den Vorteil eines mehr oder weniger kommerziellen Supports und der Implementierung rein in Java zunichte machen.
cup [11] (Constructor of Useful Parsers) ist eine Neuimplementierung von LR(1) in Java, angelehnt an yacc. Abgesehen von einer etwas barocken Syntax, reichlichen Einschränkungen zur Anordnung der Eingaben und vielen Verabredungen im Laufzeitsystem, funktioniert cup ähnlich wie yacc und jay. Die Quellen sind frei verfügbar. cup generiert mehrere freistehende Klassen -- für Parser, Aktionen und Eingabesymbolnummern. Die Aktionen-Klasse verwendet $ im Namen, das könnte Probleme geben. Fehlerbehandlung funktioniert (leider nur fast) wie für yacc; man kann die Wiederaufnahme der Parsierung bei wichtigen Eingabesymbolen schlecht beeinflussen. Insgesamt ist eine erfolgreiche Fehlerbehandlung deutlich schwieriger. cup kann Zeichenpositionen in der Eingabe verwalten; damit könnte man sehr präzise Fehlermeldungen generieren.
jb [8] ist in Java implementiert und übersetzt Parser, die mit bison erzeugt wurden, von C in Java. Da bison präzisere Fehlermeldungen liefert als BSD-yacc, hat jb diesbezüglich Vorteile gegenüber jay, aber jb bedingt eine zweistufige Übersetzung und ein Laufzeitpaket.
cup, jb und jay sind die Werkzeuge, die yacc- und C-Kundige in der Java-Entwicklung vor die geringste Lernkurve stellen. cup verzichtet auf die einfache Repräsentierung von BNF, die yacc so trivial zu erlernen macht, und hat Schwächen in der Fehlerbehandlung, da der Algorithmus neu implementiert wurde. jb benötigt zwei Übersetzungsschritte, ein Laufzeitsystem und hat viele zusätzliche Konventionen. Durch Modifikation der BSD-Quellen war jay viel leichter zu implementieren und reagiert so, wie man es gewohnt ist. jay ändert yacc nur dort ab, wo C und Java anders benutzt werden sollten. yacc-Kundige können sich daher ganz auf die Codierung der Aktionen in Java konzentrieren. Neueinsteiger erhalten ein Werkzeug, bei dem eine Grammatik ohne viel Verbrämung als Kontrollstruktur zur Ausführung von Java-Fragmenten dient. jay bietet eine elegante Syntax zur Einbettung der Parser-Klasse, welche von einer beliebigen Klasse abstammen darf. Es wird nur eine Java-Klasse generiert, die keine Runtime-Unterstützung beansprucht. Die Parser-Klasse stellt intern als inneres Interface eine Schnittstelle zum Parser zur Verfügung. Der Scanner kann damit frei programmiert werden. Es ist egal, ob der Scanner aus einer Oberfläche oder aus einem einfachen Objekt kommt.
jay ist eben yacc mit Klasse.
Ramsau, März 1999