LALR-Parsergeneratoren wie der/das nach Haskell kompilierende happy generieren üblicherweise tabellenbasierte Parser.

Bei SLL-Grammatiken verzichtet man hingegen häufig auf Parsergeneratoren (die tabellenbasierte Parser generieren) und programmiert die Grammatik als Rekursive Abstiegsparser aus. Ähnlich wie bei kompiliert vs. interpretiert ergibt sich operational ein Geschwindigkeitsvorteil bei erhöhter Code-Größe. Außerdem muss keine generatorspezifische eDSL für die Beschreibung der Grammatik erlernt werden, denn die Grammatik ist klar aus der Struktur des Parsers ableitbar.

Das Analog zu ausprogrammiertem Rekursivem Abstieg für LALR ist Rekursiver Aufstieg ("recursive ascent", ursprüngliches Paper von 1986, bessere Einführung). Im Gegensatz zu Rekursivem Abstieg ist eine solche Implementierung aber schwer von Hand editierbar. Auch die Vielzahl an Zuständen und die resultierende Code-Größe erwiesen sich als problematisch.

Mit Rekursivem Aufstieg-Abstieg (recursive ascent-descent, ursprüngliches Paper von 2005) konnte die Anzahl an Zuständen reduziert werden, indem ab dem Punkt, an dem die zu parsende Produktion feststeht (recognition point), auf Rekursiven Abstieg gewechselt wird. Ab diesem Punkt können dann auch semantische Aktionen eingefügt werden.

Das Problem der fehlenden Wartbarkeit von Hand war damit noch nicht gelöst; das schaffte aber ScalaBison (2010), indem sie den Parser aus den Zuständen eines üblichen LALR-Parsergenerators heraus generierten.

Parallel gab es in der Welt der funktionalen Programmierung Anstrengungen, ein Verfahren zur Generierung eines typsicheren, ausprogrammierten LR Parsers direkt aus Eigenschaften von LR-Grammatiken abzuleiten: Derivation of a Typed Functional LR Parser (2005). Continuation-passing style verhilft hier zu einem typsicheren Rekursivem Aufstiegsparser.

Aufgabe:

In dieser Arbeit soll happy um ein Backend erweitert werden, das einen Rekursiven Aufstiegs-Abstiegsparser generiert. Der generierte Parser soll

• typsicher im Sinne von Typed LR sein
• Nutzen aus happy's bestehenden Algorithmen zur Vereinfachung der Parserzustände schlagen
• In der Lage dazu sein, im GHC benutzt zu werden
• Optional: Besser durch den GHC optimierbar sein als der tabellenbasierte Parser
• Optional: Vergleichbare Code-Größe aufweisen

Die letzten beiden Punkte sind wünschenswert, erfordern aber Performance-Tuning, das aus dem Rahmen dieser Arbeit fällt.

Voraussetzungen

Gute Haskell-Kenntnisse

Schlüsselworte

Haskell, Parsergenerator 

Veröffentlichungen

Veröffentlichung

A Typed Recursive Ascent-Descent Backend for Happy

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Graf

Studenten

Ehemalige Hiwis
David Knothe