Parser-Bau mit ANTLR: Sprachunterricht

Der Parser-Generator ANTLR (der Name steht für „ANother Tool for Language Recognition“) liegt mittlerweile in Version 4 vor [1]; Ende März 2017 wurde bereits Version 4.7 mit weiteren Verbesserungen veröffentlicht. ANTLR ist ein sehr aktives Projekt, das seit 25 Jahren von Terence Parr, Professor an der University of San Francisco, entwickelt wird [2]. Das Projekt steht unter der BSD-3-Clause-Lizenz und wird über GitHub [3] bereitgestellt. Da es in der dotnetpro bereits einen hervorragenden Artikel zu ANTLR 4 gab [4], soll es das an dieser Stelle mit den einleitenden Worten auch gewesen sein. Dieser Beitrag versteht sich als Ergänzung.ANTLR ist ein sehr gutes Beispiel dafür, warum das Rad nicht neu erfunden werden sollte – ein Problem, das in der Informatik sehr häufig anzutreffen ist. Terence Parr hatte vor über 25 Jahren ein Problem, das er lösen wollte. Anstatt dieses eine Problem manuell zu lösen, wollte er eine generische Implementierung schaffen. Herausgekommen ist ANTLR. Er selbst sagt dazu: „Why program by hand in five days what you can spend twenty-five years of your life automating?“Das entbehrt nicht einer gewissen Ironie. Auf der einen Seite hat er selbst dadurch erheblich mehr Zeit in die Entwicklung von ANTLR gesteckt als in das ursprüngliche Problem. Auf der anderen Seite ist dadurch ein Tool entstanden, das nun vielen anderen hilft, eigene Probleme zu lösen. Dieses ursprüngliche Problem hatte Terence Parr 1980. Darauf angesprochen gibt er aber mittlerweile zu, dass er sich daran gar nicht mehr erinnern kann.

Wofür ANTLR?

Nur ein kleines Missverständnis gilt es noch aus der Welt zu schaffen. ANTLR ist ohne Zweifel ein Parser-Generator. Wie der Name schon verrät, lassen sich damit Parser aus Grammatiken generieren, die strukturierten Text lesen, verarbeiten und ausführen oder übersetzen können.

Die Bezeichnung „strukturierter Text“ für die Eingabe ist nicht ohne Grund so allgemein formuliert. Trotzdem verstehen die meisten die Begriffe Parser/Compiler im klassischen Sinne, also als gedacht für Programmiersprachen, sowohl in Richtung DSLs (Domain Specific Languages) als auch GPLs (General Purpose Languages). Das ist zwar verständlich, allerdings sind die Einsatzbereiche von ANTLR weit größer. Strukturierter Text liegt unter anderem auch bei Importformaten vor, bei denen es ebenfalls eine Überlegung wert sein kann, eine Grammatik für sie zu entwerfen, um das Format validieren und verarbeiten zu können. Ebenfalls sehr beliebt ist ANTLR bei sogenannten Inselgrammatiken (siehe den gleichnamigen Kasten), zu denen LaTeX und HTML gehören. Diese kommen häufig dann zum Einsatz, wenn starre Systeme durch den Kunden angepasst werden sollen, zum Beispiel durch eine in normale Textdokumente eingebettete Programmiersprache.Zu guter Letzt können eine Grammatik und die dazugehörigen Parser ein Kommunikationsprotokoll abdecken. Zum Beispiel, indem die Grammatik die Übergänge verschiedener Protokollzustände beschreibt, die dann durch die Validierung der Syntax implizit überprüft werden. Erfreulich ist, dass ANTLR mit Binärdaten umgehen kann. Diese können zum Beispiel als Tokens genutzt werden, um eine Grammatik zu definieren. Gerade bei Kommunikationsdaten ist das sehr nützlich.Diese Beispiele sollen zeigen, dass es viele weitere Anwendungsfälle für Parser-Generatoren wie ANTLR gibt.Gute Literatur zum Thema ANTLR sind die beiden Bücher „The Definitive ANTLR 4 Reference“[5] und „Language Implementation Patterns“[6], beide von Terence Parr. Das erste bezieht sich auf ANTLR 4, das zweite enthält eher allgemeingültige Ideen, die sich aber sehr gut mit ANTLR 4 zusammen umsetzen lassen.

IDE-Support

Wer den Einsatz von ANTLR in Erwägung zieht, wird auch schnell darüber nachdenken, ob das Tool mit einer IDE oder mit der eigenen IDE zusammenarbeitet. ANTLR ist in Java implementiert und lässt sich vollständig über eine Kommando­zeile steuern. Andere Entwicklungsumgebungen bieten da­rüber hinaus viele Komfortfunktionen an. Zu nennen sind das hervorragende ANTLRWorks 2 [7], das im oben erwähnten ersten Artikel zu ANTLR zum Einsatz kam, sowie eine ganze Reihe von Plug-ins für IDEs wie Visual Studio, IntelliJ IDEA, NetBeans und Eclipse. Die Beispiele für diesen Artikel sind in IntelliJ IDEA (Bild 1) und dem ANTLR v4 Grammar Plug-in entstanden, mit dem ein komfortables Arbeiten mit ANTLR-Grammatiken möglich ist [8] – ein Überbleibsel der Masterarbeit des Autors, in der ANTLR ein Hauptakteur war.

Der Autor schließt sich aber zudem der Meinung im ersten Artikel hinsichtlich ANTLRWorks an. Damit sind insbesondere sehr gute Syntaxdiagramme zu erstellen, die einen visuellen Einblick in einzelne Regeln ermöglichen.In der Microsoft-Welt ist die Lage derzeit zweigeteilt. Auf der einen Seite entstehen neue Plug-ins und Erweiterungen für ANTLR-4-Grammatiken, wie zum Beispiel für die Entwicklungsumgebung Visual Studio Code [9]. Das ist sehr erfreulich, da sich VS Code einer immer größeren Beliebtheit erfreut und die Abhängigkeit von einem mitunter kostspieligen Visual Studio vermieden wird. Auf der anderen Seite funktioniert das offizielle Visual-Studio-Plug-in [10] nur bis einschließlich Version 2015. Die neue Version 2017 wird noch nicht unterstützt; genauer gesagt zeigt sie einige Probleme, sodass noch etwas Geduld erforderlich ist. Viele der genannten Plug-ins sind Open Source [11], was es ermöglicht, die Weiterentwicklung aktiv zu beeinflussen.Aus eigener Erfahrung kann der Autor aber sagen, dass auch die Arbeit mit IntelliJ IDEA kein Problem darstellt und sich ANTLR-4-Grammatiken ohne nennenswerten Aufwand über die ANTLR-Targets für verschiedene Zielsprachen erzeugen lassen.

ANTLR-Targets

Ein entscheidender Punkt bei ANTLR sind die sogenannten Targets: die Zielsprachen, für die ANTLR Code generiert. Viele verschmähen den Parser-Generator, weil er in Java implementiert ist.Diese Aussage ist zwar nicht falsch, aber nur die halbe Wahrheit. Ein Target sorgt dafür, dass die ANTLR-Grammatiken, die in einer speziellen Syntax (DSL) geschrieben sind, in lauffähigen Code übersetzt werden. Dieser lauffähige Code repräsentiert die Lexer- und Parser-Komponente. Damit ist Neutralität und Abstraktion zwischen Design- und Laufzeit möglich. Soll heißen: Während des Entwurfs kommt ­Java in der Kommandozeile oder einer IDE zum Einsatz, zur Laufzeit ein ANTLR-Target.Die Anzahl der Zielsprachen wächst kontinuierlich. Verfügbar sind (Stand Anfang April) Laufzeitumgebungen für die folgenden Programmiersprachen:

• Java,
• C# (zwei verschiedene),
• Python (Version 2 und 3),
• JavaScript,
• Go,
• C++,
• Swift.

Zusätzlich ist gerade ein Target für TypeScript [12] in Arbeit. Es nutzt bereits Funktionen von TypeScript 2.0 und kann in TypeScript-Projekten so eingebaut werden, dass ANTLR Änderungen an Grammatikdateien erkennt und automatisch neuen Code daraus generiert.

Die verschiedenen Targets erlauben es, eine Grammatik zu schreiben und diese anschließend in unterschiedlichen Projekten einzusetzen. So kann zum Beispiel ein Importformat sowohl im Desktop-Client (C#) als auch direkt im Browser (JavaScript) validiert werden, um nur zwei mögliche Beispiele zu nennen, siehe auch den Kasten Wissenswertes zu den ­Beispielen.

Neues bei ANTLR v4

Bevor es mit spezifischen Tipps und Tricks zu ANTLR losgeht, stellt sich die Frage, warum eigentlich ANTLR in Version 4? Die Vorgängerversion 3 erfreut sich immer noch großer Beliebtheit.Eine wichtige Neuerung ist, dass ANTLR 4 nahezu jede Grammatik entgegennimmt und in Code umwandeln kann. Viele der früheren Fehlermeldungen und Probleme in diesem Zusammenhang gehören der Vergangenheit an. Stichwörter sind hier Adaptive LL(*) (kurz auch ALL(*)) Parsing – ein spannendes, aber leider auch zu umfangreiches Thema, als dass es an dieser Stelle zu berücksichtigen wäre. Aber alleine für diese Änderungen lohnt es sich schon, ANTLR 4 den Vorzug zu geben oder von Version 3 zu migrieren.Darüber hinaus gibt es umfangreiche Verbesserungen, wenn mit ANTLR eine Programmiersprache implementiert werden soll. Das hat mit selbstreferenziellen und linksrekursiven Grammatiken zu tun, die gerade bei Ausdrücken sehr häufig zum Einsatz kommen. Dazu ein Beispiel:

Diese Regeln/Optionen bilden einen Teil der Ausdrücke der Programmiersprache Simplex ab. ANTLR 4 kann diese Regeln direkt auflösen und Code daraus generieren, ohne dass der Entwickler dazu eingreifen müsste.Zusätzlich macht ANTLR 4 einige Dinge anders und zwingt den Anwender dazu, dem auch zu folgen, zum Beispiel die Trennung von Grammatiken und Code durch die Entwurfsmuster Visitor und Listener sowie das automatische Generieren von Parse-Bäumen. Beides ist in ANTLR 4 Standard, in Version 3 aber anders gelöst.

Was wird generiert?

Bisher war nur ganz generisch von generiertem Code die Rede. ANTLR ist geeignet für Grammatiken, die einen LL(k)-Parser zur Verarbeitung benötigen. Dabei lässt sich anhand eines Lookahead entscheiden, welche mögliche Regel expandiert wird. Eine implementierungstechnisch günstige Parser-Technik für diese Art eines Top-Down-Parsers bietet der rekursive Abstieg (recursive descent [13]). Dabei handelt es sich lediglich um eine Ansammlung von rekursiven Methoden, genau genommen um eine pro Grammatikregel. Der Parse-Vorgang beginnt bei der Wurzel eines Parse-Baums und hangelt sich an den Tokens (Blättern) ­hinab.Für eine gegebene Grammatikdatei werden die darin enthaltenen Tokens (Lexer-Datei) und Regeln (Parser-Datei) in eben den Code umgewandelt, der für die Grammatik einen Parser nach dem Prinzip des rekursiven Abstiegs darstellt. Das gewählte ANTLR-Target gibt dabei die Programmiersprache des generierten Codes und einige implementierungstechnische Details vor, da in JavaScript zum Beispiel andere Konstrukte möglich sind als in C#.

Aktionen in Grammatiken

Mit ANTLR ist es möglich, Grammatiken auf zwei verschiedene Arten zu schreiben: mit eingebetteten Aktionen und ohne – zumindest bietet es sich aus der Vogelperspektive so dar, ohne weitere Details zu berücksichtigen. Ein Vorteil von ANTLR ist, dass es eine Trennung von definierten Grammatiken und dem generierten Code erlaubt. Diese Trennung wird mit in Grammatiken eingebetteten Aktionen allerdings wieder aufgehoben.Aktionen in Grammatiken können unterschiedlich implementiert sein. Zum einen ist es möglich, lauffähigen Code in eine Aktion einzubinden. Das folgende Listing zeigt dazu einen Ausschnitt einer Grammatik mit angedeuteten Aktionen:

Die geschweiften Klammern enthalten den auszuführenden Code, der hier mit den Auslassungspunkten angedeutet ist. Die Aktionen können aus normalem Java-Code bestehen, im einfachsten Fall aus einer Konsolenausgabe mit System.out. Aktionen bestehen grundsätzlich aus Java-Code, können aber spezielle Attribute der Token und Parser-Regeln nutzen [14]. Auf diese Weise besteht Zugriff beispielsweise auf den Text oder den Typ eines Tokens.Eine kleine Evolution dieser Aktionen ist der Einsatz eines Member-Bereichs in einer Grammatik, um dort Methoden zu definieren, wie das folgende Beispiel zeigt:

Bei den Methoden handelt es sich um leere Definitionen, die in den Aktionen aufgerufen werden können. Die konkrete Implementierung erfolgt in einer eigenen Klasse, abgeleitet von der von ANTLR automatisch generierten Basisklasse des Parsers für die Grammatik. Wird dann dieser Parser verwendet, werden die Methoden dort durch die Aktionen aufgerufen. Dadurch wird die starke Kopplung zwischen Grammatik und auszuführendem Code etwas gelockert, sodass sich ein und dieselbe Grammatik für unterschiedliche Anwendungen verwenden lässt. Allerdings handelt es sich noch immer um Java-Code. Um eine Grammatik auf verschiedenen Zielplattformen einsetzen zu können, müssen Grammatik und Anwendungscode weiter entkoppelt werden. Dazu lassen sich das Visitor- und das Listener-Muster nutzen.Über diese Aktionen in ANTLR 4 können Attributgrammatiken umgesetzt werden. Das sind kontextfreie Grammatiken, die um Attribute und Bedingungen erweitert sind, um somit etwa das Einhalten von Regeln zu prüfen, die mit kontextfreien Grammatiken ansonsten nicht abzubilden wären.

Listener versus Visitor

Beim Aufruf einer Grammatikregel generiert ANTLR, ausgehend davon als Wurzel, einen Syntaxbaum. Dieser AST (Abstract Syntax Tree) repräsentiert ein Programm oder einen Teilausschnitt in Form eines Baums. Um die Verarbeitung einer Grammatik vom Code einer Anwendung zu trennen, ist es wünschenswert, diesen Baum zu durchlaufen und an bestimmten Stellen anwendungsspezifischen Code auszuführen. Bei ANTLR funktioniert dies über das Muster Visitor oder Listener. Auf Wunsch erzeugt ANTLR die eine oder die andere Variante oder beide zusammen. Diese werden gerne als „Tree walking“-Mechanismen von ANTLR bezeichnet.Beim Listener-Muster erzeugt ANTLR 4 pro Regel zwei Methoden, eine sogenannte Enter- und eine Exit-Methode. Diese werden automatisch von ANTLR aufgerufen, wenn mittels der Klasse ParseTreeWalker ein Baum durchlaufen wird. Alle Enter- und Exit-Methoden sind in einer Schnittstellenbeschreibung gekapselt, sodass nur die zu implementieren sind, die tatsächlich von Interesse sind. Das ermöglicht ein Entkoppeln vom nutzerspezifischen Code und dem AST mit seiner Grammatik. Wichtig aber ist, dass der Durchlauf durch den Baum mit ParseTreeWalker automatisch geschieht. ANTLR ruft jede Enter- und Exit-Methode auf.Im Fall des Visitor-Musters werden Visit-Methoden für die verschiedenen Knoten in einem ParseTree-Objekt aufgerufen. Diese Aufrufe erfolgen nicht automatisch, sondern die Implementierung ist dafür zuständig, die jeweiligen Visitor-Methoden der nachfolgenden Knoten aufzurufen. Das, was ParseTreeWalker beim Listener-Muster noch selbst erledigt hat, ist jetzt beim Visitor-Pattern Aufgabe des Programmierers. Der Vorteil ist, dass dadurch der Durchlauf durch den Baum in den eigenen Aufgabenbereich fällt und die Kontrolle darüber zurückerlangt wird. Der Nachteil ist, dass etwas mehr zusätzlicher Code notwendig ist.

Verschiedene Zeichenkanäle

ANTLR erlaubt, Kanäle für Eingabezeichen zu definieren. Diese Kanäle können in einer Lexer-Datei festgelegt werden:

Technisch gesehen werden Kanäle lediglich durchnummeriert. Der Standardkanal, den es immer gibt und in dem normalerweise alle Zeichen landen, hat die Nummer 0. Im Beispiel ist der Whitespace-Kanal die Nummer 1, und Comment bekommt die Nummer 2. Das Beispiel zeigt auch, wie Kanäle eingesetzt werden: Hinter einer Lexer-Regel wird, eingeleitet durch einen Pfeil, der Kanal angegeben. Hier können die eben definierten Kanäle oder direkt Nummern verwendet werden.Aber was bringt das? Normalerweise landen alle Zeichen im Standardkanal (Nummer 0). Je nach Anwendungsfall sind aber gar nicht alle Zeichen sinnvoll. Der Durchschnitts-Compiler von nebenan interessiert sich zum Beispiel nicht für Leerzeichen und Kommentare. Diese können in eigene Kanäle fließen, wie das Beispiel gezeigt hat, und ausgelagert werden. Die Standardverarbeitung von Token nutzt nur den Standardkanal mit der Nummer 0. Auf selbst definierte Kanäle muss man explizit zugreifen.Bei Transformatoren sieht es unter Umständen anders aus. Dort ist es durchaus sinnvoll, Kommentare zu betrachten, allerdings vielleicht gesondert, um diese umzuwandeln oder auf sonst eine Weise aufzubereiten. Durch unterschiedliche Kanäle können Kommentare gesondert betrachtet werden, was ein Vorteil sein kann. Der Zugriff auf die gesonderten Kanäle erfolgt unter Zuhilfenahme eines aktuellen Tokens.

Namen für Grammatikregeln

Wie schon erwähnt, werden beim Einsatz des Listener-Prinzips zum Durchlaufen eines Syntaxbaums zwei Methoden pro Grammatikregel erzeugt. Diese Enter- und Exit-Methoden decken aber normalerweise nicht die unterschiedlichen Fälle einer Regel ab:

Die Regel argument besitzt vier verschiedene Optionen, je nachdem, von welchem Typ das Argument ist. Die Namen hinter den #-Zeichen sind die angesprochenen Regelnamen. Dadurch werden nicht nur die Methoden enterArgument und exitArgument erzeugt, sondern je zwei Enter- und Exit-Methoden für jede einzelne Regel. In diesem Fall macht das ­einen erheblichen Unterschied bei der Verarbeitung. Die Struktur wird zwar umfangreicher, weil es mehr Methoden gibt, allerdings übernimmt jede einzelne Methode nur einen kleinen Teil der Verarbeitung, was diese wiederum übersichtlicher macht. In diesem konkreten Fall bedeutet das, dass zum Beispiel in jeder Exit-Methode klar ist, um welchen Datentyp es sich bei einem Argument handelt. Es ist nicht nötig, in einer sehr allgemeinen Methode für ein Argument zu differenzieren, welche Regeloption eigentlich gemeint ist. Diese Aufgabe übernimmt ANTLR oder genauer der davon generierte Code.

Zugriffe auf Regelelemente

Der Zugriff auf Elemente einer Grammatikregel ist essenziell bei der Verarbeitung von Eingabedaten. Durch die Regel wird die Eingabe auf eine definierte Art und Weise aufgeteilt. Auf diese Teilelemente einer Regel möchten wir nun in der Verarbeitungsphase früher oder später zurückgreifen. Denn neben normalen Tokens, die in der Regel eher weniger inte­ressieren, sind zahlreiche Lexeme von großem Interesse. Als Tokens können die in der Eingabe vorkommenden Zeichengruppen angesehen werden, die vom Parser auf Validität untersucht werden. Ein Lexem ist dabei eine konkrete Ausprägung eines Tokens, wie hier zu sehen ist:

Das Token CURLY_OPEN definiert nur eine Art von Lexem, nämlich die öffnende geschweifte Klammer. Das Token ID definiert allerdings eine Gruppe von Lexemen, nämlich alle Bezeichner, die mit einem Buchstaben anfangen, gefolgt von Zahlen, Buchstaben, Unterstrichen oder dem Punkt.Um auf diese Angaben während der Verarbeitung sehr einfach zugreifen zu können, bietet es sich unter Umständen an, eigene Variablen in den Regeln zu definieren. Ein Beispiel:

Diese Variablen oder Bezeichner sind die Bereiche vor den Gleichheitszeichen. In dem Beispiel lässt sich das Lexem, das durch das Token ID erkannt wird, über die Name-Eigenschaft abrufen. Bei den Instruktionen am Ende der Regeldefinition ist es sogar so, dass eine Liste von Instruktionen in der Eigenschaft ins hinterlegt ist. Auf diese Weise ist während der Verarbeitung sehr schnell der Zugriff auf die Teile einer Regel möglich, die von Bedeutung sind.

Fehler und Fehlermeldungen

Fehler sind normal. Aus Sicht von ANTLR interessieren aber weniger die Fehler, die wir beim Entwickeln der Software machen. Viel interessanter sind die Fehler, welche die Anwender machen.Wird zum Beispiel eine eigene Sprache entwickelt, besteht ein nicht unerheblicher Aufwand bei der Implementierung darin, den Anwendern aussagekräftige Fehlermeldungen zu präsentieren. Zumindest sollte es so sein. Viel zu häufig werden leider lediglich die Fehlermeldungen des Parse-Prozesses an den Anwender weitergeleitet.Zunächst gibt es grundsätzlich zwei verschiedene Arten, mit Fehlerzuständen umzugehen. Im Modus der ErrorRecoveryStrategie versucht ANTLR einen Fehler zu korrigieren, vereinfacht gesagt dadurch, indem es weitere, nachfolgende Zeichen liest, bis eine der Grammatikregeln passt. Das ist, wie gesagt, eine sehr vereinfachte Darstellung, da es in der Regel bessere Mechanismen gibt, die ANTLR verwendet, um solche Syntaxfehler auszubügeln.Die andere Strategie ist die BailErrorStrategy. Sie wird gern als „Bail out“ bezeichnet. Das lässt sich mit „den Schleudersitz betätigen“ übersetzen, was den Kern sehr gut beschreibt. Bei dieser Strategie bricht ANTLR das Parsen sofort ab und erzeugt eine Fehlermeldung. In der Regel ist diese Strategie bei Programmiersprachen die richtige. Niemand möchte, dass ein C#-Compiler die nächsten Eingabezeichen weiterverarbeitet oder gar versucht zu erraten, wie es weitergehen könnte, nur um einen Fehler zu beseitigen. Bei Inselgrammatiken sieht das aber schon wieder anders aus. Bei ­HTML zum Beispiel ist es nicht erwünscht, dass eine Webseite gar nicht angezeigt wird, nur weil irgendwo ein Zeichen fehlt.ANTLR erlaubt zudem eigene Fehlerbehandlungen, zum Beispiel, indem ein ErrorListener zum Listener-Interface hinzugefügt wird, sodass die Fehlermeldungen nicht, wie normalerweise vorgesehen, auf der Konsole ausgegeben werden. Die Klasse BaseErrorListener (hier auf das Java-API bezogen) erlaubt zudem die Implementierung ganz eigener Listener. Dort gibt es zum Beispiel Methoden wie SyntaxError. Dies ist die richtige Stelle, wenn ein Syntaxfehler untersucht werden soll, um dem Nutzer hilfreiche Fehlermeldungen anzuzeigen.Des Weiteren bietet ANTLR das Interface ANTLRErrorStrategy an. Eine konkrete Implementierung ist in der Klasse DefaultErrorStrategy zu finden. Dieses Interface bietet unter anderem Operationen wie die sync()-Methode an. Wird diese in einer eigenen Implementierung überschrieben und leer gelassen, wird bei der Codegenerierung durch ANTLR der Codeteil weggelassen, der für die Synchronisation beim Recovery in einer Sub-Regel sorgt.Ein sehr pragmatisches Herangehen beim Erkennen von Syntaxfehlern sind eigene Grammatikregeln. Durch eigens erstellte Regeln, die typische Syntaxfehler repräsentieren, werden diese direkt erkannt und lassen sich entsprechend behandeln. Dazu ein minimales Beispiel:

Die erste Regel ist korrekt. Sie erkennt einen Ausdruck, der von zwei runden Klammern eingeschlossen ist. Die zweite Regel, dargestellt als Option, erkennt den Fall, dass die geschlossene runde Klammer fehlt. Durch diese Regel wird ein Syntaxfehler vermieden, der somit auch nicht von ANTLR gemeldet werden kann. In einem solchen Fall ist der Entwickler gefragt, eine eigene Implementierung als Listener oder Visitor bereitzustellen, die eine Fehlermeldung erzeugt oder sonstige Hilfen für den Anwender bereitstellt.Durch diese Tricks und Kniffe lässt sich der durch ANTLR generierte Code auf den eigenen Anwendungsfall zuschneiden – eine häufige Anforderung, da bei Parser-Generatoren oft befürchtet wird, dass der erzeugte Code für jeden erdenklichen Anwendungsfall passen muss und somit sehr aufgebläht ist.

Arbeiten mit Bäumen

Die Arbeit mit Parsern ist im Prinzip die Arbeit mit Bäumen. In der Regel muss der AST in irgendeiner Weise verarbeitet werden, was in einem oder mehreren Durchläufen durch den Baum endet. Das Listener- und das Visitor-Muster erlauben dies bereits auf einfache Weise. Manchmal ist es aber sinnvoll, den vorhandenen AST nicht einfach nur zu durchlaufen, um die darin vorhandenen Daten zu verarbeiten, sondern den Baum umzuschreiben. Die Klasse TokenStreamRewriter erlaubt es, eine Abfolge von Tokens zu verändern, zum Beispiel, um neue Tokens hinzuzufügen. So ist es durchaus möglich, einen geparsten Quelltext um bestimmte Elemente zu erweitern, die immer vorhanden sein sollen. Im Grunde ist es denkbar, auf diese Weise Typkonvertierungen in einen Quelltext zu injizieren, wenn dies durch das gewählte Typsystem erforderlich wäre.

Testen von Grammatiken

Normalerweise erfolgen die Tests der Grammatik direkt im Projekt, wo die generierten Lexer- und Parser-Dateien zum Einsatz kommen sollen. Wer eine allgemeine Grammatik entwickelt, die keine Abhängigkeiten zu einer konkreten Programmiersprache besitzt, hat zudem weitere Testmöglichkeiten. ANTLRWorks 2 ist dafür eine gute Möglichkeit, da zum Beispiel Syntaxdiagramme mit angezeigt werden. Diese können die Fehlersuche erheblich erleichtern (siehe Bild 2).

Wer eine lauffähige Java-Umgebung sein Eigen nennt, kann zudem über das sogenannte TestRig testen, das bei ANTLR zur Verfügung steht. Dort stehen Befehle wie die folgenden beiden zur Verfügung:

Der Platzhalter <Grammatik> ist jeweils mit der eigenen Grammatikdatei zu ersetzen. Durch diese Befehle werden Tokens, ein AST und eine kleine grafische Oberfläche erzeugt und gestartet. Auf diese Weise lassen sich Grammatiken schnell prüfen.Des Weiteren bieten IDEs wie IntelliJ die Möglichkeit, eine Grammatik direkt im Editor auszuprobieren. Auch so lassen sich Fehler nachvollziehen, allerdings nur manuell. Es kann aber ein Vorteil sein, wenn Code manuell eingegeben wird, wie das zum Beispiel bei einer Programmiersprache in der letztendlichen Zielanwendung häufig der Fall sein wird.Ansonsten bleibt nur der gute alte Weg über Unit-Tests, bei denen für Eingabedaten passende Ausgabedaten in Form von Bäumen oder zum Beispiel generiertem Zielcode gegeneinander überprüft werden.

Performance

Bei Parser-Generatoren spielt immer das Laufzeitverhalten eine große Rolle. Dies allgemeingültig zu klären ist praktisch nicht möglich, da es stark davon abhängt, welche Gramma­tik­regeln geschrieben wurden und welchem Zweck diese dienen. Eine komplexe Ausgangssprache benötigt eine komplexere Verarbeitung als eine einfache.Über die bereits genannte Error-Strategie ist es möglich, in den Generierungsprozess von ANTLR 4 einzugreifen. Auf diese Weise lässt sich von vornherein Code vermeiden, der nicht benötigt wird, zum Beispiel bei einem Netzwerkprotokoll. Werden darüber Daten von A nach B gesendet, ist anzunehmen, dass diese Daten syntaktisch korrekt sind – zumindest nach einer ausreichend langen Testphase der Implementierung, da alle gesendeten Daten automatisch erzeugt wurden. Der dadurch eingesparte Code für die Fehlerbehandlung reduziert natürlich auch den Druck, der zur Laufzeit auf dem Compiler lastet.Eigene Erfahrungen zeigen, dass auch in JavaScript implementierte, also für dieses Target erzeugte Parser sehr leistungsfähig sind, und zwar auch dann noch, wenn der Compiler im Hintergrund bei jedem Tastendruck aktiviert wird. Natürlich gilt dabei die Einschränkung, dass die Eingabedaten nicht zu groß werden. Ansonsten generiert ANTLR performanten Code, der seit Jahren erprobt ist. Dennoch ist pro Anwendungsfall zu entscheiden, wie viele Daten durch einen von ANTLR erzeugten Parser verarbeitet werden sollen und wie sich das Leistungsverhalten zur Eingabegröße verhält.

Was spricht dagegen?

Häufig ist es so, dass jeder, der eine neue Technik kennenlernt, zunächst versucht, jedwedes Problem damit zu lösen. Das ist die berühmte Holzhammermethode: ein Organisations-, Management- beziehungsweise Prozess-Antimuster, auch unter dem Namen Wunderwaffe (Golden Hammer) bekannt.Nicht zu jedem Problem passt ANTLR. Am besten geeignet ist es bei kontextfreien Grammatiken und allen Anwendungsgebieten, die damit zu tun haben. Bei Programmiersprachen, ob DSLs oder GPLs, ist das recht offensichtlich. Bei Importformaten, die oben erwähnt wurden, ist das nicht immer so eindeutig. Das Problem dabei ist, dass sich im Allgemeinen nur das Vorhandensein einer Struktur wirklich gut validieren lässt. Also zum Beispiel, dass nach Feld A immer Feld B folgt und dass es nach dem Feld X mit Feld Y oder Feld Z weitergeht.Deutlich schwieriger bis nahezu unmöglich wird es, wenn der Feldinhalt ebenfalls validiert werden soll. Unter Umständen lässt sich noch feststellen – wie in einer Programmiersprache auch –, ob es sich zum Beispiel um eine Zahl oder um Text handelt. Aber selbst das ist durchaus mit vielen Problemen verbunden, da die Daten von sehr unterschiedlicher Natur sein können und kontextfreie Grammatiken hier Grenzen haben; vor allem dann, wenn syntaktisch identische Daten anders interpretiert werden sollen. Spätestens, wenn vermehrt zu regulären Ausdrücken gegriffen wird, um Daten auszuwerten, ist abzuwägen, ob der Einsatz von ANTLR tatsächlich Vorteile bietet.Des Weiteren gibt es einige Probleme, die sich ohne den Einsatz von ANTLR gar nicht stellen würden. Dazu gehören zum Beispiel Konflikte in Grammatiken, die durchaus viel Zeit in Anspruch nehmen können. ANTLR ist in Version 4 deutlich besser geworden, was zum Beispiel die Auflösung von unklaren Grammatiken betrifft. Häufig anzutreffen sind die linksrekursiven Grammatikregeln, die von ANTLR automatisch umgewandelt werden. Das betrifft auch andere Hürden, wie zum Beispiel Warnungen bei nicht eindeutigen Grammatikregeln. Nutzer von Yacc (Yet Another Compiler Compiler [15]) sind vermutlich mit Reduce/reduce-Fehlern vertraut. Diese und ähnliche Probleme treten zwar in ANTLR 4 deutlich weniger häufig auf, können aber immer noch viel Zeit und Mühe kosten.Darüber hinaus können Merkmale, die bereits im Artikel genannt wurden, den Aufwand in die Höhe treiben. Gramma­tiken mit konkretem Code vergrößern die Abhängigkeit zu einer spezifischen Technologie, und der im Compilerbau so vielgelobte Syntaxbaum kann in Anwendungen, in denen es nicht um die Verarbeitung einer Programmiersprache geht, für zusätzlichen Aufwand sorgen. Denn meist liegt ein ­solcher AST nicht in dem Format vor, wie es der jeweilige Anwendungsfall erfordert. Dann sind mitunter umfangreiche Umbauarbeiten notwendig, um Knoten des Baums zu verändern.Viele der Automatismen beim Generieren von Lexern und Parsern führen dazu, die jeweiligen Tools als Allround-Antwort für zahlreiche Probleme zu betrachten. Das ist in der weiträumigen Disziplin Informatik aber selten der Fall. Daher gilt es, vor dem Einsatz von ANTLR auf die Vor- und Nachteile zu schauen, die dadurch entstehen.

Fazit

ANTLR ist ein sehr mächtiges Tool, das nicht ohne Grund seit Jahrzehnten sowohl in Wissenschaft und Lehre als auch in der Praxis zum Einsatz kommt. Es befähigt Entwickler, mit relativ geringem Aufwand Grammatiken zu definieren, die anschließend durch die verschiedenen Targets zu lauffähigem Code umgewandelt werden.Bei der Masterarbeit des Autors hat das dazu geführt, eine eigene Programmiersprache in kurzer Zeit auf die Beine zu stellen, inklusive Verarbeitung und Transformation zu einer Zwischensprache, die wiederum mithilfe von ANTLR zu Bytecode für die Zielplattform übersetzt wird. Diese Dinge, samt statischem Typsystem, waren und sind ohne große Schwierigkeiten mit ANTLR abzubilden.Das Werkzeug ist daher für alle etwas, die vielleicht in das Gebiet des „Language Engineering“ hineinschnuppern oder ihr Compiler-Wissen auffrischen wollen oder vielleicht eine konkrete Projektidee haben, bei der eine formale Sprache nützlich sein kann.

Fussnoten

1. ANTLR, http://www.antlr.org
2. Terence Parr auf Twitter, http://www.dotnetpro.de/SL1708ANTLR1
3. ANTLR auf GitHub, http://www.dotnetpro.de/SL1708ANTLR2
4. Florian Fordermaier, Konkrete und abstrakte Bäume, Mit ANTLR zum eigenen Compiler, dotnetpro 1/2016, S. 104 ff., http://www.dotnetpro.de/A1601ANTLR
5. Terence Parr, The Definitive ANTLR 4 Reference, ISBN 978-1-934356-99-9,
6. Terence Parr, Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages, ISBN 978-1-934356-45-6,
7. ANTLRWorks 2, http://www.dotnetpro.de/SL1708ANTLR3
8. ANTLR v4 grammar plugin, http://www.dotnetpro.de/SL1708ANTLR4
9. ANTLR4 grammar syntax support (Plug-in für Visual Studio Code), http://www.dotnetpro.de/SL1708ANTLR5
10. ANTLR Language Support (Plug-in für Visual Studio), http://www.dotnetpro.de/SL1708ANTLR6
11. Updates for ANTLR4 Node.js/Visual Studio Code tools now available, http://www.dotnetpro.de/SL1708ANTLR7
12. antrl4ts – TypeScript/JavaScript target for ANTLR 4, http://www.dotnetpro.de/SL1708ANTLR8
13. Wikipedia, Rekursiver Abstieg, http://www.dotnetpro.de/SL1708ANTLR9
14. ANTLR 4, Actions and Attributes, http://www.dotnetpro.de/SL1708ANTLR10
15. Wikipedia, Yacc, http://www.dotnetpro.de/SL1708ANTLR11
16. Fabian Deitelhoff, Simplex-Language, Simplex auf GitHub, http://www.dotnetpro.de/SL1708ANTLR12