Jüngst habe ich im Rahmen meiner Tätigkeit als studentische Hilfkraft mit dem Erstellen einer Dokumentation ein Teilprojekt abgeschlossen, das wiederum ein Teil von EVAS ist. Für mich ging es unter anderem darum, eine Eingabeschnittstelle für eine eingeschränkte Instanz der CTL* zu schaffen. Meine Chefin wünschte sich eine Eingabe als String, also musste ich irgendeine Form von Parser auf die Beine stellen.
Ein einfaches Beispiel für eine kombinierte Lexer- und Parsergrammatik (ANTLRWorks)
Im Web stieß ich recht schnell auf das Tool ANTLR, das hauptsächlich von einem amerikanischen Professor namens Terence Parr entwickelt wird. ANTLR ist ein Parsergenerator, erstellt also aus speziellen Grammatiken Quellcode für Parser in verschiedenen Sprachen, wobei Java die hauptsächlich unterstützte ist. Es werden LL(*)-Parser erzeugt (Wikipedia kennt bisher nur LL(k)), die also theoretisch beliebigen Lookahead ermöglichen. Backtracking, semantische Prädikate und sonstiger Schnickschnack sind natürlich auch dabei, was die Klasse der möglichen Parser recht mächtig macht; so sind für viele große, komplizierte Sprachen bereits Grammatiken implementiert. Die Anwendungen erstrecken sich von Interpretern über Parser bis hin zu ganzen Compilern.
ANTLR an sich ist ein rein textbasiertes Programm. Besonders neckisch ist aber die Entwicklerunterstützung durch das Programm ANTLRWorks, das eine graphische IDE zum Entwickeln von Grammatiken bietet. Es zeichnet Syntaxdiagramme zu Regeln, erkennt und markiert linksrekursive Regeln und liefert Interpreter und Debugger für schnelles, stückweises Testen der Grammatiken. Die Grammatiken werden in einer erweiterten Form der EBNF notiert, was für jemanden vom Fach sofort eingängig ist. Ich selbst habe noch keine LR-Parser gebaut; man sagt aber LL-Parsern nach, dass sie intuitivere Grammatiken als jene ermöglichen.
Es gibt potentiell drei Stufen der Verarbeitung: Lexing, Parsing und Tree Walking. Die ersteren beiden kann man in einer kombinierten Grammatik zusammenfassen; die letzte macht nur Sinn, wenn der Parser einen AST statt einer direkten Ausgabe erzeugt. Dieser Zwischenschritt kann bei komplexeren Sprachen Sinn machen, da die Parsebäume sehr eklig werden und die logische Struktur der Ausdrücke verschleiern können. Alle drei Stufen werden von ANTLRWorks graphisch unterstützt.
Ein bisschen nörgelig wird ANTLR, sobald man linksrekursive Regeln hat. Dann reicht Lookahead allein nämlich im Allgemeinen wohl nicht mehr aus, um deterministisch eine Alternative zu zu wählen. In den Griff bekommen kann man das zum Einen durch Umschreiben der Grammatik, was im schlimmsten Fall die Lesbarkeit stark einschränkt, oder zum Anderen durch Backtracking. Schaltet man Backtracking für eine Grammatik global ein, frisst ANTLR so gut wie alles, das wird aber als schlechter Stil angesehen. Es ist also möglich, Backtracking nur für bestimmte Regeln zu verwenden. Außerdem gibt es eine Option, mit der sich der Parser während des Lookahead merkt, was er schon so gelesen hat, damit er im Erfolgsfall nicht noch mal alles lesen muss. So soll eine (fast) lineare Laufzeit erreicht werden können.
Ein Beispiel mit Aktionen
Als Entwickler legt man direkt in seiner Zielsprache Details des Parsers fest. Hinter jeder Alternative einer Regel kann man eine Aktion formulieren, die bei einem Match ausgeführt wird. Regeln können Rückgabewerte haben und auf solche aufgerufener Regeln zugreifen. Außerdem können viele Aspekte, wie zum Beispiel die Behandlung von Syntaxfehlern, direkt in der Grammatik mit Code in der Zielsprache überschrieben und erweitert werden. Es ist also möglich, sehr spezialisierte Parser zu schreiben.
Mit ANTLR hat man mit einfachen Beispielen sehr schnell Erfolgserlebnisse. Leider muss man bald feststellen, dass die Abgründe des Parsens sehr tief sind und dass manchmal nützliche Tools auch eher problemverschleiernd wirken. Nach Lektüre von Parrs Referenzwerk und intensivem Nutzen der Mailingliste mit sehr hilfsbereiten und kompetenten Stammgästen lässt sich aber einiges in den Griff bekommen. ANTLR wird konsequent weiterentwickelt, so ist die von mir genutzte Version schon wieder veraltet, die im Buch vorgestellte erst recht. Insbesondere bei der Syntax der Grammatiken ändert sich ab und an einiges, sodass zum Beispiel Grammatiken der v2 nicht kompatibel zu v3 sind. Längerfristig mit ANTLR arbeiten heißt also, immer am Ball zu bleiben. Insbesondere für kleine, einfache Sprachen, für die man mal schnell eine Parser braucht, ist ANTLR möglicherweise sehr zu empfehlen. Sobald man aber auf Probleme stößt, die oft auch struktureller, theoretischer Natur sind, wird ein größerer Arbeitsaufwand nötig, der sich meines Erachtens nach aber lohnt, denn das ist vermutlich bei jedem Parsergenerator so. Ohne Verständnis für die grundsätzlichen Eigenschaften von Wortproblemen und Parsen sowie tiefere Einblicke in die Funktionsweise von ANTLR lassen sich manche Probleme nicht richtig lösen. Eines habe ich bei dieser Arbeit mindestens gelernt: Parsen kann sehr, sehr hart sein.
Nachtrag: In einem neueren Beitrag verlinke ich einige Beispiele.
