diff options
Diffstat (limited to 'literature.md')
-rw-r--r-- | literature.md | 43 |
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 @@ | |||
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 |