Open Source im professionellen Einsatz
Linux-Magazin 04/2005

Parser mit JavaCC generieren

Erkenne die Zeichen

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.

531

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.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Wir können auch anders

    Bisher vorgestellte Programme waren in funktionaler Weise implementiert. Schemes Stärken liegen zwar hauptsächlich in diesem Bereich, jedoch gibt es auch die Möglichkeit, objektorientiert vorzugehen.

  • Hello, World!

    Programmiersprachen, Bibliotheken, Tools, Entwicklungsumgebungen: Das Linux-Magazin widmet sich in einer eigenen Rubrik den Fragen rund ums Programmieren.

  • Haskell

    Haskell ist keine Skriptsprache, sondern wird in der Regel kompiliert. Mit einigen Handgriffen lassen sich aber Shellskripte in die funktionale Sprache einbinden. Haskells starkes Typensystem greift dann ein, um Fehler durch Argumente in falscher Anzahl oder Art zu verhindern.

  • Shell scripting with type-safety using Haskell

    Why is scripting usually done in dynamically typed languages? This article applies strong typing in Haskell to shell programs. The end result can still be light-weight but also save time by reducing runtime errors.

  • Übersetzungskünstler

    Lexer und Parser in Perl schreiben ist keineswegs langbärtigen Gurus vorbehalten. Am Beispiel eines mathematischen Formelparsers nimmt dieser Perl-Snapshot die Angst vor Token und RPN.

comments powered by Disqus

Ausgabe 09/2017

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.