Category Archives: Work - Page 3

Beispiele für ANTLR

Einer der meistbesuchten Einträge in meinem Blog ist jener über den Compilergenerator ANTLR. Einige suchen scheinbar nach (einfachen) Beispielen – das suggerieren zumindest die Suchbegriffe, mit denen Leute hier landen. Da kommt es doch gelegen, dass ich jüngst für eine Demo einige Beispiele gebastelt habe, und diese nun online stellen kann. Hier kann der geneigte Leser ein Archiv herunterladen, das einige Grammatikdateien, Anwendungsstubs und Skripte sowie die verwendete ANTLR-Bibliothek enthält.

Im ersten Ordner finden sich sehr einfach Grammatiken, die im Wesentlichen verschiedene Features von ANTLRWorks zeigen sollen, da sie fröhlich Fehlermeldungen erzeugen. Die im zweiten Ordner enthaltenen Grammatiken lassen sich interpretieren und debuggen, eine sogar mit Ausgabe. Im letzten Ordner ist schließlich die komplette Folge von Tools, die ANTLR bietet, ausgereizt worden. Auf die Anwendung von Prädikaten habe ich dabei verzichtet, das hätte die Demo gesprengt.

Viel Vergnügen!

Existenzbeweis trifft Stochastik

Diese Woche habe ich eine verblüffende und elegante Sache in meiner Nebenfachvorlesung gelernt. Die Aufgabe:

Insgesamt 12% der Oberfläche einer Kugel ist schwarz (und bildet eine Borelmenge), und der Rest ist weiß. Gibt es einen einbeschriebenen Würfel, dessen Ecken allesamt weiß sind?

Ich weiß nicht, wie es Anderen geht, aber Übungsgruppe nebst -leiter haben erstmal etwas planlos reagiert. Mit einem analytischen Ansatz wird man sich vermutlich das Hirn verdrehen; zum Glück war aber ein Hinweis auf Erdös’ probabilistische Methode gegeben: Um die Existenz eines Element zu beweisen, genügt es, eine positive Wahrscheinlichkeit dafür nachzuweisen, ein solches zu erhalten, wenn man aus dem Grundraum zufällig ein Element wählt. A posteriori klar.

Was haben wir uns viele Gedanken gemacht. Klar ist, dass die acht nötigen Punkte nicht unabhängig zufällig wählbar sind. Spätestens drei (passend) gewählte Punkte legen die übrigen eindeutig fest. Kann man beschreiben, wie sie voneinander abhängen? Wenn man einen oder zwei Punkte festhält, was für Schlüsse kann man ziehen?
Antwort: Keine. Wir zumindest nicht.

Die Lösung war nun fast schon enttäuschend einfach, daher verblüffend und elegant. Seien also

$$S_k := \text{Ereignis, dass k-te Wuerfelecke schwarz}$$
$$W_k := \text{Ereignis, dass k-te Wuerfelecke weiss}$$

Klar ist, dass für einen zufällig gewählten Punkt auf der Kugel die Wahrscheinlichkeit, dass er schwarz ist, gerade

$$P\left(X \text{ schwarz}\right) = \frac{12}{100}$$

ist. Wir suchen nun die Wahrscheinlichkeit, dass alle Würfelecken weiß sind, also

$$P\left(\bigcap\limits^{8}_{i=1} W_k\right) = 1 – P\left(\bigcup\limits^{8}_{i=1}S_k\right)$$

Gut, hier sind wir immerhin schon darauf gekommen, uns das Gegenereignis anzuschauen, was uns den Schnitt vom Hals schafft. Das ist nicht weiter spektakulär, denn hier sind die komplizierten Abhängigkeiten der Punkte immer noch drin. Wegen der -Subadditivität der zugrundeliegenden Borel--Algebra (Kugeloberfläche als Grundraum; nach Voraussetzung ist der schwarze Anteil eine Borelmenge!) folgt aber, dass

$$1 – P\left(\bigcup\limits^{8}_{i=1}S_k\right) \geq 1 – \sum\limits^{8}_{i=1}P\left(S_k\right) = \frac{4}{100} > 0$$

Womit wir, den Hinweis auf Erdös nutzend, das zu Zeigende gezeigt haben. Diese Beweistechnik muss ich mir auf jeden Fall merken.
Der Beweis klappt nun leider für 13% Schwarzfärbung so nicht mehr. Das kommt dann vermutlich auf dem nächsten Übungsblatt. Oder in der Prüfung.

Schönes Statement auch in der entsprechenden Vorlesung, sinngemäß:

“Der Beweis modulo gewisser Formalitäten liefert immerhin noch eine anschauliche Heuristik, die hier genügen soll.”

Warum nur reagieren Dozenten immer so gepresst, wenn man in der Klausur so argumentieren möchte?

Parser für domänenspezifische Sprachen mit ANTLR

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)

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

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.