[pago]

Parser Generierung mit JavaCC - Eine Einführung
Häufig ist es notwendig, einen Parser für eine kleine DSL (Domain Specific Language) oder komplette Programmier- bzw. Scriptsprachen zu entwickeln, um bestimmte Programmteile zu realisieren.

Prominente Beispiele für DSL sind z.B. SQL, reguläre Ausdrücke und sogar URL (also z.B. eine ganz normale Web-Adresse). Einen entsprechenden Parser per Hand zu schreiben, ist definitiv möglich, aber weder einfach, noch besonders wirkungsvoll und sehr häufig schwer zu warten und mit Fehlern bestückt. Zum Glück gibt es aber Programme, die aus einer relativ einfachen "Grammer"-Definition (ein "Grammer" beschreibt meistens die
Syntax einer Sprache) einen Parser erzeugen. Wenn wir Java verwenden, dann haben wir hier wirklich eine große Auswahl, trotzdem befasse ich mich in diesem Tutorial ausschließlich mit JavaCC.

Die Anwendung von JavaCC wird anhand eines simplen Parsers und Interpreters einer primitiven Sprache zur Beschreibung einer mathematischen Formel erläutert. Weniger elitär ausgedrückt
bedeutet dies, dass wir einen einfachen mathematischen Ausdruck parsen und interpretieren wollen.

Voraussetzungen
Dieses Tutorial ist nicht für Java-Einsteiger gedacht. Ich werde unter keinen Umständen irgendetwas erläutern, dass mit Java im Zusammenhang steht. Außerdem werde ich voraussetzen, dass reguläre Ausdrücke bekannt sind und sie nur dann erläutern, wenn es zweckdienlich oder notwendig ist.

Vorbereitungen
Um die Beispiele testen zu können, muss auf jedenfall JavaCC installiert werden. Zu beziehen ist dieses Programm auf https://javacc.dev.java.net. Ich erwarte an dieser Stelle, dass der Leser fähig ist, der Installationsanleitung selbstständig zu folgen und verzichte daher auf eine Hilfestellung dahingehend.

Syntax unserer Sprache
Wir wollen nicht viel mehr verarbeiten können, als folgenden Ausdruck:

5 + (4+5)*2

Dabei sollte unser Parser/Interpreter hinterher das korrekte Ergebnis berechnen können (23).
Die Operatoren "-" und "/" sollen ebenfalls unterstützt werden.

Begriffsklärung
Wahrscheinlich bin ich der falsche, um diesen Abschnitt zu verfassen, aber ich will dennoch eine grobe Erläuterung bereitstellen.

Token: Ein "Token" ist ein Teil einer Sprache. In unserer Sprache würde z.B. der Token "NUMBER" für, nun ja, Zahlen in der Sprache stehen. Also "981" genauso wie "7" und "51". Es ist also die abstraktion eines Sprachelements.

Lexer: Ein Lexer zerteilt einen Text in Token. Bsp.: text = "5+7";
token = (NUMBER, PLUS, NUMBER)

Parser: Der Parser verarbeitet die Token (filtert unnötige Elemente heraus, wandelt sie in irgendeiner Form um) so, dass der Interpreter sie interpretieren kann. In unserem Beispiel wäre er dafür verantwortlich, dass die "Punkt-vor-Strich"-Regel eingehalten wird und Klammern
ihrer tatsächlichen Bedeutung entsprechen.

Interpreter: Übernimmt die Interpretation der vom Parser erarbeiteten Struktur. Aus dem obigen Beispiel würde unser späterer Interpreter z.B. 12 interpretieren.

Für unser konkretes Beispiel werden wir wahrscheinlich den Begriff "Lexer" nicht benötigen.
Er wurde daher nur der Vollständigkeit halber erwähnt.

Erste Berührung
Da ich davon ausgehe, dass keine Grundlagen über JavaCC vorhanden sind, werde ich zuerst einen kleinen Teil des Parsers entwerfen und die funktionsweise erläutern.
Genau genommen soll dieser Parser nur sagen, ob die Syntax korrekt ist und nur Zahlen und das Pluszeichen kennen.

// Konfiguration (JavaCC-Manual konsultieren)
options {
	STATIC = true; // alle Parser-operationen sind static
}

// hier beginnt unsere Parser Klasse ("MathParse")
PARSER_BEGIN(MathParse)
// hier kann ganz normaler Java-Code verwendet werden
public class MathParse {
	public static void main(String[] args) {
		// auch ein statischer Parser muss initiiert werden
		// - allerdings nur einmal
		MathParse parser = new MathParse(System.in);
		try {
			parser.parse();
		} catch(ParseException e) {
			e.printStackTrace();
		}
	}
	
	// die Parser-Methoden werden automatisch hinzugefügt
}
PARSER_END(MathParse)

// Diese Zeichen ignorieren wir
// SKIP : { $regex$ }
SKIP : { " " | "\t" }

// Jetzt definieren wir unsere Token

// TOKEN : { < $tokenname$ : $regex$ >}
// "NUMBER" mindestens eine Zahl von 0 bis 9, danach kann optional ein Punkt
// und wieder beliebig viele Zahlen von 0 bis 9 folgen
TOKEN : { < NUMBER : (["0"-"9"])+ ("." (["0"-"9"])+)? > }
TOKEN : { < EOL : "\n" > }

// Und fröhlich weiter mit der tatsächlichen Syntax
void parse() : {}
{
	// Erläuterung im Text
	<NUMBER> ("+" <NUMBER>)* (<EOF> | <EOL>)
}

Die meisten Teile sind bereits ausführlich genug kommentiert, deshalb beschränke ich meine Erläuterung auf den wichtigsten Teil:

<NUMBER> ("+" <NUMBER>)* (<EOF> | <EOL>)

Eigentlich selbsterklärend, aber dennoch: Es werden die zugelassenen Token definiert.
In diesem Falle NUMBER, "+", "EOL" und "EOF" ("End Of File") - einem vordefinierten Token.
Da es sich hierbei um einen simplen regulären Ausdruck handelt, sollte das als Erklärung ausreichen.

Nun generieren wir via JavaCC unseren Java-Code. Bei mir sieht das so aus:

pago@pago:~/java/parser/javacc/javacc-4.0/javacc-4.0/grammers/mathparse$ ~/bin/javacc mathparse.jj
Java Compiler Compiler Version 4.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file mathparse.jj . . .
File "TokenMgrError.java" does not exist. Will create one.
File "ParseException.java" does not exist. Will create one.
File "Token.java" does not exist. Will create one.
File "SimpleCharStream.java" does not exist. Will create one.
Parser generated successfully.

Anschließend kompilieren wir den Code:

pago@pago:~/java/parser/javacc/javacc-4.0/javacc-4.0/grammers/mathparse$ javac *.java
Note: MathParse.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Führen ihn aus und füttern ihn mit einer Beispieleingabe:

pago@pago:~/java/parser/javacc/javacc-4.0/javacc-4.0/grammers/mathparse$ java MathParse
5+3 + 2
pago@pago:~/java/parser/javacc/javacc-4.0/javacc-4.0/grammers/mathparse$

Wunderbar, es funktioniert.

Jetzt wollen wir aber wirklich etwas berechnen. Bleiben wir vorerst beim limitierten Funktionsumfang. (Anmerkung: Ich werde hier nur die Änderungen aufführen.)

// Wir wollen etwas ausgeben, also müssen wir das auch tun
System.out.println(parser.parse());

double parse() : {
    Token t;
    double value;
}
{
    t=<NUMBER>    { value  = Double.parseDouble(t.image); }
    (
        "+"
        t=<NUMBER>  { value += Double.parseDouble(t.image); }
    )*
    (<EOF> | <EOL>)  { return value; }
}

Wir haben hier die Signatur der "parse"-Produktion so geändert, dass sie ein int zurückgibt.
Die ersten "{}" nach dem ":" können Java-Code beinhalten und werden häufig zur Deklaration von benötigten Variablen verwendet. Die Token-Klasse wurde von JavaCC erzeugt und besitzt zwei Attribute, die besonders wichtig für uns sind: "kind" und "image". "kind" identifiziert
den Token über einen double-Wert, wir können damit also prüfen, ob ein Token von einem bestimmten Typ (z.B. NUMBER) ist. "image" entspricht dem String, den der Token darstellt, also die Zahl, die wir gefunden haben.

Wir können außerdem direkt in die Syntax-Definition Java-Code einbinden, indem wir ihn innerhalb von "{}" stecken. Da dies eine simple Grammatik ist, nutzen wir diese Möglichkeit, um die Eingabe direkt zu interpretieren.

Außerdem wird deutlich, dass wir einen Token direkt in einer zuvor deklarierten Variablen speichern können ("t=<NUMBER>") - es kann allerdings immer nur ein Token gespeichert werden.

Generieren, kompilieren, starten und freuen. Es funktioniert alles, wie erwartet.

Jetzt geht's rund
In diesem Abschnitt werden wir den Rest der Grammer implementieren. Dazu sind einige Änderungen notwendig, aber wenn bisher alles verstanden wurde, sollte es leicht zu verstehen sein. Es wird nichts neues mehr eingeführt.

// Konfiguration (JavaCC-Manual konsultieren)
options {
	STATIC = true; // alle Parser-operationen sind static
	// verwende zwei Token um zu entscheiden, was passieren soll
	LOOKAHEAD = 2;
}

// hier beginnt unsere Parser Klasse ("MathParse")
PARSER_BEGIN(MathParse)
// hier kann ganz normaler Java-Code verwendet werden
public class MathParse {
	public static void main(String[] args) {
		// auch ein statischer Parser muss initiiert werden
		// - allerdings nur einmal
		MathParse parser = new MathParse(System.in);
		try {
			System.out.println(parser.parse());
		} catch(ParseException e) {
			e.printStackTrace();
		}
	}
	
	// die Parser-Methoden werden automatisch hinzugefügt
}
PARSER_END(MathParse)

// Diese Zeichen ignorieren wir
// SKIP : { $regex$ }
SKIP : { " " | "\t" }

// Jetzt definieren wir unsere Token

// TOKEN : { < $tokenname$ : $regex$ >}
// "NUMBER" entspricht einer unbegrenzten Anzahl (min. 1) an Zahlen
// (von 0 bis 9)
TOKEN : { < NUMBER : (["0"-"9"])+ ("." (["0"-"9"])+)? > }
TOKEN : { < EOL : "\n" > }

// Und fröhlich weiter mit der tatsächlichen Syntax
double parse() : {
	double value;
}
{
	value=expr()
	(<EOF> | <EOL>)		{ return value; }
}

double expr() : {
	double x;
	double y;
}
{
	x=term()
	(
		"+" y=expr()	{ x += y; }
	|
		"-" y=expr()	{ x -= y; } 
	)*
	{ return x; }
}

double term() : {
	double x;
	double y;
}
{
	x=value()
	(
		"*" y=term()	{ x *= y; }
		|
		"/" y=term()	{ x /= y; }
	)*
	{ return x; }
}

double value() : {
	double value;
}
{
	"-" value=number()	{ return -value; }
	|
	value=number()		{ return value; }
}

double number() : {
	Token t;
	double value;
}
{
	t=<NUMBER>		{ return Double.parseDouble(t.image); }
	|
	"(" value=expr() ")"	{ return value; }
}

Dieses Grammer definiert alle Regeln, die wir zuvor vereinbart hatten und liefert das richtige Ergebnis.

Es gibt nur zwei "neue" Eigenschaften im Vergleich zur vorherigen Syntax-Definition.
Zum einen haben wir die Option "LOOKAHEAD" auf 2 gesetzt. Dies ist nötig, damit der Parser die einzelnen Token der richtigen Prozedur zuweisen kann. Andernfalls würden wir ein falsches Ergebnis bekommen.

Zum anderen verwenden wir nun Prozeduren statt einfachen Token. Die Verwendung bleibt aber identisch. Eine Prozedur entspricht einer Methode, die einen bestimmten Syntax-Bereich verarbeitet.

Unser Programm ist nun in der Lage, relativ komplexe Ausdrücke zu interpretieren.
Beispiele:

-5+(-(2*3))
2*3-2*4
(5+2)-7
usw.

Spätestens jetzt sollte klar sein, warum JavaCC eine wirklich sehr gute Alternative zu einem handgeschriebenem Parser darstellt. Der Modulo-Operator würde sich z.B. mit zwei Zeilen hinzufügen lassen, das speichern von Ausdrücken (bzw. deren Ergebnissen) wäre ebenfalls sehr
schnell hinzugefügt, Funktionen zu integrieren, wäre auch kein Problem.

Nun gut, Funktionen wären einfach hinzuzufügen, wenn sie nur double-Werte verlangen und diese zurückgeben. Damit wären natürlich Funktionen zur Ableitung/Integration anderer Funktionen noch nicht möglich. Um solche Funktionen realisieren zu können, müsste man einen
AST ("Abstract Syntax Tree") erzeugen. Das lässt sich mit JavaCC nur per Hand machen, oder man verwendet JJTree, dass eine JavaCC-Grammer erzeugt und syntaktisch nahezu identisch ist (es besitzt ein paar mehr Möglichkeiten). Darauf werde ich aber hier nicht mehr eingehen.

Fazit
Der Leser sollte nun in der Lage sein, ein JavaCC-Grammer zu verstehen und selbstständig zu entwickeln. Wer möchte könnte z.B. zum hier entwickelten Grammer (simple) Funktionen und Variablen hinzufügen.