blob: b0b8ae734273353dda319ad7c4f31753e51b529c (
plain)
1
2
3
4
5
6
7
8
9
|
Wir haben Definitionen von edit-lenses, finite-state-automata und manchen nützlichen algebraischen Operationen (Wort-DFST, Produkt von FSTs) darauf, sowohl menschenlesbar als auch in lauffähigem und idiomatischen Haskell gegeben.
Wir haben zudem ein Verfahren dargelegt, um aus einem gegebenen DFST einen inkrementellen Parser abzuleiten und diesen direkt als edit-lens konstruiert, um später Wiederverwendbarkeit zu gewährleisten.
Die gewünschte Laufzeitcharakteristik erreichen wir indem wir als Komplement einen balancierten Binärbaum von Transducer-Wirkungen speichern und, soweit möglich, nur Teilbäume davon betrachten müssen, um einen edit zu propagieren.
Zudem beschreiben wir ein interaktives Demonstrationsprogramm für das dargelegte Verfahren, das wir zusammen mit der Haskell-Implementierung ausliefern und geben einen groben Überblick über die bestehende Forschung in diesem Gebiet.
Unsere konkrete Implementierung hat, wie in Abschnitt \ref{performance} besprochen, Performance-Charakteristik, die sie für den tatsächlichen Einsatz untauglich macht.
Aufgrund der Struktur unserer Implementierung (siehe Abschnitt \ref{ausblick-anwendbarkeit-der-implementierung-auf-andere-parser}) lässt sich jedoch eine der unterliegenden Ideen, das Komplement der edit-lens als Binärbaum von Wirkungen darzustellen und durch effizientes Austauschen von Baumfragmenten die gewünschte Laufzeit-Charakteristik zu erreichen, in Zukunft recht einfach auf andere Parser anwenden.
Zusammenfassend haben wir eine neue und nicht-triviale Anwendung von edit-lenses vorgestellt.
|
