Eigene DSL mit CongoCC erstellen

“Every day, work to refine the skills you have and to add new tools to your repertoire.”

Andrew Hunt

Für viele Aufgabenbereiche werden keine vollständigen Programmiersprachen benötigen, stattdessen können sogenannte Domain-Specific Languages (DSL) verwendet werden. Eine DSL ist auf eine spezielle Domäne zugeschnitten und Probleme können in ihr sehr spezifisch formuliert werden.

Obwohl eine vollständige Programmiersprachen wie Java, Python oder Lua weit mächtiger ist als eine DSL haben diese dennoch einige Vorteile. Zum einen ist der Lernaufwand nicht so groß, so dass auch Nicht-Entwickler diese Sprachen nutzen können Der technische und syntaktische Ballast ist nicht so groß, da der spezielle, enge Domänenzuschnitt Redundanzen eliminiert.

Entwickler arbeiten jeden Tag mit den unterschiedlichsten DSL Varianten. Die bekanntesten sind SQL und andere Abfragesprachen, Gradle, Maven, Regex, AWK und natürlich die Grammatiken der Parser- und Lexer-Generatoren wie Lex, YaCC, Bison, CoCo, JavaCC, CongoCC und Template-Engines wie FreeMarker und FreshMarker. Statt eine Anwendung für ein spezielles Problem zu entwickeln, kann also auch eine DSL verwendet werden oder aber auch eine neue DSL für die Domäne entwickelt werden.

Die folgenden CSV Daten enthalten die Passagierliste der Titanic, die am 15. April 1912 gesunken ist.

1;0;3;"Braund, Mr. Owen Harris";male;22;1;0;A/5 21171;7.25;;S
2;1;1;"Cumings, Mrs. John Bradley (Florence Briggs Thayer)";female;38;1;0;PC 17599;71.2833;C85;C
3;1;3;"Heikkinen, Miss. Laina";female;26;0;0;STON/O2. 3101282;7.925;;S
4;1;1;"Futrelle, Mrs. Jacques Heath (Lily May Peel)";female;35;1;0;113803;53.1;C123;S
5;0;3;"Allen, Mr. William Henry";male;35;0;0;373450;8.05;;S
6;0;3;"Moran, Mr. James";male;;0;0;330877;8.4583;;Q
7;0;1;"McCarthy, Mr. Timothy J";male;54;0;0;17463;51.8625;E46;S
8;0;3;"Palsson, Master. Gosta Leonard";male;2;3;1;349909;21.075;;S
9;1;3;"Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)";female;27;0;2;347742;11.1333;;S
10;1;2;"Nasser, Mrs. Nicholas (Adele Achem)";female;14;1;0;237736;30.0708;;C
…

Jede Zeile enthält die Daten zu einem einzelnen Passagier. In der zweiten Spalte steht eine 1 für einen überlebenden und eine 0 für einen verstorbenen Passagier. In der dritten Spalte steht die gebuchte Klasse und in der vierten Spalte der Name des Passagiers.

Um Daten der Passagiere aus dieser CSV Datei zu extrahieren kann ein eigenes Programm geschrieben werden, ein Tool wie AWK verwendet oder eine eigene DSL zum Einsatz kommen.

Die eigene DSL nennt sich CQL und beherrscht eine Mixtur aus SQL und AWK Syntax.

SELECT $3, $4, $5 FROM input WHERE $2 == 0 && $3 = 1 USING ';' LIMIT 25;

Die Beispiel Abfrage liefert für eine Zeile in der Passagierliste die Spalten 3, 4 und 5 wenn der Passagier nicht überlebt hat und in der ersten Klasse gereist ist. Durch die USING Anweisung wird das Semikolon als Separator verwendet. Ohne die USING Anweisung wird, wie bei AWK üblich, Whitespace als Separator verwendet. Die LIMIT Anweisung reduziert das Ergebnis auf 25 Einträge.

@ParameterizedTest
@CsvSource(value = {
    "SELECT $3, $4, $5 FROM input WHERE $2 == 0 && $3 == 1 USING ';,' LIMIT 25;"
}, delimiter = '#')
void titanic(String input) throws URISyntaxException, IOException {
  CQLParser parser = new CQLParser("cql", input);
  parser.Root();
  Node rootNode = parser.rootNode();
  if (rootNode.get(0) instanceof SelectStatement selectStatement) {
    SelectHandler selectHandler = new SelectHandler();
    StatementVisitor statementVisitor = new StatementVisitor();
    SelectHandler selectHandler = selectStatement.accept(statementVisitor, selectHandler);
    Path path = Path.of(getClass().getClassLoader().getResource("titanic.txt").toURI());
    assertEquals(25, selectHandler.handle(List.of(path)).size());
  }
}

Da es noch keinen vollständigen CQL Interpreter gibt, werden die ersten Gehversuche mit der eigenen DSL mit Hilfe von JUnit Tests durchgeführt. Der obige Test führt das CQL Beispiel auf der Titanic Passagierliste aus. Das Ergebnis der Ausführung ist die nachfolgende Liste.

1 "McCarthy, Mr. Timothy J" male
1 "Fortune, Mr. Charles Alexander" male
1 "Uruchurtu, Don. Manuel E" male
1 "Meyer, Mr. Edgar Joseph" male
1 "Holverson, Mr. Alexander Oskar" male
1 "Ostby, Mr. Engelhart Cornelius" male
1 "Harris, Mr. Henry Birkhardt" male
1 "Stewart, Mr. Albert A" male
1 "Carrau, Mr. Francisco M" male
1 "Chaffee, Mr. Herbert Fuller" male
1 "Goldschmidt, Mr. George B" male
1 "White, Mr. Richard Frasar" male
1 "Porter, Mr. Walter Chamberlain" male
1 "Baxter, Mr. Quigg Edmond" male
1 "White, Mr. Percival Wayland" male
1 "Futrelle, Mr. Jacques Heath" male
1 "Giglio, Mr. Victor" male
1 "Williams, Mr. Charles Duane" male
1 "Baumann, Mr. John D" male
1 "Van der hoef, Mr. Wyckoff" male
1 "Smith, Mr. James Clinch" male
1 "Isham, Miss. Ann Elizabeth" female
1 "Rood, Mr. Hugh Roscoe" male
1 "Minahan, Dr. William Edward" male
1 "Stead, Mr. William Thomas" male

Implementiert wird der CQL Interpreter mit Hilfe des CongoCC Parser-Generator. Die folgende Grammatik umfasst den gesamten Sprachumfang, mit dem Zeilen aus Dateien extrahiert werden können und deren manipulierten Spalten auf StdOut ausgegeben werden.

PARSER_PACKAGE="de.schegge.cql";
NODE_PACKAGE="de.schegge.cql.ast";

SKIP : <WHITESPACE : (" "| "\t"| "\n"| "\r")+>;

TOKEN :
      <OPEN_PAREN : "(">
    | <CLOSE_PAREN : ")">
    | <EQUALS : "=">
    | <DOT : ".">
    | <PLUS : "+">
    | <MINUS : "-">
    | <TIMES : "*">
    | <DIVIDE : "/">
    | <PERCENT : "%">
    | <XOR : "^">
    | <OR : "|">
    | <AND : "&">
    | <LT : "<">
    | <GT : ">">
    | <COMMA : ",">
    | <COLON : ":">
    | <SEMICOLON : ";">
    | <EXCLAM : "!">
    | <DOT_DOT : "..">
    | <DOUBLE_EQUALS : "==">
    | <NOT_EQUALS : "!=">
    | <LTE : "<=">
    | <GTE : ">=">
    | <OR2 : "||">
    | <AND2 : "&&">
    | <NULL : "null">
    | <TRUE : "true">
    | <FALSE : "false">
    | <VARIABLE : ("$" (["0"-"9"])+)>
    | <INTEGER : (["0"-"9"])+>
    | <DECIMAL : <INTEGER> "." <INTEGER>>
    | <STRING_LITERAL :
      ("\"" ((~["\\", "\""]) | ("\\" ~[]))* "\"")
      |
      ("'" ((~["\\", "'"]) | ("\\" ~[]))* "'")
      >
;

TOKEN [IGNORE_CASE] #Keyword :
    <SELECT : "select">
  | <FROM : "from">
  | <WHERE : "where">
  | <LIMIT : "limit">
  | <USING : "using"> 
;

TOKEN : <IDENTIFIER : ((["A"-"Z","a"-"z"]) (["A"-"Z","a"-"z","0"-"9","_"])*)> #Identifier ;

Expression : OrExpression ;

OrExpression : AndExpression ( (<OR>|<OR2>|<XOR>) AndExpression )* ;

AndExpression : EqualityExpression ( (<AND>|<AND2>) EqualityExpression )* ;

EqualityExpression : 
    RelationalExpression [ (<EQUALS>|<DOUBLE_EQUALS>|<NOT_EQUALS>) RelationalExpression ] ;

RelationalExpression : AdditiveExpression [ (<GT>|<GTE>|<LT>|<LTE>) AdditiveExpression ] ;

AdditiveExpression : MultiplicativeExpression ( (<PLUS>|<MINUS>|<DOT_DOT>) MultiplicativeExpression )* ;

MultiplicativeExpression : UnaryExpression ( (<TIMES>|<DIVIDE>|<PERCENT>) UnaryExpression )* ;

UnaryExpression #void : UnaryPlusMinusExpression | NotExpression | BaseExpression ;

NotExpression : <EXCLAM> PrimaryExpression ;

UnaryPlusMinusExpression : (<PLUS>|<MINUS>) PrimaryExpression ;

PrimaryExpression : BaseExpression ;

BaseExpression : NumberLiteral | StringLiteral | BooleanLiteral | <VARIABLE> | <IDENTIFIER>| 
    Parenthesis | NullLiteral ;

StringLiteral : <STRING_LITERAL> ;

NumberLiteral : <INTEGER>|<DECIMAL> ;

BooleanLiteral : <TRUE>|<FALSE> ;

NullLiteral : <NULL> ;

Parenthesis : <OPEN_PAREN> Expression <CLOSE_PAREN> ;

Select #SelectStatement :
    <SELECT>
    Expression (<COMMA> Expression)*
    <FROM>
    <IDENTIFIER>
    [ <WHERE> Expression ]
    [ <LIMIT> <INTEGER> ]
    [ <USING> StringLiteral ]
    <SEMICOLON>
;

Root : (Select)+ <EOF> ;

Da CongoCC ein Nachfolger des bekannten JavaCC Parser-Generators ist, zeigt die Grammatik eine gewisse Ähnlichkeit. Jedoch ist sie mit CongoCC erfreulich schlanker geraten.

Die Verknüpfung zwischen Grammatik und dem Parser Code kann bei CongoCC vollständig über die INJECT Anweisungen erfolgen. Für dieses einfache Beispiel erhalten alle Knoten über das Node Interface eine accept Methode für einen CqlVisitor.

INJECT Node :
  import de.schegge.cql.CqlVisitor;
{
   default <I, O> O accept(CqlVisitor visitor, I input) {
        throw new UnsupportedOperationException();
   }
}

INJECT SelectStatement :
  import de.schegge.cql.CqlVisitor;
{
   public <I, O> O accept(CqlVisitor visitor, I input) {
      return (O)visitor.visit(this, input);
   }
}
…

Damit ein spezieller Type von Knoten von dem CqlVisitor korrekt bearbeitet werden kann, wird eine eigene Implementierung über eine INJECT Anweisung eingefügt. Als Beispiel ist hier die INJECT Anweisung für das SelectStatement dargestellt.

Der CQL Interpreter nutzt eine Instanz der Klasse SelectHandler um die Eingaben zu verarbeiten. Der Selecthandler wird von dem StatementVisitor erzeugt, der eine Implementierung von CqlVisitor ist.

class StatementVisitor implements CqlVisitor<SelectHandler, SelectHandler> {
    private static final ExpressionEvaluator EXPRESSION_EVALUATOR = new ExpressionEvaluator();

    @Override
    public SelectHandler visit(SelectStatement selectStatement, SelectHandler input) {
        Node where = selectStatement.firstDescendantOfType(TokenType.WHERE);
        Node limit = selectStatement.firstDescendantOfType(TokenType.LIMIT);
        Node using = selectStatement.firstDescendantOfType(TokenType.USING);
        int max = getLastColumnIndex(selectStatement, where, limit, using);

        for (int i = 1, j = 1; i < max - 2; i += 2, j++) {
            Node node = selectStatement.get(i);
            input.addColumnHandler(context -> node.accept(EXPRESSION_EVALUATOR, context).toString());
        }

        if (where != null) {
            Node whereClause = where.nextSibling();
            input.setWhereHandler(context -> {
                BooleanValue result = whereClause.accept(EXPRESSION_EVALUATOR, context);
                return result.get();
            });
        }
        if (limit != null) {
            Node limitSize = limit.nextSibling();
            input.setLimit(Integer.parseInt(limitSize.toString()));
        }
        if (using != null) {
            String usingDelimiter = using.nextSibling().toString();
            input.setDelimiter(usingDelimiter.substring(1, usingDelimiter.length() - 1));
        }
        return input;
    }

    private static int getLastColumnIndex(SelectStatement select, Node... nodes) {
        return Stream.of(nodes).filter(Objects::nonNull).map(select::indexOf)
          .findFirst().orElse(select.getChildCount());
    }
}
…

Die auszugebenden Spalten sind durch Knoten im SelectStatement repräsentiert. Der erste Knoten mit Index 0 ist das SELECT Token. Daher beginnt die For-Schleife mit dem Index 1 und endet vor dem ersten Token vom Type WHERE, USING oder LIMIT. In der Schleife wird mit dem ExpressionEvaluator, der auch CqlVisitor implementiert, ein ColumnHandler erzeugt. Der Zähler wird dabei immer um 2 erhöht, weil zwischen den Ausdrücken für die Spalten ein KOMMA Token platziert ist.

Ein ColumnHandler erzeugt einen Wert für die Ausgabe auf StdOut, indem Ausdrücke aus Variable, Identifier und Literale Knoten ausgewertet werden. Im Titanic Beispiel besteht jeder Ausdruck nur aus einer einzelnen Variable. Es können aber auch kompliziertere Ausdrücke verwendet werden.

SELECT $3 .. '. Klasse', $4 FROM input WHERE $2 == 0 && $3 > 1 LIMIT 25 USING ';';

In diesem Beispiel wird die Nummer der Klasse in der Variablen $3 mit dem String . Klasse verknüpft. Außerdem werden nun alle Passagiere ausgewertet, die nicht in der ersten Klasse reisten und die Ausgabe ändert sich auf die folgende Liste.

3. Klasse "Braund, Mr. Owen Harris"
3. Klasse "Allen, Mr. William Henry"
3. Klasse "Moran, Mr. James"
3. Klasse "Palsson, Master. Gosta Leonard"
3. Klasse "Saundercock, Mr. William Henry"
3. Klasse "Andersson, Mr. Anders Johan"
3. Klasse "Vestrom, Miss. Hulda Amanda Adolfina"
3. Klasse "Rice, Master. Eugene"
3. Klasse "Vander Planke, Mrs. Julius (Emelia Maria Vandemoortele)"
2. Klasse "Fynney, Mr. Joseph J"
3. Klasse "Palsson, Miss. Torborg Danira"
3. Klasse "Emir, Mr. Farred Chehab"
3. Klasse "Todoroff, Mr. Lalio"
2. Klasse "Wheadon, Mr. Edward H"
3. Klasse "Cann, Mr. Ernest Charles"
3. Klasse "Vander Planke, Miss. Augusta Maria"
3. Klasse "Ahlin, Mrs. Johan (Johanna Persdotter Larsson)"
2. Klasse "Turpin, Mrs. William John Robert (Dorothy Ann Wonnacott)"
3. Klasse "Kraeff, Mr. Theodor"
3. Klasse "Rogers, Mr. William John"
3. Klasse "Lennon, Mr. Denis"
3. Klasse "Samaan, Mr. Youssef"
3. Klasse "Arnold-Franchi, Mrs. Josef (Josefine Franchi)"
3. Klasse "Panula, Master. Juha Niilo"
3. Klasse "Nosworthy, Mr. Richard Cater"

Im ExpressionEvaluator werden die Bestandteile der Ausdrücke ausgewertet und ein Ergebnis vom Type Value<T> zurückgegeben. Für die Verwendung als Spalten-Eintrag wird das Ergebnis als String ausgegeben und für die Verwendung im Where Ausdruck in ein Boolean konvertiert.

@Override
public Value<?> visit(VARIABLE variableName, RecordContext input) {
  int index = variableName.getIndex() - 1;
  if (index == -1) {
    return new StringValue(input.record());
  }
  String[] columns = input.columns();
  if (index >= 0 && index < columns.length) {
    return new StringValue(columns[index]);
  }
  return Value.NULL;
}

@Override
public Value<?> visit(Identifier identifier, RecordContext input) {
  return switch (identifier.toString()) {
    case "NR" -> new LongValue(input.nr().longValue());
    case "FNR" -> new LongValue(input.fnr().longValue());
    case "FILENAME" -> new StringValue(input.filename());
    default -> throw new IllegalArgumentException();
  };
}

@Override
public Value<?> visit(INTEGER integer, RecordContext input) {
  return new LongValue(Long.parseLong(integer.toString()));
}

…

Die visit Methoden der ExpressionEvaluator Klasse besitzen alle einen RecordContext als Parameter. In diesem sind die die Eingabezeile record, die einzelnen Spalten der Eingabezeile columns, der Dateiname filename und die AWK-ähnlichen Zählvariablen nr und fnr hinterlegt.

Die visit Methode für das VARIABLE Token liefert für $0 die gesamte Zeile und für $1, die erste Spalte, für $2 die zweite Spalte, usw. bis keine weiteren Spalten in der Eingabezeile existieren. Für alle weiteren Variablen wird Value.NULL zurück geliefert.

Die visit Methode für den Identifier Node liefert für die bekannten Namen NR, FNR und FILENAME die Werte aus dem RecordContext und wirft bei unbekannten Namen eine IllegalArgumentException.

Die visit Methoden für Literale sind besonders einfach, wie hier für das INTEGER Token gezeigt ist. Die String Darstellung des Token wird in Long umgewandelt und in den passenden Value<T> Type eingefügt. Der einzige Fehler der hier auftreten kann ist der Long Überlauf. Der CQL Interpreter wirft also eine Exeption, falls die Zahl größer ist als 9223372036854775807.

Interessanter sind aber die visit Methoden für die nicht terminalen Knoten in den Ausdrücken. Hier einmal beispielhaft die Auswertung einer AdditiveExpression.

AdditiveExpression : 
  MultiplicativeExpression 
  ( 
    (<PLUS>|<MINUS>|<DOT_DOT>) 
    MultiplicativeExpression 
  )* 
;

Eine AdditiveExpression besteht aus einer nicht optionalen MultiplicativeExpression und danach einer beliebig langen Kette von weiteren MultiplicativeExpression mit einem vorhergehenden Token als Operator.

@Override
public Value<?> visit(AdditiveExpression additiveExpression, RecordContext input) {
  Value<?> result = additiveExpression.get(0).accept(this, input);
  for (int i = 1; i < additiveExpression.getChildCount(); i += 2) {
    Value<?> second = additiveExpression.get(i + 1).accept(this, input);
    result = switch (((Token) additiveExpression.get(i)).getType()) {
      case DOT_DOT -> new StringValue(result.toString() + second.toString());
      case PLUS -> result.toNumber().plus(second.toNumber());
      case MINUS -> result.toNumber().minus(second.toNumber());
      default -> throw new IllegalArgumentException();
    };
  }
  return result;
}

Die entsprechende visit Methode ist strukturell identisch aufgebaut. Zu beachten ist nur, dass der Visitor nicht direkt auf MultiplicativeExpression arbeitet, sondern die accept Methode entsprechenden Nodes in der AdditiveExpression aufruft. Das hat nicht nur ästhetische oder pädagogische Gründe, sondern ist dem Parse-Tree geschuldet, der von CongoCC generiert wird. Wird eine Zahl als erste MultiplicativeExpression gefunden, dann wird kein MultiplicativeExpression Knoten eingefügt, sondern nur ein INTEGER oder ein DECIMAL Token. Hier schützt das Visitor Pattern vor häufigen Gebrauch des instanceof Operators im Parse-Tree.

Zuletzt fehlt nur die handle Methode des SelectHandlers als Herzstück des CQL Interpreters. In ihr werden die Zeilen aus de Eingabe eingelesen, der RecordContext erzeugt, der Where-Ausdruck überprüft und bei erfolgreicher Überprüfung die Ausgabe erzeugt.

private void handlePath(AtomicInteger nr, AtomicInteger count, Path path) throws IOException {
    AtomicInteger fnr = new AtomicInteger();
    try (BufferedReader reader = Files.newBufferedReader(path)) {
        String line;
        while ((line = reader.readLine()) != null) {
            nr.incrementAndGet();
            fnr.incrementAndGet();
            String[] columns = line.split(delimiter);
            RecordContext context = new RecordContext(line, columns, nr, fnr, path.toString());
            if (!whereHandler.handle(context)) {
                continue;
            }
            if (limit < count.incrementAndGet()) {
                break;
            }
            String result = columnHandlers.stream().map(ch -> ch.handle(context)).collect(joining(" "));
            System.out.println(result);
        }
    }
}

Neben der Auswertung von Titanic Passagierlisten existieren natürlich auch andere Anwendungsfälle für CQL. Es können Spalten aus CSV-Dateien gelöscht werden, Spalten aufaddiert werden, die Mehrwertsteuer zu Nettopreis-Spalten hinzufügen, etc.

Damit ist die eigene DSL im Grunde schon implementiert und es fehlt lediglich eine passende Fassade um die DSL auf der Kommandozeile zu nutzen.

Leave a Comment