Programm Easterhegg 2017

Eine der häufigsten Herausforderungen für Programmier*innen ist Parsen. Reguläre Ausdrücke ("regex") sind weit verbreitet, bringen aber oft mehr Probleme mit sich als sie lösen. Parsing Expression Grammars (PEGs) sind angetreten, diese Problem zu lösen, jedoch noch weitgehend unbekannt. Der Vortrag bietet eine Einführung in PEGs und erläutert u. a., wie man eine PEG als Programm darstellen kann, das auf einer speziellen virtuellen (Parsing-)Maschine laufen kann, wodurch sich ganz neue Möglichkeiten ergeben.

Eine Parsing Expression Grammar (PEG) beschreibt eine formale Sprache als Regeln, die Strings in einer Sprache erkennen können. Sie wurde 2004 von Brain Ford beschrieben, fristet allerdings ein Schattendasein. Sie eignen sich ideal für Sprachen, die vom Computer gelesen oder interpretiert werden müssen, wie z. B. Programmiersprachen oder künstliche humane Sprachen; was wohl die häufigste Art von Sprachen ist, für die Programmierer*innen Parser schreiben.

PEGs haben starke Ähnlichkeit mit anderen kontext-freien Grammatiken (CFG). Im Gegensatz zu z. B. Regulären Ausdrücken (RE, RegEx) haben sie jedoch einige Unterschiede. Der herausragendste ist ihre Ausführung: In einer PEG wird im Falle einer Verzweigung (Choice) immer zuerst der erste Weg verwendet; in CFGs ist die Ausführung mehrdeutig und oft nicht vorhersagbar. PEGs sind damit immer eindeutig, d. h. es gibt nur einen validen Parse Tree. Dies erlaubt es z. B., eine PEG als Programm für eine spezielle virtuelle (Parsing-)Maschine zu konvertieren. Außerdem lässt sich der Parse Tree optimieren; theoretisch sogar JIT in der VM auf Basis der Analyse der Eingabedaten.

Parsing ist eine häufige Aufgabe in der Programmierung. Auch wenn REs oft eingesetzt werden, taugen sie oft nur zur lexikalischen Analyse; die semantische Analyse muss von separatem Code übernommen werden. PEGs bieten als Grammatik die Möglichkeit vollständig zu parsen, also lexikalische und semantische Analyse direkt durchzuführen.

Der Vortrag hat zum Ziel, PEGs selbst vorzustellen und bekannter zu machen. Es wird auf die oben genannten Vorzüge intensiver eingegangen und eine Implementierung für die Java Virtual Machine (JVM) vorgestellt. Ich werde die Konzepte so allgemein und verständlich wie möglich vorzustellen; jedoch ist eine vorherige Beschäftigung mit dem Thema sicherlich hilfreich beim Verständnis.

Info

Tag: 14.04.2017
Anfang: 20:30 Uhr
Dauer: 01:00
Raum: Vortragssaal

Sprache: de

Links:

• iCalendar
• Parsing Expression Grammar on Wikipedia