Schlagwörter

Wann immer ich in meinen Projekten an dem Punkt angekommen bin, dass es galt einen komplexen Sachverhalt ohne Programmierung zu beschreiben wie

  • Konfigurationsfiles
  • Regeln
  • Formatdefinitionen
  • u.ä.

habe ich es vermieden den Begriff „Parser“ auch nur zu denken. Viel zu gut hatte ich noch die Vorlesung „Algorithmen I“ im Hinterkopf, in der wir ganz trockenen und komplizierten Stoff mit Grammatiken, Lexern und LL(1)-Regeln durchgenommen haben. Statt dessen habe ich diese Problemstellungen mit Key-Value- oder XML-Syntaxen vergewaltigt, oder exzessiven Gebrauch von StringTokenizern und RegEx gemacht.

Nun bin ich dankbar auf ein Problem gestossen zu sein, dass sich nicht mehr mit diesen Mitteln lösen ließ und mich gezwungen hat, mich mit dem Definieren und Verarbeiten einer eigenen Sprache zu beschäftigen.

Es wäre jetzt falsch zu sagen, dass das Intepretieren von Texten trivial wäre, aber mit den richtigen Tools ist es eine Sache, in die man sich innerhalb ein paar Abende einarbeiten kann.

XText

Meine ersten Versuche habe ich mit XText gemacht. XText ist ein Eclipse-Projekt, das es erlaubt eigene Grammatiken zu verfassen und dann zu verarbeiten, bringt darüber hinaus dann auch Support mit, damit diese Syntax in Eclipse Syntax-Highlighting, Autovervollständigung und vieles mehr hat. Grundsätzlich hatte mich diese Suite angesprochen, aber wie es so ist: Viel Macht kommt mit viel Schwergewichtigkeit. So braucht man für die Arbeit mit XText eine spezielle Eclipse-Distribution, die Einstiegshürde seine erste Grammatik zum Laufen zu bekommen war recht hoch.

Da ich vieles von dem, was XText mitbringt nicht brauche, habe ich mich recht schnell nach einem anderen Tool umgesehen.

ANTLR
ANTLR (ANother Tool for Language Recognition) ist ein Parser, der es erlaubt eine eigene Grammatik zu definieren und daraus Basisklassen erzeugt, um auf die Elemente aus einer geparsten Datei zugreifen zu können. Der Zugriff auf eine geparste Datei erfolgt ähnlich dem Verarbeiten eines XML-Dokumentes: man kann entweder auf den Element-Baum zugreifen, oder man definiert einen Listener, der immer alarmiert wird, wenn ein bestimmtes Ereignis eintritt.

Anbei wollen wir uns eine einfache Grammatik anschauen, die aus einer Textdatei ermittelt, wer gegrüßt und wer verabschiedet wird. Die Datei ist zeilensepariert aufgebaut und kann folgende Inhalte haben
Hello <name>
Bye <name>
Daneben kann das ganze noch um Zeilenend- Kommentare und Inline-Kommentare erweitert werden

Hier ein Beispiel unserer zu verarbeitenden Datei:

# Hier stehen Grüße drin
Hello world
Hello Michael # am Anfang der Zeile steht ein Tab, am Ende ein Kommentar
Bye    /* hier steht ein Kommentar */    Terence
# Und zum Abschluß noch mehr Komemntare

Diese können wir mit folgender Grammatik verarbeiten:

// Define a grammar called Hello
grammar Hello;

// Parser-Regeln
greetings
            : greeting (ENDL greeting)* EOF
            ;

greeting
            : hello
            | bye
            |
            ;

hello
            : 'Hello' ID
            ;

bye
            : 'Bye' ID
            ;

// Lexer-Regeln
ID
            : [a-zA-Z]+
            ;

ENDL
            : '\r'? '\n'
            ;

// Whitespaces, Kommentare & Co
WS
           : [ \t]+ -> skip
           ;

LINE_COMMENT
           : '#' ~('\n'|'\r')* -> skip
           ;

COMMENT
           : '/*' .*? '*/' -> skip
           ;

Die Grammatik ist in Parser-Regeln und Lexer-Regeln unterteilt. Grob gesagt sagt eine Lexer Regel aus, wie ein einzelnes Wort erkannt wird, eine Parser-Regel sagt aus, wie aus Worten Sätze gebildet werden. Alle klein-geschriebenen Definitionen sind Parser-Definitionen, alles großgeschriebene Lexer-Definitionen.

In Zeile 5 steht die Hauptregel. Diese besagt, dass ein Dokument aus einem greeting besteht, gefolgt von 0 oder mehr weiterer greetings, die durch Zeilenumbrüche getrennt sind. Danach folgt das Ende der Datei

Ein greeting kann entweder eine hello-Regel, eine bye-Regel oder eine leere Regel (damit wird eine Leerzeile abgebildet) sein (Zeile 9).

hello besteht aus dem Schlüsselwort ‚Hello‘ und einem Namen (Zeile 15). bye aus dem Schlüsselwort ‚Bye‘ und einem Namen (Zeile 19). Ein Name darf aus den Zeichen [a-zA-Z]+ bestehen (Zeile 24).

Ab Zeile 33 folgen Patterns, die ignoriert werden sollen, also Whitespaces, Tabs und Kommentare. Das „-> skip“ sorgt dafür, dass das Auftreten dieser Token ignoriert wird.

Aus dieser Gramatik erzeugt ANTLR für uns einige Java-Klassen. Wie man das macht, will ich nicht beschreiben, das ist im ANTLR-Tutorial unter http://www.antlr.org/wiki/display/ANTLR4/Getting+Started+with+ANTLR+v4 schon viel besser erkärt. Es gibt aber noch etwas Java-Code, den wir schreiben müssen.

public class HelloListener extends HelloBaseListener {
  private List<String> hellos = new LinkedList<String>();
  private List<String> byes = new LinkedList<String>();

  @Override
  public void enterHello(HelloContext ctx) {
    hellos.add(ctx.ID().getText());
  }

  @Override
  public void enterBye(ByeContext ctx) {
    byes.add(ctx.ID().getText());
  }

  public List<String> getHellos() {
    return hellos;
  }

  public List<String> getByes() {
    return byes;
  }
}

Und um das Ganze auszuführen, noch etwas Boilerplate

public class Main {
  public static void main(String[] args) throws Exception {
    String filename = "/test.hello";
    ANTLRInputStream antIstream = new ANTLRInputStream(Main.class.getResourceAsStream(filename));
    HelloLexer lexer = new HelloLexer(antIstream);
    HelloParser parser = new HelloParser(new CommonTokenStream(lexer));
    ParseTree tree = parser.greetings();
    ParseTreeWalker walker = new ParseTreeWalker();
    HelloListener wtlListener = new DslHelloListener();
    walker.walk(wtlListener, tree);
    System.out.println("Hellos: " + wtlListener.getHellos());
    System.out.println("Byes: " + wtlListener.getByes());
  }
}

Die ganzen Klassen mit einem Hello im Namen (außer dem oben gezeigten HelloListener) sind durch ANTLR erzeugt worden.

Die Ausgabe sieht dann wie folgt aus:

Hellos: [world, Michael]
Byes: [Terence]

Fazit
Schon an diesem relativ einfachen Beispiel sieht man, dass man mit einfachen Java-Boardmitteln beim Parsen nicht weit kommen würde. ANTLR nimmt uns hier eine Masse Arbeit ab.
Natürlich wird man als Einsteiger in ein paar Fallen laufen und sich ein paar Patterns und Best Practises erarbeiten müssen (Allein nur die Grammatik so zu definieren, dass man die letzte Zeile nicht mit einem Zeilenumbruch beenden muss, hat mich einen Abend gekostet). Die Integration in eine Buildumgebung muss man sich auch erarbeiten, aber es gibt eine steile Lernkurve ohne sich mit akademischen Theoremen auseinandersetzen zu müssen. Und im Nachhinein ärgere ich mich an einigen Stellen zu schnell auf XML gesetzt zu haben, anstatt mir eine eigene Sprache auszudenken.

Hier noch zwei Buchtipps, für diejenigen, die sich tiefer mit der Materie auseinader setzen wollen. Beide sind von Terence Parr, dem Macher von ANTLR und angenehm zu lesen:

Language Implementations Patterns legt die Grundlagen für das Erstellen eigener Sprachen und stellt Patterns vor, die ANTLR Reference überträgt diese Patterns dann auf die konkrete Nutzung von ANTLR.

Advertisements