blob: eb633aaf4b839fa695cac1d727e32fcdb0677b2c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch
in einer Implementierung in Haskell als edit-lenses (alá @hofmann2012edit)
auffassen.
Unter einem inkrementellen Parser verstehen wir (analog zu
@ghezzi1979incremental) ein Programm, das, nach einem initialen Parsevorgang,
gegeben eine Spezifikation einer Änderung der textuellen Eingabe schneller ein
neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre
(gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe).
Für die Darstellung als edit-lens erweitern wir diese Definition und fordern,
dass statt einem neuen Ergebnis eine Spezifikation einer Änderung am Ergebnis
erzeugt werden soll (das Anwenden dieser Änderung auf ein altes Ergebnis sollte
die Laufzeit nicht verschlechtern).
Unsere Implementierung soll inkrementelle Parser für reguläre- und
$LL(1)$-Sprachen sowie für Fragmente von Java und XML bereitstellen.
|
