From b83a8e228725d9ab1b37805bf440cbbf97aea6c0 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 24 Oct 2017 21:31:06 +0200 Subject: Discuss Incremental Analysis of Real Programming Languages --- literature.md | 43 +++++++++++++++++++++++++++++++++---------- 1 file changed, 33 insertions(+), 10 deletions(-) (limited to 'literature.md') 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 -- cgit v1.2.3