Inhalt | Einführung | Theorie | JavaCC | JavaCC in der Praxis

JavaCC in der Praxis


Szenario

In diesem Kapitel wird es darum gehen die Funktionsweise von JavaCC zu verdeutlichen. Hierzu wird ein kleines Beispiel dienen das schrittweise erweitert wird, sodass wir uns die verschiedenen Aspekte näher anschauen können

Ziel soll es sein, einen kleinen Taschenrechner zu programmieren. Er soll in der Lage sein arithmetische Ausdrücke zu validieren, zu berechnen, und als Syntaxbaum auszugeben. Er soll ferner in der Lage sein, Punkt vor Strichrechnung zu beachten und Klammerausdrücke beherrschen.

Der erste Schritt besteht darin, eine entsprechende Grammatik in eBNF zu formulieren, die wie folgt aussehen könnte

sum 	::= product ( ( "+" | "-" ) product )*
product ::= term ( ( "*" | "%" | "/" ) term )*
term ::= "+" term | "-" term | "(" sum ")" | number
number ::= ( const )+
const ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Eine Summe wird als die Summe bzw. Differenz zweier oder mehrerer Produkte definiert.

Ein Produkt wird als Produkt bzw. Differenz zweier oder mehrerer Terme definiert.

Ein Term ist als positiver Term, negativer Term, geklammerte Summe oder als Nummer definiert.

Ein Nummer besteht aus beliebig vielen Konstanten, die wiederum aus den Terminalsymbolen 1-9 zusammengesetz sind.

Die oben genannten Rechenregeln sind bereits in der Grammatik eingebaut, sodass keine weitere Logik programmiert werden muss.

Beispiel 1

Das erste Beispiel wird sich mit der Validierung der Syntax beschäftigen. Es zeigt, wie die Grammatik in der Definitionsdatei umgesetz wird, ohne konkrete Ergebnisse zu berechnen. Der Parser wird laufen, solange der Benutzer gültige arithmetische Ausdrücke eingibt. Stellt der Parser einen Fehler fest, bricht das Programm mit einer Exception ab. Der entsprechende Quellcode ist nachfolgend aufgeführt:
// based on examples by Chuck McManis
// recognize arithmetic expressions0

PARSER_BEGIN(Calc0)		// must define parser class
  public class Calc0 {
    public static void main (String args []) {
      Calc0 parser = new Calc0(System.in);
      for (;;)
	try {
	  if (parser.expr() == -1)
	    System.exit(0);
	} catch (Exception e) {
	  e.printStackTrace(); System.exit(1);
	}
    }
  }
PARSER_END(Calc0)

SKIP:				// defines input to be ignored
  { " " | "\r" | "\t"
  }

TOKEN:				// defines token names
  { < EOL: "\n" >
  | < CONSTANT: (  )+ >	// re: 1 or more
  | < #DIGIT: ["0" - "9"] >	// private re
  }

int expr():			// expr: sum \n
  {}				// -1 at eof, 0 at eol
  { sum() 	{ return 1; }
  | 	{ return 0; }
  | 	{ return -1; }
  }

void sum():			// sum: product { +- product }
  {}
  { product() ( ( "+" | "-" ) product() )*
  }

void product():			// product: term { *%/ term }
  {}
  { term() ( ( "*" | "%" | "/" ) term() )*
  }

void term():			// term: +term | -term | (sum) | number
  {}
  { "+" term()
  | "-" term()
  | "(" sum() ")"
  | 
  }

Erstellung des Parsers

Ausgehend von der oben gezeigten Definitionsdatei kann ein lauffähiger Parser erzeugt werden. Die dazu notwendigen Schritte sollen an dieser Stelle kurz erläutert werden

Der erste Schritt besteht darin, die Definitionsdatei zu übersetzten. Dazu genügt folgender Aufruf

javacc calc0.jj	

JavaCC erstellt darauf hin die entsprechenden Javaklassen. Bei näherer Betrachtung kann man die entsprechenden Definitionen in den generierten Quelldateien finden. Der nächste Schritt besteht nun darin, den Quellcode zu kompilieren. Dies geschieht mittels

javac *.java

Nachfolgend sollten sich nun die entsprechenden *.class Dateien im Order befinden. Der eigentliche Parser kann nun mittels

java calc0

aufgerufen werden

Beispiel 2

Das Beispiel 1 soll um die Berechnung des Ergebnisses erweitert werden. Dazu sind nur einige wenige Änderungen nötig. Zum einen muss der Rückgabetyp der Methoden von "void" auf "int" angepasst werden, zum anderen benötigen wir ein wenig Javacode. An diesem Beispiel kann man gut erkennen, wie man JavaCode in die Grammatik einfliessen lassen kann. Diese Vorgehensweise ist jedoch nicht sonderlich empfehlenswert. In der Praxis würde man eine strikte Trennung zwischen Parser und Logik anstreben. Es würde daher sinnvoller sein, sich eine Baumstruktur zu erstellen und diese dann für die Berechnung zu nutzen.
PARSER_BEGIN(Calc2)
  public class Calc2 {
    public static void main (String args []) {
      Calc2 parser = new Calc2(System.in);
      for (;;)
	try {
	  if (parser.expr() == -1)
	    System.exit(0);
	} catch (Exception e) {
	  e.printStackTrace(); System.exit(1);
	}
    }
  }
PARSER_END(Calc2)

SKIP:				// defines input to be ignored
  { " " | "\r" | "\t"
  }

TOKEN:				// defines token names
  { < EOL: "\n" >
  | < CONSTANT: (  )+ >	// re: 1 or more
  | < #DIGIT: ["0" - "9"] >	// private re
  }
int expr() throws Exception:	// expr: sum \n
  { int e; }			// prints result; -1 at eof, 0 at eol/error
  { try {
      ( e = sum() 	{ System.out.println("\t"+e); return 1; }
      | 		{ return 0; }
      | 		{ return -1; }
      )
    } catch (Exception err) {
      if (err instanceof ParseException || err instanceof ArithmeticException
	  || err instanceof NumberFormatException) {
	System.err.println(err);
	for (;;)
	  switch (getNextToken().kind) {
	  case EOF:	return -1;
	  case EOL:	return 0;
	  }
	}
      throw err;
    }
  }

int sum() throws NumberFormatException:		// sum: product { +- product }
  { int s, r; }					// returns value
  { s = product()
    ( "+" r = product()	{ s += r; }
    | "-" r = product()	{ s -= r; }
    )*			{ return s; }
  }

int product() throws NumberFormatException:	// product: term { *%/ term }
  { int p, r;}					// returns value
  { p = term()
    ( "*" r = term()	{ p *= r; }
    | "%" r = term()	{ p %= r; }
    | "/" r = term()	{ p /= r; }
    )*			{ return p; }
  }

int term() throws NumberFormatException:
				// term: +term | -term | (sum) | number
  { int t; }			// returns value
  { "+" t = term()	{ return t; }
  | "-" t = term()	{ return -t; }
  | "(" t = sum() ")"	{ return t; }
  | 		{ return Integer.parseInt(token.image); }
  }

Beispiel 3

Abschliessend soll die Syntaxbaumerstellung mittels des Präpozessors JJTree gezeigt werden. Auch hier sind wieder geringfügige Änderungen nötig. Die Definitionsdatei erhält nun die Endung *.jjt und weist darauf hin, dass ein Syntaxbaum erstellt werden soll.
PARSER_BEGIN(Calc3)
  public class Calc3 {
    public static void main (String args []) {
      Calc3 parser = new Calc3(System.in);
      for (;; jjtree.reset())	// restart tree builder
	try {
	  switch (parser.expr()) {
	  default:	((SimpleNode)jjtree.rootNode()).dump("\t");
	  case 0:	break;
	  case -1:	System.exit(0);
	  }
	} catch (Exception e) {
	  e.printStackTrace(); System.exit(1);
	}
    }
  }
PARSER_END(Calc3)
SKIP:				// defines input to be ignored
  { " " | "\r" | "\t"
  }
TOKEN:				// defines token names
  { < EOL: "\n" >
  | < CONSTANT: (  )+ >	// re: 1 or more
  | < #DIGIT: ["0" - "9"] >	// private re
  }
int expr():			// expr: sum \n
  {}				// -1 at eof, 0 at eol/error
  { try {
      ( sum() 	{ return 1; }
      | 		{ return 0; }
      | 		{ return -1; }
      )
    } catch (ParseException pe) {
      System.err.println(pe);
      for (;;)
	switch (getNextToken().kind) {
	case EOF:	return -1;
	case EOL:	return 0;
	}
    }
  }
void sum(): {}			// sum: product { +- product }
  { product() ( ( "+" | "-" ) product() )*
  }
void product():	{}		// product: term { *%/ term }
  { term() ( ( "*" | "%" | "/" ) term() )*
  }
void term(): {}			// term: +term | -term | (sum) | number
  { "+" term()
  | "-" term()
  | "(" sum() ")"
  | 
  }

Im PARSE_BEGIN, PARSE_END Block teilen wir dem Präprozessor mit, dass wir einen Syntaxbaum erstellt haben möchten. Der Präprozessor erstellt nun mittels

jjtree calc3.jjt
eine gewohne *.jjt Definitionsdatei, die die entsprechenden Aufrufe zur Knotenerstellung beinhaltet.

Der Quellcode wurde um die Klassen erweitert, die den Baum repräsentieren. Das erlaubt es uns, das Verhalten des Baumes an unsere gegebenheiten anzupassen und zu erweitern.