Eigene Parser mit JavaCC 21 erstellen

„Die Analphabeten des 21. Jahrhunderts werden nicht diejenigen sein, die nicht Lesen und Schreiben können, sondern diejenigen, die nicht lernen, verlernen und wieder lernen.“

Alvin Toffler

Der Java Compiler Compiler (kurz JavaCC) ist ein Parser Generator für die Java Entwicklung. Aus einer bestehenden Grammatik erstellt dieses Programm Java Code, mit dem Eingaben gegen diese Grammatik geprüft und verarbeitet werden können. Bei JavaCC handelt es sich um einen alten Bekannten, schon 2002 nutzte ich das Tool für die CSS2 Verarbeitung in einem embedded HTML Browser.

Nach zwanzig Jahren hat sich im Hauptprojekt zu JavaCC nicht viel getan, deshalb war ich umso erfreuter, als ich auf das Projekt JavaCC 21 gestoßen bin. Das Projekt beinhaltet einige interessante neue Features und Detailverbesserungen, die neugierig machen.

Eine Besonderheit von Compilern und Parser Generatoren hat mich schon immer fasziniert. Ein Parser Generator kann seine Verarbeitung durch seine eigenen Resultate mittels Bootstrapping verbessern. Bootstrapping ist das wortwörtliche an den Stiefeln aus dem Sumpf ziehen des Barons von Münchhausen.

Wer einen Parser Generator von Hand erstellt hat, kann mit diesem aus Grammatiken für SQL, JSON, Java oder CSS ausführbaren Code erzeugen. Mit diesem Code können dann Java Anwendungen entsprechende Daten in SQL, JSON, Java oder CSS Format verarbeiten. Der Parser Generator kann aber auch eine Grammatik für sein eigenes Grammatik Format verarbeiten und passenden Verarbeitungscode erzeugen. Diesen Code kann der Entwickler u.a. dazu verwenden, den manuell erstellten Code im Parser Generator zu ersetzen. Der Entwickler genießt damit die Verbesserungen am Parser Generator doppelt. Durch die Verbesserungen der allgemeinen Parser Erzeugung, aber auch durch die Verbesserungen, die direkt zurück in den Parser Generator fließen.

Um die Arbeitsweise von JavaCC vorzuführen soll eine einfache Regelsprache für die Rete-Engine aus dem Beitrag Der Rete Algorithmus erstellt werden. Die Regelsprache soll nicht wie das antiquierte OPS 5 anmuten, sondern an der Java Syntax angelehnt sein. Das folgende Beispiel zeigt drei einfache Regeln im angedachten Format.

package de.schegge.example;

import de.schegge.rules.example.Rectangle;
import de.schegge.rules.example.Ellipse;

rule squareAndCircle {
  (Rectangle ^width size ^height == size)
  (Ellipse   ^width size ^height == size) => {
    print("square and circle");
  }
}

rule square {
  (Rectangle ^width size ^height == size) => {
    print("square");
  }
}

rule circle {
  (Ellipse ^width size ^height == size) => {
    print("circle");
  }
}

Die erste Regel feuert, wenn ein Quadrat und ein Kreis mit identischer Breite und Höhe vorhanden sind, die anderen beiden Regeln feuern, wenn entweder ein Kreis oder ein Quadrat vorhanden sind.

Damit JavaCC 21 einen Parser für diese Sprache erstellen kann, wird zuerst einmal eine Gramatik benötigt. Die Grammatik unterteilt sich in einem oberen Bereich mit Optionen, danach folgen Definitionen für die lexikalische und danach Regeln für die syntaktische Analyse.

PARSER_PACKAGE=de.schegge.rules.ops;
PARSER_CLASS=Ops;

SKIP : " " | "\t" | "\n" | "\r" ;

TOKEN #Operators :
      < GT: ">" >
    | < LT: "<" >
    | < EQ: "==" >
    | < LE: "<=" >
    | < GE: ">=" >
    | < NE: "!=" >
    ;

TOKEN #Keyword:
     <IMPORT : "import">
   | <PACKAGE : "package">
   | <RULE : "rule">
   ;

TOKEN :
     <NUMBER :  (<DIGIT>)+ ("."(<DIGIT>)+)?>
   | <IDENTIFIER : (<LETTER>)+ ((<LETTER> | <DIGIT>)+)?>
   | <STRING_LITERAL : "\"" (~["\""])* "\"" >
   | <#DIGIT : ["0"-"9"]>
   | <#LETTER : ["a"-"z","A"-"Z"]>
   ;

ProductionSet : PackageDeclaration ( ImportDeclaration )* ( Production )+ <EOF> ;

ImportDeclaration : <IMPORT> Name ";";

Name : <IDENTIFIER> ( => "." <IDENTIFIER>)* ;

Production : <RULE> <IDENTIFIER> "{" Lhs "=>" Rhs "}";

Lhs : ( "(" <IDENTIFIER> ( "^" <IDENTIFIER> [ Predicate ] Value )+ ")" )+;

Rhs : "{" ( "print(" Value ");" )* "}";

Predicate : <GT> | <LT> | <GE> | <LE> | <EQ> | <NE>;

Value : <IDENTIFIER> | <STRING_LITERAL> | <NUMBER>;

Für die lexikalische Analyse werden Token definiert, die den terminalen Bestandteilen der Sprache entsprechen. Dies sind in diesem Fall Keywords, Zahlen, Identifier und Strings. Die Token werden über String Konstanten und reguläre Ausdrücke definiert.

Die syntaktischen Regeln beschreiben, wie Elemente der Sprache in kleiner Elemente zerlegt werden können. So besteht eine einzelne Import Anweisung aus dem Token import, einen Namen und einen Token ;. Der Name wiederum kann zerlegt werden in eine Reihe von Identifier Token, die durch . Token verbunden sind. Dabei ist nur das erste Token zwingend, alle anderen Token sind optional.

Wer schon Erfahrungen mit JavaCC gesammelt hat, wird den kompakteren Code der Grammatik sicherlich bemerkt haben. Der Entwickler von JavaCC 21 hat unnötige syntaktische Elemente der Grammatik entfernt oder optional werden lassen.

Um aus der Grammatik ein ausführbares Programm zu erhalten, kann man sich des INJECT Anweisung bedienen. Diese fügt Java Code in die generierte Klasse ein. In dem folgenden Beispiel wird eine main Methode zur Hauptklasse des Parsers hinzugefügt. In dieser Methode wird eine als Argument angegebene Datei geparst und der generierte Abstract Syntax Tree ausgegeben.

INJECT PARSER_CLASS :
    import java.io.IOException;
{
    static public void main(String[] args) throws ParseException, IOException {
        PARSER_CLASS parser = new PARSER_CLASS(Path.of(args[0]));
        parser.ProductionSet();
        System.out.println("Dumping the AST...");
        parser.rootNode().dump();
    }
}

Um das Programm auszuführen, muss es natürlich erst einmal erzeugt werden.

java -jar javacc-full.jar -jdk11 Ops.javacc
javac de/schegge/rules/ops/*.java

java de.schegge.rules.ops.Ops test.ops

In der letzten Zeile wird der generierte Parser ausgeführt und für die Beispielregeln folgende Ausgabe produziert.

ProductionSet
  PackageDeclaration
    package
    Name
      de
      .
      schegge
      .
      example
    ;
  ImportDeclaration
    import
    Name
      de
      .
      schegge
      .
      test
      .
      Rectangle
    ;
  ImportDeclaration
    import
    Name
      de
      .
      schegge
      .
      test
      .
      Ellipse
    ;
  Production
    rule
    squareAndCircle
    {
    Lhs
      (
      Rectangle
      ^
      width
      size
      ^
      height
      ==
      size
      )
      (
      Ellipse
      ^
      width
      size
      ^
      height
      ==
      size
      )
    =>
    Rhs
      {
      print(
      "square and circle"
      );
      }
    }
  Production
    rule
    square
    {
    Lhs
      (
      rectangle
      ^
      width
      size
      ^
      height
      ==
      size
      )
    =>
    Rhs
      {
      print(
      "square"
      );
      }
    }
  Production
    rule
    circle
    {
    Lhs
      (
      ellipse
      ^
      width
      size
      ^
      height
      ==
      size
      )
    =>
    Rhs
      {
      print(
      "circle"
      );
      }
    }
  EOF

Damit ist das Prüfen einer Eingabe gegen einen durch JavaCC 21 generierten Parser auch schon umgesetzt. Im nächsten Beitrag zum Thema JavaCC 21 wird die Java Code Generierung für die Rete-Engine hinzugefügt und die Möglichkeiten der Regelsprache erweitert.