1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
# Thema
Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch
in einer Implementierung in Haskell als edit-lenses auffassen.
Diese Implementierung soll inkrementelle Parser für reguläre- und
$LL(1)$-Sprachen sowie für Fragmente von Java und XML bereitstellen.
# Bekannte Ergebnisse
$LL(1)$-Parser
~ @wagner1998efficient haben bereits einen inkrementellen $LL(1)$-Parser mit dem
gewünschten Laufzeitverhalten vorgestellt.
Dies deckt unsere DEA- und Klammerungs-Beispiele ab, nicht jedoch z.B. XML.
Zudem planen wir unsere Beispiele möglichst deklarativ (z.B. in
idiomatischem Haskell) statt imperativ (@wagner1998efficient verwenden C++)
zu formulieren.
Applikative parser mit lazy evaluation
~ @bernardy2009lazy beschreibt eine Implementierung applikativer Parser (alá
@swierstra2001combinator) die noch während dem parse-Vorgang Resultate
produziert (der Parser ist _online_) und über einen Mechanismus verfügt
partielle Resultate für den Lauf des Parsers auf einem Präfix der Eingabe zu
memoisieren.
Unter der Verwendung von lazy evaluation lassen sich damit unsere Anforderungen
an inkrementelle Parser realisieren.
Abgrenzen lassen sich die von uns verfolgten Ziele von den Ergebnissen aus
[-@bernardy2009lazy] vor allem durch die Darstellung als edit-lenses und
dass wir Parser für eine weitere Auswahl von Grammatiken konkret
implementieren möchten.
# Verwandte Themen
Parser als Linsen
~ @zaytsev2014parsing stellen eine Taxonomie von Darstellungen (als String,
Liste von Tokens (wmgl. getypt), Parse-Baum (wmgl. mit Vieldeutigkeiten), …)
vor und charakterisieren Prozesse die zwischen Darstellungen konvertieren
(insbesondere Parser als funktionale Linsen).
@hofmann2012edit erweitern das gewöhnliche Bild von funktionalen Linsen um
solche, die direkt auf Differenzen von Strukturen agieren.
Die beiden Ergebnisse lassen sich insofern kombinieren, dass inkrementelle
Parser als edit lenses aufgefasst werden, was mitunter Ziel der Arbeit sein
soll (@zaytsev2014parsing schlagen diese Anwendung in ihrer Arbeit vor).
Edit languages
~ @hofmann2013edit spezifizieren eine Sprache zur Beschreibung von
edit-Operationen auf _information-trees_.
Es ist naheliegend geparste XML-Dokumente als information-tree aufzufassen
und Veränderungen in der serialisierten Darstellung des Dokuments vermöge
unserer XML-Parser edit-lens auf edit-Operationen aus [-@hofmann2013edit]
abzubilden.
Bidirectional tree- & string transformations
~ @foster2007combinators spezifizieren eine Sprache für bidirektionale
Baum-Transformationen als funktionale Linsen und deren Kompositionen.
Sollte sich im Laufe der Implementierung herausstellen, dass eine
Repräsentierung der edit-Operationen auf XML als Linsen zusätzliche
Uniformität hervorbringt, so ist es zweckmäßig von der Beschreibung alá
@hofmann2013edit auf bidirektionale Baum-Transformationen umzusteigen.
Es ist abzusehen, dass, falls eine Beschreibung der edit-Operationen auf
Bäume nützlich ist, sie es auch auf Strings sein wird. In diesem Fall bieten
sich die Methoden von @bohannon2008boomerang an.
Symmetrische Linsen
~ Unparsing (pretty-printing) soll nicht im Umfang der Arbeit sein.
Polish Parsers & Parser-Kombinatoren
~ Es ist nicht auszuschließen, dass wir unsere Beispiel-Parser vermöge einer
eigenen Implementierung von Parser-Kombinatoren (alá
@swierstra2001combinator) konstruieren.
Falls sich eine Implementierung von Parser-Kombinatoren anbietet gibt es
keinen offensichtlichen Grund warum sich die Konstruktion aus
[-@hughes2003polish] nicht anwenden lassen sollte.
|
