Häufig müssen Programme strukturierte Eingabedateien verarbeiten und verstehen. Komplizierte Dateiformate erfordern dabei hohen Programmieraufwand – oder den Einsatz eines Parsergenerators. JavaCC deckt die wichtigsten Aspekte der Parsergenerierung für Java-Programme ab.

Im einfachsten Fall reichen Java-Bordmittel, um Eingabedateien zu verarbeiten. Das Package »java.util« bringt dafür die Klasse »StringTokenizer« mit, »java .io« die Klasse »StreamTokenizer«. Das funktioniert aber nur, wenn die Dateien wirklich sehr einfach aufgebaut sind und zum Beispiel immer das gleiche Trennzeichen verwenden.

Einzelne logischen Tokens (also für den Parser bedeutungsvolle Einheiten) identifizieren ist ohnehin nur die halbe Miete. Tokens werden nämlich auch durch die Syntax bestimmt: So gibt es beispielsweise bei der Definition einer Java-Methode Tokens für Methodennamen und Argumentnamen. Beide haben oberflächlich zwar den gleichen Aufbau, aber nicht den gleichen Kontext.

Parser schreiben lassen

Deshalb unterscheidet man zwischen dem Lexer, der für die Zerlegung des Eingabestroms in Tokens verantwortlich ist, und dem eigentlichen Parser, der aus den Tokens – ihrem syntaktischen Zusammenhang entsprechend – etwas macht. Dieses Etwas ist in einfachen Fällen ein Verarbeitungspro-gramm, in komplexeren eine ganze Datenstruktur – typischerweise ein Baum – für die spätere Verarbeitung.

Lexer lassen sich vergleichsweise einfach selbst schreiben, in Java durch die oben erwähnten Hilfsklassen sogar einfacher als in anderen Sprachen. Je komplexer aber die syntaktischen Regeln (die so genannte Grammatik), desto schwieriger und fehleranfälliger wird es, einen Parser dafür selbst zu bauen. Einfacher ist es, die Grammatik in einer Grammatik-Beschreibungssprache zu formulieren und daraus einen Parser generieren zu lassen.

Der wird zwar nicht so performant sein wie ein für den Spezialfall geschriebener Parser. Da aber in aller Regel das Parsen des Eingabestroms nur einen kleinen Teil der gesamten Verarbeitungszeit einnimmt, steht der Optimierungsgewinn in keinem Verhältnis zum Aufwand. Bei Java übernimmt diese Aufgabe der Parsergenerator JavaCC von Sun, der unter einer BSD-Lizenz steht.

Der Coffeeshop kann natürlich keine Einführung in Parser- und Lexer-Theorie bieten. Trotzdem profitieren auch Leser ohne entsprechende Vorkenntnisse davon. Sie lernen ein nützliches und einfach anzuwendendes Tool der Java-Welt kennen, das bei der Verarbeitung strukturierter Eingabedaten hilft.

Entpacken genügt

JavaCC ist als Zip- oder Tar.gz-Archiv auf[1] verfügbar. Bei Redaktionsschluss war Version 3.2 aktuell. Die Installation beschränkt sich aufs Auspacken, etwa folgendermaßen:

tar -xvpf javacc-3.2.tar.gz -C /usr/local

Die drei Wrapper-Skripte »javacc, jjtree« und »jjdoc« stehen dann unter »/usr/ local/javacc-3.2/bin«. Um die Skripte ohne Pfadangaben auszuführen, nimmt man das Verzeichnis in den Ausführungspfad »PATH« auf.

Das Skript »javacc« ist der eigentliche Parsergenerator. Es verarbeitet Eingabedateien mit der Endung ».jj« und gibt Java-Source-Dateien aus. Für das Ausführen der folgenden Befehle empfiehlt sich daher ein neues Verzeichnis:

$ /usr/local/javacc-3.2/bin/javacc /usr/local/javacc-3.2/examples/SimpleExamples/Simple3.jj
$ javac -d . *.java
$ java -cp . Simple3

Der erste Befehl erzeugt sieben Java-Dateien, die Tokenizer- und Parser-Code enthalten, der zweite kompiliert sie. Der dritte Befehl führt die Klassendatei »Simple3.class« aus und startet somit den Parser, der auf Eingaben wartet. Sind einige Zeichen getippt, bricht [Strg]+[D] die Eingabe ab und der Parser verarbeitet die Eingabe. Im üblichen Anwendungsfall liest der Parser eine Datei, die er über eine Pipe erhält.

Neben vielen Beispielen enthält der Download umfangreiche Dokumentation in Form einer Grammatikreferenz sowie einige Tutorials. Außerdem finden sich im Internet ein Grammatik-Repository[2], eine FAQ[3] sowie eine Mailingliste zu JavaCC.

Einfacher Parser

Der Beispielparser soll Eingabedateien verarbeiten, die wie Listing 1 aussehen (natürlich ohne Zeilennummerierung). Das Format kennt drei optionale Schlüsselwörter: »anrede«, »vorname« und »nachname«. Leerzeichen und -zeilen sind ebenfalls optional, außer sie treten als Bestandteil der Werte auf wie etwa in »anrede = Herr Dr. Dr.«.

Listing 2 spezifiziert die Grammatik im JavaCC-Format. Am Anfang stehen Optionen für den Parsergenerator, die sich auch über Kommandozeilenargumente setzen lassen. Während der Grammatikentwicklung ist es sehr nützlich, den Debug-Modus anzuschalten. Das Flag »DEBUG_PARSER« produziert vergleichsweise wenig Ausgaben, »DEBUG _TOKEN_MANAGER« ist dagegen sehr geschwätzig.

Die eigentliche Parserdefinition steht zwischen den Zeilen 27 (»PARSER_BEGIN«) und 38 (»PARSER_END«). Der Name nach »PARSER_BEGIN« legt fest, wie die generierten Datei- und Klassennamen lauten, in diesem Fall »HelloWorld.java«, »HelloWorldTokenManager .java« und »HelloWorldConstants.java«. Zwischen »PARSER_BEGIN« und »PARSER_END« kann beliebiger Java-Code stehen, solange dort eine Klassendefinition für eine Klasse mit dem angegebenen Namen vorhanden ist.

01 anrede = Herr
02 vorname=Bernhard
03 nachname = Bablok

22 options {
23   DEBUG_PARSER = true;
24   DEBUG_TOKEN_MANAGER = false;
25 }
26
27 PARSER_BEGIN(HelloWorld)
28
29 package hello;
30
31 public class HelloWorld {
32   public static void main(String args[]) throws ParseException {
33     HelloWorld parser = new HelloWorld(System.in);
34     parser.processInput();
35   }
36 }
37
38 PARSER_END(HelloWorld)
39
40 <DEFAULT> SKIP :
41 {
42   " "
43 | "t"
44 | "n"
45 | "r"
46 }
47
48 <DEFAULT> TOKEN :
49 {
50   < EQ: "="(" ")* >: VALUE
51 | < FIRSTNAME: "Firstname" | "firstname" | "f" >
52 | < LASTNAME: "Lastname" | "lastname" | "l" >
53 | < TITLE: "Title" | "title" | "a" >
54 }
55
56 <VALUE> TOKEN:
57 {
58  < STRING_LITERAL: (~["n","r"])*>:DEFAULT
59 }
60
61 void processInput() :
62 { }
63 {
64   (keyspec())*
65 }
66
67 void keyspec() :
68 {
69 }
70 {
71   titleSpec() | firstnameSpec() |  lastnameSpec()
72 }
73
74 void titleSpec() :
75 { }
76 {
77   <TITLE> <EQ> <STRING_LITERAL>
78 }
79
80 void firstnameSpec() :
81 { }
82 {
83   <FIRSTNAME> <EQ> <STRING_LITERAL>
84 }
85
86 void lastnameSpec() :
87 { }
88 {
89   <LASTNAME> <EQ> <STRING_LITERAL>
90 }

Token und lexikalischer Status

Nach der grundsätzlichen Parserdefinition folgen die Produktionen. Im Beispiel sind dies zunächst drei so genannte Regular Expression Productions der Typen »SKIP« und »TOKEN«. Wie der englische Name Skip (überspringen) nahe legt, definiert diese Produktion Zeichen, die der Parser ignoriert. Das Symbol »TOKEN« legt Einheiten fest, die der Tokenizer als Token erkennt.

Wie andere Lexer unterstützt auch JavaCC mehrere Zustände für den lexikalischen Status. Im Beispiel gibt es zwei: »DEFAULT« und »VALUE«. Damit unterscheidet der Lexer zwischen dem »=«-Zeichen als lexikalischem Element (das für den Parser von Bedeutung ist) und einem »STRING_LITERAL« (das der Parser unbesehen übernimmt).

In Zeile 50 von Listing 2 ist das »EQ«-Token definiert. Das Suffix »: VALUE« zeigt an, dass der Lexer nach diesem Token in den Status »VALUE« gehen soll. Analog dazu wechselt der Lexer nach einem »STRING_LITERAL« zum Status »DEFAULT« zurück (Zeile 58).

BNF-Produktionen

Ab Zeile 61 folgen so genannte BNF-Produktionen. BNF steht für Backus-Naur-Form, eine formale Notation, um die Syntax einer Sprache festzulegen. John Backus beschrieb mit einer Vorversion die Sprache Algol58, Peter Naur erweiterte sie und beschrieb Algol60. Eine hervorragende Übersicht zum Thema BNF und Parser gibt[4]. Eine Variante der BNF-Notation ist die EBNF, die die Möglichkeit bietet, Wiederholungen ohne Rekursion zu definieren. JavaCC verwendet EBNF in einer speziellen funktionalen Notation, die eng mit Java verknüpft ist.

Das Prinzip der BNF ist einfach: Ein Symbol ist entweder terminal oder es wird durch andere Symbole definiert. Im Beispiel ist das Toplevel-Symbol »processInput« (Zeile 61), es besteht aus beliebig vielen »keyspec« (Zeile 64). Nach der Definition des Symbols folgt ein Block mit beliebigem Java-Code (etwa Zeile 62), der im Beispiel aber stets leer ist. Die funktionale Notation erlaubt es auch, Parameter zu übergeben und Werte zurückzugeben.

Semantische Aktionen

Anhand der Grammatik hangelt man sich am Baum entlang: Ein »keyspec« besteht entweder aus »titleSpec«, »firstnameSpec« oder »lastnameSpec« (Zeile 71). Letztere bestehen aus den vorher definierten Token (Zeilen 77, 83 und 89). Es ist wichtig, die JavaCC-Syntax zu verstehen und die Grammatik formal korrekt zu formulieren.

Listing 3 zeigt einen typischen Ablauf: Erzeugen des Parsers über »javacc« (Zeilen 1 bis 5), Kompilieren mittels »javac« (Zeile 6) und Ausführen (Zeilen 7 bis 30). Der im Debug-Modus generierte Parser zeigt alle Methodenaufrufe und erkannte Token.

Damit der Parser mehr macht, als nur eine Datei syntaktisch zu analysieren, braucht er so genannte semantische Aktionen. Es gibt zwar auch lexikalische Aktionen, die immer dann ausgeführt werden, wenn ein Token erkannt wird. Aber sie sind meist nur für Spezialanwendungen sinnvoll, etwa für einen Parser, der die Anzahl von »STRING_LITERAL«-Vorkommnissen zählt.

01 $ /usr/local/javacc-3.2/bin/javacc -OUTPUT_DIRECTORY=src/hello HelloWorld.jj
02 Java Compiler Compiler Version 3.2 (Parser Generator)
03 (type "javacc" with no arguments for help)
04 Reading from file HelloWorld.jj . . .
05 Parser generated successfully.
06 $ javac -d build src/hello/*
07 $ cat helloworld.txt | java -cp build/ hello.HelloWorld
08 Call:   processInput
09   Call:   keyspec
10     Call:   titleSpec
11       Consumed token: <<TITLE>: "title">
12       Consumed token: <<EQ>: "=">
13       Consumed token: <<STRING_LITERAL>: "Herr">
14     Return: titleSpec
15   Return: keyspec
16   Call:   keyspec
17     Call:   firstnameSpec
18       Consumed token: <<FIRSTNAME>: "firstname">
19       Consumed token: <<EQ>: "= ">
20       Consumed token: <<STRING_LITERAL>: "Bernhard">
21     Return: firstnameSpec
22   Return: keyspec
23   Call:   keyspec
24     Call:   lastnameSpec
25       Consumed token: <<LASTNAME>: "lastname">
26       Consumed token: <<EQ>: "= ">
27       Consumed token: <<STRING_LITERAL>: "Bablok">
28     Return: lastnameSpec
29   Return: keyspec
30 Return: processInput

27 PARSER_BEGIN(HelloWorld)
28
29 package hello;
30
31 public class HelloWorld {
32   private static String iTitle, iFirstname, iLastname;
33
34   public static void main(String args[]) throws ParseException {
35     HelloWorld parser = new HelloWorld(System.in);
36     parser.processInput();
37     parser.doHello();
38   }
39
40   private void doHello() {
41     System.out.println("Hello " + iTitle + " " + iFirstname + " " + iLastname);
42   }
43 }
44
45 PARSER_END(HelloWorld)
79
80 void titleSpec() :
81 { }
82 {
83   <TITLE> <EQ> <STRING_LITERAL>
84   { iTitle = getToken(0).image; }
85 }
86
87 void firstnameSpec() :
88 { }
89 {
90   <FIRSTNAME> <EQ> <STRING_LITERAL>
91   { iFirstname = getToken(0).image; }
92 }
93
94 void lastnameSpec() :
95 { }
96 {
97   <LASTNAME> <EQ> <STRING_LITERAL>
98   { iLastname = getToken(0).image; }
99 }

Parser für Programmiersprachen bauen typischerweise Bäume auf, die ein Backend danach weiterverarbeitet. Die semantische Aktion besteht in diesem Fall darin, das Token am passenden Ort im Baum einzuhängen. Für einfachere Fälle eignet sich die direkte Verarbeitung. Das Hello-World-Beispiel speichert den Wert des Token einfach in einer Stringvariablen. Listing 5 zeigt die gegenüber Listing 4 entsprechend geänderten Codeabschnitte.

Abbildung 1: Nach der Generierung der Parser-Dateien gibt das Tool JJTree den erzeugten Baum aus.

Die Klasse »HelloWorld« besitzt in dieser Implementation einige Felder (Zeile 32) und eine Methode »doHello()«, um das Ergebnis auszugeben. Interessanter sind aber die Zeilen 84, 91 und 98. Sie enthalten die hier wichtigen semantischen Aktionen. Das Programm speichert den Wert des Token in den Instanzvariablen »iTitle«, »iFirstname« und »iLastname«. Die »getToken()«-Methode gibt mit dem Argument 0 das bereits verarbeitete Token zurück. Bei größeren Argumenten (1, 2 …) liefert der Tokenmanager die folgenden Token.

Abbildung 2: Die Grammatik des Beispiels in BNF-Notation als HTML-Ansicht.

Bäume mit JJTree bauen

Bestandteil der JavaCC-Distribution ist auch JJTree (»/usr/local/javacc-3.2/bin/jjtree«). Es fungiert als Präprozessor, der semantische Aktionen zum Aufbau des Baums in eine Grammatik einbaut. Um den Ablauf zu demonstrieren, soll das Beispiel den Grammatikbaum konstruieren und ausgeben. Dazu sind nur in der Parserklasse kleine Änderungen notwendig (Listing 5, Zeile 36), die eigentliche Grammatik bleibt unberührt.

Das Ergebnis ist in Abbildung 1 zu sehen. Es durchläuft zwei Stufen (»jjtree«, »javacc«) bis zum kompilierbaren Code. Beide benutzen dabei die Kommandozeilenoption »-OUTPUT_DIRECTORY«, um das Verzeichnis für die Ausgabe zu spezifizieren. Ohne weitere Angaben erzeugt JJTree Knoten der Klasse »SimpleNode«: eine Knotenklasse praktisch ohne Inhalte.

Für echte Anwendungen muss der Programmierer natürlich eine eigene Knotenklasse schreiben und in eigenen semantischen Aktionen die Knoten mit Werten füllen, zum Beispiel aus dem aktuellen Token. Die Variable »jjtThis« referenziert stets den aktuellen Knoten. Der Aufbau des Baums selbst ist aber auch in diesem Fall Aufgabe von JJTree.

Ein weiteres nützliches Tool des JavaCC-Pakets ist JJDoc (»/usr/local /javacc-3.2/bin/jjdoc«). Es wandelt eine JavaCC-Grammatik wahlweise in Text oder in verlinkten Hypertext um. Dazu ruft es der Anwender lediglich mit der Grammatik als Parameter auf:

jjdoc HelloWorld.jjt

Das Ergebnis ist eine HTML-Datei, die jeder Browser darstellen kann, siehe Abbildung 2. Damit entsteht eine BNF-Sicht, die das Format exakt dokumentiert: Sie legt eindeutig fest, wie die Eingabedaten auszusehen haben. Ruft man JJTree mit dem Kommandozeilenparameter »-TEXT« auf, schreibt es die Grammatik im Ascii-Textformat.

Zusätzlich ist es eine gute Idee, auch von der JavaCC-Grammatik (zu finden in den Beispielen) eine HTML-Seite anzufertigen. Sie bietet einen kompakten Überblick über die gesamte Syntax – die Dokumentation hält eine annotierte Version bereit.

finally{}

Wer klassische Lexer und Parser kennt, muss sich nur wenig umgewöhnen. Ein Unterschied ist natürlich die generierte Sprache. Aber auch in Syntax und Arbeitsweise unterscheiden sie sich, denn JavaCC ist kein so genannter LALR(1)-Parser wie Bison/Yacc. Mehr Details dazu liefern die FAQ[3].

JavaCC ist in der Java-Welt der Standard für Parsergenerierung. Das zeigt sich nicht nur an der langen Liste verfügbarer Grammatiken[2], sondern auch an der Integration in das klassische Java-Buildtool Ant. Oft nutzen Anwendungen JavaCC, ohne dass der Benutzer es merkt. Viele Open-Source-Projekte liefern die durch JavaCC generierten Java-Quellen mit und ersparen damit dem Anwender dessen Installation.

Wer Open Source nutzt, hat meist die Wahl zwischen mehreren Lösungen. Das gilt auch für Parsergeneratoren. Eine gute Alternative zu JavaCC ist ANTLR[5], der Code in verschiedenen Programmierprachen generieren kann. Eine Übersicht über verfügbare Parser bietet die Website[6]. (ofr)

27 PARSER_BEGIN(HelloWorld)
28
29 package hello;
30
31 public class HelloWorld {
32   public static void main(String args[]) throws  ParseException {
33     HelloWorld parser = new HelloWorld(System.in);
34     try {
35       parser.processInput();
36       ((SimpleNode) jjtree.rootNode()).dump("-");
37     } catch (Exception e) {
38       e.printStackTrace();
39     }
40   }
41 }
42
43 PARSER_END(HelloWorld)