Bachelor's thesis; look up literature

28 files changed, 252 insertions, 0 deletions

diff --git a/all.gup b/all.gup
new file mode 100644
index 0000000..ad40ad4
--- /dev/null
+++ b/all.gup
@@ -0,0 +1,3 @@
+#!/usr/bin/env sh
+
+gup -u literature.pdf
diff --git a/literature.md b/literature.md
new file mode 100644
index 0000000..9e4f27e
--- /dev/null
+++ b/literature.md
@@ -0,0 +1,81 @@
+# Thema
+
+Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch
+in einer Implementierung in Haskell als edit-lenses auffassen.
+
+Diese 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
+    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.
+
+Applikative parser mit lazy evaluation
+  ~ @bernardy2009lazy beschreibt eine Implementierung applikativer Parser (alá
+    @swierstra2001combinator) die noch während dem parse-Vorgang Resultate
+    produziert (der Parser ist _online_) und über einen Mechanismus verfügt
+    partielle Resultate für den Lauf des Parsers auf einem Präfix der Eingabe zu
+    memoisieren.
+    Unter der Verwendung von lazy evaluation lassen sich damit unsere Anforderungen
+    an inkrementelle Parser realisieren.
+
+    Abgrenzen lassen sich die von uns verfolgten Ziele von den Ergebnissen aus
+    [-@bernardy2009lazy] vor allem durch die Darstellung als edit-lenses und
+    dass wir Parser für eine weitere Auswahl von Grammatiken konkret
+    implementieren möchten.
+    
+# Verwandte Themen
+
+Parser als Linsen
+  ~ @zaytsev2014parsing stellen eine Taxonomie von Darstellungen (als String,
+    Liste von Tokens (wmgl. getypt), Parse-Baum (wmgl. mit Vieldeutigkeiten), …)
+    vor und charakterisieren Prozesse die zwischen Darstellungen konvertieren
+    (insbesondere Parser als funktionale Linsen).
+
+    @hofmann2012edit erweitern das gewöhnliche Bild von funktionalen Linsen um
+    solche, die direkt auf Differenzen von Strukturen agieren.
+
+    Die beiden Ergebnisse lassen sich insofern kombinieren, dass inkrementelle
+    Parser als edit lenses aufgefasst werden, was mitunter Ziel der Arbeit sein
+    soll (@zaytsev2014parsing schlagen diese Anwendung in ihrer Arbeit vor).
+
+Edit languages
+  ~ @hofmann2013edit spezifizieren eine Sprache zur Beschreibung von
+    edit-Operationen auf _information-trees_.
+    
+    Es ist naheliegend geparste XML-Dokumente als information-tree aufzufassen
+    und Veränderungen in der serialisierten Darstellung des Dokuments vermöge
+    unserer XML-Parser edit-lens auf edit-Operationen aus [-@hofmann2013edit]
+    abzubilden.
+    
+Bidirectional tree- & string transformations
+  ~ @foster2007combinators spezifizieren eine Sprache für bidirektionale
+    Baum-Transformationen als funktionale Linsen und deren Kompositionen.
+    
+    Sollte sich im Laufe der Implementierung herausstellen, dass eine
+    Repräsentierung der edit-Operationen auf XML als Linsen zusätzliche
+    Uniformität hervorbringt, so ist es zweckmäßig von der Beschreibung alá
+    @hofmann2013edit auf bidirektionale Baum-Transformationen umzusteigen.
+    
+    Es ist abzusehen, dass, falls eine Beschreibung der edit-Operationen auf
+    Bäume nützlich ist, sie es auch auf Strings sein wird. In diesem Fall bieten
+    sich die Methoden von @bohannon2008boomerang an.
+    
+Symmetrische Linsen
+  ~ Unparsing (pretty-printing) soll nicht im Umfang der Arbeit sein.
+  
+Polish Parsers & Parser-Kombinatoren
+  ~ Es ist nicht auszuschließen, dass wir unsere Beispiel-Parser vermöge einer
+    eigenen Implementierung von Parser-Kombinatoren (alá
+    @swierstra2001combinator) konstruieren.
+
+    Falls sich eine Implementierung von Parser-Kombinatoren anbietet gibt es
+    keinen offensichtlichen Grund warum sich die Konstruktion aus
+    [-@hughes2003polish] nicht anwenden lassen sollte.
diff --git a/literature.meta.yml.gup b/literature.meta.yml.gup
new file mode 100644
index 0000000..dc8e95d
--- /dev/null
+++ b/literature.meta.yml.gup
@@ -0,0 +1,26 @@
+#!/usr/bin/env zsh
+
+exec 1>$1
+
+echo '---'
+
+cat <<-EOF
+        lang: de-de
+        link-citations: true
+        EOF
+
+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
+
+echo '...'
diff --git a/literature/a-programmable-editor.bibtex b/literature/a-programmable-editor.bibtex
new file mode 100644
index 0000000..e0649ca
--- /dev/null
+++ b/literature/a-programmable-editor.bibtex
@@ -0,0 +1,8 @@
+@inproceedings{hu2004programmable,
+  title={A programmable editor for developing structured documents based on bidirectional transformations},
+  author={Hu, Zhenjiang and Mu, Shin-Cheng and Takeichi, Masato},
+  booktitle={Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation},
+  pages={178--189},
+  year={2004},
+  organization={ACM}
+}
diff --git a/literature/bidirectional-tree-transformations.bibtex b/literature/bidirectional-tree-transformations.bibtex
new file mode 100644
index 0000000..1d75f45
--- /dev/null
+++ b/literature/bidirectional-tree-transformations.bibtex
@@ -0,0 +1,10 @@
+@article{foster2007combinators,
+  title={Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem},
+  author={Foster, J Nathan and Greenwald, Michael B and Moore, Jonathan T and Pierce, Benjamin C and Schmitt, Alan},
+  journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
+  volume={29},
+  number={3},
+  pages={17},
+  year={2007},
+  publisher={ACM}
+}
diff --git a/literature/bidirectional-tree-transformations.pdf b/literature/bidirectional-tree-transformations.pdf
new file mode 120000
index 0000000..d541644
--- /dev/null
+++ b/literature/bidirectional-tree-transformations.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/3q/Q4/SHA256E-s2005957--10cd19a1094b457df9d486cc90d410fed0d89de9c53a20925e38957cc6dcb611.pdf/SHA256E-s2005957--10cd19a1094b457df9d486cc90d410fed0d89de9c53a20925e38957cc6dcb611.pdf
\ No newline at end of file
diff --git a/literature/boomerang.bibtex b/literature/boomerang.bibtex
new file mode 100644
index 0000000..4699c15
--- /dev/null
+++ b/literature/boomerang.bibtex
@@ -0,0 +1,10 @@
+@inproceedings{bohannon2008boomerang,
+  title={Boomerang: resourceful lenses for string data},
+  author={Bohannon, Aaron and Foster, J Nathan and Pierce, Benjamin C and Pilkiewicz, Alexandre and Schmitt, Alan},
+  booktitle={ACM SIGPLAN Notices},
+  volume={43},
+  number={1},
+  pages={407--419},
+  year={2008},
+  organization={ACM}
+}
diff --git a/literature/combinator-parsers.bibtex b/literature/combinator-parsers.bibtex
new file mode 100644
index 0000000..215218a
--- /dev/null
+++ b/literature/combinator-parsers.bibtex
@@ -0,0 +1,10 @@
+@article{swierstra2001combinator,
+  title={Combinator parsers: From toys to tools},
+  author={Swierstra, S Doaitse},
+  journal={Electronic Notes in Theoretical Computer Science},
+  volume={41},
+  number={1},
+  pages={38--59},
+  year={2001},
+  publisher={Elsevier}
+}
diff --git a/literature/combinator-parsers.pdf b/literature/combinator-parsers.pdf
new file mode 120000
index 0000000..188b004
--- /dev/null
+++ b/literature/combinator-parsers.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/G5/8f/SHA256E-s209412--683422aea849a1620f405bd53b3a853d015b600e4cd07c20dd7172d6d976a9ab.pdf/SHA256E-s209412--683422aea849a1620f405bd53b3a853d015b600e4cd07c20dd7172d6d976a9ab.pdf
\ No newline at end of file
diff --git a/literature/delta-lenses-and-opfibrations.bibtex b/literature/delta-lenses-and-opfibrations.bibtex
new file mode 100644
index 0000000..75f6c6e
--- /dev/null
+++ b/literature/delta-lenses-and-opfibrations.bibtex
@@ -0,0 +1,7 @@
+@article{johnson2013delta,
+  title={Delta lenses and opfibrations},
+  author={Johnson, Michael and Rosebrugh, Robert},
+  journal={Electronic Communications of the EASST},
+  volume={57},
+  year={2013}
+}
diff --git a/literature/delta-lenses-and-opfibrations.pdf b/literature/delta-lenses-and-opfibrations.pdf
new file mode 120000
index 0000000..91b80ba
--- /dev/null
+++ b/literature/delta-lenses-and-opfibrations.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/65/k5/SHA256E-s219945--e885ea109010acbca66336a48077e8b0c37424eca1629d025bdb2839a1a4fa89.pdf/SHA256E-s219945--e885ea109010acbca66336a48077e8b0c37424eca1629d025bdb2839a1a4fa89.pdf
\ No newline at end of file
diff --git a/literature/edit-languages-for-information-trees.bibtex b/literature/edit-languages-for-information-trees.bibtex
new file mode 100644
index 0000000..b7feb3d
--- /dev/null
+++ b/literature/edit-languages-for-information-trees.bibtex
@@ -0,0 +1,7 @@
+@article{hofmann2013edit,
+  title={Edit languages for information trees},
+  author={Hofmann, Martin and Pierce, Benjamin and Wagner, Daniel},
+  journal={Electronic Communications of the EASST},
+  volume={57},
+  year={2013}
+}
diff --git a/literature/edit-languages-for-information-trees.pdf b/literature/edit-languages-for-information-trees.pdf
new file mode 120000
index 0000000..c986c6f
--- /dev/null
+++ b/literature/edit-languages-for-information-trees.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/xx/4w/SHA256E-s244187--e868ab15cd182552ccabf44118f98f746285d564f571961a1e74ad6e1dadc773.pdf/SHA256E-s244187--e868ab15cd182552ccabf44118f98f746285d564f571961a1e74ad6e1dadc773.pdf
\ No newline at end of file
diff --git a/literature/edit-lenses.bibtex b/literature/edit-lenses.bibtex
new file mode 100644
index 0000000..13ca5bf
--- /dev/null
+++ b/literature/edit-lenses.bibtex
@@ -0,0 +1,10 @@
+@inproceedings{hofmann2012edit,
+  title={Edit lenses},
+  author={Hofmann, Martin and Pierce, Benjamin and Wagner, Daniel},
+  booktitle={ACM SIGPLAN Notices},
+  volume={47},
+  number={1},
+  pages={495--508},
+  year={2012},
+  organization={ACM}
+}
diff --git a/literature/efficient-and-flexible-incremental-parsing.bibtex b/literature/efficient-and-flexible-incremental-parsing.bibtex
new file mode 100644
index 0000000..41e9ab4
--- /dev/null
+++ b/literature/efficient-and-flexible-incremental-parsing.bibtex
@@ -0,0 +1,10 @@
+@article{wagner1998efficient,
+  title={Efficient and flexible incremental parsing},
+  author={Wagner, Tim A and Graham, Susan L},
+  journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
+  volume={20},
+  number={5},
+  pages={980--1013},
+  year={1998},
+  publisher={ACM}
+}
diff --git a/literature/efficient-and-flexible-incremental-parsing.pdf b/literature/efficient-and-flexible-incremental-parsing.pdf
new file mode 120000
index 0000000..728b64f
--- /dev/null
+++ b/literature/efficient-and-flexible-incremental-parsing.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/8X/GX/SHA256E-s143343--a090c1362970814e718010e4164d894a30a230fd7bb2604ed1fb6c86f0cf09ee.pdf/SHA256E-s143343--a090c1362970814e718010e4164d894a30a230fd7bb2604ed1fb6c86f0cf09ee.pdf
\ No newline at end of file
diff --git a/literature/incremental-parsing.bibtex b/literature/incremental-parsing.bibtex
new file mode 100644
index 0000000..96ec6c4
--- /dev/null
+++ b/literature/incremental-parsing.bibtex
@@ -0,0 +1,18 @@
+@article{Ghezzi:1979:IP:357062.357066,
+ author = {Ghezzi, Carlo and Mandrioli, Dino},
+ title = {Incremental Parsing},
+ journal = {ACM Trans. Program. Lang. Syst.},
+ issue_date = {July 1979},
+ volume = {1},
+ number = {1},
+ month = jan,
+ year = {1979},
+ issn = {0164-0925},
+ pages = {58--70},
+ numpages = {13},
+ url = {http://doi.acm.org/10.1145/357062.357066},
+ doi = {10.1145/357062.357066},
+ acmid = {357066},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
\ No newline at end of file
diff --git a/literature/incremental-parsing.pdf b/literature/incremental-parsing.pdf
new file mode 120000
index 0000000..3d34726
--- /dev/null
+++ b/literature/incremental-parsing.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/2z/KX/SHA256E-s679194--ddd3575d5c0bf3a34759d9e188cec285541cea52fc89ef4612b0cb3a63acf304.pdf/SHA256E-s679194--ddd3575d5c0bf3a34759d9e188cec285541cea52fc89ef4612b0cb3a63acf304.pdf
\ No newline at end of file
diff --git a/literature/lazy-functional-incremental-parsing.bibtex b/literature/lazy-functional-incremental-parsing.bibtex
new file mode 100644
index 0000000..3c82f51
--- /dev/null
+++ b/literature/lazy-functional-incremental-parsing.bibtex
@@ -0,0 +1,8 @@
+@inproceedings{bernardy2009lazy,
+  title={Lazy functional incremental parsing},
+  author={Bernardy, Jean-Philippe},
+  booktitle={Proceedings of the 2nd ACM SIGPLAN symposium on Haskell},
+  pages={49--60},
+  year={2009},
+  organization={ACM}
+}
diff --git a/literature/lenses-and-bidirectional-programming.bibtex b/literature/lenses-and-bidirectional-programming.bibtex
new file mode 100644
index 0000000..47bac9e
--- /dev/null
+++ b/literature/lenses-and-bidirectional-programming.bibtex
@@ -0,0 +1,4 @@
+@masterthesis{dyluslenses,
+  title={Lenses and Bidirectional Programming in Curry},
+  author={Dylus, Sandra and Hanus, Michael}
+}
diff --git a/literature/dylus.pdf b/literature/lenses-and-bidirectional-programming.pdf
index 3418031..3418031 120000
--- a/literature/dylus.pdf
+++ b/literature/lenses-and-bidirectional-programming.pdf
diff --git a/literature/parsing-in-a-broad-sense.bibtex b/literature/parsing-in-a-broad-sense.bibtex
new file mode 100644
index 0000000..56b0369
--- /dev/null
+++ b/literature/parsing-in-a-broad-sense.bibtex
@@ -0,0 +1,8 @@
+@inproceedings{zaytsev2014parsing,
+  title={Parsing in a broad sense},
+  author={Zaytsev, Vadim and Bagge, Anya Helene},
+  booktitle={International Conference on Model Driven Engineering Languages and Systems},
+  pages={50--67},
+  year={2014},
+  organization={Springer}
+}
diff --git a/literature/polish-parsers.bibtex b/literature/polish-parsers.bibtex
new file mode 100644
index 0000000..ecd6ea2
--- /dev/null
+++ b/literature/polish-parsers.bibtex
@@ -0,0 +1,10 @@
+@article{hughes2003polish,
+  title={Polish parsers, step by step},
+  author={Hughes, R John M and Swierstra, S Doaitse},
+  journal={ACM SIGPLAN Notices},
+  volume={38},
+  number={9},
+  pages={239--248},
+  year={2003},
+  publisher={ACM}
+}
diff --git a/literature/p224-swierstra.pdf b/literature/polish-parsers.pdf
index 0ee4c6c..0ee4c6c 120000
--- a/literature/p224-swierstra.pdf
+++ b/literature/polish-parsers.pdf
diff --git a/literature/symmetric-lenses.bibtex b/literature/symmetric-lenses.bibtex
new file mode 100644
index 0000000..8ac01e0
--- /dev/null
+++ b/literature/symmetric-lenses.bibtex
@@ -0,0 +1,10 @@
+@inproceedings{hofmann2011symmetric,
+  title={Symmetric lenses},
+  author={Hofmann, Martin and Pierce, Benjamin and Wagner, Daniel},
+  booktitle={ACM SIGPLAN Notices},
+  volume={46},
+  number={1},
+  pages={371--384},
+  year={2011},
+  organization={ACM}
+}
diff --git a/literature/symmetric-lenses.pdf b/literature/symmetric-lenses.pdf
new file mode 120000
index 0000000..9ee4ecb
--- /dev/null
+++ b/literature/symmetric-lenses.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/p6/JQ/SHA256E-s461824--bd917931388a6789b23954f030693db7383988c589ff32f94f429eb787ca09f2.pdf/SHA256E-s461824--bd917931388a6789b23954f030693db7383988c589ff32f94f429eb787ca09f2.pdf
\ No newline at end of file
diff --git a/literature/universal-updates-for-symmetric-lenses.bibtex b/literature/universal-updates-for-symmetric-lenses.bibtex
new file mode 100644
index 0000000..d525546
--- /dev/null
+++ b/literature/universal-updates-for-symmetric-lenses.bibtex
@@ -0,0 +1,4 @@
+@article{johnsonuniversal,
+  title={Universal Updates for Symmetric Lenses},
+  author={Johnson, Michael and Rosebrugh, Robert}
+}
diff --git a/literature/universal-updates-for-symmetric-lenses.pdf b/literature/universal-updates-for-symmetric-lenses.pdf
new file mode 120000
index 0000000..02ca7ce
--- /dev/null
+++ b/literature/universal-updates-for-symmetric-lenses.pdf
@@ -0,0 +1 @@
+../../.git/annex/objects/gj/gW/SHA256E-s347098--7172db6b2de519753231d4c68920905bb3d3dd53ee5cf3895fd1db8dba30291f.pdf/SHA256E-s347098--7172db6b2de519753231d4c68920905bb3d3dd53ee5cf3895fd1db8dba30291f.pdf
\ No newline at end of file