blob: 9b8949a6d47a473221814002046879eb1a445c9a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
|
\section*{Zusammenfassung}
Parser, die bekannte Texte nach einer kleinen Änderung neu analysieren können, ohne die ganze Eingabe erneut zu betrachten, nennt man inkrementell.
Inkrementelle Parser sind seit den 1970er-Jahren bekannt und inzwischen umfangreich erforscht.
Edit-lenses sind eine vergleichsweise neue algebraische Darstellung von Programmen, die algebraisch strukturierte Änderungen zwischen Strukturen übersetzen.
Wir demonstrieren, dass sich Inkrementelle Parser in der Sprache von edit-lenses fassen lassen, anhand einer besonders einfachen Klasse von Parsern, den deterministic finite state transducers.
Hierzu speichern wir im unterliegenden Zustand der assoziierten edit-lens die Ausgabe-Wirkung des DFST als balancierten Binärbaum um Teile davon effizient austauschen zu können.
Im Rahmen dessen stellen wir eine Implementierung von edit-lenses im Allgemeinen und unserem Verfahren in möglichst idiomatischem Haskell vor.
|
