--- a/ChengsongTanPhdThesis/example.bib Sat Nov 12 21:34:40 2022 +0000
+++ b/ChengsongTanPhdThesis/example.bib Thu Nov 17 23:13:57 2022 +0000
@@ -233,9 +233,93 @@
bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397509001789},
bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2009.02.022}}
+
+@incollection{Aho1990,
+title = {CHAPTER 5 - Algorithms for Finding Patterns in Strings},
+editor = {JAN {VAN LEEUWEN}},
+booktitle = {Algorithms and Complexity},
+publisher = {Elsevier},
+address = {Amsterdam},
+pages = {255-300},
+year = {1990},
+series = {Handbook of Theoretical Computer Science},
+isbn = {978-0-444-88071-0},
+doi = {https://doi.org/10.1016/B978-0-444-88071-0.50010-2},
+url = {https://www.sciencedirect.com/science/article/pii/B9780444880710500102},
+author = {A.V.~Aho},
+abstract = {Publisher Summary
+This chapter discusses the algorithms for solving string-matching problems that have proven useful for text-editing and text-processing applications. String pattern matching is an important problem that occurs in many areas of science and information processing. In computing, it occurs naturally as part of data processing, text editing, term rewriting, lexical analysis, and information retrieval. Many text editors and programming languages have facilities for matching strings. In biology, string-matching problems arise in the analysis of nucleic acids and protein sequences, and in the investigation of molecular phylogeny. String matching is also one of the central and most widely studied problems in theoretical computer science. The simplest form of the problem is to locate an occurrence of a keyword as a substring in a sequence of characters, which is called the input string. For example, the input string queueing contains the keyword ueuei as a substring. Even for this problem, several innovative, theoretically interesting algorithms have been devised that run significantly faster than the obvious brute-force method.}
+}
+
%% back-references--------------------
%% -------------------------------------
+
+
+%%----------------------------------------------------------------
+%%----------------------------------------zippers
+@article{10.1145/3408990,
+author = {Darragh, Pierce and Adams, Michael D.},
+title = {Parsing with Zippers (Functional Pearl)},
+year = {2020},
+issue_date = {August 2020},
+publisher = {Association for Computing Machinery},
+address = {New York, NY, USA},
+volume = {4},
+number = {ICFP},
+url = {https://doi.org/10.1145/3408990},
+doi = {10.1145/3408990},
+abstract = {Parsing with Derivatives (PwD) is an elegant approach to parsing context-free grammars (CFGs). It takes the equational theory behind Brzozowski's derivative for regular expressions and augments that theory with laziness, memoization, and fixed points. The result is a simple parser for arbitrary CFGs. Although recent work improved the performance of PwD, it remains inefficient due to the algorithm repeatedly traversing some parts of the grammar. In this functional pearl, we show how to avoid this inefficiency by suspending the state of the traversal in a zipper. When subsequent derivatives are taken, we can resume the traversal from where we left off without retraversing already traversed parts of the grammar. However, the original zipper is designed for use with trees, and we want to parse CFGs. CFGs can include shared regions, cycles, and choices between alternates, which makes them incompatible with the traditional tree model for zippers. This paper develops a generalization of zippers to properly handle these additional features. Just as PwD generalized Brzozowski's derivatives from regular expressions to CFGs, we generalize Huet's zippers from trees to CFGs. Abstract The resulting parsing algorithm is concise and efficient: it takes only 31 lines of OCaml code to implement the derivative function but performs 6,500 times faster than the original PwD and 3.24 times faster than the optimized implementation of PwD.},
+journal = {Proc. ACM Program. Lang.},
+month = {aug},
+articleno = {108},
+numpages = {28},
+keywords = {Derivatives, Zippers, Parsing with Derivatives, Parsing}
+}
+
+
+
+@article{Edelmann:287059,
+ title = {Efficient Parsing with Derivatives and Zippers},
+ author = {Edelmann, Romain},
+ institution = {IINFCOM},
+ publisher = {EPFL},
+ address = {Lausanne},
+ pages = {246},
+ year = {2021},
+ abstract = {Parsing is the process that enables a computer system to make sense of raw data. Parsing is common to almost all computer systems: It is involved every time sequential data is read and elaborated into structured data. The theory of parsing usually focuses on the binary recognition aspect of parsing and eschews this essential data-elaboration aspect. In this thesis, I present a declarative framework for value-aware parsing that explicitly integrates data elaboration.
+Within the framework of the thesis, I present parsing algorithms that are based on the concept of Brzozowski's derivatives. Derivative-based parsing algorithms present several advantages: they are elegant, amenable to formal reasoning, and easy to implement. Unfortunately, the performance of these algorithms in practice is often not competitive with other approaches. In this thesis, I show a general technique inspired by Huet's Zipper to greatly enhance the performance of derivative-based algorithms, and I do so without compromising their elegance, amenability to formal reasoning, or ease of implementation.
+First, I present a technique for building efficient tokenisers that is based on Brzozowski's derivatives and Huet's zipper and that does not require the usual burdensome explicit conversion to automata. I prove the technique is correct in Coq and present SILEX, a Scala lexing library based on the technique. I demonstrate that the approach is competitive with state-of-the-art solutions.
+Then, I present a characterisation of LL(1) languages based on the concept of should-not-follow sets. I present an algorithm for parsing LL(1) languages with derivatives and zippers. I show a formal proof of the algorithm's correctness and prove its worst-case linear-time complexity. I show how the LL(1) parsing with derivatives and zippers algorithm corresponds to the traditional LL(1) parsing algorithm.
+I then present SCALL1ON, a Scala parsing combinators library for LL(1) languages that incorporates the LL(1) parsing with derivatives and zippers algorithm. I present an expressive and familiar combinator-based interface for describing LL(1) languages. I present techniques that help precisely locate LL(1) conflicts in user code. I discuss several advantages of the parsing with derivatives approach within the context of a parsing library. I also present SCALL1ON's enumeration and pretty-printing features and discuss their implementation. Through a series of benchmarks, I demonstrate the good performance and practicality of the approach. Finally, I present how to adapt the LL(1) parsing with derivatives and zippers algorithm to support arbitrary context-free languages. I show how the adapted algorithm corresponds to general parsing algorithms, such as Earley's parsing algorithm.},
+ url = {http://infoscience.epfl.ch/record/287059},
+ doi = {10.5075/epfl-thesis-7357},
+}
+
+@inproceedings{Zippy2020,
+author = {Edelmann, Romain and Hamza, Jad and Kun\v{c}ak, Viktor},
+title = {Zippy LL(1) Parsing with Derivatives},
+year = {2020},
+isbn = {9781450376136},
+publisher = {Association for Computing Machinery},
+address = {New York, NY, USA},
+url = {https://doi.org/10.1145/3385412.3385992},
+doi = {10.1145/3385412.3385992},
+abstract = {In this paper, we present an efficient, functional, and formally verified parsing algorithm for LL(1) context-free expressions based on the concept of derivatives of formal languages. Parsing with derivatives is an elegant parsing technique, which, in the general case, suffers from cubic worst-case time complexity and slow performance in practice. We specialise the parsing with derivatives algorithm to LL(1) context-free expressions, where alternatives can be chosen given a single token of lookahead. We formalise the notion of LL(1) expressions and show how to efficiently check the LL(1) property. Next, we present a novel linear-time parsing with derivatives algorithm for LL(1) expressions operating on a zipper-inspired data structure. We prove the algorithm correct in Coq and present an implementation as a part of Scallion, a parser combinators framework in Scala with enumeration and pretty printing capabilities.},
+booktitle = {Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation},
+pages = {1036–1051},
+numpages = {16},
+keywords = {Parsing, Zipper, Formal proof, LL(1), Derivatives},
+location = {London, UK},
+series = {PLDI 2020}
+}
+
+
+
+%%----------------------------------------zippers
+%%----------------------------------------------------------------
+
+
@article{fowler2003,
title={An interpretation of the POSIX regex standard},
author={Fowler, Glenn},