This page is intended to provide acknowledgement.
The implementation of Aurelia has been using different algorithsm from the state of art of research. Those algorithms are originally presented in the following papers.
The parser generator is based on:
- Elizabeth Scott, Adrian Johnstone, GLL Parsing, Electronic Notes in Theoretical Computer Science, Volume 253, Issue 7, Proceedings of the Ninth Workshop on Language Descriptions Tools and Applications (LDTA 2009), 17 September 2010, Pages 177-189, ISSN 1571-0661, DOI: 10.1016/j.entcs.2010.08.041.
There are few optimization that were made. However some are breaking the worst case complexity, but appear to be useful for Aurelia.
Lock-free data structures
The generic lock-free hash map implementation, which is used in the maximally shared terms and in GLL parsing, is based from the algorithms from those two papers:
- Ori Shalev and Nir Shavit, Split-ordered lists: Lock-free extensible hash tables, J. ACM 53, 3 (May. 2006), 379-405, DOI: 10.1145/1147954.1147958.
- Timothy L. Harris, A Pragmatic Implementation of Non-blocking Linked-Lists, In Proceedings of the 15th international Conference on Distributed Computing (October 03 - 05, 2001). J. L. Welch, Ed. Lecture Notes In Computer Science, vol. 2180. Springer-Verlag, London, 300-314.