Tag Archives: Computer Science - Page 2

N. Misra on Polynomial Kernelization

Neeldhara Misra, PhD student from IMSc (Chennai, India), recently visited our department at Chalmers. I had the opportunity to attend her well-given talk about the occasional infeasibility of polynomial kernelization. I liked the ideas she presented so I want to share them; you can read her own summary and download her complete work on her website.

Idea of Kernelization

Kernelization is about formalising preprocessing for hard problems and figuring out what can and cannot be achieved. In particular, NP-complete problems are studied; for these problems no fast (i.e. with polynomial bound on runtime) algorithms have been found yet. The idea is to crunch down a given instance of size to a size that is manageable by — more or less — naive algorithms while preserving equivalence, that is the reduced instance should have a solution if and only if the original instance has one. The notion of manageability is captured by a problem and instance dependent parameter ; we say that we have a polynomial kernel if there is an equivalent problem whose size is bounded by a polynomial in (i.e. independent of ). If is small — which is often the case in practical scenarios — the kernel can be solved reasonably quickly. Of course, the reduction process should then also be fast. Remains to mention that has to be chosen wisely; only knowing at least an upper bound for enables useful kernelizations. Read more »

Erhabene Informatik

Wir reden oft über das Bild der Informatik, das viele Menschen haben oder besser nicht haben. Wir können nicht genau bestimmen, woher die vielen Missverständnisse rühren oder wie man sie ausräumen kann. In der Dezemberausgabe 2009 des Informatik Spektrum adressiert Gunter Dueck in seiner Kolumne Das Erhabene, die Sterne und die Informatik ähnliche Fragen im Kontext der Astronomie:

Das muss das Erhabene des Weltalls sein, das mich auch oft erfasst. Und natürlich blitzt sofort die Assoziation zu Immanuel Kant auf, der alles in erhabene Worte fasste:
“Zwei Dinge erfüllen das Gemüt mit immer neuer und zunehmender Bewunderung und Ehrfurcht, je älter und anhaltender sich das Nachdenken damit beschäftigt: der gestirnte Himmel über mir und das moralische Gesetz in mir.”
Bei Informatik ist das irgendwie anders, oder? Und in der Mathematik auch. Dort ist nie dieser heilige Schauer zu spüren, wohl aber immer wieder das Gefühl überirdischer Schönheit – für die man allerdings oft einen speziellen Sinn braucht. Welchen Sinn “befriedigt” Informatik? Hat sie je darüber nachgedacht?

Wer in den Himmel sieht, fängt an zu träumen.

Er schreibt noch über die Erhabenheit der Astronomie, die Schönheit der Mathematik und stellt die Frage, warum es keine positive Belegung der Informatik gibt. Gerade im Kontext des Hefts, wo es um Informatik als Hilfswissenschaft für Astronomen und Astrophysiker geht, ist diese Frage überaus angebracht. Mir sagte ein Astrophysiker mal: “Informatik brauchen wir nicht, programmieren können wir selber!” Ich konnte ihm nicht klarmachen, wie widersprüchlich seine Aussage ist. Read more »

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!

Turingmaschine aus Lego

Gerade wurde mir ein Video zugesteckt, das in einer doch amüsant aufgemachten Weise ein Projekt an der Aarhus University vorstellt:

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.