From acaa6097127fa23e1a61a40b38a14a39af5c22b1 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 24 Oct 2017 15:32:28 +0200 Subject: Bachelor's thesis; look up literature --- all.gup | 3 + literature.md | 81 ++++++++++++++++++++++ literature.meta.yml.gup | 26 +++++++ literature/a-programmable-editor.bibtex | 8 +++ .../bidirectional-tree-transformations.bibtex | 10 +++ literature/bidirectional-tree-transformations.pdf | 1 + literature/boomerang.bibtex | 10 +++ literature/combinator-parsers.bibtex | 10 +++ literature/combinator-parsers.pdf | 1 + literature/delta-lenses-and-opfibrations.bibtex | 7 ++ literature/delta-lenses-and-opfibrations.pdf | 1 + literature/dylus.pdf | 1 - .../edit-languages-for-information-trees.bibtex | 7 ++ .../edit-languages-for-information-trees.pdf | 1 + literature/edit-lenses.bibtex | 10 +++ ...ficient-and-flexible-incremental-parsing.bibtex | 10 +++ .../efficient-and-flexible-incremental-parsing.pdf | 1 + literature/incremental-parsing.bibtex | 18 +++++ literature/incremental-parsing.pdf | 1 + .../lazy-functional-incremental-parsing.bibtex | 8 +++ .../lenses-and-bidirectional-programming.bibtex | 4 ++ .../lenses-and-bidirectional-programming.pdf | 1 + literature/p224-swierstra.pdf | 1 - literature/parsing-in-a-broad-sense.bibtex | 8 +++ literature/polish-parsers.bibtex | 10 +++ literature/polish-parsers.pdf | 1 + literature/symmetric-lenses.bibtex | 10 +++ literature/symmetric-lenses.pdf | 1 + .../universal-updates-for-symmetric-lenses.bibtex | 4 ++ .../universal-updates-for-symmetric-lenses.pdf | 1 + 30 files changed, 254 insertions(+), 2 deletions(-) create mode 100644 all.gup create mode 100644 literature.md create mode 100644 literature.meta.yml.gup create mode 100644 literature/a-programmable-editor.bibtex create mode 100644 literature/bidirectional-tree-transformations.bibtex create mode 120000 literature/bidirectional-tree-transformations.pdf create mode 100644 literature/boomerang.bibtex create mode 100644 literature/combinator-parsers.bibtex create mode 120000 literature/combinator-parsers.pdf create mode 100644 literature/delta-lenses-and-opfibrations.bibtex create mode 120000 literature/delta-lenses-and-opfibrations.pdf delete mode 120000 literature/dylus.pdf create mode 100644 literature/edit-languages-for-information-trees.bibtex create mode 120000 literature/edit-languages-for-information-trees.pdf create mode 100644 literature/edit-lenses.bibtex create mode 100644 literature/efficient-and-flexible-incremental-parsing.bibtex create mode 120000 literature/efficient-and-flexible-incremental-parsing.pdf create mode 100644 literature/incremental-parsing.bibtex create mode 120000 literature/incremental-parsing.pdf create mode 100644 literature/lazy-functional-incremental-parsing.bibtex create mode 100644 literature/lenses-and-bidirectional-programming.bibtex create mode 120000 literature/lenses-and-bidirectional-programming.pdf delete mode 120000 literature/p224-swierstra.pdf create mode 100644 literature/parsing-in-a-broad-sense.bibtex create mode 100644 literature/polish-parsers.bibtex create mode 120000 literature/polish-parsers.pdf create mode 100644 literature/symmetric-lenses.bibtex create mode 120000 literature/symmetric-lenses.pdf create mode 100644 literature/universal-updates-for-symmetric-lenses.bibtex create mode 120000 literature/universal-updates-for-symmetric-lenses.pdf 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/dylus.pdf b/literature/dylus.pdf deleted file mode 120000 index 3418031..0000000 --- a/literature/dylus.pdf +++ /dev/null @@ -1 +0,0 @@ -../../.git/annex/objects/gG/1v/SHA256E-s1719789--38149c95efe58f903f8ca1e0d0e504143f0bf8fb878093586f2d5f606de819d3.pdf/SHA256E-s1719789--38149c95efe58f903f8ca1e0d0e504143f0bf8fb878093586f2d5f606de819d3.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/lenses-and-bidirectional-programming.pdf b/literature/lenses-and-bidirectional-programming.pdf new file mode 120000 index 0000000..3418031 --- /dev/null +++ b/literature/lenses-and-bidirectional-programming.pdf @@ -0,0 +1 @@ +../../.git/annex/objects/gG/1v/SHA256E-s1719789--38149c95efe58f903f8ca1e0d0e504143f0bf8fb878093586f2d5f606de819d3.pdf/SHA256E-s1719789--38149c95efe58f903f8ca1e0d0e504143f0bf8fb878093586f2d5f606de819d3.pdf \ No newline at end of file diff --git a/literature/p224-swierstra.pdf b/literature/p224-swierstra.pdf deleted file mode 120000 index 0ee4c6c..0000000 --- a/literature/p224-swierstra.pdf +++ /dev/null @@ -1 +0,0 @@ -../../.git/annex/objects/xf/fV/SHA256E-s144820--678e7de3d2c0024a5ce9b5053acc6d6bfca3db84ff7397b677fe5a8adb5e5d75.pdf/SHA256E-s144820--678e7de3d2c0024a5ce9b5053acc6d6bfca3db84ff7397b677fe5a8adb5e5d75.pdf \ No newline at end of file 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/polish-parsers.pdf b/literature/polish-parsers.pdf new file mode 120000 index 0000000..0ee4c6c --- /dev/null +++ b/literature/polish-parsers.pdf @@ -0,0 +1 @@ +../../.git/annex/objects/xf/fV/SHA256E-s144820--678e7de3d2c0024a5ce9b5053acc6d6bfca3db84ff7397b677fe5a8adb5e5d75.pdf/SHA256E-s144820--678e7de3d2c0024a5ce9b5053acc6d6bfca3db84ff7397b677fe5a8adb5e5d75.pdf \ No newline at end of file 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 -- cgit v1.2.3