Discuss Incremental Analysis of Real Programming Languages

1 files changed, 33 insertions, 10 deletions

diff --git a/literature.md b/literature.md
index 9e4f27e..6b18905 100644
--- a/literature.md
+++ b/literature.md
@@ -1,22 +1,45 @@
 # Thema
 
 Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch
-in einer Implementierung in Haskell als edit-lenses auffassen.
+in einer Implementierung in Haskell als edit-lenses (alá @hofmann2012edit)
+auffassen.
 
-Diese Implementierung soll inkrementelle Parser für reguläre- und
+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.
 
 # Bekannte Ergebnisse
 
-$LL(1)$-Parser
-  ~ @wagner1998efficient haben bereits einen inkrementellen $LL(1)$-Parser mit dem
+Parser für kontextfreie Grammatiken
+  ~ @wagner1998efficient haben 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.
-
+    
+    Für allgemeine kontextfreie Grammatiken haben @wagner1997incremental eine
+    Herangehensweise entwicklet, die Mehrdeutigkeiten direkt im Ergebnis
+    kodiert.
+    Hierbei wird das gewünschte Laufzeitverhalten in den meisten
+    Anwendungsfällen (z.B. C und C++) erreicht (das worst-case Verhalten ist
+    natürlich exponentiell).
+    
+    Wir betrachten auch Beispiele die zwar nicht $LL(1)$ sind jedoch trotzdem
+    eindeutig geparst werden können (z.B. valides XML) und planen nicht
+    nondeterminismus im Parse-Vorgang zu erlauben.
+    Durch die Darstellung unserer Parser planen wir Änderungen in der Eingabe in
+    Änderungen in der Ausgabe zu übersetzen, statt, wie in den referenzierten
+    Arbeiten, in eine bereits neu konstruierte Ausgabe.
+    Zudem planen wir unsere Beispiele möglichst deklarativ (in idiomatischem
+    Haskell) statt imperativ (die referenzierten Arbeiten 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