From acaa6097127fa23e1a61a40b38a14a39af5c22b1 Mon Sep 17 00:00:00 2001
From: Gregor Kleen <gkleen@yggdrasil.li>
Date: Tue, 24 Oct 2017 15:32:28 +0200
Subject: Bachelor's thesis; look up literature

---
 literature.md | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)
 create mode 100644 literature.md

(limited to 'literature.md')

diff --git a/literature.md b/literature.md
new file mode 100644
index 0000000..9e4f27e
--- /dev/null
+++ b/literature.md
@@ -0,0 +1,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.
-- 
cgit v1.2.3