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 --- .gitignore | 3 ++- literature.md | 43 +++++++++++++++++++++++++++-------- literature.meta.yml.gup | 4 ---- literature/incremental-parsing.bibtex | 2 +- 4 files changed, 36 insertions(+), 16 deletions(-) diff --git a/.gitignore b/.gitignore index bb009ce..670b81f 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,3 @@ literature.pdf -literature.meta.yml \ No newline at end of file +literature.meta.yml +**/.gup 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 diff --git a/literature.meta.yml.gup b/literature.meta.yml.gup index dc8e95d..a4c0d42 100644 --- a/literature.meta.yml.gup +++ b/literature.meta.yml.gup @@ -14,11 +14,7 @@ printf "bibliography:\n" typeset -a bibFiles bibFiles=(literature/**.bibtex) -# sha256sum ${bibFiles} >&2 - gup --contents <<<"${bibFiles}" -gup -u ${bibFiles} - for bibFile (${bibFiles}); do printf " - %s\n" ${bibFile} done diff --git a/literature/incremental-parsing.bibtex b/literature/incremental-parsing.bibtex index 96ec6c4..e3e5758 100644 --- a/literature/incremental-parsing.bibtex +++ b/literature/incremental-parsing.bibtex @@ -1,4 +1,4 @@ -@article{Ghezzi:1979:IP:357062.357066, +@article{ghezzi1979incremental, author = {Ghezzi, Carlo and Mandrioli, Dino}, title = {Incremental Parsing}, journal = {ACM Trans. Program. Lang. Syst.}, -- cgit v1.2.3