diff options
-rw-r--r-- | .gitignore | 3 | ||||
-rw-r--r-- | literature.md | 43 | ||||
-rw-r--r-- | literature.meta.yml.gup | 4 | ||||
-rw-r--r-- | literature/incremental-parsing.bibtex | 2 |
4 files changed, 36 insertions, 16 deletions
@@ -1,2 +1,3 @@ | |||
1 | literature.pdf | 1 | literature.pdf |
2 | literature.meta.yml \ No newline at end of file | 2 | literature.meta.yml |
3 | **/.gup | ||
diff --git a/literature.md b/literature.md index 9e4f27e..6b18905 100644 --- a/literature.md +++ b/literature.md | |||
@@ -1,22 +1,45 @@ | |||
1 | # Thema | 1 | # Thema |
2 | 2 | ||
3 | Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch | 3 | Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch |
4 | in einer Implementierung in Haskell als edit-lenses auffassen. | 4 | in einer Implementierung in Haskell als edit-lenses (alá @hofmann2012edit) |
5 | auffassen. | ||
5 | 6 | ||
6 | Diese Implementierung soll inkrementelle Parser für reguläre- und | 7 | Unter einem inkrementellen Parser verstehen wir (analog zu |
8 | @ghezzi1979incremental) ein Programm, das, nach einem initialen Parsevorgang, | ||
9 | gegeben eine Spezifikation einer Änderung der textuellen Eingabe schneller ein | ||
10 | neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre | ||
11 | (gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe). | ||
12 | Für die Darstellung als edit-lens erweitern wir diese Definition und fordern, | ||
13 | dass statt einem neuen Ergebnis eine Spezifikation einer Änderung am Ergebnis | ||
14 | erzeugt werden soll (das Anwenden dieser Änderung auf ein altes Ergebnis sollte | ||
15 | die Laufzeit nicht verschlechtern). | ||
16 | |||
17 | Unsere Implementierung soll inkrementelle Parser für reguläre- und | ||
7 | $LL(1)$-Sprachen sowie für Fragmente von Java und XML bereitstellen. | 18 | $LL(1)$-Sprachen sowie für Fragmente von Java und XML bereitstellen. |
8 | 19 | ||
9 | # Bekannte Ergebnisse | 20 | # Bekannte Ergebnisse |
10 | 21 | ||
11 | $LL(1)$-Parser | 22 | Parser für kontextfreie Grammatiken |
12 | ~ @wagner1998efficient haben bereits einen inkrementellen $LL(1)$-Parser mit dem | 23 | ~ @wagner1998efficient haben einen inkrementellen $LL(1)$-Parser mit dem |
13 | gewünschten Laufzeitverhalten vorgestellt. | 24 | gewünschten Laufzeitverhalten vorgestellt. |
14 | 25 | ||
15 | Dies deckt unsere DEA- und Klammerungs-Beispiele ab, nicht jedoch z.B. XML. | 26 | Für allgemeine kontextfreie Grammatiken haben @wagner1997incremental eine |
16 | Zudem planen wir unsere Beispiele möglichst deklarativ (z.B. in | 27 | Herangehensweise entwicklet, die Mehrdeutigkeiten direkt im Ergebnis |
17 | idiomatischem Haskell) statt imperativ (@wagner1998efficient verwenden C++) | 28 | kodiert. |
18 | zu formulieren. | 29 | Hierbei wird das gewünschte Laufzeitverhalten in den meisten |
19 | 30 | Anwendungsfällen (z.B. C und C++) erreicht (das worst-case Verhalten ist | |
31 | natürlich exponentiell). | ||
32 | |||
33 | Wir betrachten auch Beispiele die zwar nicht $LL(1)$ sind jedoch trotzdem | ||
34 | eindeutig geparst werden können (z.B. valides XML) und planen nicht | ||
35 | nondeterminismus im Parse-Vorgang zu erlauben. | ||
36 | Durch die Darstellung unserer Parser planen wir Änderungen in der Eingabe in | ||
37 | Änderungen in der Ausgabe zu übersetzen, statt, wie in den referenzierten | ||
38 | Arbeiten, in eine bereits neu konstruierte Ausgabe. | ||
39 | Zudem planen wir unsere Beispiele möglichst deklarativ (in idiomatischem | ||
40 | Haskell) statt imperativ (die referenzierten Arbeiten verwenden C++) zu | ||
41 | formulieren. | ||
42 | |||
20 | Applikative parser mit lazy evaluation | 43 | Applikative parser mit lazy evaluation |
21 | ~ @bernardy2009lazy beschreibt eine Implementierung applikativer Parser (alá | 44 | ~ @bernardy2009lazy beschreibt eine Implementierung applikativer Parser (alá |
22 | @swierstra2001combinator) die noch während dem parse-Vorgang Resultate | 45 | @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" | |||
14 | typeset -a bibFiles | 14 | typeset -a bibFiles |
15 | bibFiles=(literature/**.bibtex) | 15 | bibFiles=(literature/**.bibtex) |
16 | 16 | ||
17 | # sha256sum ${bibFiles} >&2 | ||
18 | |||
19 | gup --contents <<<"${bibFiles}" | 17 | gup --contents <<<"${bibFiles}" |
20 | gup -u ${bibFiles} | ||
21 | |||
22 | for bibFile (${bibFiles}); do | 18 | for bibFile (${bibFiles}); do |
23 | printf " - %s\n" ${bibFile} | 19 | printf " - %s\n" ${bibFile} |
24 | done | 20 | 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 @@ | |||
1 | @article{Ghezzi:1979:IP:357062.357066, | 1 | @article{ghezzi1979incremental, |
2 | author = {Ghezzi, Carlo and Mandrioli, Dino}, | 2 | author = {Ghezzi, Carlo and Mandrioli, Dino}, |
3 | title = {Incremental Parsing}, | 3 | title = {Incremental Parsing}, |
4 | journal = {ACM Trans. Program. Lang. Syst.}, | 4 | journal = {ACM Trans. Program. Lang. Syst.}, |