%token NUMBER%%sum : sum '+' NUMBER| NUMBER
jay - Ein yacc für Java
Axel T. Schreiner und Bernd Kühl
Fachbereich Mathematik/Informatik, Universität Osnabrück
mailto:{axel,bekuehl}@uos.de
http://www.informatik.uni-osnabrueck.de/jay
jay ist eine weitgehend originalgetreue Variante des bekannten UNIX-Werkzeugs yacc, mit der Parser generiert werden können, die Java als Implementierungssprache verwenden. Nach einer kurzen Einführung in yacc beschäftigt sich der vorliegende Artikel vor allem mit dem Design der Parser-Klasse, die von jay erzeugt wird, und zeigt, wie in der Implementierung viele Gestaltungsmöglichkeiten offengehalten wurden. jay produziert im Vergleich zu yacc verbesserte Fehlermeldungen und kann eine Ablaufverfolgung für den Parser generieren, auf Wunsch mit grafischer Oberfläche.
yacc - die Idee
Als Compilerbau-Werkzeug für Java gibt es bei Sun den Parser-Generator javacc und den Präprozessor jjtree zur Konstruktion von Bäumen [1]. Sie zeichnen sich vor allem durch eine barocke Syntax aus; rudimentäre Dokumentation trägt zusätzlich dazu bei, daß selbst der Test einer einfachen Grammatik unverhältnismäßig aufwendig ist. Mit Eingabefehlern fertig zu werden, erfordert derzeit einige Anstrengungen.
%token NUMBER
%%
sum : sum '+' NUMBER
| NUMBER
| Abbildung 1: yacc-Quelle zur Erkennung von Summen |
Zu UNIX-Zeiten gab es etwas Besseres [2]: yacc akzeptiert Grammatikregeln in der eleganten, primitiven Backus-Naur-Form (Abbildung 1), benötigt zusätzlich nur noch eine Liste der Eingabesymbole (token), testet die Grammatik bezüglich Mehrdeutigkeiten und liefert einen Parser, der aus Tabellen und einer Funktion yyparse() besteht, die diese Tabellen interpretiert und untersucht, ob Eingaben der Grammatik genügen, siehe Abbildung 2.
Abbildung 2: Von yacc generierter Interpreter |
Da bewußt mehrdeutig formulierte Grammatiken oft einfacher zu verstehen und kompakter zu repräsentieren sind, kann man zum Beispiel für arithmetische Ausdrücke eine Vorrangtabelle angeben und mit weniger Regeln auskommen, siehe Abbildung 3.
%token <node> NUMBER
%type <node> expr
%left '+' '-'
%left '*' '/' '%'
%%
expr : expr '+' expr { $$ = newAdd($1, $3); }
| expr '-' expr { $$ = newSub($1, $3); }
| expr '*' expr { $$ = newMul($1, $3); }
| expr '/' expr { $$ = newDiv($1, $3); }
| expr '%' expr { $$ = newMod($1, $3); }
| NUMBER
| Abbildung 3: Quelle zur Konstruktion eines Formelbaums |
Zur Fehlerbehandlung wird eine fehlerhafte Eingabe durch ein Symbol error repräsentiert; damit kann man in Grammatikregeln ausdrücken, wie man Eingabefehler im Rahmen des Parsers akzeptieren will. Fairerweise muß man zugeben, daß error anders als normale Eingabesymbole erkannt und verarbeitet wird, aber mit einfachen Kochrezepten kann man zum Beispiel alle Wiederholungen in einer Grammatik absichern [3].
yacc kann auch zur Konstruktion von Bäumen herangezogen werden: Jede Grammatikregel kann eine Aktion enthalten, die dann ausgeführt wird, wenn Eingaben erkannt wurden, die die Regel erfüllen. Abbildung 2 zeigt, daß yacc zwei Stacks unterhält, auf denen (prinzipiell) Eingabesymbole und dazugehörige Werte abgelegt werden - zu einem Token NUMBER also zum Beispiel der tatsächliche Zahlenwert in einer geeigneten Repräsentierung. In einer Aktion bezieht sich eine Angabe wie $1 auf den Wert, der zum 1. Symbol in der Grammatikregel gehört, und $$ vertritt den Wert,
der nach der Aktion zusammen mit der erkannten Regel auf den Stack gebracht wird. In Abbildung 3 werden als Beispiel die Repräsentierungen für zwei Zahlen mit einem Knoten für eine arithmetische Operation verknüpft. Dieser Knoten befindet sich dann bei der nächsten Aktion auf dem Wert-Stack und wird zum Beispiel mit einer weiteren Zahl in einer Addition verbunden.
Bäume zu konstruieren, ist eine besonders häufige Aufgabe für Aktionen. Allgemein kann man mit yacc beliebige Aktionen abwickeln - die Grammatikregeln bilden letztlich die Kontrollstruktur, die die Aktionen auslöst. Aktionen können prinzipiell beliebige Werte verarbeiten, aber man muß normalerweise beschreiben, welche Arten von Werten auf dem Wert-Stack liegen. Dazu dient die Angabe <typ>, entweder im Vorspann der yacc-Quelle (Abbildung 3) oder in der Form $<typ>1 etc. in den Aktionen.
yacc verwendet C oder Dialekte als Implementierungssprache für yyparse(). Der Wert-Stack besteht folglich aus Elementen, die durch union beschrieben werden. <typ> bezieht sich auf eine Alternative in dieser union. Zur Übersetzung von yyparse() muß diese union vereinbart werden - in der Regel verwendet man dazu eine Konstruktion %union { } im Vorspann der yacc-Quelle.
jay - die Implementierung
Wie kommt man zu yacc mit Java als Implementierungssprache für den erzeugten Parser? Im Netz findet man zum Beispiel cup, eine Implementierung von yacc in Java, die Parser in Java erzeugt [4], und jb, einen in Java implementierten Postprozessor für bison, der von bison in C erzeugte Parser in Java übersetzt [5, 6].
cup ist eigentlich das bevorzugte Werkzeug, da man insgesamt nur eine Java-Plattform für Generierung und Ausführung eines Parsers braucht. Leider wird für cup-Quellen eine ebensosehr überladene Syntax wie bei javacc vorgeschrieben, und die Fehlerbehandlung läuft in einem von cup generierten Parser anders ab als in einem von yacc generierten - mit der Konsequenz, daß man einen cup-Parser nicht immer so programmieren kann, daß er sich von allen Eingabefehlern erholt.
bison ist sehr kompatibel mit yacc und von GNU frei verfügbar. Um einen bison-Parser in Java zu erzeugen, braucht man eine Plattform für C, auf der man bison betreibt, und eine Plattform für Java, auf der man mit jb den Parser fertig übersetzen und ausführen kann. Man vermeidet dabei die Fehler von cup und gewinnt die elegante Eingabe-Syntax von yacc und bison. Leider hat jb unübersichtlich viele zusätzliche Konventionen.
Es geht auch etwas direkter. Von Berkeley sind Quellen zu yacc ebenfalls frei verfügbar, zum Beispiel auf einer CD, die die Quellen der Berkeley-UNIX-Distribution enthält [7]. Es ist nicht besonders schwierig, diese Quellen so abzuändern, daß das resultierende Programm, nämlich jay, sofort einen in Java implementierten Parser erzeugt. Zwar benötigt man zur Ausführung von jay eine C-Plattform, aber gegenüber jb vermeidet man Probleme in der Kaskadierung von zwei Übersetzungen, und gegenüber cup bleibt es bei dem exakten Algorithmus und der eleganten Eingabe-Syntax von yacc. Im Folgenden wird gezeigt, wie man bei der Implementierung von jay mit möglichst einfachen Konventionen in der Zusammenarbeit mit Java auskommt.
jay - die Design-Entscheidungen
Man kann yacc als Filter ansehen: Aus einer Grammatik werden Tabellen berechnet und die Aktionen zu einem großen switch zusammengefügt. Anschließend werden Tabellen, Aktionen und einige Definitionen zusammen mit einem Interpreter für die Tabellen, einer Funktion yyparse(), ausgegeben.
Für Java kann man entweder wie cup den Parser von einer Basisklasse aller Parser ableiten, die den Interpreter schon enthält. Zur Ausführung benötigt man dann ein Paket mit dieser Basisklasse, und man wird wahrscheinlich für die Aktionen eine eigene Klasse generieren. Es entstehen zwar klare Verhältnisse für lokale Informationen, aber der Benutzer muß recht genau wissen, an wen er sich wenden muß, um eigene lokale Informationen zu verwalten oder beispielsweise den Parser abzubrechen.
skeleton
jay kopiert wie bison und viele Implementierungen von yacc den Interpreter als Text aus einer Datei:
jay grammatik.y <skeleton >Parser.java
Das hat den Nachteil, daß jay aus zwei Dateien besteht - dem Programm jay und einem konstanten, wiederverwendbaren Text skeleton als Vorlage für alle Interpreter. jay agiert aber damit auch als Filter für skeleton, und diese Vorlage ist so konzipiert, daß man einige Design-Entscheidungen nachträglich leicht abändern könnte, indem man einfach skeleton ändert. Wenn eine Ablaufverfolgung des Parsers nicht benötigt wird, kommentiert jay diese aus der Vorlage aus. Um eine Grammatik zu prüfen, braucht man die Vorlage nicht einmal, /dev/null genügt. Will man einen Parser auf mehrere Klassen verteilen, kann man jay mit verschiedenen Vorlagen mehrfach auf die gleiche Grammatik anwenden.
Parser-Klasse
jay generiert wie yacc eine Datei. Für Java gibt es keinen Präprozessor, folglich sollte die resultierende Datei nicht nur eine Funktion wie yyparse(), sondern eine komplette Klasse enthalten, um direkt übersetzbar zu sein. package, import, den Klassenkopf und zusätzliche Attribute für die Klasse sollte der Benutzer selbst angeben können.
| %{ // prolog wird an den Anfang der Ausgabe kopiertpackage ...import ...public class ... { %} ... %% %{ // local wird an den Anfang der Interpreter-Funktion kopiert lokale Variablen für alle Aktionen%} ... %% // epilog wird an das Ende der Ausgabe kopiert} beendet die Parser-Klasse
Abbildung 4: Java-Bereiche in einer jay-Quelle |
yacc verfügt schon über die Konvention, daß bestimmte Teile der Quelle direkt an bestimmte Stellen in der Ausgabe kopiert werden, siehe Abbildung 4. jay übernimmt diese Konventionen dadurch, daß in skeleton an den entsprechenden Stellen Befehle wie prolog, local und epilog angegeben sind, für die jay Teile aus der Quelle einfügt. Damit hat der Benutzer ohne zusätzliche Syntax vollständig die Kontrolle darüber, in welcher Klasse und mit welcher zusätzlichen Ausstattung der Parser generiert werden soll.
Es bleibt zwar die Konvention, daß Namen für jay reserviert sind, die mit yy beginnen, aber diese Konvention bezieht sich bei jay nur noch auf die Parser-Klasse, nicht auf deren Umgebung.
Scanner-Schnittstelle
Im Parser werden Eingabesymbole als int-Werte verarbeitet, die von einem Scanner angeliefert werden müssen. Mit %token vereinbart man in der Quelle Namen, die in der Grammatik verwendet werden. yacc generiert für diese Namen #define-Anweisungen, damit sie auch im Scanner verwendet werden können. jay muß dafür Konstanten anlegen. skeleton definiert mit einem Befehl tokens als Präfix für diese Konstanten public static final int und generiert sie in der Parser-Klasse, womit sie auch in den Aktionen sichtbar sind, aber man könnte beispielsweise auch ein separates Interface anlegen.
public interface yyInput {
boolean advance () throws java.io.IOException;
int token ();
Object value ();
}
| Abbildung 5: Interface zum Scanner |
Parser und Scanner verkehren ohnehin über ein Interface, siehe Abbildung 5. advance() wird aufgerufen, damit der Scanner das nächste Eingabesymbol bereitstellt. Hat er keines mehr, liefert er false. Andernfalls wird der Parser das Symbol mit token() und den zugehörigen Wert mit value() abholen. Diese Schnittstelle ist eigentlich nicht Parser-spezifisch, wird aber von skeleton als inneres Interface in der Parser-Klasse angelegt, damit kein Laufzeitpaket benötigt wird.
Fehlerbehandlung
Ebenfalls als innere Klasse definiert ist yyException. Mit einem derartigen Objekt signalisiert der Parser seinem Aufrufer, daß ein Eingabefehler nicht abgefangen werden konnte. Fehler werden zunächst durch Aufruf einer Methode yyerror() berichtet, siehe Abbildung 6.
public void yyerror (String message) {
yyerror(message, null);
}
public void yyerror (String message, String[] expected) { ... }
| Abbildung 6: Fehlermeldungen |
skeleton enthält eine Methode, die eine Fehlermeldung auf System.err ausgibt, aber man kann diese Methode etwa bei der Instantiierung eines Parsers in einer anonymen Klasse ersetzen, um zum Beispiel eine Positionsangabe vom Scanner einzufügen oder in einer Oberfläche ein Panel zu zeigen. Wie in [3] schon für yacc-Parser erklärt, berechnet skeleton bei Eingabefehlern aus den Parser-Tabellen, welche Eingabesymbole akzeptabel gewesen wären und liefert diese Information mit an yyerror().
Parser-Methode
Um den Lernaufwand möglichst gering zu halten, verhalten sich die von jay und yacc generierten Parser möglichst ähnlich. yyparse() wurde allerdings in skeleton für jay deutlich anders vereinbart, um einige Schwächen von yacc auszumerzen. Da ernsthafte Eingabefehler zu einer yyException führen, kann yyparse() ein sinnvolles Resultat liefern, nämlich das Resultat der zuletzt ausgeführten Aktion.
public Object yyparse (yyInput yyLex, Object yydebug)
throws java.io.IOException, yyException;
public Object yyparse (yyInput yyLex)
throws java.io.IOException, yyException;
| Abbildung 7: Parser-Methoden |
Abbildung 7 zeigt, daß der Parser als Argument einen Scanner bekommt sowie optional ein Objekt, das sich mit der Ausgabe einer Ablaufverfolgung beschäftigen muß, falls skeleton entsprechend von jay gefiltert wurde. Da yyparse() zusätzlich in der benutzerdefinierten Parser-Klasse verkapselt ist, können mehrere Parser und Scanner problemlos in einem Programm koexistieren. yyparse() ist in der normalen Vorlage nicht static vereinbart, damit der Benutzer von jay in der Architektur seiner Parser-Klasse und seiner Aktionen größtmögliche Freiheit behält.
Ablaufverfolgung
Alan Holub hat ursprünglich vorgeführt [8], daß man den Ablauf eines Parsers ganz interessant in einer Oberfläche mit mehreren Textfenstern beobachten kann. skeleton kann von jay so gefiltert werden, daß über ein Interface jay.yydebug.yyDebug alle interessanten Vorgänge an ein Objekt berichtet werden, das sie im einfachsten Fall als Protokoll ausgibt, siehe Abbildung 8.
$ java arith.Arith
36/5
push state 0 value null
reduce state 0 uncover 0 rule (9) prog :
goto from state 0 to 1
lex state 1 reading Number value 36.0
push state 1 value null
shift from state 1 to 3
push state 3 value 36.0
reduce state 3 uncover 1 rule (8) expr : Number
| Abbildung 8: Ablaufverfolgung als Protokoll |
Das Interface ist so konzipiert, daß man es auch mit einer grafischen Oberfläche implementieren kann, siehe Abbildung 9. In diesem Fall kann man in jedem Textfeld einen Schalter setzen, damit die Ausführung des Parsers angehalten wird, nachdem im Textfeld eine Ein- oder Ausgabe erfolgt ist.
Abbildung 9: Ablaufverfolgung mit grafischer Oberfläche |
Besonders interessant ist hier natürlich eine interaktive Ausführung, bei der man am Terminal ein Programm eingibt und in der Oberfläche beobachtet, wie das Programm vom Parser verarbeitet wird. Leider blockiert Java nicht nur einen Thread, sondern gleich die ganze virtuelle Maschine, wenn eine Eingabe vom Terminal erwartet wird. Das bedeutet, daß eine grafische Oberfläche in diesem Fall nicht aktualisiert wird, weil die paint- und event-Threads nahezu ständig blockiert sind. Die in Abbildung 9 gezeigte Oberfläche enthält deshalb ein Textfeld, in dem ein Terminal mit Ein- und Ausgabe simuliert wird. yyDebug und Klassen zur Implementierung als Protokoll und mit grafischer Oberfläche bilden eine kleines Paket, mit dem beliebige jay-Parser jederzeit beobachtet werden können.
jay ist hier yacc insofern eine Nasenlänge voraus, als man zu yacc zwar immer den Parse-Stack, aber nicht den Wert-Stack darstellen kann: Für jay enthält der Wert-Stack grundsätzlich Object-Elemente, die man immer mit toString() darstellen kann.
Wert-Stack
In der Behandlung des Wert-Stacks differiert das Design der jay- und yacc-Parser deutlicher. yacc verwendet nach Voreinstellung int-Werte, und man wird normalerweise eine union als Elementtyp vereinbaren. Für jay hätte sich angeboten, daß man eine Klasse für die Elemente festlegt, Felder public vereinbart und wie bei einer union mit
yyVals[yyTop-position].feld
zugreift. Abgesehen vom unnötig hohen Platzverbrauch, hat diese Lösung den Haken, daß bei der normalen Zuweisung für eine union ihr kompletter Wert (Speicherbereich), für ein Objekt aber nur ein Verweis (Zeiger) kopiert wird, das heißt, man muß unter Umständen dafür sorgen können, daß eine echte Kopie auf den Wert-Stack gebracht wird. skeleton verwendet sicherheitshalber eine Methode yyDefault(), die man gegebenenfalls ersetzen könnte.
Einige Versuche zeigten, daß sich Object als Wert-Klasse wesentlich besser eignet. Damit man Angaben wie $1 in Aktionen sinnvoll verwenden kann, muß man in einer Vereinbarung wie
%token <Integer> NUMBER
das Etikett Integer als Klasse und nicht als Feldnamen auffassen, das heißt, für $1 muß jay so etwas wie
((Integer)yyVals[yyTop-1])
generieren. Daran kann man allerdings nicht mehr zuweisen, das heißt, $$ sollte jay in den meisten Fällen so nicht übersetzen. Da man aber immer an eine Basisklasse wie Object zuweisen kann, kann jay bei der Übersetzung von $$ die Klassenangabe einfach weglassen.
Das geht an zwei Stellen schief: Wenn ein versierter yacc-er in einer Aktion etwa an $1 zuweisen will, muß er bei jay durch die Angabe von $<>1 die Übersetzung mit Umwandlung verhindern. Will man in einer Aktion auf den Wert von $$ zugreifen, muß man durch Angabe von $<klasse>$ die Übersetzung mit Umwandlung erzwingen. Wenigstens die zweite Technik ist yacc-Benutzern ohnehin vertraut; die erste erschien uns eine vernünftige Erweiterung zur einfachen Lösung eines relativ selten auftretenden Problems.
yacc ist sehr kleinlich: Wird überhaupt eine Typangabe verwendet, müssen sich alle Aktionen an die Spielregeln halten. Für jay erweist sich dies als Plus; allerdings haben wir jay nicht so ausgebaut, daß in Anweisungen wie $$ = $2 an sich zulässige Kombinationen von Basis- und abgeleiteten Klassen stillschweigend akzeptiert werden können; allzu raffinierte Zuweisungen werden von jay angemeckert.
Fehlermeldungen
Ein in der Benutzung gravierender Nachteil bleibt: yacc fügt in die übersetzten C-Quellen seiner Parser #line-Anweisungen ein, damit der C-Compiler seine Fehlermeldungen auf die ursprüngliche yacc-Quelle bezieht. Der Java-Compiler hat keinen Präprozessor und konsequentermaßen auch keine Möglichkeit, Fehlermeldungen auf andere Dateien und Zeilennummern zu beziehen als die seiner direkten Quellen. Um das ein bißchen auszugleichen, fügt jay wenigstens entsprechende Kommentare ein. Schreibt man fehlerhafte Aktionen in einer jay-Quelle, kann man durch Inspektion der Kommentare in der Java-Quelle dann die Fehler einigermaßen zurückverfolgen.
Fazit
Wir fanden yacc für C leichter zu erlernen als javacc oder cup für Java; yacc kommt mit deutlich weniger Konventionen und weniger Vokabeln aus als der Wettbewerb, erlaubt eine triviale Prüfung von Grammatiken sowie eine einfache und in der Regel akzeptable Fehlerbehandlung und generiert recht mächtige Parser. Mit jlex [9], einem sehr nützlichen, Java-basierten Nachbau von lex, kommt man schnell zu passenden Scannern; in einfachen Fällen genügt sogar ein StreamTokenizer. jay wurde möglichst sorgfältig so entworfen, daß die Stärken von yacc und insbesondere die einfache und vielen Programmierern bereits bekannte Syntax und Struktur erhalten blieben, obgleich Java natürlich einige Konventionen durch die Klassenarchitektur zusätzlich aufzwingt.
Durch die Gestaltung von jay als Filter könnte man viele unserer Entscheidungen nachträglich durch Veränderung der Vorlage skeleton umgestalten. Man muß sich dazu nur mit Java-Text auseinandersetzen, C-Kenntnisse sind nicht nötig. Die Filterung erlaubt auch, Ablaufverfolgung und erweiterte Fehlermeldungen individuell zu kontrollieren. Speziell die grafische Ablaufverfolgung ist sehr hübsch, aber sie hat in einem Produktions-Parser kaum etwas verloren - auch nicht in Form von unerreichbaren Anweisungen, die dann in einer optimierten Java-Übersetzung verschwinden sollten.
jay aus einer yacc-Quelle zu entwickeln, halten wir für einen vernünftigen Kompromiß, insbesondere, weil der Zeitaufwand dafür nur sehr wenige Tage betrug. yacc implementiert einen reichlich komplizierten Algorithmus, der durch Vorkehrungen zur Fehlerbehandlung und zur kontrollierten Tolerierung von Mehrdeutigkeiten noch aufwendiger wird. Allein die Kompaktierung der Parser-Tabellen ist mühsam, aber für einen effizienten Parser sehr wichtig. yacc-Benutzer sollten von einem yacc für Java keine Überraschungen akzeptieren - implementiert man den Algorithmus neu, ist das kaum zu garantieren, darunter leidet cup. Selbst der von uns als Grundlage verwendete und weit verbreitete Berkeley-yacc differiert noch von Johnsons ursprünglicher Implementierung und erkennt pathologische Grammatikfehler nicht.
Nach einer Compilerbau-Vorlesung mit jay und seinen Wettbewerbern [10] sind wir alle von seinen Vorzügen sehr überzeugt. Interessenten können die Beispiele gerne nachvollziehen und die Quellen im Web abholen.
Quellen
| [1] | http://www.sun.com/suntest/products/ |
| [2] | UNIX Programmer's Manual, Band 2, Holt, Rinehart and Winston 1982. |
| [3] | A.-T. Schreiner, H. G. Friedman jr., Compiler bauen mit UNIX, Hanser 1985. |
| [4] | http://www.cs.princeton.edu/~appel/modern/java/CUP/ |
| [5] | ftp://ftp.cs.colorado.edu/pub/cs/distribs/arcadia/jb.tar |
| [6] | ftp://prep.ai.mit.edu/pub/gnu/bison-* |
| [7] | BSD-Lite CD, Addison-Wesley. |
| [8] | A. Holub, Compiler-Design With C, Prentice-Hall 1990. |
| [9] | http://www.cs.princeton.edu/~appel/modern/java/JLex/ |
| [10] | http://www.uni-osnabrueck.de/vorlesungen/informatik/compilerbau98 |
Ramsau, im März 1999